Result Details

One-Turn Regulated Pushdown Automata and Their Reduction

MEDUNA, A.; KOLÁŘ, D. One-Turn Regulated Pushdown Automata and Their Reduction. FUNDAMENTA INFORMATICAE, 2001, vol. 2001, no. 21, p. 1001-1007. ISSN: 0169-2968.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc.
Kolář Dušan, doc. Dr. Ing.
Abstract

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

Keywords

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

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
BibTeX 
@article{BUT41079,
  author="Alexandr {Meduna} and Dušan {Kolář}",
  title="One-Turn Regulated Pushdown Automata and Their Reduction",
  journal="FUNDAMENTA INFORMATICAE",
  year="2001",
  volume="2001",
  number="21",
  pages="1001--1007",
  issn="0169-2968"
}
Departments
Faculty of Information Technology (FIT)
Back to top