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

bounds for linear context-free and regular simple matrix languagesnonterminal complexitytree controlled grammars

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Review text

Tree controlled grammars were introduced in [\textit{K. Čulik II.} and \textit{H. A. Maurer}, Computing 19, 129--139 (1977; Zbl 0363.68108)] as a pair \((G,R)\), where \(G\) is a context-free grammar and \(R\) is a regular control language containing words composed of the terminal and nonterminal alphabets of \(G\), and it is used to control the work of \(G\) by restricting the set of derivations which \(G\) is allowed to make. Only those words belong to the generated language which can be generated by the context-free grammar \(G\) having a derivation tree where, for all the strings obtained by reading from left to right, the symbols labeling the nodes which belong to the same level of the tree (with the exception of the last level) are elements of the regular set \(R\).NEWLINENEWLINEThe nonterminal complexity of tree controlled grammars was defined in [the first author et al., Theor. Comput. Sci. 412, No. 41, 5789--5795 (2011; Zbl 1234.68187)] as the sum of the number of nonterminals of the context-free grammar and the number of nonterminals which are necessary to generate the regular control language; it was shown that nine nonterminals are sufficient to generate any recursively enumerable language.NEWLINENEWLINEIn the present paper this bound is decreased from nine to seven, and other language classes are also considered from the point of view of nonterminal complexity with respect to tree controlled grammars. Regular, linear, and regular simple matrix languages are shown to be generated with three nonterminals which is an optimal bound since a regular language is presented which cannot be generated with two nonterminals. For context-free languages, on the other hand, four nonterminals are sufficient, although it is not known whether this bound can be decreased to three or not.

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

• 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
• 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?)
• 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)

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

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)