ZDDs

Let $F,G$ be ZDDs in the same universe $U=\{1,...,n\}$. How do we construct their union, $F\cup G$?

If one family is the empty or unit family then the question is easy, and these special cases also hint at the general solution. In particular, if $G=\epsilon$ (represented by the single node $\top$) and $F\ne \varnothing ,\epsilon$ (so $F$ contains a nonterminal node) then, if it does not already exist, we add a dotted edge so that we can travel from the root of $F$ to to $\top$ by following the LO branch every time: $G$ bubbles down from the root of $F$ along dotted lines and then attaches itself to the ZDD with a dotted line.

Consider the case when both $F$ and $G$ contain more than one node, that is, neither is the empty or unit family. Suppose they both have a root node labelled $v$ for some $v\in [1..n]$. Let $F_0,F_1$ be the ZDDs on the LO and HI edges respectively. Define $G_0,G_1$ similarly:

Recall $F_0,F_1$ partition the families of sets of $F$ on whether they contain $v$ or not, and similarly for $G_0,G_1$, hence our solution must be:

where we recursively find $H_0=F_0\cup G_0$ and $H_1=F_1\cup G_1$.

This argument holds for any binary operation $f$ that distributes over union satisfying $f(F,G)\subseteq F\cup G$, namely the output lies within the union of the inputs. This ensures we can compute $f$ by solving two subproblems, one involving only sets of the families containing a particular element $v$, and the other involving only those not containing $v$.

Thus the only case requiring deeper investigation is when $F$ and $G$ have root nodes with differing integer labels. Suppose $F$ has root node with label $v$ and $G$ has root node with label $w$, and $v<w$. Let $F_0,F_1$ be the LO and HI children of $v$ respectively.

Now $w$ is the smallest integer contained in any set of $G$, hence no set in $G$ contains $v$. Thus $F\cup G$ is:

where $H=F_0\cup G$. Hence $G$ "bubbles down the dotted line" whenever $w>v$. Compare with the special case we discussed earlier, which we can accommodate by defining $\top$ to be larger than every integer.

Thus we have described all cases of a top-down recursive algorithm for constructing the union of any two families. There are two technicalities: we avoid creating nodes whose HI edges point to $\top$, and we avoid duplicating any nodes.

As $F\cap G,F\setminus G,F\oplus G\subseteq F\cup G$, for these operations, the above arguments apply when $F,G$ have root nodes with the same label. Similarly, the "bubble-down" argument still holds when the root $w$ of $G$ is greater than the root $v$ of $F$. The only difference is in the handling of $F_1$. For intersections, since this represents the sets of $F$ containing $v$ and since no set in $G$ contains $v$, we lop off the entire branch leaving only the ZDD $F_0\cap G$. For the difference and symmetric difference, as in the union, we leave $F_1$ intact as it represents sets of $F$ not present in $G$.

One more wrinkle: the case $v>w$ is symmetric except for the asymmetric difference operation. We have $F\setminus G=F\setminus G_0$ in this case.

Let us summarize the nonterminal cases. Let $\diamond$ be one of $\cup ,\cap ,\setminus ,\oplus$. We reuse the above notation, that is, $F,G$ are nontrivial ZDDs with roots labelled $v,w$ respectively, and $F_0,F_1$ are the LO and HI children of $v$ respectively and $G_0,G_1$ are similarly defined.

When $v=w$, then $F\diamond G$ is recursively defined by:

where $H_0=F_0\diamond G_0,H_1=F_1\diamond G_1$.

When $v<w$, let $H=F_0\diamond G$. If $\diamond =\cap$ then $F\cap G=H$, otherwise $F\diamond G$ is:

Lastly, when $v>w$ the cases are symmetric except when $\diamond =\setminus$, whence $F\setminus G=F\setminus G_0$.

TODO: computing the join, meet, ….