4
$\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$
  • $\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. Mar 29 '16 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 Mar 29 '16 at 15:22
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
    $\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 Mar 28 '16 at 19:59
3
$\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
    $\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. Mar 29 '16 at 8:14

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.