On the Complexity of Szilard Languages of Regulated Grammars
From MaRDI portal
Publication:3105746
DOI10.1007/978-3-642-23283-1_8zbMath1351.68098OpenAlexW2168928734MaRDI QIDQ3105746
Liliana Cojocaru, Erkki Maekinen
Publication date: 6 January 2012
Published in: Theoretical Aspects of Computing – ICTAC 2011 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-23283-1_8
alternating Turing machines\(\mathrm{NC}^1\)Szilard languages\(\mathrm{NC}^2\) complexity classesregulated rewriting grammars
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
One-Sided Random Context Grammars with Leftmost Derivations, On some derivation mechanisms and the complexity of their Szilard languages, A compositional view of derivations as interactive processes with applications to regulated and distributed rewriting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On context-free and Szilard languages
- On uniform circuit complexity
- On Szilard's languages associated to a matrix grammar
- A shrinking lemma for random forbidding context languages
- A note on leftmost restricted random context grammars
- On derivation languages corresponding to context-free grammars
- Alternation
- The Tape Comilexity of Some Classes of Szilard Languages
- Szilard languages of IO-grammars
- Counter machines and counter languages
- Programmed Grammars and Classes of Formal Languages
- Matrix grammars with a leftmost restriction
- A pumping lemma for random permitting context languages