Language classes generated by tree controlled grammars with bounded nonterminal complexity
From MaRDI portal
Publication:443749
DOI10.1016/j.tcs.2012.04.013zbMath1260.68215OpenAlexW2165539736MaRDI 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 complexitybounds for linear context-free and regular simple matrix languagestree controlled grammars
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Descriptive complexity and finite models (68Q19)
Related Items (2)
Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars ⋮ Unnamed Item
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
This page was built for publication: Language classes generated by tree controlled grammars with bounded nonterminal complexity
