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.
| Author details: | Henning BordihnORCiD, Henning FernauORCiDGND, Markus HolzerGND, Vincenzo MancaORCiD, Carlos Martin-VideGND |
|---|---|
| DOI: | https://doi.org/10.1016/j.tcs.2006.07.059 |
| ISSN: | 0304-3975 |
| Title of parent work (English): | Theoretical computer science |
| Publisher: | Elsevier |
| Place of publishing: | Amsterdam |
| Publication type: | Article |
| Language: | English |
| Year of first publication: | 2006 |
| Publication year: | 2006 |
| Release date: | 2020/04/14 |
| Tag: | Lindenmayer systems; finite state sequential transducers; state complexity |
| Volume: | 369 |
| Issue: | 1 |
| Number of pages: | 15 |
| First page: | 67 |
| Last Page: | 81 |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer review: | Referiert |
| Institution name at the time of the publication: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
