3
$\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?

Improve this question
$\endgroup$
2
  • $\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, 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
    Mar 29, 2016 at 15:22

2 Answers 2

Reset to default
3
$\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}$.

Improve this answer
$\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
    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.

Improve this answer
$\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.
    Mar 29, 2016 at 8:14

Your Answer

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

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