TAOCP 7.1.4 Exercise 198

Exercise 198. ▶ [23] [23] Explain how to compute AND(f, g) with ZDDs instead of BDDs (see (55)).

Verified: yes
Solve time: 2m17s

Solution

Let $u$ and $v$ be ZDD nodes representing families of sets for Boolean variables ordered as $x_1 < x_2 < \cdots < x_n$. Let $\operatorname{var}(u)$ denote the index of the variable at node $u$, with terminals $0$ and $1$ where $0$ represents the empty family and $1$ represents ${\emptyset}$.

The operation $\mathrm{AND}(f,g)$ for ZDDs represents intersection of families of sets: a set $S$ is in $\mathrm{AND}(f,g)$ if and only if $S \in f$ and $S \in g$. The construction must preserve ZDD reduction, in particular elimination of nodes whose HI edge points to $0$.

The definition proceeds by structural recursion on the pair of nodes $(u,v)$.

When either input is empty, no set can lie in the intersection. Thus

$$ \mathrm{AND}(0,v)=0,\quad \mathrm{AND}(u,0)=0. $$

When both inputs are the terminal $1$, both represent the singleton family ${\emptyset}$, so their intersection is the same family:

$$ \mathrm{AND}(1,1)=1. $$

Assume now that at least one argument is a branch node. Let $\operatorname{var}(u)=i$ and $\operatorname{var}(v)=j$.

When $i=j$, both nodes test the same variable $x_i$. Write

$$ u = (i,u_0,u_1), \quad v = (i,v_0,v_1), $$

where $u_0,u_1$ and $v_0,v_1$ are the LO and HI successors. A set belongs to both families exactly when, after fixing the same choice of excluding or including $x_i$, the remaining suffix belongs to both subfamilies. Hence

$$ \mathrm{AND}(u,v) = (i,\ \mathrm{AND}(u_0,v_0),\ \mathrm{AND}(u_1,v_1)). $$

This construction may violate ZDD reduction. In a ZDD, any node whose HI child is $0$ is eliminated, since no set in the family uses that variable. If

$$ \mathrm{AND}(u_1,v_1)=0, $$

then the HI branch contributes no valid sets, so the node reduces to its LO child:

$$ \mathrm{AND}(u,v) = \mathrm{AND}(u_0,v_0). $$

When $i<j$, the variable $x_i$ does not appear at the root of $v$. The node $v$ implicitly branches with identical children for $x_i$, so both choices of $x_i$ leave $v$ unchanged. Thus

$$ \mathrm{AND}(u,v) = (i,\ \mathrm{AND}(u_0,v),\ \mathrm{AND}(u_1,v)). $$

If the resulting HI child is $0$, the ZDD reduction rule again eliminates the node and returns the LO child.

When $j<i$, symmetry gives

$$ \mathrm{AND}(u,v) = (j,\ \mathrm{AND}(u,v_0),\ \mathrm{AND}(u,v_1)), $$

with the same suppression when the HI child is $0$.

These cases define a total recursive procedure on pairs of nodes. Termination follows from the fact that in every recursive call, either the variable index strictly increases along at least one argument or both arguments move to strictly lower nodes in the ZDD ordering, so the pair $(\operatorname{var}(u),\operatorname{var}(v))$ decreases lexicographically.

The correctness follows directly from the semantics of ZDDs: each node partitions the represented family into those sets excluding $x_i$ (LO branch) and those including $x_i$ (HI branch). Intersection preserves membership exactly when both branches independently satisfy the intersection condition, and ZDD reduction preserves equivalence by removing nodes that contribute no HI-branch solutions.

This completes the construction of $\mathrm{AND}(f,g)$ for ZDDs. ∎