Aufsatz in einer Fachzeitschrift
On alternating phrase-structure grammars
Details zur Publikation
Autor(inn)en: | Moriya, E.; Otto, F. |
Publikationsjahr: | 2010 |
Zeitschrift: | International Journal of Foundations of Computer Science |
Seitenbereich: | 1-25 |
Jahrgang/Band : | 21 |
ISSN: | 0129-0541 |
Zusammenfassung, Abstract
The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.
The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.
