Language classes generated by tree controlled grammars with bounded nonterminal complexity

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

zbMATH Keywords

nonterminal complexitybounds for linear context-free and regular simple matrix languagestree controlled grammars

Mathematics Subject Classification ID

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