Conference paper
Authors list: Kutrib, Martin; Messerschmidt, Hartmut; Otto, Friedrich
Publication year: 2010
Pages: 781-798
Journal: International Journal of Foundations of Computer Science
Volume number: 21
Issue number: 5
ISSN: 0129-0541
eISSN: 1793-6373
DOI Link: https://doi.org/10.1142/S0129054110007556
Conference: 12th International Conference on Automata and Formal Languages (AFL 2008)
Publisher: 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.
Citation Styles
Harvard Citation style: 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 Citation style: 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
Keywords
CHURCH-ROSSER LANGUAGES; CONTEXT-SENSITIVE LANGUAGES; restarting automaton; stateless device; Two-pushdown automaton
