A grammatical characterization of alternating pushdown automata

Etsuro Moriya*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


The notion of an alternating context-free grammar is introduced and it is shown that the class of alternating context-free languages is equal to the class of languages accepted by alternating pushdown automata. Some properties on alternating context-free languages are also studied.

Original languageEnglish
Pages (from-to)75-85
Number of pages11
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 1989 Sept 5
Externally publishedYes

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'A grammatical characterization of alternating pushdown automata'. Together they form a unique fingerprint.

Cite this