## 3 Algorithms
### Traversal Part  
Let us first consider a naive method to compute a co-occurrence partition. Suppose that a ZDD represents a collection \(\mathcal{C}\) of subsets of a set \(S\). The co-occurrence partition is incrementally constructed as follows. We start with the partition \(\{S\}\) consisting of the single block \(S\). For each path \(P\) from the root to \(\top\), we obtain a new partition from the current partition by separating each block \(b\) into the two parts \(b\cap T_{P}\) and \(b\cap(S\setminus T_{P})\) if both parts are nonempty, where \(T_{P}\) denotes the set in \(\mathcal{C}\) corresponding to \(P\). This can be done by checking which arc is selected at each node of \(P\). For example, let us see the ZDD given in Figure 3: If we first examine the path \(1\dashrightarrow 2\dashrightarrow 3\dashrightarrow 4\rightarrow\top\), then the block \(S\) of the initial partition splits into the two parts \(\{4\}\) and \(S\setminus\{4\}\), since HI arc is selected only at the label \(4\) node. It can be easily verified that after all paths are examined, the co-occurrence partition induced by \(\mathcal{C}\) is constructed. However, since this method depends on the number of paths (thus the size of \(\mathcal{C}\)), this is not effective for ZDDs which efficiently compress a large number of sets. It would be desirable if we could construct a co-occurrence partition directly from a ZDD. **Figure 3.** The computing process of our algorithm for the ZDD that represents the set family \(\{\{e_{4}\},\{e_{3},e_{5}\},\{e_{2},e_{6}\},\{e_{1},e_{4}\},\{e_{1},e_{3},e_{5} \},\{e_{1},e_{2},e_{4},e_{6}\}\}\) is shown below. For example, in the third line  
The difference from the usual depth-first search is that when we visit an already visited node, we go down from the node to \(\top\) by selecting only HI-arcs. This is essential because the usual depth-first search may fail to detect separable elements. For example, in Figure 4, the two elements \(e_{3}\) and \(e_{4}\) are separable, and in our traversal the third and fourth columns in the table 3b have different arc types thus we can know that they are really separated. On the other hand, in the usual depth-first search they are observed as if they had a common arc type: Since an already visited node is no longer visited, the arc type of \(e_{4}\) in the table 3a is not updated, which means the type remains LO. Unlike the usual depth-first search, we do not skip necessary paths as the following lemma implies. **Lemma 3.1**. : _In each visit of a node \(g\) after the first, two elements get separated when traversing the subgraph whose root is \(g\) if and only if they get separated when going from \(g\) to \(\top\) with only HI-arcs._  
Proof. : Since the sufficiency is immediate, we only show the necessity. Suppose for contradiction that two elements \(e_{i}\) and \(e_{j}\) (\(i<j\)) get separated when visiting all nodes below \(g\), while they are not separated when only selecting HI-arcs. Let \(e_{k}\) denote the element corresponding to \(g\). For the case \(i<k\), there are two paths from \(g\) such that they have different arc types at \(e_{j}\). However, in the first visit of \(g\), we could trace both paths and know that \(e_{i}\) and \(e_{j}\) are separated, which is a contradiction. For the other case \(k\leq i\), there is a path from \(g\) with different arc types at \(e_{i}\) and \(e_{j}\), and we could trace this path in the first visit of \(g\) and reach a contradiction. The traversal part is formally described in Algorithm 1. We here explain some notation and terminology. Recall that in each internal node \(f\), the next node of \(f\) in a LO arc first order is the LO child if \(f\) is a branch node, _i.e._, an internal node whose two children have paths leading to \(\top\); otherwise, the HI child. In order to traverse a ZDD, branch nodes are pushed onto the stack \(\mathrm{BRANCH}\), and visited nodes are contained in \(N_{\mathrm{visited}}\).