Finite state sequential transducers are considered, by using the mechanism of iterated transduction. Their power in defining classes of languages is studied by investigating the hierarchy on the number of state. This hierarchy collapses: four states are enough in order to characterize the recursively enumerable languages. Three states cover the ETOL languages, while two states can cover the EOL (hence also context-free) languages. The case of deterministic transducers remains open.
Iterated GSM Mappings: A Collapsing Hierarchy
MANCA, Vincenzo;
1999-01-01
Abstract
Finite state sequential transducers are considered, by using the mechanism of iterated transduction. Their power in defining classes of languages is studied by investigating the hierarchy on the number of state. This hierarchy collapses: four states are enough in order to characterize the recursively enumerable languages. Three states cover the ETOL languages, while two states can cover the EOL (hence also context-free) languages. The case of deterministic transducers remains open.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
