Publication Details

Regulated Nondeterminism in PDAs: The Non-Regular Case

MASOPUST Tomáš. Regulated Nondeterminism in PDAs: The Non-Regular Case. In: Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA). books@ocg.at Band 256. Wroclaw: Austrian Computer Society, 2009, pp. 181-194. ISBN 978-3-85403-256-4.
Czech title
Řízený nedeterminismus v zásobníkových automatech: Neregulární případ
Type
conference paper
Language
english
Authors
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Keywords

Pushdown automata, regulation, computational power, descriptional complexity.

Abstract

In this paper, we discuss pushdown automata which can make a nondeterministic decision only if the pushdown content forms a string that belongs to a given control language. It proves that if the control language is linear and non-regular, then the computational power of pushdown automata regulated in this way is increased to the power of Turing machines. Naturally, checking the pushdown content in each computational step is not practically efficient. Therefore, we also prove that two checks of the form of the pushdown content during any computation are sufficient for these automata to be computationally complete. Finally, some descriptional complexity results are discussed.

Published
2009
Pages
181-194
Proceedings
Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)
Series
books@ocg.at Band 256
Conference
Workshop on Non-Classical Models of Automata and Applications (NCMA), Wroclaw, Poland, PL
ISBN
978-3-85403-256-4
Publisher
Austrian Computer Society
Place
Wroclaw, PL
BibTeX 
@INPROCEEDINGS{FITPUB8977,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Regulated Nondeterminism in PDAs: The Non-Regular Case",
   pages = "181--194",
   booktitle = "Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)",
   series = "books@ocg.at Band 256",
   year = 2009,
   location = "Wroclaw, PL",
   publisher = "Austrian Computer Society",
   ISBN = "978-3-85403-256-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8977"
}
Back to top