Journalartikel

Jahr der Veröffentlichung: 2010

Seiten: 391-412

Zeitschrift: Acta Informatica

Bandnummer: 47

Heftnummer: 7-8

ISSN: 0001-5903

eISSN: 1432-0525

DOI Link: https://doi.org/10.1007/s00236-010-0125-4

Verlag: Springer

Abstract: 
The transitions of a stateless automaton do not depend on internal states but solely on the symbols currently scanned by its head accessing the input and memory. We investigate stateless deterministic restarting automata that, after executing a rewrite step, continue to read their tape before performing a restart. Even the weakest class thus obtained contains the regular languages properly. The relations between different classes of stateless automata as well as between stateless automata and the corresponding types of automata with states are investigated, and it is shown that the language classes defined by the various types of deterministic stateless restarting automata without auxiliary symbols are anti-AFLs that are not even closed under reversal.

Harvard-Zitierstil: Kutrib, M., Messerschmidt, H. and Otto, F. (2010) On stateless deterministic restarting automata, Acta Informatica, 47(7-8), pp. 391-412. https://doi.org/10.1007/s00236-010-0125-4

APA-Zitierstil: Kutrib, M., Messerschmidt, H., & Otto, F. (2010). On stateless deterministic restarting automata. Acta Informatica. 47(7-8), 391-412. https://doi.org/10.1007/s00236-010-0125-4