Conference paper

Publication year: 2009

Pages: 3447-3460

Journal: Theoretical Computer Science

Volume number: 410

Issue number: 37

ISSN: 0304-3975

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2009.06.002

Conference: 12th International Conference on Implementation and Application of Automata

Publisher: Elsevier

Abstract: 
A generalization of pushdown automata towards regulated nondeterminism is studied. The nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. More precisely, the content of the stack is considered as a word over the stack alphabet, and the pushdown automaton is allowed to act nondeterministically, if this word belongs to some given set R of control words. Otherwise its behavior is deterministic. It turns out that non-context-free languages can be accepted if R is a context-free and non-regular language. On the other hand, if the control sets R are regular languages, then the resulting devices are not more powerful than nondeterministic pushdown automata. This raises the natural question of the relations between the structure and complexity of regular sets R on one hand and the computational capacity of the corresponding R-PDA on the other hand. The main result of the paper shows that an infinite proper hierarchy of regular control sets leads to an infinite proper hierarchy of the corresponding language classes. Additionally, closure properties and decision problems of these language classes are investigated. (C) 2009 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M., Malcher, A. and Werlein, L. (2009) Regulated nondeterminism in pushdown automata, Theoretical Computer Science, 410(37), pp. 3447-3460. https://doi.org/10.1016/j.tcs.2009.06.002

APA Citation style: Kutrib, M., Malcher, A., & Werlein, L. (2009). Regulated nondeterminism in pushdown automata. Theoretical Computer Science. 410(37), 3447-3460. https://doi.org/10.1016/j.tcs.2009.06.002