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.
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.
