On some derivation mechanisms and the complexity of their Szilard languages

DOI10.1016/j.tcs.2014.02.048zbMath1359.68151OpenAlexW2046912551MaRDI QIDQ2453536

Liliana Cojocaru, Erkki Maekinen

Publication date: 10 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.048

zbMATH Keywords

Chomsky grammarsgrammar systemscomplexity classesALOGTIMESzilard languages(alternating) Turing machines\(\mathcal{NC}^1\)\(\mathcal{NC}^2\)regulated grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Unnamed Item ⋮ A compositional view of derivations as interactive processes with applications to regulated and distributed rewriting ⋮ Derivation languages and descriptional complexity measures of restricted flat splicing systems

Cites Work

• On context-free and Szilard languages
• A note on depth-first derivations
• On uniform circuit complexity
• On Szilard's languages associated to a matrix grammar
• Some decision problems for parallel communicating grammar systems
• A shrinking lemma for random forbidding context languages
• Regulated grammars under leftmost derivation
• A note on leftmost restricted random context grammars
• On derivation languages corresponding to context-free grammars
• On the Complexity of Szilard Languages of Regulated Grammars
• Some New Modes of Competence-Based Derivations in CD Grammar Systems
• Bag Context Tree Grammars
• On homomorphic images of szilard languages
• Alternation
• The Tape Comilexity of Some Classes of Szilard Languages
• On Relating Time and Space to Size and Depth
• Szilard languages of IO-grammars
• ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS
• The Complexity of Szilard Languages of Matrix Grammars Revisited
• Counter machines and counter languages
• Programmed Grammars and Classes of Formal Languages
• Matrix grammars with a leftmost restriction
• Developments in Language Theory
• A pumping lemma for random permitting context languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item