Language classes generated by tree controlled grammars with bounded nonterminal complexity

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

zbMATH Keywords

nonterminal complexity; bounds for linear context-free and regular simple matrix languages; tree controlled grammars

Mathematics Subject Classification ID

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