Language classes generated by tree controlled grammars with bounded nonterminal complexity

DOI10.1016/J.TCS.2012.04.013MaRDI QIDQ443749zbMATH OpenOpenAlexFDO

Authors Sherzod Turaev, Florin Manea, Mohd Hasan Selamat, Jürgen 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)

Recommendations

• On the nonterminal complexity of tree controlled grammars
• Nonterminal complexity of tree controlled grammars
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Generative capacity of subregularly tree controlled grammars
• Two collapsing hierarchies of subregularly tree controlled languages
• scientific article; zbMATH DE number 1836410
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Tree-controlled grammars with restrictions placed upon cuts and paths
• Parsing based on \(n\)-path tree-controlled grammars
• Upper bounds on recognition of a hierarchy of non-context-free languages

Cites work

• scientific article; zbMATH DE number 3870627 (Why is no real title available?)
• scientific article; zbMATH DE number 3974325 (Why is no real title available?)
• scientific article; zbMATH DE number 4064526 (Why is no real title available?)
• scientific article; zbMATH DE number 709441 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 4001501 (Why is no real title available?)
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• scientific article; zbMATH DE number 3254902 (Why is no real title available?)
• A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
• Descriptional complexity of multi-parallel grammars
• Generative capacity of subregularly tree controlled grammars
• Generative power of three-nonterminal scattered context grammars
• Nonterminal complexity of programmed grammars.
• Nonterminal complexity of tree controlled grammars
• On the complexity of regulated context-free rewriting
• On the degree of scattered context-sensitivity.
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• On the generative capacity of tree controlled grammars
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• Simple matrix languages
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• Tree controlled grammars

Cited in

(9)

• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Conclusive tree-controlled grammars
• Nonterminal complexity of tree controlled grammars
• Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
• Generative capacity of subregularly tree controlled grammars
• On the nonterminal complexity of tree controlled grammars
• On the degree of nondeterminism of tree adjoining languages and head grammar languages
• Two collapsing hierarchies of subregularly tree controlled languages
• Tree-controlled grammars with restrictions placed upon cuts and paths

This page was built for publication: Language classes generated by tree controlled grammars with bounded nonterminal complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443749)