## 3 Algorithms
### Conditional Co-occurrence Relations  
Given a ZDD where every two elements are separable, Algorithm 1 cannot extract any useful information from the ZDD, but even so, we want to find some structural information hidden in the ground set. In this subsection we focus on the condition that enforces some elements always to be in a HI state and some elements always to be in a LO state.  
Let \((\mathrm{ON},\mathrm{OFF})\) be a pair of subsets of the ground set \(S\) of a ZDD. Two elements \(e_{i},e_{j}\in S\) are conditionally inseparable with respect to \((\mathrm{ON},\mathrm{OFF})\) if they co-occur with each other for all paths that satisfy the condition: the HI arcs are always selected for all elements in \(\mathrm{ON}\); The LO arcs are always selected for all elements in \(\mathrm{OFF}\).  
Before extracting this relation, we need a preprocessing so that we can trace only paths that satisfy the condition above. Recall that the cardinality of a node \(f\) is the number of paths from \(f\) to \(\top\). It is known (see also Algorithm C and Exercise 208 in [12]) that given a ZDD, the cardinalities of all nodes in the ZDD can be computed in time proportional to the size of \(f\). This computation can be done in a bottom-up fashion: The cardinalities of \(\bot\) and \(\top\) are \(0\) and \(1\), respectively; the cardinality of each internal node is the sum of the cardinalities of the two children. Given a pair \((\mathrm{ON},\mathrm{OFF})\), it is easy to change to be able to compute the numbers of paths from all internal nodes \(f\) to \(\top\) that satisfy the condition concerning \((\mathrm{ON},\mathrm{OFF})\). For convenience we call these numbers conditional cardinalities with respect to \((\mathrm{ON},\mathrm{OFF})\).  
To construct a conditional co-occurrence partition, change Algorithm 1 as follows.  
Figure 5: For each step of the traversal of the ZDD given in Figure 3, the doubly linked list of HI-state elements is shown below, where the index denotes the number of times \(\top\) was visited and the double box or circle denotes the position after which an element is inserted.  
1. Return the initial partition if the conditional cardinality of the root is zero.
2. The next node \(g\) of the current node \(f\) is the LO child if the conditional cardinalities of the two children are nonzero; else if the conditional cardinality of the LO child is zero, the HI child; else, the LO child.
3. In the while block of Algorithm 1, the next node \(g\) is the LO child if the conditional cardinality of the HI child is zero; otherwise, the HI child.  
**Theorem 3.3**.: _Let \(m\) be the number of branch nodes. Let \(n\) be the size of a ground set. The computation for a conditional co-occurrence partition can be done in time proportional to \(mn\)._  
Proof.: This theorem can be proved in a similar way to the proof in Theorem 3.2, but an upper bound for the number of the traversed nodes cannot be similarly calculated. Indeed, because of the change in the while block, we may have to select many LO arcs. At least we can say that the size of each path \(P_{i}\) is at most \(n\) and the number of periods is at most \(m+1\). Thus the time is proportional to \(mn\).  
Thanks to this theorem, when selecting a pair \((\mathrm{ON},\mathrm{OFF})\), there is no need to worry about a rapid increase of computation time. This is in contrast to the case where we arbitrarily select paths and compute a co-occurrence partition from the selected paths. These paths are no longer compressed, and even if they can be compressed in some way, the size is generally irrelevant to the size of the original ZDD, and thus we cannot give a similar guarantee.