Regulated Nondeterminism in PDAs: The Non-Regular Case

Tomáš MasopustTomáš Masopust

Download

Tomáš Masopust
Regulated Nondeterminism in PDAs: The Non-Regular Case
Proc. of Workshop on Non-Classical Models of Automata and Applications (NCMA), 181-194, 2009

Details
Bibtex

KurzfassungAbstract
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. We prove 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, from the practical point of view, checking the pushdown content in each computational step is not efficient. Therefore, we prove that two checks of the form of the pushdown content during any computation are sufficient enough for these automata to be computationally complete. Based on this observation, a new model is discussed. Finally, some descriptional complexity results are presented.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{M2009,
  author    = {Tom{\'{a}}{\v{s}} Masopust},
  title     = {Regulated Nondeterminism in {PDAs:} The Non-Regular Case},
  booktitle = {Proc. of Workshop on Non-Classical Models of Automata and
               Applications (NCMA)},
  year      = {2009},
  pages     = {181-194}
}