Journal articleMEDUNA Alexander. Simultaneously OneTurn TwoPushdown Automata. International Journal of Computer Mathematics. 2003, vol. 2003, no. 80, pp. 679687. ISSN 00207160.  Publication language:  english 

Original title:  Simultaneously OneTurn TwoPushdown Automata 

Title (cs):  Souběžně jednoobrátkové dvouzásobníkové automaty. 

Pages:  679687 

Book:  International Journal of Computer Mathematics 

Place:  London, GB 

Year:  2003 

Journal:  International Journal of Computer Mathematics, Vol. 2003, No. 80, GB 

ISSN:  00207160 

Publisher:  Taylor & Francis Informa plc 

Keywords 

recursively enumerable languages, oneturn twopushdown automata 
Annotation 

It is proved that simultaneously oneturn twopushdown automata are equivalent to the Turing machines. 
Abstract 

Consider two consecutive moves m_1 and m_2, made by a twopushdown 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 twopushdown automaton is oneturn if it makes no more than one turn in either of its pushdowns during any computation. A twopushdown automaton is simultaneous oneturn 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 oneturn twopushdown automaton. Conesequently, every recursively enumerable language is accepted by a oneturn twopushdown automaton. 
BibTeX: 

@ARTICLE{
author = {Alexander Meduna},
title = {Simultaneously OneTurn TwoPushdown Automata},
pages = {679687},
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 = {00207160},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=7038}
} 
