TAOCP 7.1.4 Exercise 102

Section 7.1.4: Binary Decision Diagrams

Exercise 102. [23] [23] Design a method to cache the results of functional composition using the fol- lowing conventions: The system maintains at all times an array of functions [g1, . . . , gn], one for each variable xj. Initially gj is simply the projection function xj, for 1 ≤j ≤n. This array can be changed only by the subroutine NEWG(j, g), which replaces gj by g. The subroutine COMPOSE(f) always performs functional composition with respect to the current array of replacement functions.

Verified: no
Solve time: 4m47s

Solution

Let $f(x_1,\dots,x_n)$ be a Boolean function represented by its BDD as in Section 7.1.4. The system maintains functions $g_j$ for $1 \le j \le n$, initially $g_j = x_j$, and these functions are updated only by calls to $\texttt{NEWG}(j,g)$ which sets $g_j \leftarrow g$.

For any Boolean function $f$, define

$f^{\ast}(x_1,\dots,x_n) = f(g_1,\dots,g_n),$

where composition is taken with respect to the current array $(g_1,\dots,g_n)$.

The goal of $\texttt{COMPOSE}(f)$ is to evaluate or construct a representation of $f^{\ast}$ efficiently, while reusing previously computed composed subfunctions so that repeated structure is cached rather than recomputed.

The key observation from the BDD model is that every Boolean function is represented uniquely by its set of beads, and each node corresponds to a subfunction determined by a pair of subtables. Thus caching must be done at the level of BDD nodes, not at the level of syntactic expressions.

The algorithm is defined recursively on the structure of the BDD of $f$.

For a sink node, if $f = \bot$, then $f^{\ast} = \bot$, and if $f = \top$, then $f^{\ast} = \top$. These values are returned immediately.

Assume $f$ is a branch node labeled $k = V(f)$ with LO and HI children $f_0$ and $f_1$. Then

\begin{cases} f_0(x_1,\dots,x_n), & x_k = 0, \ f_1(x_1,\dots,x_n), & x_k = 1. \end{cases}$$ After substitution of the current array $(g_1,\dots,g_n)$, this becomes $$f^{\ast}(x_1,\dots,x_n) = \begin{cases} f_0^{\ast}(x_1,\dots,x_n), & g_k(x_1,\dots,x_n) = 0, \ f_1^{\ast}(x_1,\dots,x_n), & g_k(x_1,\dots,x_n) = 1. \end{cases}$$ Thus composition preserves the Shannon decomposition structure, but replaces the test variable $x_k$ by the function $g_k$. The resulting composed function is determined by the triple $(k, g_k, f_0^{\ast}, f_1^{\ast})$. --- Caching is introduced by maintaining a memo table indexed by BDD nodes. Let $\mathcal{C}(f)$ denote the cached result of $\texttt{COMPOSE}(f)$. The cache invariant is that if two calls receive isomorphic BDD subgraphs, they return identical stored results without recomputation. Define the computation: If $\mathcal{C}(f)$ is already defined, return it. Otherwise compute it recursively. For a branch node $f$ with index $k$, first ensure that $g_k$ is itself represented in BDD form. Then recursively compute $\mathcal{C}(f_0)$ and $\mathcal{C}(f_1)$, obtaining $h_0$ and $h_1$. Construct the composed node $h$ as the unique reduced BDD node with index determined by the smallest variable index appearing in $g_k$, and LO and HI branches determined by the Shannon expansion of $g_k$: $$g_k = (g_k|{x_i=0}, g_k|{x_i=1}).$$ Then define $$h = \text{MK}(k, h_0, h_1, g_k),$$ where MK denotes the reduced-node constructor that merges identical triples and eliminates nodes with equal children. Finally store $\mathcal{C}(f) \leftarrow h$ and return $h$. --- The correctness follows from structural induction on the BDD of $f$. For sink nodes the result is immediate. For a branch node, assuming correctness of $h_0 = f_0^{\ast}$ and $h_1 = f_1^{\ast}$, the constructed node $h$ implements exactly the Shannon decomposition of $f^{\ast}$ with respect to the substituted decision function $g_k$, and thus represents $f^{\ast}$. Reduction rules preserve equivalence because they identify only nodes with identical functional behavior. --- Running time is determined by the number of distinct BDD nodes of $f$ and by the cost of composing each node once. Each node is evaluated at most once due to caching. Each evaluation performs a constant number of pointer accesses plus one construction in MK, and MK performs at most constant-time table lookup in the unique-table representation of reduced BDDs. Let $B(f)$ denote the number of beads of $f$, which equals the number of BDD nodes. Each node contributes $O(1)$ work when first visited, and thereafter is never recomputed. Thus $$T(\texttt{COMPOSE}(f)) = O(B(f)).$$ Since $B(f)$ is also the size of the resulting reduced representation of any composed form up to sharing, no algorithm based on node expansion can asymptotically improve this bound in the worst case without avoiding examination of each node, because each node encodes at least one distinct subfunction determined by a bead and must be processed to determine its image under substitution. Therefore the cached composition algorithm runs in time linear in the size of the input BDD and produces a result whose size is bounded by the product of the sizes of the participating BDD structures, with sharing preventing exponential recomputation in typical cases. This completes the solution. ∎