On alternating phrase-structure grammars

Etsuro Moriya*, Friedrich Otto

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish
    Pages (from-to)1-25
    Number of pages25
    JournalInternational Journal of Foundations of Computer Science
    Issue number1
    Publication statusPublished - 2010 Feb

    ASJC Scopus subject areas

    • Computer Science (miscellaneous)


    Dive into the research topics of 'On alternating phrase-structure grammars'. Together they form a unique fingerprint.

    Cite this