Nonterminal complexity of tree controlled grammars |
| |
| Authors: | S. Turaev J. Dassow M. Selamat |
| |
| Affiliation: | a Faculty of Computer Science and Information Technology, University Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysiab Faculty of Computer Science, Otto-von-Guericke University Magdeburg, D-39016 Magdeburg, Germany |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
