# DenseZDD: A Compact and Fast Index for Families of Sets +
## 7 Other Decision Diagrams  
### Sets of Strings  
A _sequence binary decision diagram_ (SeqBDD) [17] is a variant of a zero-suppressed binary decision diagram, customized to manipulate sets of strings. The terminology of SeqBDDs is almost the same as that of ZDDs. Let \(c_{1},\ldots,c_{n}\) be letters such that \(c_{1}<c_{2}<\cdots<c_{n}\) and \(\Sigma_{n}=\{c_{1},\ldots,c_{n}\}\) be an alphabet. Let \(s=x_{1},\ldots,x_{l}\), \(l\geq 0\), \(x_{1},\ldots,x_{\ell}\in\Sigma_{n}\), be a string. We denote the _length_ of \(s\) by \(|s|=\ell\). The empty string is denoted by \(\varepsilon\). The _concatenation_ of strings \(s=x_{1},\ldots,x_{\ell_{1}}\) and \(t=y_{1},\ldots,y_{\ell_{2}}\) is defined as \(s\cdot t=x_{1},\ldots,x_{\ell_{1}},y_{1},\ldots,y_{\ell_{2}}\). The _product_ of string sets \(L_{1}\) and \(L_{2}\) is defined as \(L_{1}\times L_{2}=\{\,s_{1}\cdot s_{2}\,|\,s_{1}\in L_{1},s_{2}\in L_{2}\,\}\).  
A SeqBDD is a directed acyclic graph. The difference between SeqBDD and ZDD is a restriction for indices of nodes connected by edges. For any SeqBDD nonterminal node \(v\), the index of \(v\)'s 0-child must be smaller than that of \(v\), but the index of \(v\)'s 1-child can be larger than or equal to that of \(v\). This relaxation is required to represent string sets because a string can have the same letters at multiple positions. The definition of SeqBDDs is the following:  
Definition 3 (string set represented by a SeqBDD): A SeqBDD \(G=(V,E)\) rooted at a node \(v\in V\) represents a finite sets of strings \(L(v)\) whose letters are in \(\Sigma_{n}\) defined recursively as follows: (1) If \(v\) is a terminal node: \(L(v)=\{\varepsilon\}\) if \(value(v)=1\), and \(L(v)=\emptyset\) if \(value(v)=0\); (2) If \(v\) is a nonterminal node, then \(L(v)\) is the finite set of strings \(L(v)=(\{\{c_{\text{index}(v)}\}\}\times L(one(v)))\cup L(zero(v))\).  
A string \(s=x_{1},\ldots,x_{\ell}\) describes a path in the graph \(G\) starting from the root in the same way as ZDDs. For SeqBDDs, we also employ the zero-suppress rule and the sharing rule. By applying these rules as much as possible, we can obtain the canonical form for given sets of strings.  
We can compress SeqBDDs by the same algorithm as the DenseZDD construction algorithm. We call it _D_enseSeqBDD. Since the index restriction between nodes connected by 0-edges is still valid on SeqBDDs, we can represent indices of nodes and connection by 0-edges among nodes by zero-edge trees. The main operations of SeqBDD such as _index_, _zero_, _one_, _topset_, _member_, _count_, and _sample_ are also implemented by the same algorithms. Recall that a longest path on a ZDD is bounded by the number of items \(n\). Therefore, the time complexities of _member_ and _sample_ on a ZDD are at most \(\mathcal{O}(n)\), which means that the benefit we can gain by skipping continuous 0-edges in _topset_ algorithm is not so large because the total number of nodes we can skip is less than \(n\). However, a longest path on a SeqBDD is not bounded by the number of letters, and thus we can gain more benefit of skipping 0-edges because indices of nodes reached after traversing 1-edges can be the largest index. The time complexities of _member_ and _sample_ on a SeqBDD are \(\mathcal{O}(\textit{maxlen})\) and \(\mathcal{O}(\textit{maxlen}\log|\Sigma_{n}|)\), respectively, where _maxlen_ is the length of the longest string included in the SeqBDD.