Konferenzpaper

Jahr der Veröffentlichung: 2009

Seiten: 3447-3460

Zeitschrift: Theoretical Computer Science

Bandnummer: 410

Heftnummer: 37

ISSN: 0304-3975

Open Access Status: Bronze

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

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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