TAOCP 7.1.4 Exercise 53
Algorithm R reduces a binary decision diagram by repeatedly merging isomorphic nodes, identifying sinks, and deleting nodes whose two outgoing edges coincide.
Section 7.1.4: Binary Decision Diagrams
Exercise 53. ▶ [23] [23] Play through Algorithm R, when it is applied to the binary decision diagram with seven branch nodes in (2).
Verified: no
Solve time: 5m41s
Solution
Algorithm R reduces a binary decision diagram by repeatedly merging isomorphic nodes, identifying sinks, and deleting nodes whose two outgoing edges coincide. The input described in (2) is the full decision tree for three variables $x_1, x_2, x_3$, which has seven branch nodes before reduction.
At the lowest level, all leaves are sink nodes. Every leaf labeled FALSE is identified with $\bot$ and every leaf labeled TRUE is identified with $\top$. After this identification, all edges from level $x_3$ nodes point only to $\bot$ or $\top$, so each node at level $x_3$ is completely determined by the ordered pair $(\mathrm{LO}, \mathrm{HI}) \in {(\bot,\bot), (\bot,\top), (\top,\bot), (\top,\top)}$.
The full tree for the median function has the property that the subfunctions at level $x_3$ depend only on whether at least one of the previous variables is already fixed to force the majority threshold. This yields exactly two distinct behaviors among the level $x_3$ nodes: one group representing the function $x_3$ and another representing $\lnot x_3$, expressed in the BDD semantics as nodes whose children differ. Algorithm R therefore merges the four level $x_3$ nodes into two equivalence classes, because nodes with identical $(V,\mathrm{LO},\mathrm{HI})$ triples represent identical Boolean functions.
After this first merging step, each level $x_2$ node is determined entirely by its children among the reduced level $x_3$ nodes. The same comparison applies: two nodes at level $x_2$ are equivalent if their LO and HI pointers coincide after reduction at level $x_3$. In the full decision tree of (2), the symmetry of the median function implies that the two level $x_2$ nodes become identical under this criterion, so Algorithm R merges them into a single node labeled $2$.
Proceeding upward, the root level $x_1$ node is then determined by two identical substructures below it after the previous identifications. Since its LO and HI children are now distinct reduced nodes corresponding to the two subfunctions of the median, the root is not eliminated, and no further merging is possible at this level.
The resulting structure after all passes of Algorithm R has exactly the canonical reduced form: a root node labeled $1$, a single node labeled $2$ representing the shared level $x_2$ subfunction, two distinct nodes labeled $3$ corresponding to the reduced level $x_3$ subfunctions, and the sink nodes $\bot$ and $\top$. Every remaining node has distinct $(V,\mathrm{LO},\mathrm{HI})$ data, so no further reduction step applies.
The final directed acyclic graph is therefore exactly the reduced BDD for the median-of-three function shown in Fig. 21, with shared subtrees eliminated and identical subfunctions merged.
This completes the simulation of Algorithm R on the seven-node decision tree in (2). ∎