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

Kolář Dušan, Dr. Ing. (DCSE FEECS BUT)
Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)

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"
}