TY - JOUR

T1 - Language classes generated by tree controlled grammars with bounded nonterminal complexity

AU - Turaev, Sherzod

AU - Dassow, Jürgen

AU - Manea, Florin

AU - Selamat, Mohd Hasan

N1 - Funding Information:
The works of the first and fourth authors were supported by University Putra Malaysia via RUGS 05-01-10-0896RU. Florin Manea’s work is supported by the DFG grant 582014. Part of this paper was written when Florin Manea was a Research Fellow of the Alexander von Humboldt Foundation at the Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, whose support is also acknowledged.

PY - 2012/8/31

Y1 - 2012/8/31

N2 - A tree controlled grammar is specified as a pair (G,G') where G is a context-free grammar and G' is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree-except the last level-belong to L(G'). We define the nonterminal complexity V ar(H) of H=(G,G') as the sum of the numbers of nonterminals of G and G'. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with V ar(H) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G,G') where the number of nonterminals of G and G' is at most four.

AB - A tree controlled grammar is specified as a pair (G,G') where G is a context-free grammar and G' is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree-except the last level-belong to L(G'). We define the nonterminal complexity V ar(H) of H=(G,G') as the sum of the numbers of nonterminals of G and G'. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with V ar(H) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G,G') where the number of nonterminals of G and G' is at most four.

KW - Bounds for linear context-free and regular simple matrix languages

KW - Nonterminal complexity

KW - Tree controlled grammars

UR - http://www.scopus.com/inward/record.url?scp=84863577568&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863577568&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.04.013

DO - 10.1016/j.tcs.2012.04.013

M3 - Article

AN - SCOPUS:84863577568

SN - 0304-3975

VL - 449

SP - 134

EP - 144

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -