Back to Search Start Over

Descriptional Complexity of Union and Star on Context-Free Languages

Authors :
Dassow, Jürgen
Harbich, Ronny
Publication Year :
2012
Publisher :
Institut für Informatik, Justus-Liebig-Universität Giessen, 2012.

Abstract

We investigate context-free languages with respect to the measures Prod and Symb of descriptional complexity, which give the minimal number of productions and the minimal total number of symbols in productions, respectively, necessary to generate the language by context-free grammars. In particular, we consider the behaviour of these measures with respect to operations. For a measure $K\in \{\Prod,\Symb\}$, given natural numbers $c_1,c_2,\dots ,c_n$ and an $n$-ary operation $\tau$ on languages, we discuss the set $g_{\tau,K}(c_1,c_2,\dots ,c_n)$ which is the range of $K(\tau(L_1,L_2,\dots , L_n))$ where, for $1\leq i\leq n$, $L_i$ is a context-free language with $K(L_i)=c_i$. The operations under discussion are union and Kleene closure.<br />Journal of Automata, Languages and Combinatorics, Volume 17, Numbers 2-4, 2012, 123-143

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi...........e7fb322b3d9608bce25c07134d6abdcf
Full Text :
https://doi.org/10.25596/jalc-2012-123