TY - GEN
T1 - Language classes generated by tree controlled grammars with bounded nonterminal complexity
AU - Turaev, Sherzod
AU - Dassow, Jürgen
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 - 2011
Y1 - 2011
N2 - A tree controlled grammar can be given 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 its descriptional complexity Var(G,G′) as the sum of the numbers of nonterminals of G and G′. In [24] we have shown that tree controlled grammars (G,G′) with Var(G,G′)∈≥∈9 are sufficient to generate all recursively enumerable languages. In this paper, our main result improves the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a descriptional complexity bounded by three.
AB - A tree controlled grammar can be given 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 its descriptional complexity Var(G,G′) as the sum of the numbers of nonterminals of G and G′. In [24] we have shown that tree controlled grammars (G,G′) with Var(G,G′)∈≥∈9 are sufficient to generate all recursively enumerable languages. In this paper, our main result improves the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a descriptional complexity bounded by three.
UR - http://www.scopus.com/inward/record.url?scp=79961200258&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79961200258&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22600-7_23
DO - 10.1007/978-3-642-22600-7_23
M3 - Conference contribution
AN - SCOPUS:79961200258
SN - 9783642225994
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 289
EP - 300
BT - Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings
T2 - 13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011
Y2 - 25 July 2011 through 27 July 2011
ER -