Result: Context-dependent nondeterminism for pushdown automata

Title:
Context-dependent nondeterminism for pushdown automata
Authors:
KUTRIB, Martin, MALCHER, Andreas
Source:
Developments in language theoryTheoretical computer science. 376(1-2):101-111
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie des langages et analyse syntaxique, Language theory and syntactical analysis, Automates. Machines abstraites. Machines de turing, Automata. Abstract machines. Turing machines, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Automate borné, Bounded automaton, Autómata limitado, Automate déterministe, Deterministic automaton, Autómata determinista, Automate à pile, Push down automaton, Autómata a pila, Famille langage, Language family, Familia lenguaje, Fermeture, Closure, Cerradura, Informatique théorique, Computer theory, Informática teórica, Langage CF, Context free language, Lenguaje CF, Langage rationnel, Regular language, Lenguaje racional, Non déterminisme, Non determinism, No determinismo, Capacité calcul, Computational capacity, Langage régulier, Propriété fermeture, Préfixe, Système reconnaissance temps-efficace, Time-efficient recognizer, Closures of languages, Context-free languages, Deterministic pushdown automata, Time-efficient recognizers
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Institut für Informatik, Johann Wolfgang Goethe-Universität, 60054 Frankfurt am Main, Germany
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18748491
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18748491
Database:
PASCAL Archive

Further Information

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.