Publication Details

Regulated Pushdown Automata

KOLÁŘ Dušan and MEDUNA Alexander. Regulated Pushdown Automata. Acta Cybernetica, vol. 2000, no. 4, pp. 653-664. ISSN 0324-721X.
Type
journal article
Language
english
Authors
Keywords

pushdown automata, regulated accepting, control languages

Abstract

The paper suggests a new investigation area of the formal language theory - regulated automata. Specifically, it investigates pushdown automata that regulate the use of their rules by control languages. It proves that this regulation has no effect on the power of pushdown automata if the control languages are regular. However, the pushdown automata regulated by linear control languages characterize the family of recursively enumerable languages.

Published
2000
Pages
653-664
Journal
Acta Cybernetica, vol. 2000, no. 4, ISSN 0324-721X
Book
Acta Cybernetica
Place
Szeged, HU
BibTeX
@ARTICLE{FITPUB6020,
   author = "Du\v{s}an Kol\'{a}\v{r} and Alexander Meduna",
   title = "Regulated Pushdown Automata",
   pages = "653--664",
   booktitle = "Acta Cybernetica",
   journal = "Acta Cybernetica",
   volume = 2000,
   number = 4,
   year = 2000,
   location = "Szeged, HU",
   ISSN = "0324-721X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6020"
}
Back to top