Nonterminal complexity of tree controlled grammars

S. Turaev; J. Dassow; M. Selamat

doi:10.1016/j.tcs.2011.06.033

Nonterminal complexity of tree controlled grammars

S. Turaev
, J. Dassow
, M. Selamat

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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.

Original language	English
Pages (from-to)	5789-5795
Number of pages	7
Journal	Theoretical Computer Science
Volume	412
Issue number	41
DOIs	https://doi.org/10.1016/j.tcs.2011.06.033
Publication status	Published - Sept 23 2011
Externally published	Yes

Keywords

Descriptional complexity
Formal languages
Regulated rewriting
Tree controlled grammars

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2011.06.033

Cite this

@article{96313d6cb3114d0690a9622aabb307ee,

title = "Nonterminal complexity of tree controlled grammars",

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 = "Descriptional complexity, Formal languages, Regulated rewriting, Tree controlled grammars",

author = "S. Turaev and J. Dassow and M. Selamat",

note = "Funding Information: We would like to thank the anonymous referees of an earlier version of our paper for their hints, especially for the suggestion to use the Geffert normal form for recursively enumerable languages (which we have taken in this paper) which led to a reduction of the number of nonterminals from fifteen to nine. This work was supported by University Putra Malaysia via RUGS 05-01-10-0896RU.",

year = "2011",

month = sep,

day = "23",

doi = "10.1016/j.tcs.2011.06.033",

language = "English",

volume = "412",

pages = "5789--5795",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "41",

}

TY - JOUR

T1 - Nonterminal complexity of tree controlled grammars

AU - Turaev, S.

AU - Dassow, J.

AU - Selamat, M.

N1 - Funding Information: We would like to thank the anonymous referees of an earlier version of our paper for their hints, especially for the suggestion to use the Geffert normal form for recursively enumerable languages (which we have taken in this paper) which led to a reduction of the number of nonterminals from fifteen to nine. This work was supported by University Putra Malaysia via RUGS 05-01-10-0896RU.

PY - 2011/9/23

Y1 - 2011/9/23

N2 - 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.

AB - 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.

KW - Descriptional complexity

KW - Formal languages

KW - Regulated rewriting

KW - Tree controlled grammars

UR - https://www.scopus.com/pages/publications/79961205439

UR - https://www.scopus.com/pages/publications/79961205439#tab=citedBy

U2 - 10.1016/j.tcs.2011.06.033

DO - 10.1016/j.tcs.2011.06.033

M3 - Article

AN - SCOPUS:79961205439

SN - 0304-3975

VL - 412

SP - 5789

EP - 5795

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 41

ER -

Nonterminal complexity of tree controlled grammars

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this