Language classes generated by tree controlled grammars with bounded nonterminal complexity

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

Full description

Bibliographic Details
Main Authors:	Turaev, Sherzod, Dassow, Juergen, Manea, Florin, Selamat, Mohd Hasan
Format:	Article
Language:	English
Published:	Elsevier 2012
Subjects:	QA Mathematics QA75 Electronic computers. Computer science
Online Access:	http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf

id	iium-27237
recordtype	eprints
spelling	iium-272372013-04-15T04:32:29Z http://irep.iium.edu.my/27237/ Language classes generated by tree controlled grammars with bounded nonterminal complexity Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan QA Mathematics QA75 Electronic computers. Computer science 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. Elsevier 2012-08 Article PeerReviewed application/pdf en http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf 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 http://www.sciencedirect.com/science/article/pii/S030439751200357X 10.1016/j.tcs.2012.04.013
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English
topic	QA Mathematics QA75 Electronic computers. Computer science
spellingShingle	QA Mathematics QA75 Electronic computers. Computer science Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan Language classes generated by tree controlled grammars with bounded nonterminal complexity
description	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.
format	Article
author	Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan
author_facet	Turaev, Sherzod Dassow, Juergen Manea, Florin Selamat, Mohd Hasan
author_sort	Turaev, Sherzod
title	Language classes generated by tree controlled grammars with bounded nonterminal complexity
title_short	Language classes generated by tree controlled grammars with bounded nonterminal complexity
title_full	Language classes generated by tree controlled grammars with bounded nonterminal complexity
title_fullStr	Language classes generated by tree controlled grammars with bounded nonterminal complexity
title_full_unstemmed	Language classes generated by tree controlled grammars with bounded nonterminal complexity
title_sort	language classes generated by tree controlled grammars with bounded nonterminal complexity
publisher	Elsevier
publishDate	2012
url	http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/ http://irep.iium.edu.my/27237/1/Language_classes_generated_by_tree_controlled_grammars_with_bounded_nonterminal_complexity.pdf
first_indexed	2023-09-18T20:40:31Z
last_indexed	2023-09-18T20:40:31Z
_version_	1777409334145187840

Language classes generated by tree controlled grammars with bounded nonterminal complexity

Similar Items