Paper Info
Title
Language classes generated by tree controlled grammars with bounded nonterminal complexity
Abstract
A tree controlled grammar can be given 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 its descriptional complexity Var(G, G′) as the sum of the numbers of nonterminals of G and G′. In [24] we have shown that tree controlled grammars (G, G′) with Var(G, G′ ) ≤ 9 are sufficient to generate all recursively enumerable languages. In this paper, our main result improves the bound to seven. Moreover, we show that all linear and regular simple matrix languages can be generated by tree controlled grammars with a descriptional complexity bounded by three.
Year
DOI
Venue
2012
10.1016/j.tcs.2012.04.013
Theoretical Computer Science
Keywords
DocType
Volume
Tree controlled grammars,Nonterminal complexity,Bounds for linear context-free and regular simple matrix languages
Journal
449,
ISSN
Citations 
PageRank 
0304-3975
1
0.40
References 
Authors
18
3
Name
Order
Citations
PageRank
Sherzod Turaev13110.81
Jürgen Dassow2530118.27
Mohd Hasan Selamat37914.82