On some derivation mechanisms and the complexity of their Szilard languages

DOI10.1016/J.TCS.2014.02.048zbMATH Open1359.68151OpenAlexW2046912551MaRDI QIDQ2453536FDOQ2453536

Authors: Liliana Cojocaru, Erkki Mäkinen

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

Recommendations

On the complexity of Szilard languages of regulated grammars
On context-free and Szilard languages
On Szilard languages of InsDel systems
scientific article; zbMATH DE number 3856428
Publication:3028359
The complexity of Szilard languages of matrix grammars revisited
scientific article; zbMATH DE number 4028929
Derivational complexity of context-free grammars
On derivation languages of a class of splicing systems
On the complexity of realization of finite languages by formulas

complexity classes ALOGTIME Chomsky grammars Szilard languages grammar systems (alternating) Turing machines \(\mathcal{NC}^1\)\(\mathcal{NC}^2\)regulated grammars

Mathematics Subject Classification ID

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

Cites Work

Title not available (Why is that?)
On uniform circuit complexity
Alternation
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
On Relating Time and Space to Size and Depth
A shrinking lemma for random forbidding context languages
Title not available (Why is that?)
A pumping lemma for random permitting context languages
Counter machines and counter languages
Matrix grammars with a leftmost restriction
Title not available (Why is that?)
Regulated grammars under leftmost derivation
Programmed Grammars and Classes of Formal Languages
A note on leftmost restricted random context grammars
On context-free and Szilard languages
On derivation languages corresponding to context-free grammars
A note on depth-first derivations
On Szilard's languages associated to a matrix grammar
The Tape Comilexity of Some Classes of Szilard Languages
Title not available (Why is that?)
Some decision problems for parallel communicating grammar systems
On the leftmost derviation in matrix grammars
The complexity of Szilard languages of matrix grammars revisited
On the complexity of Szilard languages of regulated grammars
On cooperating distributed grammar systems with competence based start and stop conditions
Some New Modes of Competence-Based Derivations in CD Grammar Systems
Bag Context Tree Grammars
On homomorphic images of szilard languages
Title not available (Why is that?)
Szilard languages of IO-grammars
Title not available (Why is that?)
Title not available (Why is that?)
Developments in Language Theory

Cited In (9)

The complexity of Szilard languages of matrix grammars revisited
A note on the inclusion problem for szilard languages^†
On Szilard languages of InsDel systems
On the complexity of Szilard languages of regulated grammars
A compositional view of derivations as interactive processes with applications to regulated and distributed rewriting
Title not available (Why is that?)
On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
Searching for traces of communication in szilard languages of parallel communicating grammar systems -- complexity views
Derivation languages and descriptional complexity measures of restricted flat splicing systems

This page was built for publication: On some derivation mechanisms and the complexity of their Szilard languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453536)