×

On stateless two-pushdown automata and restarting automata. (English) Zbl 1207.68193

Summary: We investigate restarting automata and two-pushdown automata 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.

MSC:

68Q45 Formal languages and automata

Software:

UCFL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/978-3-642-59136-5_3 · doi:10.1007/978-3-642-59136-5_3
[2] DOI: 10.1006/inco.1997.2681 · Zbl 0894.68093 · doi:10.1006/inco.1997.2681
[3] Harrison M., Introduction to Formal Language Theory (1978) · Zbl 0411.68058
[4] Hopcroft J. E., Series in Computer Science, in: Introduction to Automata Theory, Languages and Computation (1979)
[5] DOI: 10.1016/j.ic.2007.02.003 · Zbl 1127.68051 · doi:10.1016/j.ic.2007.02.003
[6] DOI: 10.1007/BF01761708 · Zbl 0287.02022 · doi:10.1007/BF01761708
[7] DOI: 10.1016/j.ic.2004.09.003 · Zbl 1075.68046 · doi:10.1016/j.ic.2004.09.003
[8] F. Otto, Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence 25, eds. Z. Ésik, C. Martin-Vide and V. Mitrana (Springer, Berlin, 2006) pp. 269–303.
[9] DOI: 10.1006/jcss.1999.1693 · Zbl 0956.68055 · doi:10.1006/jcss.1999.1693
[10] DOI: 10.1016/S0022-0000(72)80020-5 · Zbl 0242.68038 · doi:10.1016/S0022-0000(72)80020-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.