A characterization of exponential-time languages by alternating context- free grammars

DOI10.1016/0304-3975(92)90355-JzbMath0774.68073OpenAlexW2083245182MaRDI QIDQ1193905

Hui Wang, Oscar H. Ibarra, Tao Jiang

Publication date: 27 September 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90355-j

zbMATH Keywords

alternating pushdown automataexponential-time languageslinear-erasing alternating context-free grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (6)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On Alternating Phrase-Structure Grammars ⋮ On state-alternating context-free grammars ⋮ Model checking propositional dynamic logic with all extras ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition

Cites Work

• Unnamed Item
• On the power of alternation in automata theory
• A grammatical characterization of alternating pushdown automata
• On the generative power of transformational grammars
• The Power of Alternating One-Reversal Counters and Stacks
• Alternating Pushdown and Stack Automata
• Alternation bounded auxiliary pushdown automata
• Alternation

This page was built for publication: A characterization of exponential-time languages by alternating context- free grammars