Language classes generated by tree controlled grammars with bounded nonterminal complexity

Sherzod Turaev, Jürgen Dassow, Florin Manea, Mohd Hasan Selamat

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 V ar(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 V ar(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 grammars with 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.

Original languageEnglish
Pages (from-to)134-144
Number of pages11
JournalTheoretical Computer Science
Volume449
DOIs
Publication statusPublished - Aug 31 2012
Externally publishedYes

Keywords

  • Bounds for linear context-free and regular simple matrix languages
  • Nonterminal complexity
  • Tree controlled grammars

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Language classes generated by tree controlled grammars with bounded nonterminal complexity'. Together they form a unique fingerprint.

Cite this