Publication Details

One-Turn Regulated Pushdown Automata and Their Reduction

MEDUNA Alexander and KOLÁŘ Dušan. One-Turn Regulated Pushdown Automata and Their Reduction. Fundamenta Informaticae, vol. 2001, no. 21, pp. 1001-1007. ISSN 0169-2968.
Czech title
Jednoobrátkové řízené zásobníkové automaty.
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Kolář Dušan, doc. Dr. Ing. (DIFS FIT BUT)
Keywords

automata, reduction, recursively enumerable languages, atomic one-turn regulated pushdown automata

Abstract

Regulated pushdown automata are reduced. Their special cases are studied.

Annotation

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.

Published
2001
Pages
1001-1007
Journal
Fundamenta Informaticae, vol. 2001, no. 21, ISSN 0169-2968
Book
Fundamenta Informaticae
Publisher
IOS Press
Place
Warsaw, PL
BibTeX 
@ARTICLE{FITPUB7035,
   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 = "https://www.fit.vut.cz/research/publication/7035"
}
Back to top