Finding smallest context free grammar that generates a set of sets 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:


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