Konferenzpaper

Jahr der Veröffentlichung: 2010

Seiten: 781-798

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 21

Heftnummer: 5

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054110007556

Konferenz: 12th International Conference on Automata and Formal Languages (AFL 2008)

Verlag: World Scientific Publishing

Abstract: 
Restarting automata and two-pushdown automata are investigated that have a single internal state only. As such an automaton must always stay in the same state, this state is of no importance for the behaviour of the automaton. Accordingly, these automata are called stateless. We consider various types of stateless two-pushdown automata and restarting automata. We investigate their expressive power, comparing them in particular to each other and to the corresponding types of automata with states.

Harvard-Zitierstil: Kutrib, M., Messerschmidt, H. and Otto, F. (2010) ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA, International Journal of Foundations of Computer Science, 21(5), pp. 781-798. https://doi.org/10.1142/S0129054110007556

APA-Zitierstil: Kutrib, M., Messerschmidt, H., & Otto, F. (2010). ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA. International Journal of Foundations of Computer Science. 21(5), 781-798. https://doi.org/10.1142/S0129054110007556