14
$\begingroup$

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 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.

$\endgroup$
  • $\begingroup$ (prior comment ref to deleted question deleted). formulated this compression problem 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). $\endgroup$ – vzn Mar 7 '13 at 22:50
  • $\begingroup$ See related question cstheory.stackexchange.com/q/4962 $\endgroup$ – András Salamon Jul 29 '15 at 10:32
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.