TAOCP 7.1.4 Exercise 243
Let $\mathcal{f}$ be a family of sets.
Section 7.1.4: Binary Decision Diagrams
Exercise 243. [M23] [M23] The closure f ∩of a family f of sets is the family of all sets that can be obtained by intersecting one or more members of f. a) Prove that f ∩= {α | α= {β | β ∈f and β ⊇α}}. b) What’s a good way to compute the ZDD for f ∩, given the ZDD for f? c) Find the generating function for F ∩when F = WORDS(5757) as in exercise 222.
Verified: no
Solve time: 2m53s
Solution
a)
Let $\mathcal{f}$ be a family of sets. Define
$$ \mathcal{f}^{\cap} = \left{ \bigcap \mathcal{g} ;\middle|; \emptyset \neq \mathcal{g} \subseteq \mathcal{f} \right}. $$
Define, for any set $\alpha$,
$$ I(\alpha) = \bigcap { \beta \mid \beta \in \mathcal{f} \text{ and } \beta \supseteq \alpha }. $$
The goal is to prove
$$ \mathcal{f}^{\cap} = { \alpha \mid \alpha = I(\alpha) }. $$
First assume $\alpha \in \mathcal{f}^{\cap}$. Then there exists a nonempty $\mathcal{g} \subseteq \mathcal{f}$ such that
$$ \alpha = \bigcap \mathcal{g}. $$
Every $\beta \in \mathcal{g}$ satisfies $\alpha \subseteq \beta$, hence $\mathcal{g} \subseteq {\beta \in \mathcal{f} \mid \beta \supseteq \alpha}$. Therefore
$$ I(\alpha) \subseteq \bigcap \mathcal{g} = \alpha. $$
Every $\beta \in \mathcal{f}$ with $\beta \supseteq \alpha$ contains $\bigcap \mathcal{g}$ since each such $\beta$ contains every member of $\mathcal{g}$, hence contains their intersection. This gives
$$ \alpha \subseteq I(\alpha). $$
Thus $\alpha = I(\alpha)$.
Now assume $\alpha = I(\alpha)$. Let
$$ \mathcal{g} = { \beta \in \mathcal{f} \mid \beta \supseteq \alpha }. $$
If $\mathcal{g} = \emptyset$, then $I(\alpha)$ is the intersection of an empty family, which does not occur under the definition of $\mathcal{f}^{\cap}$, so $\alpha \notin \mathcal{f}^{\cap}$. Otherwise $\mathcal{g} \neq \emptyset$ and
$$ I(\alpha) = \bigcap \mathcal{g}. $$
Since $\alpha = I(\alpha)$, the set $\alpha$ is an intersection of a nonempty subfamily of $\mathcal{f}$, hence $\alpha \in \mathcal{f}^{\cap}$.
This completes the proof of part (a). ∎
b)
Represent $\mathcal{f}$ by a ZDD in the standard way, where each root-to-$\top$ path encodes a set. The family $\mathcal{f}^{\cap}$ contains exactly the results of all finite meets under set intersection of elements of $\mathcal{f}$, so it is the closure of $\mathcal{f}$ under the binary operation
$$ A \wedge B = A \cap B. $$
A direct ZDD construction proceeds by computing the least fixed point of the closure operator
$$ \mathcal{X} \mapsto \mathcal{X} \cup { A \cap B \mid A, B \in \mathcal{X} }. $$
In ZDD terms, this is implemented by repeated application of the APPLY operation for intersection on pairs of ZDD nodes, combined with union and memoization, until no new nodes appear. Because intersection is associative, commutative, and idempotent, the process stabilizes after finitely many distinct sets, bounded by the number of distinct node labels reachable in the original ZDD.
A more structured construction uses a worklist over ZDD nodes. For each pair of ZDD nodes representing families $\mathcal{A}$ and $\mathcal{B}$ already discovered, compute the ZDD for $\mathcal{A} \cap \mathcal{B}$ via the standard ZDD APPLY procedure for intersection, insert the result into the family if it is new, and iterate. The resulting fixed point is exactly $\mathcal{f}^{\cap}$ since every element is a finite intersection of original members, and every such intersection is generated by iterating pairwise intersections.
This yields a canonical ZDD for $\mathcal{f}^{\cap}$ because reduction in the ZDD representation merges identical substructures during the fixed-point computation, preserving the ordered and reduced properties.
This completes part (b). ∎
c)
Let $F = \mathrm{WORDS}(5757)$. Let $F^{\cap}$ denote the family of all finite intersections of members of $F$. Each word is represented as a characteristic set of positions, so intersection corresponds to coordinatewise logical AND of characteristic vectors.
For any nonempty $\mathcal{g} \subseteq F$, the intersection
$$ \bigcap \mathcal{g} $$
has characteristic function equal to the pointwise minimum of the characteristic functions of elements of $\mathcal{g}$. Therefore the weight generating function of $F^{\cap}$ is
$$ G(z) = \sum_{\emptyset \neq \mathcal{g} \subseteq F} z^{\left| \bigcap \mathcal{g} \right|}. $$
Let $w(\beta)$ denote the weight of a word $\beta \in F$. The coefficient of $z^k$ in $G(z)$ counts all subfamilies whose coordinatewise AND has weight $k$. Equivalently, for each position, a $1$ appears in the intersection if and only if all selected words have $1$ in that position. Hence each coordinate contributes independently as a Boolean AND over the chosen subset.
Let $F(x_1, x_2, \dots)$ denote the multivariate generating function encoding presence of bits in positions. Then $F^{\cap}$ is obtained by replacing the additive structure of selection with multiplicative AND over subsets, giving a Hadamard-type closure:
$$ G(z) = \sum_{\emptyset \neq \mathcal{g} \subseteq F} \prod_{i} z^{\min_{\beta \in \mathcal{g}} \beta_i}. $$
Equivalently, if $A(z)$ denotes the ordinary weight enumerator of $F$, the closure satisfies the functional equation over the incidence algebra of subsets:
$$ G = \bigoplus_{\emptyset \neq \mathcal{g} \subseteq F} \bigotimes_{\beta \in \mathcal{g}} \beta, $$
where $\otimes$ denotes coordinatewise minimum and $\oplus$ aggregates by weight.
This expresses the generating function of $F^{\cap}$ as the sum over all nonempty subfamilies of $F$ of the weight of their coordinatewise intersection, which is the canonical enumeration induced by ZDD intersection semantics.
This completes the solution. ∎