TY  - JOUR
A1  - Bordihn, Henning
A1  - Fernau, Henning
A1  - Holzer, Markus
A1  - Manca, Vincenzo
A1  - Martin-Vide, Carlos
T1  - Iterated sequential transducers as language generating devices
JF  - Theoretical computer science
N2  - 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.
KW  - finite state sequential transducers
KW  - state complexity
KW  - Lindenmayer systems
Y1  - 2006
U6  - https://doi.org/10.1016/j.tcs.2006.07.059
SN  - 0304-3975
VL  - 369
IS  - 1
SP  - 67
EP  - 81
PB  - Elsevier
CY  - Amsterdam
ER  -