On the Complexity of Szilard Languages of Regulated Grammars

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

zbMATH Keywords

alternating Turing machines\(\mathrm{NC}^1\)Szilard languages\(\mathrm{NC}^2\) complexity classesregulated rewriting grammars

Mathematics Subject Classification ID

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