Nonterminal complexity of tree controlled grammars

DOI10.1016/j.tcs.2011.06.033zbMath1234.68187OpenAlexW2070647957MaRDI QIDQ719323

Sherzod Turaev, Juergen Dassow, Mohd Hasan Selamat

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://psasir.upm.edu.my/id/eprint/22489/1/Nonterminal%20complexity%20of%20tree%20controlled%20grammars.pdf

zbMATH Keywords

formal languagesregulated rewritingdescriptional complexitytree controlled grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

On the Nonterminal Complexity of Tree Controlled Grammars, Language classes generated by tree controlled grammars with bounded nonterminal complexity, Unnamed Item, Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• 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.
• Forbidding ET0L grammars.
• Generative power of three-nonterminal scattered context grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• On the complexity of regulated context-free rewriting