Citation
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
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.
Download File
Official URL or Download Paper: http://www.sciencedirect.com/science/article/pii/S...
|
Additional Metadata
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Computer Science and Information Technology |
| DOI Number: | https://doi.org/10.1016/j.tcs.2011.06.033 |
| Publisher: | Elsevier |
| Keywords: | Formal languages; Regulated rewriting; Tree controlled grammars; Descriptional complexity |
| Depositing User: | Nabilah Mustapa |
| Date Deposited: | 27 Nov 2015 08:02 |
| Last Modified: | 27 Nov 2015 08:02 |
| Altmetrics: | http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.1016/j.tcs.2011.06.033 |
| URI: | http://psasir.upm.edu.my/id/eprint/22489 |
| Statistic Details: | View Download Statistic |
Actions (login required)
 |
View Item |