Nonterminal complexity of tree controlled grammars
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 genera...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2011
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/22489/ http://psasir.upm.edu.my/id/eprint/22489/1/Nonterminal%20complexity%20of%20tree%20controlled%20grammars.pdf |
| _version_ | 1848844498610683904 |
|---|---|
| author | Turaev, Sherzod Dassow, Jurgen Selamat, Mohd Hasan |
| author_facet | Turaev, Sherzod Dassow, Jurgen Selamat, Mohd Hasan |
| author_sort | Turaev, Sherzod |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T08:31:53Z |
| format | Article |
| id | upm-22489 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T08:31:53Z |
| publishDate | 2011 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-224892015-11-27T08:02:18Z http://psasir.upm.edu.my/id/eprint/22489/ Nonterminal complexity of tree controlled grammars Turaev, Sherzod Dassow, Jurgen Selamat, Mohd Hasan 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. Elsevier 2011-09 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/22489/1/Nonterminal%20complexity%20of%20tree%20controlled%20grammars.pdf Turaev, Sherzod and Dassow, Jurgen and Selamat, Mohd Hasan (2011) Nonterminal complexity of tree controlled grammars. Theoretical Computer Science, 412 (41). pp. 5789-5795. ISSN 0304-3975 http://www.sciencedirect.com/science/article/pii/S0304397511005603 10.1016/j.tcs.2011.06.033 |
| spellingShingle | Turaev, Sherzod Dassow, Jurgen Selamat, Mohd Hasan Nonterminal complexity of tree controlled grammars |
| title | Nonterminal complexity of tree controlled grammars |
| title_full | Nonterminal complexity of tree controlled grammars |
| title_fullStr | Nonterminal complexity of tree controlled grammars |
| title_full_unstemmed | Nonterminal complexity of tree controlled grammars |
| title_short | Nonterminal complexity of tree controlled grammars |
| title_sort | nonterminal complexity of tree controlled grammars |
| url | http://psasir.upm.edu.my/id/eprint/22489/ http://psasir.upm.edu.my/id/eprint/22489/ http://psasir.upm.edu.my/id/eprint/22489/ http://psasir.upm.edu.my/id/eprint/22489/1/Nonterminal%20complexity%20of%20tree%20controlled%20grammars.pdf |