<p>A kind reviewer sent me a paper which proves exactly the same lower bound I do, in exactly the same way. The paper is</p>

<blockquote>
  <p>K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, <em>Regular expressions: new results and open problems</em>, J. Autom. Lang. Comb. <strong>10</strong> (2005), 407–432.</p>
</blockquote>

<p>The result is Theorem 30 in the paper.</p>

CC BY-SA 3.0
2015-07-26T16:11:50.497Z
A preprint of the paper is at https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf
András Salamon
CC BY-SA 3.0
2011-06-14T18:34:24.207Z
2011-06-14T18:34:24.207Z
Yuval Filmus
<p>Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?</p>

<p>We can make the question more interesting by specifying a sequence of languages $L_n$, for example $L_n$ is the set of all permutations of $\{1,\ldots,n\}$: intuitively, a CFG for $L_n$ would "need" to have size $\Omega(n!)$. So we're interested in the asymptotic size of the smallest CFGs for the languages.</p>

<p>Similar questions have been dealt with in several papers:</p>

<ul>
<li>Charikar et al. ("Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models") consider how difficult it is to approximate the size of the smallest CFG generating a given <i>word</i>.</li>
<li>More work in that direction is Arpe and Reischuk, "On the Complexity of Optimal Grammar-Based Compression".</li>
<li>Peter Asveld has several papers on the subject (e.g. "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form"). He's trying to optimize some parameters on specific types of grammars generating the set of all permutations, specifically Chomsky and Greibach normal forms.</li>
</ul>

<p>However, so far I haven't been able to find any paper trying to prove a bound of $\Omega(n!)$ on the size of a CFG generating $L_n$.</p>

<blockquote>
  <p>Are there papers providing lower bounds for the size of context-free grammars for specific finite languages?</p>
</blockquote>

<p>In response to several questions on this site as well as on math.stackexchange, I came up with a simple <a href="https://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969">method</a> able to prove exponential lower bounds on CFGs for specific languages, for example $L_n$. Are these results new? I find that hard to believe, and I'll be glad to get any literature pointers.</p>

CC BY-SA 3.0
2013-03-07T22:50:48.220Z
(prior comment ref to deleted question deleted). formulated this [compression problem](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) such that it could be very relevant or useful in proving lower bounds wrt cfg compression possibly via diagonalization techniques & (also maybe tiein with kolmogorov complexity).
vzn
CC BY-SA 3.0
2015-07-29T10:32:49.310Z
See related question http://cstheory.stackexchange.com/q/4962
András Salamon
<reference-request><fl.formal-languages><lower-bounds><grammars><context-free>
Lower bounds on the size of CFGs for specific finite languages
Yuval Filmus
# Lower bounds on the size of CFGs for specific finite languages

(Asked by: username_0 on 2011-02-19)

Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?

We can make the question more interesting by specifying a sequence of languages $L\_n$, for example $L\_n$ is the set of all permutations of $\{1,\ldots,n\}$: intuitively, a CFG for $L\_n$ would "need" to have size $\Omega(n!)$. So we're interested in the asymptotic size of the smallest CFGs for the languages.

Similar questions have been dealt with in several papers:

* Charikar et al. ("Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models") consider how difficult it is to approximate the size of the smallest CFG generating a given *word*.
* More work in that direction is Arpe and Reischuk, "On the Complexity of Optimal Grammar-Based Compression".
* Peter Asveld has several papers on the subject (e.g. "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form"). He's trying to optimize some parameters on specific types of grammars generating the set of all permutations, specifically Chomsky and Greibach normal forms.

However, so far I haven't been able to find any paper trying to prove a bound of $\Omega(n!)$ on the size of a CFG generating $L\_n$.

> Are there papers providing lower bounds for the size of context-free grammars for specific finite languages?

In response to several questions on this site as well as on math.stackexchange, I came up with a simple [method](https://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969) able to prove exponential lower bounds on CFGs for specific languages, for example $L\_n$. Are these results new? I find that hard to believe, and I'll be glad to get any literature pointers.

**Tags:** reference-request, fl.formal-languages, lower-bounds, grammars, context-free
> **Comments:**
> **username_1**: (prior comment ref to deleted question deleted). formulated this [compression problem](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) such that it could be very relevant or useful in proving lower bounds wrt cfg compression possibly via diagonalization techniques & (also maybe tiein with kolmogorov complexity).  
> **username_2**: See related question http://cstheory.stackexchange.com/q/4962  

---

## 1 answers

### Answer by username_0 on 2011-06-14. Score: 13 | Accepted answer

A kind reviewer sent me a paper which proves exactly the same lower bound I do, in exactly the same way. The paper is

> K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, *Regular expressions: new results and open problems*, J. Autom. Lang. Comb. **10** (2005), 407–432.

The result is Theorem 30 in the paper.

> **Comments:**
> **username_2**: A preprint of the paper is at https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf  

---

