6
$\begingroup$

Problem:

Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that recognizes all of these strings.

If $k$ is a constant, and $n = poly(\ell)$, what can one say about this problem's complexity as $\ell$ grows?

This seems similar to the smallest grammar problem, which is NP-Hard for the optimization problem. However it is a little different because of having multiple strings, since now one needs to recognize each string independently instead of recognizing all of them at once. The smallest grammar problem is clearly a subset of this, but for small $\ell$ this might be much easier to solve, I'm not sure.

Is there a way to approximately solve this problem efficiently?

$\endgroup$
4
  • $\begingroup$ Almost certainly not what you're looking for, but have you seen the Sequitur algorithm? It's a heuristic for a related problem. $\endgroup$
    – D.W.
    Commented Mar 29, 2016 at 8:58
  • $\begingroup$ Oo that is really close/useful for my purposes. You're right it doesn't solve this problem but thanks for the reference. $\endgroup$
    – Phylliida
    Commented Mar 29, 2016 at 15:22
  • 1
    $\begingroup$ How do you measure the size of a CFG? There are lots of different measures, including total number of occurrences of variables and terminals on both sides of all productions in the grammar; number of variable occurrences on both sides of all productions; number of productions; number of distinct variables. (I doubt it will make a great difference to the asymptotic complexity) $\endgroup$ Commented Nov 21, 2023 at 8:49
  • 1
    $\begingroup$ What do you mean by grammar the "recognizes all of these strings"? If you mean that $\{x_1,x_2,...,x_n\}$ is a subset of the language of the grammar, then the answer is surely $O(1)$, since, ignoring a few edge cases, the grammar $\Sigma^*$ will be minimal for the job. So you mean that the language of the grammar is exactly $\{x_1,x_2,...,x_n\}$? $\endgroup$ Commented Nov 21, 2023 at 8:54

3 Answers 3

5
$\begingroup$

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018):

Given a context-free grammar of size $s$ generating a finite language $L$, it is impossible to approximate the minimum grammar size of $L$ within a factor of $o(s^\frac{1}{7})$, unless P = NP.

Hermann Gruber, Markus Holzer, and Simon Wolfsteiner. On Minimal Grammar Problems for Finite Languages. In Mizuho Hoshi and Shinnosuke Seki, editors, 22nd International Conference on Developments in Language Theory (DLT 2018), Tokyo, Japan, volume 11088 of Lecture Notes in Computer Science, pages 342--353. Springer, September 2018.

Notice that the number of words in the reduction is exponential in their length. To my knowledge, there are no research papers that address the exact case of polynomially many words. But the theorem shows the important point, in that it disproves the intuition that there may be a "quantity discount" effect if we want one minimal grammar for many words.

(A late answer; I hope it will still prove useful for somebody.)

$\endgroup$
4
$\begingroup$

If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions. Consequently, the complexity will be $O(1)$, if you consider $\ell$ and $k$ as fixed and look at the asymptotics as $n$ increases.

Why are there only finitely many possible problem instances? Because when $\Sigma$ and $\ell$ are fixed and $\Sigma$ is finite, there are only finitely many subsets of $\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots \cup \Sigma^{\ell}$.

$\endgroup$
1
  • 1
    $\begingroup$ While you are technically correct, isn't this lookup table massive for any reasonable $\ell$ and $k$? Specifically, you have $\sum_{i=1}^\ell k^i=(k (k^\ell-1))/(k-1)$ possible strings, and thus $2^{\sum_{i=1}^\ell k^i}$ possible problem instances. It's my fault for not specifying that I would like a reasonable dependence on $\ell$ and $k$, but I figured a solution should be fairly reasonable for small $\ell$ and $k$ (say less than 15), yet your lookup table for $\ell=3$ and $k=3$ has 549,755,813,888 possible elements. $\endgroup$
    – Phylliida
    Commented Mar 28, 2016 at 19:59
2
$\begingroup$

Worst case you have a Kolmogorov complexity issue where you have chosen half of the $k^l$ words at random. Since it is random your CFG has to take $O(k^l)$ space since it cannot compress.

$\endgroup$
1
  • 1
    $\begingroup$ Your answer is talking about the size of the smallest CFG. The question seems to be asking about the running time of an algorithm to find the smallest CFG. Therefore, while it's a valid comment, it doesn't seem to answer the question that was asked. $\endgroup$
    – D.W.
    Commented Mar 29, 2016 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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