TY - JOUR
T1 - Nonterminal complexity of tree controlled grammars
AU - Turaev, S.
AU - Dassow, J.
AU - Selamat, M.
N1 - Funding Information:
We would like to thank the anonymous referees of an earlier version of our paper for their hints, especially for the suggestion to use the Geffert normal form for recursively enumerable languages (which we have taken in this paper) which led to a reduction of the number of nonterminals from fifteen to nine. This work was supported by University Putra Malaysia via RUGS 05-01-10-0896RU.
PY - 2011/9/23
Y1 - 2011/9/23
N2 - This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.
AB - This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.
KW - Descriptional complexity
KW - Formal languages
KW - Regulated rewriting
KW - Tree controlled grammars
UR - http://www.scopus.com/inward/record.url?scp=79961205439&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79961205439&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.06.033
DO - 10.1016/j.tcs.2011.06.033
M3 - Article
AN - SCOPUS:79961205439
SN - 0304-3975
VL - 412
SP - 5789
EP - 5795
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 41
ER -