Aufsatz in einer Fachzeitschrift
On state-alternating context-free grammars



Details zur Publikation
Autor(inn)en:
Otto, F.; Hofbauer, D.; Huber, M.; Moriya, E.
Publikationsjahr:
2005
Zeitschrift:
Theoretical Computer Science
Seitenbereich:
183-216
Jahrgang/Band:
337
Erste Seite:
183
Letzte Seite:
216
ISSN:
0304-3975

Zusammenfassung, Abstract
State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75-85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated. (c) 2005 Elsevier B.V. All rights reserved.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-01-11 um 16:06