On state-alternating context-free grammars
DOI10.1016/J.TCS.2004.12.029zbMATH Open1108.68071OpenAlexW2019032507MaRDI QIDQ557822FDOQ557822
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
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
Alternating context-free grammarAlternating pushdown automatonContext-free grammar with statesState-alternating context-free grammar
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)
Cites Work
- Alternation
- Growing context-sensitive languages and Church-Rosser languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- A grammatical characterization of alternating pushdown automata
- A characterization of exponential-time languages by alternating context- free grammars
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Membership for growing context-sensitive grammars is polynomial
- Alternating Pushdown and Stack Automata
- A hierarchy between context-free and context-sensitive languages
- Matrix grammars with a leftmost restriction
- An infinite hierarchy of intersections of context-free languages
- Some remarks on state grammars and matrix grammars
Cited In (8)
- Title not available (Why is that?)
- ON ALTERNATING PHRASE-STRUCTURE GRAMMARS
- A characterization of exponential-time languages by alternating context- free 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)
