# Straight-line program for sets

Let $$\mathcal{S}$$ be a collection of sets. A set straight-line program that enumerates $$\mathcal{S}$$ is a sequence of sets $$B_1,\ldots,B_m$$, such that

• $$\mathcal{S}\subseteq \{B_1,\ldots,B_m\}$$.
• For each $$i$$, either $$|B_i|=1$$ or $$B_i = B_j\cup B_k$$ for some $$j,k.

Have this kind of problem been studied before?

• I haven't seen this exactly before, but people have studied circuits over sets of natural numbers, where the operations are $\cap,\cup,+,\times$ and complement, and each gate computes a set of natural numbers. Seems pretty related. See en.wikipedia.org/wiki/Circuits_over_sets_of_natural_numbers and refs therein. Apr 11 at 14:41
• ZDD can be seen as a restricted form of what you want to do (without unions and with an underlying order the elements should go in); OBDD too but the semantics is a bit farther from what you ask. With union, that would give non deterministic OBDD; I do not know whether non det ZDD have been introduced in the literature but that would not be too hard to define (just add $\vee$-gates corresponding to unions). That would give you interesting properties: you can compute size of the set computed by a ZDD, or approximate it with an FPRAS in the non-deterministic case, uniformly sample elements etc.
– holf
Apr 12 at 14:43