6
$\begingroup$

Are there any results known about the size of smallest context free grammar that generates a set of sets?

That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ and I want to find the smallest context free grammar $G$ whose language $L$ has the property that $A \in S \Leftrightarrow (\exists x \in L~\forall l \in \Sigma~[l \in x \Leftrightarrow l \in A])$.

For instance, if $\Sigma =\{a,b,c,d\}$ and $S=\{\{d,a,c,b\},\{b,c,a\},\{a,b\},\{a\},\{\}\}$, I can have following grammar $G$ of size 14 which corresponds to the given $S$: $$ \begin{array}{l} G \rightarrow ``dacb"\\ G \rightarrow ``bca"\\ G \rightarrow ``ab"\\ G \rightarrow ``a"\\ G \rightarrow \lambda \end{array} $$

However, I can also use the fact that $S$ is a set and have the following smaller grammar $G'$ of size 13 which corresponds to representing $S$ as $``\{\{a,b,c,d\},\{a,b,c\},\{a,b\},\{a\}\}"$ $$ \begin{array}{l} G' \rightarrow aA\\ A \rightarrow bB\\ A \rightarrow \lambda\\ B \rightarrow cd\\ B \rightarrow c\\ B \rightarrow \lambda \end{array} $$

I am interested in the following questions:

  1. Has this problem been studied somewhere? In this regard, do we know the complexity of this problem? If it happens to be computationally complex, are there any approximation algorithms? What about good heuristics?

  2. Has problems similar to this been studied before? For example, instead of using context free grammars, use set theoretic operations such as union and intersection or maybe use some other type of grammar (maybe more restricted than CFGs?).

I am interested in all results that use the underlying assumption of wanting to represent a set (i.e., order is irrelevant). I know that, in the compression literature, there are works on optimal arithmetical encodings of sets. However, I cannot see any direct translation from those results to this domain where we are interested in finding a short grammar.

Improve this question
$\endgroup$
2
  • $\begingroup$ @Aryeh Remember that $A \in S$ "if and only if" the language has a sentence $x$ containing exactly the same set of letters. So, if $L$ generates $\Sigma^*$, it can only represent $\mathbb{P}(\Sigma)$ because that is the only set that contains every possible subset of $\Sigma$. $\endgroup$
    – Shahab
    Commented Sep 1, 2016 at 12:57
  • $\begingroup$ Perhaps this paper helps. $\endgroup$
    – Yuval Filmus
    Commented Sep 1, 2016 at 15:11

2 Answers 2

Reset to default
3
$\begingroup$

Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order.

Conjecture: the optimum is always obtained by some nicely-ordered language, i.e., if $G$ is the smallest such grammar that generates $S$, then there exists a grammar $G'$ of the same size that also generates $S$ and such that $L(G')$ is nicely-ordered.

If this conjecture is true, then your problem reduces to a kind of grammar induction. In particular, we are given a finite language, and the goal is to find the minimal context-free grammar that generates that language.

There are heuristics for this problem. For instance, see the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms, as well as others.

In the general case (given an arbitrary finite language, find the smallest context-free language that generates it), the problem is NP-hard; I don't know if it remains NP-hard when restricted to nicely-ordered finite languages. You could take a look at the standard proof of NP-hardness and see if it can be adjusted to apply to nicely-ordered languages. See also Lower bounds on the size of CFGs for specific finite languages for other results in this space.

So, back to the conjecture. One angle of attack on the problem might to try to prove or disprove this conjecture. For instance, you might try writing a program to search for counterexamples (generate small random sets, look for the optimal grammar, check whether the conjecture holds, and repeat millions of times). If the conjecture is true, it might make your problem much easier to solve. If it's false, it might shed light on what makes the problem challenging.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the references. I think your conjecture is not right. For example, if $\Sigma=\{a_1,\dots,a_n,b_1,\dots,b_k,c_1,\dots,c_n,d_1,\dots,d_k\}$ with the letter ordering being as written above. Also, let $S=\{a_i b_1b_2\dots b_kc_id_1d_2\dots d_k~|~1 \leq i \leq n\}$, i.e., $S$ has $n$ words of size $2k+2$. Since $b_1\dots b_kd_1 \dots d_k$ happens everywhere, introduce new non-terminal $B$ to represent them (despite not being next to each other in the ordering). If $L$ was to be nicely-ordered, we would need two new nonterminals and had to use both in all rules, i.e., extra $O(n)$ size. $\endgroup$
    – Shahab
    Commented Sep 2, 2016 at 22:15
  • $\begingroup$ So, now, the question becomes if some ordering always exists that satisfies the nicely-ordered requirement. My guess would be that it's not the case either but I might be wrong .... $\endgroup$
    – Shahab
    Commented Sep 2, 2016 at 22:17
  • $\begingroup$ @Shahab, very nice! I am persuaded. $\endgroup$
    – D.W.
    Commented Sep 3, 2016 at 0:05
1
$\begingroup$

Because the order of your symbols does not matter, you can always move the nonterminals to the very right of the productions. If there is no more than one in any rule, the resulting grammar is regular. If there are several, I think they can easily be coded into a single one.

Thus you can look for the minimal regular grammar, and this problem is quite well-studied.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you please also give some citation? $\endgroup$
    – Shahab
    Commented Sep 2, 2016 at 21:41
  • 1
    $\begingroup$ "If there are several, I think they can easily be coded into a single one." - Can you give a justification or proof of this statement? It doesn't look right to me. Suppose $AB$ appears at the end of one rule, $BC$ appears at the end of another rule, $AC$ appears at the end of a third rule, and $A$ appears at the end of a fourth rule. Now what? How are we going to code them so each rule ends with only a single terminal, without increasing the size of the grammar? (If you try to replace $AB$, $BC$, $AC$, $A$ with $X$, $Y$, $Z$, $A$, but now the rules for $X,Y,Z$ might be much larger.) $\endgroup$
    – D.W.
    Commented Sep 3, 2016 at 0:06
  • $\begingroup$ Yes, @D.W. the grammar will become larger. Even more than what you suggest, because you have to do a "leftmost" derivation (at least if you want to preserve the original order of terminals, which is not so relevant here) in the compressed symbols, so X might need many steps until it descends down to a single original non-terminal. But if you then minimize this larger grammar, the result will be minimal. Of course, one "set language" corresponds to many string languages, and it is not clear which one will have the smallest minimal grammar. $\endgroup$
    – Peter Leupold
    Commented Sep 3, 2016 at 20:16
  • $\begingroup$ The flaw in your reasoning is that you assume that the minimal grammar for this language will be regular. But that's not correct. There might be a context-free grammar that's smaller than any regular grammar for the language. Consequently, finding some regular grammar for the language and then looking for the minimal regular grammar for that language does not necessarily yield an optimum solution to the original problem; there might be a context-free grammar that's smaller still. $\endgroup$
    – D.W.
    Commented Sep 3, 2016 at 20:27
  • $\begingroup$ Alright - minimality for regular grammars is measured in the number of nonterminals, while the question here asks for number of occurences of any kind of symbol in the rules. For this, by the way, it is completely irrelevant how many new non-terminals are introduced. Anyway, this is not a flaw in my reasoning, I just suggested to look at the problem in this way. Andmy intuition is that normally if not always the minimalities will coincide. $\endgroup$
    – Peter Leupold
    Commented Sep 3, 2016 at 20:37

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.