Iterated sequential transducers as language generating devices

Iterated finite state sequential transducers are considered as language generating devices. The hierarchy induced by the size of the state alphabet is proved to collapse to the fourth level. The corresponding language families are related to the families of languages generated by Lindenmayer systems and Chomsky grammars. Finally, some results on deterministic and extended iterated finite state transducers are established.

Metadaten
Verfasserangaben:	Henning Bordihn ORCiD, Henning Fernau ORCiD GND, Markus Holzer GND, Vincenzo Manca ORCiD, Carlos Martin-Vide GND
DOI:	https://doi.org/10.1016/j.tcs.2006.07.059
ISSN:	0304-3975
Titel des übergeordneten Werks (Englisch):	Theoretical computer science
Verlag:	Elsevier
Verlagsort:	Amsterdam
Publikationstyp:	Wissenschaftlicher Artikel
Sprache:	Englisch
Jahr der Erstveröffentlichung:	2006
Erscheinungsjahr:	2006
Datum der Freischaltung:	14.04.2020
Freies Schlagwort / Tag:	Lindenmayer systems; finite state sequential transducers; state complexity
Band:	369
Ausgabe:	1
Seitenanzahl:	15
Erste Seite:	67
Letzte Seite:	81
Organisationseinheiten:	Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
DDC-Klassifikation:	0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke
Peer Review:	Referiert
Name der Einrichtung zum Zeitpunkt der Publikation:	Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik