Language classes generated by tree controlled grammars with bounded nonterminal complexity

Turaev, Sherzod and Dassow, Juergen and Manea, Florin and Selamat, Mohd Hasan (2012) Language classes generated by tree controlled grammars with bounded nonterminal complexity. Theoretical Computer Science, 449 (2012). pp. 134-144. ISSN 0304-3975

PDF (Language classes generated by tree controlled grammars with bounded nonterminal complexity) - Published Version Restricted to Repository staff only Download (255kB) | Request a copy

Abstract

A tree controlled grammar is specified as a pair (G, G′) where G is a context-free grammar and G′ is a regular grammar. Its language consists of all terminal words with a derivation in G such that all levels of the corresponding derivation tree – except the last level – belong to L(G′). We define the nonterminal complexity Var(H) of H = (G, G′) as the sum of the numbers of nonterminals of G and G′. In Turaev et al. (2011) [23] it is shown that tree controlled grammars H with Var(H) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, we improve the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammarswith a nonterminal complexity bounded by three, and we prove that this bound is optimal for the mentioned language families. Furthermore, we show that any context-free language can be generated by a tree controlled grammar (G, G′) where the number of nonterminals of G and G′ is at most four.

Item Type:	Article (Journal)
Additional Information:	6846/27237
Uncontrolled Keywords:	Tree controlled grammars Nonterminal complexity Bounds for linear context-free and regular simple matrix languages
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Dr. Sherzod Turaev
Date Deposited:	04 Dec 2012 10:31
Last Modified:	15 Apr 2013 12:32
URI:	http://irep.iium.edu.my/id/eprint/27237

Actions (login required)

View Item