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

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

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

• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• 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
• Alternating Pushdown and Stack Automata
• Alternation
• An infinite hierarchy of intersections of context-free languages
• Growing context-sensitive languages and Church-Rosser languages
• Matrix grammars with a leftmost restriction
• Membership for growing context-sensitive grammars is polynomial
• Some remarks on state grammars and matrix grammars

Cited in

(8)

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

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)