On some derivation mechanisms and the complexity of their Szilard languages

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)

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

Cites work

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

Cited in

(9)

The complexity of Szilard languages of matrix grammars revisited
A note on the inclusion problem for szilard languages^†
On the complexity of Szilard languages of regulated grammars
On Szilard languages of InsDel systems
A compositional view of derivations as interactive processes with applications to regulated and distributed rewriting
scientific article; zbMATH DE number 3856428 (Why is no real title available?)
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)