Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity

DOI10.1007/978-3-642-22600-7_23zbMath1341.68112OpenAlexW4256356181MaRDI QIDQ5200099

Mohd Hasan Selamat, Sherzod Turaev, Juergen Dassow

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_23

Mathematics Subject Classification ID

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

Related Items (1)

On the Nonterminal Complexity of 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

This page was built for publication: Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity