Back to Search
Start Over
Descriptional Complexity of Union and Star on Context-Free Languages
- 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