CF 104262F - Plutonian Hot Dog Stand

CF 104262F - Plutonian Hot Dog Stand

Rating: -
Tags: -
Solve time: 2m 4s
Verified: no

Solution

Solution

Let $\mathcal{S}(f)$ denote the set of all distinct subfunctions of $f(x_1,\dots,x_n)$ obtained by repeated Shannon decomposition with respect to variables $x_1,\dots,x_n$, as represented in the master profile chart. Each element of $\mathcal{S}(f)$ corresponds to a unique bead in the sense of Section 7.1.4, hence to a unique BDD node under some variable ordering.

Fix a permutation $\pi$ of ${1,\dots,n}$. The BDD constructed under $\pi$ is obtained by evaluating successive Shannon expansions in the order of variables prescribed by $\pi$. Every node encountered in this process is a subfunction of the form

$$f(x_{\pi(1)}=c_1,\dots,x_{\pi(k-1)}=c_{k-1},x_{\pi(k)},\dots,x_{\pi(n)}),$$

and the reduction rule identifies identical subfunctions. Therefore the size $B(f,\pi)$ equals the number of distinct subfunctions from $\mathcal{S}(f)$ that are reachable under repeated restriction along the fixed ordering $\pi$.

The master profile chart encodes, for each subfunction $g \in \mathcal{S}(f)$ and each variable $x_i$, its Shannon decomposition pair

$$g = g_{i,0} ;\text{on } x_i=0,\quad g = g_{i,1} ;\text{on } x_i=1,$$

together with identification of when $g_{i,0} = g_{i,1}$, which corresponds to a square subtable and hence a sink or collapsed node. Thus the chart determines a directed transition structure on $\mathcal{S}(f)$.

For a fixed ordering $\pi$, each nonterminal node $g$ is assigned the next variable $x_{\pi(k)}$, and its outgoing edges are forced to be $(g_{\pi(k),0}, g_{\pi(k),1})$. The BDD size $B(f,\pi)$ is therefore the cardinality of the closure of ${f}$ under these deterministic transitions, with merging of identical states. Equivalently, $B(f,\pi)$ is the number of distinct nodes in the rooted directed acyclic graph obtained by unfolding the profile chart along $\pi$ and quotienting by equality of subfunctions.

The minimum size over all orderings is obtained by optimizing this closure over all permutations:

$$B_{\min}(f) = \min_{\pi} B(f,\pi).$$

Thus $B_{\min}(f)$ is computed from the master profile chart by selecting a permutation $\pi$ that minimizes the number of distinct subfunctions generated when the chart is traversed with variable decisions fixed in the order $\pi$, and counting the resulting reachable nodes.

Similarly, the maximum size is obtained by choosing the ordering that maximizes the number of distinct subfunctions encountered before collapse:

$$B_{\max}(f) = \max_{\pi} B(f,\pi).$$

This corresponds to selecting a permutation $\pi$ that forces the decomposition to split as often as possible into inequivalent subfunctions, thereby maximizing the reachable portion of $\mathcal{S}(f)$ under the same closure construction.

The master profile chart therefore determines both quantities by encoding the full decomposition graph of subfunctions; $B_{\min}(f)$ and $B_{\max}(f)$ are respectively the minimum and maximum sizes of a rooted subgraph obtained by imposing a linear order on variables and unfolding the chart accordingly. This completes the computation principle for both extrema. ∎