## Journal article

Publication language: MEDUNA Alexander. Simultaneously One-Turn Two-Pushdown Automata. International Journal of Computer Mathematics. 2003, vol. 2003, no. 80, pp. 679-687. ISSN 0020-7160. english Simultaneously One-Turn Two-Pushdown Automata Soubì¾nì jednoobrátkové dvouzásobníkové automaty. 679-687 International Journal of Computer Mathematics London, GB 2003 International Journal of Computer Mathematics, Vol. 2003, No. 80, GB 0020-7160 Taylor & Francis Informa plc recursively enumerable languages, one-turn two-pushdown automata It is proved that simultaneously one-turn two-pushdown automata are equivalent to the Turing machines. Consider two consecutive moves m_1 and m_2, made by a two-pushdown automaton, M, whose pushdowns are denoted by \pi_1 and \pi_2. If during m_1 M does no shorten \pi_1, for some i=1, 2, while during m_2 it shortens \pi_1, then M makes a turn in \pi_1 during m_2. If M makes turn in both \pi_1 and \pi_2 during m_2, this turn is simultaneous. A two-pushdown automaton is one-turn if it makes no more than one turn in either of its pushdowns during any computation. A two-pushdown automaton is simultaneous one-turn if it makes either no turn or one simultaneous turn in its pushdowns during any computation. This paper demonstrates that every recursively enumerable language is accepted by a simultaneously one-turn two-pushdown automaton. Conesequently, every recursively enumerable language is accepted by a one-turn two-pushdown automaton. @ARTICLE{ author = {Alexander Meduna}, title = {Simultaneously One-Turn Two-Pushdown Automata}, pages = {679--687}, booktitle = {International Journal of Computer Mathematics}, journal = {International Journal of Computer Mathematics}, volume = {2003}, number = {80}, year = {2003}, location = {London, GB}, publisher = {Taylor \& Francis Informa plc}, ISSN = {0020-7160}, language = {english}, url = {http://www.fit.vutbr.cz/research/view_pub.php?id=7038} }