A grammatical characterization of alternating pushdown automata

DOI10.1016/0304-3975(89)90023-6zbMath0677.68083OpenAlexW1983957380MaRDI QIDQ1123637

Etsuro Moriya

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90023-6

zbMATH Keywords

alternating pushdown automataacceptable derivationalternating context-free grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Empty alternation ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On Alternating Phrase-Structure Grammars ⋮ A characterization of exponential-time languages by alternating context- free grammars ⋮ On state-alternating context-free grammars ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of alternation in automata theory
• Alternating tree automata
• Alternating Pushdown and Stack Automata
• Alternation bounded auxiliary pushdown automata
• Alternation
• (Semi)alternating stack automata
• One-way stack automata

This page was built for publication: A grammatical characterization of alternating pushdown automata