Nonterminal complexity of tree controlled grammars

作者：Turaev S^*; Dassow J; Selamat M

来源：Theoretical Computer Science, 2011, 412(41): 5789-5795.

DOI：10.1016/j.tcs.2011.06.033

• Formal languages
• Regulated rewriting
• Tree controlled grammars
• Descriptional complexity

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.

• 出版日期2011-9-23