On state-alternating context-free grammars

DOI10.1016/j.tcs.2004.12.029zbMath1108.68071OpenAlexW2019032507MaRDI QIDQ557822

Maria Huber, Friedrich Otto, Dieter Hofbauer, Etsuro Moriya

Publication date: 30 June 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.029

zbMATH Keywords

Alternating context-free grammarAlternating pushdown automatonContext-free grammar with statesState-alternating context-free grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Related Items (5)

On Alternating Phrase-Structure Grammars ⋮ State grammars with stores ⋮ Deep pushdown automata ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ GENERATION OF LANGUAGES BY REWRITING SYSTEMS THAT RESEMBLE AUTOMATA

Cites Work

• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• A grammatical characterization of alternating pushdown automata
• A characterization of exponential-time languages by alternating context- free grammars
• Growing context-sensitive languages and Church-Rosser languages
• A hierarchy between context-free and context-sensitive languages
• Alternating Pushdown and Stack Automata
• Alternation
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Matrix grammars with a leftmost restriction
• An infinite hierarchy of intersections of context-free languages
• Some remarks on state grammars and matrix grammars

This page was built for publication: On state-alternating context-free grammars