On state-alternating context-free grammars

DOI10.1016/J.TCS.2004.12.029MaRDI QIDQ557822zbMATH OpenOpenAlexFDO

Authors Etsuro Moriya, Dieter Hofbauer, Maria Huber, Friedrich Otto

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

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

Recommendations

• scientific article; zbMATH DE number 4068327
• Conjunctive grammars and alternating pushdown automata
• On Alternating Phrase-Structure Grammars
• ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
• scientific article; zbMATH DE number 1556865
• On multiple context-free grammars
• On a classification of sequential context-free languages and grammars
• scientific article; zbMATH DE number 3858444
• scientific article; zbMATH DE number 3259059

Cites work

• A characterization of exponential-time languages by alternating context- free grammars
• A grammatical characterization of alternating pushdown automata
• A hierarchy between context-free and context-sensitive languages
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Alternating Pushdown and Stack Automata
• Alternation
• An infinite hierarchy of intersections of context-free languages
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Matrix grammars with a leftmost restriction
• Membership for growing context-sensitive grammars is polynomial
• Some remarks on state grammars and matrix grammars

Cited in

(10)

• A characterization of exponential-time languages by alternating context- free grammars
• Deep pushdown automata
• On Alternating Phrase-Structure Grammars
• scientific article; zbMATH DE number 19775 (Why is no real title available?)
• scientific article; zbMATH DE number 1952734 (Why is no real title available?)
• ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
• GENERATION OF LANGUAGES BY REWRITING SYSTEMS THAT RESEMBLE AUTOMATA
• State grammars with stores
• State grammars with stores
• A proof theory of ( -)context-free languages, via non-wellfounded proofs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557822)