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.
9783540658948
Iterated Transducers, Recursively enumerable languages, Language hierarchies
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/928532
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact