Konferenzpaper

Jahr der Veröffentlichung: 2007

Seiten: 101-111

Zeitschrift: Theoretical Computer Science

Bandnummer: 376

Heftnummer: 1-2

ISSN: 0304-3975

Open Access Status: Bronze

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

Konferenz: 10th International Conference on Developments in Language Theory

Verlag: Elsevier

Abstract: 
Pushdown automata using a limited and unlimited amount of nondeterminism, are investigated. Moreover, nondeterministic steps are allowed only within certain contexts, i.e., in configurations that meet particular conditions. The relationships of the accepted language families with closures of the deterministic context-free languages (DCFL) under regular operations are studied. For example, automata with unbounded nondeterminism, that have to empty their pushdown store up to the initial symbol in order to make a guess are characterized by the regular closure of DCFL. Automata that additionally have to reenter the initial state are (almost) characterized by the Kleene star closure of the union closure of the prefix-free deterministic context-free languages. Pushdown automata with bounded nondeterminism are characterized by the union closure of DCFL in any of the considered contexts. Proper inclusions between all language classes discussed are shown. Finally, closure properties of these families under AFL operations are investigated. (C) 2007 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Kutrib, M. and Malcher, A. (2007) Context-dependent nondeterminism for pushdown automata, Theoretical Computer Science, 376(1-2), pp. 101-111. https://doi.org/10.1016/j.tcs.2007.01.015

APA-Zitierstil: Kutrib, M., & Malcher, A. (2007). Context-dependent nondeterminism for pushdown automata. Theoretical Computer Science. 376(1-2), 101-111. https://doi.org/10.1016/j.tcs.2007.01.015