Nonterminal complexity of tree controlled grammars

DOI10.1016/j.tcs.2011.06.033zbMath1234.68187MaRDI 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 languages; regulated rewriting; descriptional complexity; tree controlled grammars

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

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

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