Conference paper

Publication year: 2007

Pages: 101-111

Journal: Theoretical Computer Science

Volume number: 376

Issue number: 1-2

ISSN: 0304-3975

Open access status: Bronze

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

Conference: 10th International Conference on Developments in Language Theory

Publisher: 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 Citation style: 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 Citation style: 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