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.
Pages:1001-1007
Book:Fundamenta Informaticae
Place:Warsaw, PL
Year:2001
Journal:Fundamenta Informaticae, Vol. 2001, No. 21, Amsterdam, NL
ISSN:0169-2968
Publisher:IOS Press
Keywords
automata, reduction, recursively enumerable languages, atomic one-turn regulated pushdown automata
Annotation
Regulated pushdown automata are reduced. Their special cases are studied.
Abstract
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=7035}
}

Your IPv4 address: 54.225.20.73
Switch to IPv6 connection

DNSSEC [dnssec]