Journal article

MEDUNA Alexander. Simultaneously One-Turn Two-Pushdown Automata. International Journal of Computer Mathematics. 2003, vol. 2003, no. 80, pp. 679-687. ISSN 0020-7160.
Publication language:english
Original title:Simultaneously One-Turn Two-Pushdown Automata
Title (cs):Souběžně jednoobrátkové dvouzásobníkové automaty.
Pages:679-687
Book:International Journal of Computer Mathematics
Place:London, GB
Year:2003
Journal:International Journal of Computer Mathematics, Vol. 2003, No. 80, GB
ISSN:0020-7160
Publisher:Taylor & Francis Informa plc
Keywords
recursively enumerable languages, one-turn two-pushdown automata
Annotation
It is proved that simultaneously one-turn two-pushdown automata are equivalent to the Turing machines.
Abstract
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.
BibTeX:
@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}
}

Your IPv4 address: 54.82.79.109
Switch to IPv6 connection

DNSSEC [dnssec]