Conference paperMASOPUST Tomáš. Regulated Nondeterminism in PDAs: The NonRegular Case. In: Proceedings of Workshop on NonClassical Models of Automata and Applications (NCMA). Wroclaw: Austrian Computer Society, 2009, pp. 181194. ISBN 9783854032564.  Publication language:  english 

Original title:  Regulated Nondeterminism in PDAs: The NonRegular Case 

Title (cs):  Řízený nedeterminismus v zásobníkových automatech: Neregulární případ 

Pages:  181194 

Proceedings:  Proceedings of Workshop on NonClassical Models of Automata and Applications (NCMA) 

Conference:  Workshop on NonClassical Models of Automata and Applications (NCMA) 

Series:  books@ocg.at Band 256 

Place:  Wroclaw, PL 

Year:  2009 

ISBN:  9783854032564 

Publisher:  Austrian Computer Society 

Keywords 

Pushdown automata, regulation, computational power, descriptional complexity. 
Annotation 

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 nonregular, 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. 
BibTeX: 

@INPROCEEDINGS{
author = {Tom{\'{a}}{\v{s}} Masopust},
title = {Regulated Nondeterminism in PDAs: The NonRegular
Case},
pages = {181194},
booktitle = {Proceedings of Workshop on NonClassical Models of Automata
and Applications (NCMA)},
series = {books@ocg.at Band 256},
year = {2009},
location = {Wroclaw, PL},
publisher = {Austrian Computer Society},
ISBN = {9783854032564},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=8977}
} 
