Journal article

MEDUNA Alexander and KOLÁŘ Dušan. One-Turn Regulated Pushdown Automata and Their Reduction. Fundamenta Informaticae. Amsterdam: IOS Press, 2001, vol. 2001, no. 21, pp. 1001-1007. ISSN 0169-2968.
Publication language:english
Original title:One-Turn Regulated Pushdown Automata and Their Reduction
Title (cs):Jednoobrátkové řízené zásobníkové automaty.
Book:Fundamenta Informaticae
Place:Warsaw, PL
Journal:Fundamenta Informaticae, Vol. 2001, No. 21, Amsterdam, NL
Publisher:IOS Press
automata, reduction, recursively enumerable languages, atomic one-turn regulated pushdown automata
Regulated pushdown automata are reduced. Their special cases are studied.
This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final state, and acceptance by empty pushdown.
   author = {Alexander Meduna and Du{\v{s}}an Kol{\'{a}}{\v{r}}},
   title = {One-Turn Regulated Pushdown Automata and Their Reduction},
   pages = {1001--1007},
   booktitle = {Fundamenta Informaticae},
   journal = {Fundamenta Informaticae},
   volume = {2001},
   number = {21},
   year = {2001},
   location = {Warsaw, PL},
   publisher = {IOS Press},
   ISSN = {0169-2968},
   language = {english},
   url = {}

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]