]> ZDDs - Melding ZDDs

## Melding ZDDs

Let $F,G$ be ZDDs in the same universe $U=\left\{1,...,n\right\}$. 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 the $\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 \left[1..n\right]$. 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\left(F,G\right)\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. 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. Observe we avoid creating nodes whose HI edges point to $\perp$, and we avoid duplicating any nodes.

As $F\cap G,F\setminus G,F\oplus G$ all lie within $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, 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, ….