Language classes generated by tree controlled grammars with bounded nonterminal complexity
From MaRDI portal
Publication:443749
DOI10.1016/j.tcs.2012.04.013zbMath1260.68215MaRDI QIDQ443749
Mohd Hasan Selamat, Florin Manea, Sherzod Turaev, Juergen Dassow
Publication date: 13 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.013
nonterminal complexity; bounds for linear context-free and regular simple matrix languages; tree controlled grammars
68Q45: Formal languages and automata
68Q42: Grammars and rewriting systems
68Q19: Descriptive complexity and finite models
Related Items
Unnamed Item, Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
Cites Work
- Scattered context grammars generate any recursively enumerable language with two nonterminals
- Nonterminal complexity of tree controlled grammars
- Descriptional complexity of multi-parallel grammars
- A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
- Tree controlled grammars
- On the generative capacity of tree controlled grammars
- On the degree of scattered context-sensitivity.
- Nonterminal complexity of programmed grammars.
- Generative power of three-nonterminal scattered context grammars
- On the descriptional complexity of some rewriting mechanisms regulated by context conditions
- GENERATIVE CAPACITY OF SUBREGULARLY TREE CONTROLLED GRAMMARS
- Six nonterminals are enough for generating each r.e. language by a matrix grammar
- On the complexity of regulated context-free rewriting
- Simple matrix languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item