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 -