UPM Institutional Repository

Nonterminal complexity of tree controlled grammars


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


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

PDF (Abstract)
Nonterminal complexity of tree controlled grammars.pdf

Download (33kB) | Preview

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 View Item