Turaev, Sherzod, Dassow, Jürgen, Manea, Florin and Selamat, Mohd Hasan (2012) Language classes generated by tree controlled grammars with bounded nonterminal complexity. Theoretical Computer Science, 449 . pp. 134-144. DOI 10.1016/j.tcs.2012.04.013.

There is a more recent version of this item available.

Preview

Text dcfs-tcs-tdms-rev-new.pdf Download (212kB) | Preview

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)\leq 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.

Available Versions of this Item

• Language classes generated by tree controlled grammars with bounded nonterminal complexity (deposited 15 Mar 2013 14:42) [Currently Displayed]
  • Language classes generated by tree controlled grammars with bounded nonterminal complexity (deposited 16 Apr 2013 14:31)

Actions (login required)

View Item