Notes on Sequence Binary Decision Diagrams:
Relationship to Acyclic Automata andComplexities of Binary Set Operations
Shuhei Denzumi1 , Ryo Yoshinaka2 , Hiroki Arimura1 , and Shin-ichi Minato1,2
1

2

Graduate School of IST, Hokkaido University, Japan
ERATO MINATO Discrete Structure Manipulation System Project, JST, Japan{denzumi, ry, arim, minato}@ist.hokudai.ac.jp

Abstract. Manipulation of large sequence data is one of the most important problems in string processing. Recently, Loekito et al. (Knowl. Inf. Syst., 24(2), 235–268,
2009) have introduced a new data structure, called Sequence Binary Decision Diagrams(SeqBDDs, or SDDs), which are descendants of both acyclic DFAs (ADFAs) and binary
decision diagrams (BDDs). SDDs can compactly represent sets of sequences as well as
minimal ADFAs, while SDDs allow efficient set operations inherited from BDDs. A
novel feature of the SDDs is that different SDDs can share equivalent subgraphs andduplicated computation in common to save the time and space in various operations.
In this paper, we study fundamental properties of SDDs. In particular, we first present
non-trivial relationships between sizes of minimum SDDs and minimal ADFAs. We thenanalyze the complexities of algorithms for Boolean set operations, called the binary synthesis. Finally, we show experimental results to confirm the results of the theoreticalanalysis on real data sets.

1

Introduction

1.1

Background

Compact string indexes for storing sets of strings are fundamental data structuresin computer science, and have been extensively studied in the decades [2,4,5,6,9,19].
Examples of compact string indexes include: tries [1,5], finite automata and transducers [6,10], suffix trees [15], suffix arrays [14], DAWGs [2], and factor automata(FAs) [19]. By the rapid increase of massive amounts of sequence data such as biological sequences, natural language texts, and event sequences, these compact stringindexes have attracted much attention and gained more importance [5,9]. In suchapplications, an index have not only to compactly store sets of strings for searching,
but also have to efficiently manipulate them with various set operations, e.g., merge,intersection, and subtraction.
Minimal acyclic deterministic finite automata (ADFAs) [5,6,10] are one of suchindex structures that fulfill the above requirement based on finite automata theory,and have been used in many sequence processing applications [13,18]. However, they
have drawback of complicated procedures for minimization and various set operations
caused by multiple branching of the underlying directed acyclic graph structure. To
overcome this problem, Loekito et al. [12] proposed the class of sequence binary decision diagrams (sequence BDDs, or abbreviated as SDDs in this paper), which is acompact representation for sets of strings that allows a variety of operations for setsof strings. An SDD is a node-labeled graph structure, which resembles to an acyclic
DFA in binary form, but with the minimization rule which is different from one for
Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-ichi Minato: Notes on Sequence Binary Decision Diagrams: Relationship to Acyclic Automata andComplexities of Binary Set Operations, pp. 147–161.
Proceedings of PSC 2011, Jan Holub and Jan Žd’árek (Eds.), ISBN 978-80-01-04870-2 c Czech Technical University in Prague, Czech Republic

148

Proceedings of the Prague Stringology Conference 2011a minimal DFA. A novel feature of the SDDs is their ability to share equivalentsubgraphs and results of similar intermediate computation between different SDDs,
which avoids redundant generation of nodes and computation.
1.2

Main results

In this paper, we present theoretical analysis of two fundamental problems on sequence binary decision diagrams, which have not been studied before: the relationshipto acyclic automata and the complexities of binary set operations as follows.
The relationship to acyclic automata. The structure of SDDs apparently
resembles that of Acyclic Deterministic Finite Automata (ADFAs), which are a classical model for representing string sets. While a state of an ADFA may have many
outgoing edges, a node of an SDD always has two outgoing edges, which can be seen
as just the “first-child next-sibling” representation of a branching with many edges.
Indeed one can find a straightforward translation from an ADFA to an SDD andvice versa. However, there are subtle differences between those data structures andactually an SDD can be even more compact than the corresponding ADFA. We showthat the minimum SDD is never larger than the minimum ADFA but the minimum
ADFA can be |Σ| times larger than the minimum SDD for the same language overΣ.
The computational complexities of binary set operations. Next, we study
the complexity of the binary synthesis, which are binary operations for minimal SDDs,
such as union, intersection, and subtraction, which directly construct a minimal SDD.
Specifically, we study upper and lower bounds for the time complexity of the binary
synthesis algorithms. Loekito et al. [12] have proposed algorithms for union and subtraction, which are similar to the apply algorithm Bryant [3], and have conjectured
that they run in input-output linear-time. We generalize their algorithms into an algorithm Meld⋄ which uniformly implements eight set operations in the style of Knuth’s
melding operation for BDDs [11]. We show an upper bound that its time complexity
is quadratic in the input size, and linear in the size of non-reduced version of theoutput size. Moreover, we show a lower bound that Meld⋄ actually requires quadratic
time in input size for some infinite series of inputs using a technique recently devisedfor BDD [3], giving matching upper bound.
Experimental results. Finally, we run experiments on real data sets. We firstobserved that minimal SDDs were superior to minimal DFAs when large subgraphs
were shared in inputs and outputs due to the node-sharing across multiple SDDs. We
also observed that each binary synthesis operation took less than seconds to take set
operations ∪, ∩, and \ of two input SDDs with around three to four thousands of nodes
each, which were relatively smaller than the running time for set construction [7].
1.3

Related works

There have been a number of researches on manipulation of finite automata in automata theory and string algorithms. The textbook [10] gives classic examples of aquadratic-time algorithm for computing the union, intersection, and subtraction of
two DFAs, and a state-minimization algorithm for a given DFA. Daciuk, Mihov, Watson, and Watson [6] presented an incremental algorithm for constructing the minimal
ADFA for a set of strings. Blumer et al. [2] and Crochemore [4] gave linear-time algorithms for construction of the minimal state ADFAs for the set of all factors of an

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

149

input string. Compared with a straightforward two-stage algorithm for binary synthesis for ADFAs using product followed by state-minimization [10], the advantages ofthe proposed Meld⋄ are its simplicity and efficiency that it directly computes the output by applying the on-the-fly minimization [7]. Using binary synthesis, Denzumi etal. [7] presented a simple linear-time algorithm for incremental construction of SDDs,
and a recursive top-down algorithm for construction of factor SDDs.
SDDs inherit many of their features from binary decision diagrams (BDDs), which
are compact representation for storing and manipulating combinatorial structuresdeveloped in logic design community [3,11,16,21]. Especially, BDDs equipped withbinary synthesis operation were invented by Bryant [3] in the 80s for dealing with
Boolean functions, while their variant with node-sharing and zero-suppress rules,
called zero-suppressed BDDs (ZDDs), were proposed by Minato [16] in the 90s forsparse combinatorial sets. On their early history, reduced BDDs were constructedfrom tree-like circuits through offline minimization. After the invention of the binary
synthesis algorithm by Bryant [3], it became popular to build large BDDs on-thefly in real applications. Loekito et al. [12] discovered that if we remove the ordering
constraint on the 1-edges from ZDDs, the resulting variant of ZDDs, which actually
are SDDs, has a similar structure to ADFAs in binary form and suitable to storingand manipulating sets of strings. This observation led to the invention of SDDs [12].
Organization of this paper. In Section 2, we prepare basic notions and notations on SDDs. In Section 3, we give the size bounds for SDDs and DFAs. In Section 4,
we give the time and space complexities of binary synthesis procedures for SDDs. In
Section 5, we show some experimental results. In Section 6, we conclude this paper.
For details of basic properties and algorithms related to SDDs not described in thispaper, please consult the companion paper [7].

2Preliminaries

In this section, we give basic definitions and notations in strings and sequence BDDs
according to [11,12,16]. For the details of results not found here, please consult thecompanion paper [7]. An ordered alphabet is a pair hΣ, ≺i where Σ is a finite alphabet
and ≺ is a total order on Σ. The order ≺ associated with Σ is often denoted by ≺Σand the ordered alphabet is simply written Σ for legibility. A string on Σ is a sequences = s1 · · · sn of letters si ∈ Σ (1 ≤ i ≤ n), where |s| = n denotes the length. If s = xyz
for some x, y, z ∈ Σ ∗ , then we say that x is a prefix , y is a factor , and z is a suffix ofs. A string set (or a language) is any finite S ⊆ Σ ∗ . We denote by |S| the cardinality.
For any x ∈ Σ, we define x · S = { xy | y ∈ S }.
Sequence BDDs. Let dom be a countable domain of the nodes. A sequencebinary decision diagram or a sequence BDD (abbreviated as SDD 1 here) is a directed
acyclic graph (DAG) B = hΣ, V, τ, r, 0, 1i where V = V (B) ⊆ dom is a finite set ofnodes, r ∈ V is called the root of B and 0 and 1 ∈ V are distinct nodes called the0- and 1-terminals, resp. The nodes in VN = V \{0, 1} are called nonterminals. Eachnode v ∈ VN of B is labeled by a symbol v.lab in Σ and has two children, the 0-childand the 1-child, denoted by v.0 and v.1, resp, which can be identical. We call the1

Note that the abbreviation SeqBDD is used to denote sequence BDD in the original paper by Loekito et al. [12]. We also note that the abbreviation SDD was also used for the set decision diagrams(Couvreur, Thierry-Mieg, Proc. FORTE 2005, LNCS 3731, 443–457, 2005) and the spectral decision diagrams (Thornton, Drechsler, Proc. DATE’01, IEEE, 713–719, 2001).

150

Proceedings of the Prague Stringology Conference 2011

a

b

a
a

bc
b

a

b

c

b

c

b

b

c

c

a

b

c
c

a

b

c

b c
c

b

c

c
1

DFA G1

Non-reduced SDD G2

1
Reduced SDD G3

Figure 1. Examples of three index structures on Σ1 = {a, b, c} for the same string set S1 ={aa, aab, aac, ab, abb, abc, ac, acc, bb, bbb, bbc, bc, bcc, c, cc}: a minimal DFA G1 (left), a minimal DFA
as a non-reduced SDD G2 (middle), and a reduced SDD G3 (right). In the figure, solid and dottedarrows indicate the 1- and 0-edge . The edges to the 0-terminal are omitted.

edge from v to v.0 and v.1 the 0- and 1-edge of v, resp. The information is formallydescribed by a function τ : VN → Σ ×V 2 that assigns the triple τ (v) = hv.lab, v.0, v.1i
to each v ∈ VN . An SDD must be acyclic, that is, one may assume a strict partial
order ≻V on V such that v ≻V v.0 and v ≻V v.1 hold for any v ∈ VN . The 1-child and0-child of a node correspond to the leftmost-child and the right-sibling in a DAG in
binary form [1,11]. Siblings are deterministically ordered from left to right according
to the order ≺Σ . That is, we always have v.lab ≺Σ (v.0).lab unless v.0 is a terminal
node. We assume that any SDD B is well-defined meaning that B is both acyclic
and deterministic. We define the size of B by |B| = |VN | = |V | − 2, the number of
non-terminals in B.
To each node v ∈ V , we inductively (w.r.t. ≻V ) assign a language LB (v) as follows:(i) LB (0) = ∅;(ii) LB (1) = {ε};(iii) LB (v) = LB (v.0) ∪ (v.lab) · LB (v.1).
Equivalently, s ∈ LB (v) iff there is a path from v to 1 such that one obtains s byconcatenating the labels of the nodes whose 1-edges appear in the path. The language
L(B) of B is defined to be LB (r). We say that two SDDs B and B ′ are equivalent if
L(B) = L(B ′ ). An SDD B is said to be minimal if it has the smallest number of nodes
among the equivalent SDDs, i.e., |B| ≤ |B ′ | for any SDD B ′ such that L(B ′ ) = L(B).
Figure 1 illustrates examples of SDDs together with the minimum deterministic finite
automaton for the same language.
Reduced SDDs. A reduced SDD is a normal form of SDDs. An SDD is said tobe reduced if it satisfies the following two conditions:
1. For any u, v ∈ VN , τ (u) = τ (v) implies u = v (node-sharing rule).
2. For any v ∈ VN , v.1 6= 0 holds (zero-suppress rule).
The above rules say that no distinct non-terminal nodes have the same triple, andthe 1-child of any non-terminal node v is not the 0-terminal. For any finite set of
strings L ⊆ Σ ∗ , we can construct the canonical SDD for L [7] in a way similar to
the minimal DFA in Myhill-Nerode theorem (e.g.,[10,20]). Actually, the next theorem
gives a characterization of minimal SDDs in terms of a reduced SDD and the canonical
SDD. See the companion paper [7] for the details.
Theorem 1 (Denzumi et al. [7]). For any SDD B with the language L = L(B),the following (1)–(3) are equivalent to each other.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams✬
Global variable: uniqtable: hash table for triples.

Proc Getnode(x: letter, P0 , P1 : SDD):
1: if (P1 = 0) return P0 ; /* zero-suppress rule */2: else if ((R ← uniqtable[hx, P0 , P1 i]) exists) return R; /* node-sharing rule */3: else4:
R ← a new node with τ (R) = hx, P0 , P1 i; uniqtable[hx, P0 , P1 i] ← R;
5:
return R;✫
Figure 2. The Getnode procedure for on-the-fly minimization.

151

✩

✪

(1) B is a reduced SDD.
(2) B is a canonical SDD for L up to isomorphism.
(3) B is a minimal SDD.
Due to Theorem 1, for a fixed language L, we may call a reduced SDD for L the
reduced SDD for L when we work modulo isomorphism. In order to satisfy the nodesharing rule, we maintain a hash table, called uniqtable, which is the inverse of τ .
That is, it gives the unique node v such that τ (v) = hx, v0 , v1 i (if exists) for the key
hx, v0 , v1 i. As is the case for BDDs and ZDDs, usually we consider only reduced SDDs.
Hereafter we assume that all SDDs are reduced unless otherwise noted.
While an SDD represents a set of strings, we often would like to manipulate two
or more sets of strings. In our shared SDD environment, the terminals 0 and 1, thefunction τ and thus the hash uniqtable : Σ × dom × dom → dom are shared by morethan one SDD in common so that we can have a compact representation of a familyof sets of strings. One may think of the shared SDD environment as a single SDD
with multiple roots. By picking up a node v as the root, one can extract a subgraphas an SDD consisting of all the nodes that are reachable from v. For convenience, we
often identify a node v with the SDD rooted by v extracted from the shared SDD
environment. Hence |v| represents the number of nonterminal nodes reachable fromthe node v.
Figure 2 shows the node allocation procedure Getnode, which is used as a subroutine in algorithms on SDDs. Throughout this paper, we assume that the hash table
uniqtable is a global variable, and a look-up for it takes O(1) time; We have to add
additional O(log n) term if we use balanced binary tree dictionary [1]. In the shared
and reduced SDD environment studied here and in [7,12], we use write-only construction, similarly to [8], such that any new SDD is constructed by adding a new nodeon the top of already constructed SDDs using a call of Getnode given existing nodes
as its arguments. The next lemma guarantees that we always have reduced SDDs aslong as we solely use Getnode to obtain a new node.
Lemma 2 (Denzumi et al. [7]). Let B be any reduced SDD. For any symbol x ∈ Σand nodes v0 , v1 ∈ V (B) in B such that v0 6∈ VN or x ≺Σ v0 .lab, if we invoke
v = Getnode(x, v0 , v1 ) on B and add the result v to V (B), then the resulting SDD B ′with root v obtained from B is well-defined and reduced, too.
Based on the procedure Getnode above, for example, we can implement an off-line
minimization (i.e., reduction) algorithm Reduce for SDDs in linear time and space [7]2 .
2The complexity analysis assumes that a look-up for the hash table uniqtable takes O(1) time.
A precise worst-case time complexity is O(n log n) if the hash table does not work efficiently.

152

Proceedings of the Prague Stringology Conference 2011

Factually it simply makes a copy of an input SDD using Getnode, which merges
equivalent nodes in uniqtable. See [7,12] for details.

3Space-Bounds for Sequence Binary Decision Diagrams
and Acyclic Automata

The structure of SDDs apparently resembles that of acyclic deterministic finite automata (ADFAs). There is a straightforward translation from an ADFA to an SDD
and the other way around. However, we should note subtle differences between thoseformalisms. Actually SDD can be even more compact. This section discusses theirrelationship in detail.
3.1

Finite Automata

We presume a basic knowledge of the automaton theory. For a comprehensive introduction to the automaton theory, see [10] for example. A (partial) DFA is represented
by a tuple A = hΣ, Γ, δ, q0 , F i, where Σ is the input alphabet, Γ is the state set, δis the partial transition function from Γ × Σ to Γ , q0 ∈ Γ is the initial symbol andF ⊆ Γ is the set of acceptance states. The partial function δ can be regarded as asubset δ ⊆ Γ ×Σ×Γ . We define the size of a DFA A, denoted by |A|, as the numberof labeled edges in A, i.e., |A| = |δ|.
The set of strings that lead the automaton A from a state q to an accept state isdenoted by LA (q). The language L(A) accepted by A is LA (q0 ). A minimum DFA has
no state q such that LA (q) = ∅ and no distinct states q ′ and q ′′ such that LA (q ′ ) =LA (q ′′ ). Since we are concerned with finite sets of strings, all DFAs discussed in thissection are acyclic (ADFA). We say that A and B, which can be an ADFA or an
SDD, are equivalent if L(A) = L(B).
3.2

From ADFAs to SDDs

We first give a straightforward translation from an ADFA to an equivalent SDD,
which may be non-reduced, and compare the sizes of them.
Theorem 3. For any ADFA A = hΣ, Γ, δ, q0 , F i, there is an equivalent SDD B =hΣ, V, τ, 0, 1, ri such that |VN | ≤ |δ|. Moreover, for every positive integer n ≥ 1, there
is an ADFA A that admits no equivalent SDD B such that |VN | < |δ| = n.
Proof. For an ADFA A = hΣ, Γ, δ, q0 , F i, we construct an equivalent SDD B(A). Letdeg(q) = |{ a ∈ Σ | δ(q, a) is defined }| .
We define B(A) = hΣ, V, τ, 0, 1, ri as follows. The set of nodes is given by
V = {0, 1} ∪ { [q, i] | q ∈ Γ and 1 ≤ i ≤ deg(q) }.
For each q ∈ Γ with deg(q) = k ≥ 1, let a1 , . . . , ak ∈ Σ and q1 , . . . , qk ∈ Γ be suchthat
– δ(q, ai ) = qi for i = 1, . . . , k,
– a1 ≺ a2 ≺ · · · ≺ ak .

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

Define τ by

where



hai , [q, i + 1], qbi iτ ([q, i]) = hak , 1, qbk iha , 0, qb i
k
k

′

[q , 1]qb′ = 1

0

153

if i < k,if i = k and q ∈ F,
if i = k and q 6∈ F,

if deg(q ′ ) > 0,
if deg(q ′ ) = 0 and q ′ ∈ F,
if deg(q ′ ) = 0 and q ′ 6∈ F.

The root r of B(A) is qb0 .
It is easy to see that LA (q) = LB(A) (q̂) for all q ∈ Γ . We note that the above
construction can be done in linear time in |δ|.
The first claim of the theorem can be verified by the above construction of B(A).
The second claim is established by observing the minimum ADFA and the reduced
SDD that accept the singleton {an } for each positive integer n. For the detail of
construction of the reduced (canonical) SDD from a string set, consult [7].
⊓⊔We remark that B(A) in the proof is not necessarily reduced for a minimum ADFA A.
Example 4. Let us compare the minimum ADFA A and the constructed SDD B(A)for the set {ab, b} with a ≺ b:transition rules of A corresponding nodes of B(A)
δ(q0 , a) = q1
τ ([q0 , 1]) = ha, [q0 , 2], [q1 , 1]iδ(q0 , b) = q2
τ ([q0 , 2]) = hb, 0, 1i
δ(q1 , b) = q2
τ ([q1 , 1]) = hb, 0, 1i
B(A) is not reduced since τ ([q0 , 2]) = τ ([q1 , 1]) for [q0 , 2] 6= [q1 , 1].
In this example, A has two distinct edges that are labeled with b and come into q2 ,which should be merged into the same node in a reduced SDD. Hence the reduced
SDD can be more compact than the minimum ADFA for the same language. We next
discuss how much an SDD can be smaller than an ADFA through a translation froman SDD into an ADFA.
3.3

From SDDs to ADFAs

We next discuss how much an SDD can be smaller than an ADFA through a translation from an SDD into an ADFA. Let an SDD B = hΣ, V, τ, 0, 1, ri be given. We
construct an ADFA A(B) = hΣ, Γ, δ, q0 , F i such that L(A(B)) = L(B). We assume
that r 6= 0. Otherwise, the translation is trivial.
For each P ∈ VN , let Pe = [P1 , . . . , Pk ] be such that P1 = P and τ (Pi ) =hai , Pi+1 , Ri i for some Ri ∈ V for i ≤ k and Pk+1 ∈ {0, 1}. We define 1̃ to be [1]. Let
f1 | P1 6= 0 is the 1-child of some P ∈ VN },– Γ = {er} ∪ { P– q0 = er,– F = { Pe ∈ Γ | Pe = [P1 , . . . , Pk ] and Pk = 1 },fi if Pe = [P1 , . . . , Pk ] and τ (Pi ) = hai , Pi+1 , Ri i.
– δ(Pe, ai ) = R

154

Proceedings of the Prague Stringology Conference 2011

It is easy to see that LB (P ) = LA(B) (Pe) for all Pe ∈ Γ . This implies that if B
is reduced, A(B) is minimum. Contrary to the translation from an ADFA into an
equivalent SDD, this construction takes O(|Σ||VN |) time. In fact, this is optimal.
The following theorem implies that the reduced SDD can be about |Σ| times morecompact than the minimum ADFA for the same set of strings.
Theorem 5. For any SDD B = hΣ, V, τ, r, 0, 1i, one can construct in O(|Σ||VN |)time the equivalent minimum ADFA A = hΣ, Γ, δ, q0 , F i such that |Γ | ≤ |VN | + 1 and(|VN |(|VN | + 1)/2
if |VN | ≤ |Σ|;|δ| ≤|Σ|(2|VN | − |Σ| + 1)/2 if |VN | > |Σ|.
Moreover, there is an SDD B that admits no equivalent ADFA A for which the strict
inequality holds.
Proof. The first claim, |Γ | ≤ |VN | + 1, clearly holds by the conversion.
In order to establish the second part of the theorem, we give a variant of theconstruction of A(B). We define C(B) from B by replacing the definition of Γ in
A(B) with Γ = { Pe | P ∈ V − {0} }. For C(B) = hΣ, Γ, δ, q0 , F i, we prove theinequality by induction on |VN |. Clearly A(B) is not bigger than C(B), and thus thisclaim implies the theorem. In the following discussion, we ignore the root of B and
the initial state of C(B), because it does not affect the discussion of their description
size. For |VN | = 1, it is easy to see that the claim holds. Suppose that |VN | > 1.
Let B ′ be obtained from B by deleting an arbitrary nonterminal node P that has no
incoming edge.
If |VN | ≤ |Σ|, we have |δ ′ | ≤ (|VN |−1)|VN |/2 by the induction hypothesis, where δ ′denotes the transition set of C(B ′ ). By definition, C(B) can be obtained from C(B ′ )by adding one state Pe and at most |VN | outgoing edges from it. Hence|δ| ≤ |δ ′ | + |VN | ≤ (|VN | − 1)|VN |/2 + |VN | = |VN |(|VN | + 1)/2.

If |VN | > |Σ|, we have |δ ′ | ≤ |Σ|(2|VN | − |Σ| − 1)/2 by the induction hypothesis.
By definition, C(B) can be obtained from C(B ′ ) by adding one state Pe and at most|Σ| outgoing edges from it. Hence|δ| ≤ |δ ′ | + |Σ| ≤ |Σ|(2|VN | − |Σ| − 1)/2 + |Σ| = |Σ|(2|VN | − |Σ| + 1)/2.

We have proven the inequality.
In order to see that the above bound is tight, consider the reduced SDD and theminimum ADFA for the language Ln = { ak0 ai1 . . . aij | 0 ≤ k ≤ n − |Σ|, 0 ≤ j ≤min{m, n}, 1 ≤ i1 < · · · < ij ≤ m } over Σ = {a0 , . . . , am } with a0 ≺ a1 ≺ · · · ≺ am .
⊓⊔We note that if am ≺ · · · ≺ a1 ≺ a0 , we have |VN′ | = |δ| for the node set V ′ of the
reduced SDD B ′ for Ln and the transition set δ of the minimum ADFA A for Ln
in the proof of Theorem 5. Hence an order on Σ induces a reduced SDD that has
asymptotically |Σ| times more nodes than the one induced by another order on Σ.
Corollary 6. For an order π on Σ and a finite language L over Σ, let Bπ (L) =hhΣ, πi, V π , τ π , S, 0, 1i be the reduced SDD for L that respects the order π over Σ.
For any order π, ρ on Σ, we have |VNπ | ≤ |Σ||VNρ |.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

155

Proof. Let δ be the transition set of the minimum automaton for L. By Theorem 3,|VNπ | ≤ |δ|. By Theorem 5, |δ| ≤ |Σ||VNρ |. Hence |VNπ | ≤ |Σ||VNρ |.
⊓⊔Through the conversion techniques presented above between ADFAs and SDDs
and/or by Theorems 3 and 5, most known results on the size of minimum ADFAs
can be translated into those on SDDs. A special case is where the set of all factors ofa string is in concern. Let
Fact(w) = { y ∈ Σ ∗ | w = xyz for some x, z ∈ Σ ∗ }.
The literature has intensively studied the factor automata for the set Fact(w).
Theorem 7 (Blumer et al. [2], Crochemore [4]). For w ∈ Σ ∗ , let Γ and δ
be the state set and the transition set of the minimum ADFA for Fact(w). Then|Γ | ≤ 2|w| − 2 and |δ| ≤ 3|w| − 4.
Corollary 8. For w ∈ Σ ∗ , let V be the node set of the reduced SDD for Fact(w).
Then |w| ≤ |VN | ≤ 3|w| − 4.
Proof. By Theorem 7 and Theorem 5.

⊓⊔

For w = cbn a with a ≺ b ≺ c, we have |VN | = 3|w| − 4.
Corollary 9. For w ∈ Σ ∗ and order π on Σ, let V π be the node set of the reduced
SDD for Fact(w). Then |VNπ | ≤ |VNρ | + |w| − 1. Moreover, there are w, π and ρ forwhich the equality holds.
Proof. Let δ be the transition set of the minimum automaton for Fact(w). We have
|VNπ | ≤ |δ| and |Γ | ≤ |VNρ | + 1 by Theorems 3 and 5, respectively. Blumer et al. [2,Lemma 1.6] show that |δ| ≤ |Γ | + |w| − 2. Hence|VNπ | ≤ |δ| ≤ |Γ | + |w| − 2 ≤ |VNρ | + |w| − 1.
In fact for w = an b, π = hb ≺ ai, ρ = ha ≺ bi, we have |VNπ | = 2n−1 and |VNρ | = n−1.
⊓⊔

4Input- and Output-Sensitive Time-bounds for Binary
Synthesis Operations

In this section, we consider time complexity of set operations on SDDs. In particular,
given a binary set operation ⋄ ∈ {∪, ∩, \, . . .}, we consider the synthesis problem thatreceives two reduced SDDs P, Q and computes R = P ⋄ Q, where P ⋄ Q denotes the
reduced SDD such that L(P ⋄ Q) = L(P ) ⋄ L(Q). Bryant [3] presented in his seminal
paper on BDDs, a recursive synthesis algorithm for all Boolean operations. Loekito etal. [12] gave its string-counterpart for union ∪ and difference \. Below, we generalize
the algorithm in [12] for a family of set operations, called melding, in the style of
Knuth [11].

156

Proceedings of the Prague Stringology Conference 2011✬
Global variable: uniqtable, cache: hash tables for triples and operations.

✩

Algorithm Meld⋄ (P, Q: SDDs):
Output: The reduced SDD for the melding P ⋄ Q given F⋄ : {0, 1}2 → {0, 1};
1: if (P = 0 or Q = 0 or P = Q)
2:
if (F⋄ [sign(P ), sign(Q)] = 0) return 0; /* See text for F⋄ . */3:else if P 6= 0 return P ;4:else if Q 6= 0 return Q;
5: else if ((R ← cache[“Meld ⋄ (P, Q)”]) exists) return R;
6: else7:x ← P.lab; y ← Q.lab;
8:
if (x ≺Σ y) R ← Getnode(x, Meld⋄ (P.0, Q), Meld⋄ (P.1, 0));9:else if (x ≻Σ y) R ← Getnode(y, Meld⋄ (P, Q.0), Meld⋄ (0, Q.1));
10:else if (x = y) R ← Getnode(x, Meld⋄ (P.0, Q.0), Meld⋄ (P.1, Q.1));
11:
cache[“Meld ⋄ (P, Q)”] ← R;
12:
return R;
For convenience, we assume 1.lab to be a symbol larger than any symbols in Σ.
✫✪

Figure 3. An algorithm Meld⋄ for built-in binary set operations ⋄ ∈ {∪, ∩, \, ⊕, . . .}.

4.1

The Family of Melding Operations

We give a family of binary set operations ⋄ called melding below. A terminal operationtable is a binary Boolean function F : {0, 1}2 → {0, 1} such that F [0, 0] = 0. Clearly,
there are exactly eight such tables. Let O = {∪, ∩, \, /, ⊕, ∅, LHS, RHS} be a set∗∗∗of names of set operations ⋄ : 2Σ × 2Σ → 2Σ on subsets Σ ∗ . We define F⋄ by:F∪ [x, y] = x ∨ y, F∩ [x, y] = x ∧ y, F\ [x, y] = x ∧ ¬y, F/ [x, y] = ¬x ∧ y, F⊕ [x, y] = x ⊕ y(exclusive-or), F∅ [x, y] = 0, FLHS [x, y] = x, FRHS [x, y] = y, where x, y ∈ {0, 1}. For
any SDD P , we define sign(P ) to be 0 if P = 0 and 1 otherwise.
In Fig. 3, we give the algorithm Meld⋄ that computes the reduced SDD R = P ⋄ Q
for two SDDs P and Q given a terminal operation table F⋄ . Clearly, the trivial
operations ∅, LHS and RHS can be computed in constant time without Meld⋄ . Yet
those are also uniformly described as Meld⋄ . A specified terminal operation table F⋄
uniquely determines melding operation P ⋄ Q. In what follows, we assume that the
inputs P and Q and the output R are built by using the same hash table uniqtable,
where uniqtable is initialized with the empty relation before constructing P and Q.
Moreover, our algorithm uses a hash table cache : op × dom2 → dom that stores
invocation patterns of operations for avoiding redundant computation, where op is
the set of operation names. By a similar discussion in Knuth [11], we establish thefollowing theorem. Meld⋄ directly computes the output without producing redundantnodes.
Theorem 10 (correctness). Let ⋄ ∈ O be any of the eight operations. Given F⋄ ,the algorithm Meld⋄ in Fig. 3 correctly computes the reduced SDD for R = P ⋄ Q
exactly eight string set operations P ⋄ Q, where the set operation P ⋄ Q is defined asfollows:
the union P ∪ Q, the intersection P ∩ Q,
the difference P \Q, the inverse difference P/Q = Q\P ,the symmetric difference P ⊕ Q = (P \Q) ∪ (Q\P ), the empty set ∅,the left hand side LHS(P, Q) = P . the right hand side RHS(P, Q) = Q.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

4.2

157

Input-Sensitive Complexity of Binary Synthesis

First, we start with input-sensitive analysis of the time complexity for the melding
procedure. We prepare some necessary notations. Consider the algorithm Meld⋄ ofFig. 3. Let us denote by Meld0⋄ and Meld1⋄ the first and second parts of the algorithm,
that is, the top level if-clause and else-clause consisting of Lines 1 to 5 and Lines 6
to 12, respectively. For a procedure α, #α(P, Q) denotes the number of times that α
is executed during the computation of Meld⋄ (P, Q). We assume that |0| = |1| = 1 forconvenience.
Theorem 11 (input complexity of melding). Let ⋄ be any melding operation.
For reduced SDDs P and Q, the algorithm Meld⋄ of Fig. 3 computes R = P ⋄ Q in
O(|P | · |Q|) time and space.
Proof. Consider the computation of Meld⋄ (P, Q). Since the arguments P ′ and Q′ of
any subroutine call Meld⋄ (P ′ , Q′ ), resp., are subgraphs of P and Q, the number ofdistinct calls for Meld⋄ (P, Q) is at most |P | · |Q| (Claim 1 ). It also follows thatcache has O(|P | · |Q|) entries. Since the table-lookup with cache at Line 5 eliminates
duplicated calls, the Meld1⋄ can be executed at most once for each (P ′ , Q′ ), and thus, wehave #Meld1⋄ ≤ |P |·|Q| (Claim 2 ). We observe that Meld⋄ is called either (i) at the toplevel or (ii) within Meld1⋄ . Since exactly one of Line 8, 9, and 10 is executed in Meld1⋄ ,which contains at most two calls for Meld⋄ , we have #Meld⋄ ≤ 2·#Meld1⋄ +1 (Claim 3 ).
Combining Claims 2 and 3, we have that #Meld⋄ ≤ 2 · |P | · |Q| + 1 = O(|P | · |Q|). If
each call of Meld⋄ takes O(1) time, then the time complexity is O(|P | · |Q|). On theother hand, each Meld⋄ (P ′ , Q′ ) makes exactly one call for Getnode by adding a newnode. Thus, the algorithm adds at most |R| ≤ #Getnode ≤ #Meld⋄ = O(|P | · |Q|)
nodes. Since the number of cache-entries is O(|P | · |Q|) and the function stack has
depth no more than #Meld⋄ , the space complexity is O(|P | · |Q|).
⊓⊔
From the proof of the above theorem, we have the following corollary.
Corollary 12 For any melding operation ⋄ ∈ O, the reduced output size |R| isbounded from above by O(|P | · |Q|).
4.3

Pseudo Output Sensitive Complexity of Binary Synthesis

Next, we present output-sensitive analysis of the time complexity of the melding inthe style of Wegener [21], which analyzed the time complexity of Boolean operations
for BDDs based on the size of non-reduced BDDs. We define R∗ = P ⋄∗ Q to be the(possibly non-reduced) SDD computed by Meld⋄ equipped with the modification of
Getnode in Fig. 3 by removing Line 1 and 2 for node-sharing and zero-suppress rules.
Clearly, the non-reduced output size |R∗ | is bounded from above by O(|P | · |Q|).
Theorem 13 (output-sensitive complexity w.r.t. non-reduced output). The
reduced SDD for R = P ⋄∗ Q can be computed in O(|R∗ |) time and space by thealgorithm Meld⋄ in Fig. 3, where R∗ is the non-reduced SDD for P ⋄∗ Q.
Proof. Consider the computation of Meld⋄ of Fig. 3 equipped with Getnode∗ . Since
each call of Getnode∗ increases the output size by at least one, we have #Getnode∗ ≤|R∗ | (Claim 4 ). Since exactly one of Line 8, 9, and 10 is executed in Meld1⋄ and it
contains at least one call for Getnode, we have #Meld1⋄ ≤ #Getnode∗ (Claim 5 ). From

158

Proceedings of the Prague Stringology Conference 2011

the proof for Theorem 11, we have #Meld⋄ ≤ 2 · #Meld1⋄ + 1 (Claim 3 ). Combining
Claims 3, 4, and 5 above, we now have #Meld⋄ ≤ 2·#Meld1⋄ + 1 ≤ 2·#Getnode∗ + 1 ≤2·|R∗ | + 1 = O(|R∗ |)., and thus, we have the time complexity O(|R∗ |). Since uniqtable
and cache contain at most #Getnode∗ and #Meld⋄ entries, resp., the space complexity
follows from a similar argument to the proof for Theorem 11.
⊓⊔
4.4

A Lower Bound for the Time Complexity of Binary Synthesis

In the BDD community, there has been a strong belief that the quadratic inputsensitive complexities of the binary synthesis procedures for a number of variants of
BDDs, including the BDDs and ZDDs, is output-linear time for most input instances,and there has been no super-linear lower bound for its time complexity. Recently,
Yoshinaka et al. [22] show that this conjecture is not true for BDDs and ZDDs; They
constructed an infinite sequence of input BDDs that demonstrated the quadratic
lower bound for the time complexity of the melding for BDDs and ZDDs. Based on
their discussion, below we show that the above quadratic input-sensitive complexityof the melding in terms of input size is optimal for SDDs in reality.
Theorem 14. Let ⋄ be any melding operations. The algorithm Meld⋄ of Fig. 3 requires Ω(|P | · |Q|) time and space regardless of the output size, where P and Q are
the input SDDs.
Proof. Our example that the binary synthesis takes O(|P | · |Q|) time to compute
R = P ⋄ Q where |R| is linear in |P | + |Q| is just a straightforward translation of theone from [22]. The theorem can be shown in a way similar to [22]. Here we give arough sketch of the proof. Let Σ = {0, 1}. For a fixed positive integer n, we define
S = { x1 y1 · · · xn yn z1 · · · zm ∈ {0, 1}2n+m | xβ(z1 ···zm ) = 1 },T = { x1 y1 · · · xn yn z1 · · · zm ∈ {0, 1}2n+m | yβ(z1 ···zm ) = 1 },where m = ⌈log n⌉ andβ(z1 · · · zm ) =

(

1+
1

Pm

k=1 2

k−1

zk

Pm k−1zk < n;if
k=1 2
otherwise.

We haveS ⋄ T = { x1 y1 · · · xn yn z1 · · · zm ∈ {0, 1}2n+m | F⋄ [xβ(z1 ···zm ) , yβ(z1 ···zm ) ] = 1 }.
Let P and Q be the reduced SDD for S and T , resp.
We first show that |P |, |Q|, |R| = O(2n ). It is easy to see that every node in P
and Q represents a set of strings of a fixed length, since all strings in S and T havethe same length 2n + m. We define the level of a node to be 2n + m − k if the node
represents a set of strings of length k. Since the membership of x1 y1 · · · xn yn z1 · · · zm
to S does not depend on any of yi , it is not hard to see that there are at most O(2k )nodes of level 2k for 0 ≤ k < n. The number of nodes of level 2k + 1 is at most twicek
as big as that of level 2k. On the other hand, since there are at most 22 distinctksets of strings of length k, there are at most |Σ| · 22 nodes of level 2n + m − k
for 0 ≤ k ≤ m = ⌈log n⌉. All in all, |P | = O(2n ). Similarly |Q| = O(2n ). It iseasy to see that for any xi , yi , x′i , yi′ ∈ {0, 1} such that F⋄ [xi , yi ] = F⋄ [x′i , yi′ ], we have

159

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams
Data
BibleAll
BibleBi
Ecoli

Size (byte)#line#unique line Ave. line len (byte)
4,047,392
30,38330,129133.2
7,793,268
767,854
154,479
10.1
4,638,690
1
1
4,638,690.0
Table 1. Outline of data sets

|Σ |
62
27
4

Size (Kilo node)
Time (sec)Data
1
2
SDD input
H
H
∪
∩
＼
／
∪
∩
＼
／
BibleAll(Fac) 3099 3082 6110 417 3415 3388 0.67 0.44 0.59 0.58
BibleBi101 115 1673682
97 0.06 0.00 0.00 0.00
Ecoli(Fac) 4973 4970 9938 654 6346 6347 1.63 1.09 1.42 1.41
Table 2. Output size and running time of algorithms for binary synthesis

Size ratio

SDD size / DFA size

1.0

0.9

0.8

BibleAll
BibleAll (Fac)
Ecoli (Fac)

0.7

0.6
0

1,000,000

BibleBi
BibleBi (Fac)
2,000,000

Input size (byte)

Figure 4. Ratio between the sizes SDDs and DFAs in binary format

w1 xi yi w2 ∈ S ⋄ T iff w1 x′i yi′ w2 ∈ S ⋄ T for any w1 ∈ {0, 1}2k , w2 ∈ {0, 1}2n+m−k−2
with k < n. Hence we have |R| = O(2n ) by a discussion similar to the one for|P |, |Q| = O(2n ).
Second we show that #Meld⋄ ≥ 22n . For w ∈ {0, 1}2n , let Pw denote the node of P
such that L(Pw ) = { w′ | ww′ ∈ S }. In fact P has such a node for each w. Similarly
we let Qw be such that L(Qw ) = { w′ | ww′ ∈ T }. By definition, the algorithm calls
Meld⋄ (Pw , Qw ) for each w. Moreover, Px1 ···yn 6= Px′1 ···yn′ whenever xi 6= x′i for some i and
Qx1 ···yn 6= Qx′1 ···yn′ whenever yi 6= yi′ for some i. Therefore, for distinct w, w′ ∈ {0, 1}2n ,the pairs hPw , Qw i and hPw′ , Qw′ i are distinct. This means that #Meld⋄ ≥ 22n .
⊓⊔5Experiments

This section presents our experimental results on SDDs. Our first experiment hasconstructed SDDs and DFAs for the same sets of strings of real data and compared
their sizes. Secondly we have implemented the binary synthesis algorithm Meld⋄ andcomputed different binary operations on sets over SDDs.
Setting. The data sets used in our experiments are summarized in Table 1.
BibleAll and BibleBi are sets of all sentences and all word bi-grams drawn from an
English text bible.txt and Ecoli is a single DNA string in ecoli.txt in Canterbury
corpus3 . We implemented our shared and reduced SDD environment on the top of3

http://corpus.canterbury.ac.nz/resources/

160

Proceedings of the Prague Stringology Conference 2011

the SAPPORO BDD package [17] for BDDs and ZDDs written in C and C++, where
each node is encoded in a 32-bit integer and a node triple occupies approximately 30
bytes in average including hash entries in uniqtable. We also used another implementation of SDD environment in functional language Erlang. Experiments were run on
a PC (Intel Core i7, 2.67 GHz, 3.25 GB memory, Windows XP SP3). About 1.5 GBof memory was allocated to the SDD environment in maximum.
Exp 1: Comparison of the size of indexes. Figure 4 shows the sizes of SDDs
and DFAs for different sets of strings, where BibleAll (Fac), BibleBi (Fac) and Ecoli(Fac) mean the sets of all factors of sequences in the respective input files. We seethat a minimal SDD is 0 to 23 percent more succinct than the equivalent minimal
ADFA in binary format. In particular, the size ratio for factor sets is even smaller
than that for the original string data. SDDs can search strings as fast as DFAs whereedges of DFAs are represented by linked list.
Exp 2: Binary synthesis. We divided the source texts into two parts, thefirst half H1 and the second H2, and then performed Meld⋄ on those parts for ⋄ ∈{∪, ∩, \, /}. The results are presented in Table 2. It took less than seconds to computeset operations ⋄ on two SDDs with around three to four millions of nodes each. The
output size of H1 ∪ H2 is much larger than that of H1 ∩ H2, but the running time is
not different that much.
Overall, we conclude that the shared and reduced SDD environment with theabove algorithms is a practical choice for storing and manipulating string sets inlarge-scale string applications.

6

Conclusion

In this paper, we consider the class of sequence binary decision diagrams (SDDs)
proposed by Loekito et al. [12], and studied two fundamental problems on sequencebinary decision diagrams: the relationship to acyclic automata and the complexitiesof the binary synthesis operation. In Sec. 4, we showed the quadratic time complexityof the Meld⋄ algorithm. In [7], it is shown that the Meld⋄ runs in input linear time if
one of the argument is the minimal SDD of linear shape corresponding to a string.
Therefore, it would be an interesting future problem to study special cases that Meld⋄
has input linear time complexity. It would be another problem to apply SDDs forstudying the dynamic versions of sequence analysis problems such as the maximal
repeat problem and the consistent string problem [9].
Acknowledgements
The authors are grateful to anonymous referees for many useful comments and suggestions that improve the quality of this paper. They would like to thank Takashi
Horiyama, Takeru Inoue, Jun Kawahara, Takuya Kida, Toshiki Saitoh, Yasuyuki Shirai, Kana Shimizu, Yasuo Tabei, Koji Tsuda, Takeaki Uno, and Thomas Zeugmann
for their discussions and valuable comments. This research was partly supported by
MEXT Grant-in-Aid for Scientific Research (A), 20240014, FY2008–2011, MEXT/JSPS Global COE Program, FY2007–2011, and ERATO MINATO Discrete Structure
Manipulation System Project, JST.

Shuhei Denzumi et al.: Notes on Sequence Binary Decision Diagrams

161

References
1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman: The Design and Analysis of Computer
Algorithms. Addison-Wesley, 1974.
2. A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. I. Seiferas:
The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci., 40, 31–55, 1985.
3. R. E. Bryant: Graph-based algorithms for boolean function manipulation. IEEE. Trans. Comput., C-35(8), 677–691, 1986.
4. M. Crochemore: Transducers and repetitions. Theor. Comput. Sci., 45(1), 63–86, 1986.
5. M. Crochemore, C. Hancart, and T. Lecroq: Algorithms on Strings. Cambridge, 2007.
6. J. Daciuk, S. Mihov, B. W. Watson, R. E. Watson: Incremental construction of minimal
acyclic finite-state automata. Computational Linguistics, 26(1), 2000.
7. S. Denzumi, R. Yoshinaka, S. Minato, and H. Arimura: Efficient algorithms on sequencebinary decision diagrams for manipulating sets of strings. Technical Report, DCS, Hokkaido U.,
TCS-TR-A-11-53, April 2011. (submitting)
8. R. Giegerich, S. Kurtz, and J. Stoye: Efficient implementation of lazy suffix trees. Software Practice and Experience, 33, 1035–1049, 2003.
9. D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
10. J. E. Hopcroft, R. Motwani, and J. D. Ullman: Introduction to Formal Language Theory,
2nd edition. Addison-Wesley, 2001.
11. D. E. Knuth: The Art of Computer Programming, vo.4, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley, 2009.
12. E. Loekito, J. Bailey, and J. Pei: A Binary decision diagram based approach for mining
frequent subsequences. Knowl. Inf. Syst., 24(2), 235-268, 2009.
13. C. L. Lucchesi, and T. Kowaltowski: Applications of finite automata representing large
vocabularies. Software Practice and Experience, 23(1), 15–30, 1993.
14. U. Manber and E. W. Myers: Suffix arrays: a new method for on-line string searches. SIAM
J. Comput., 22(5), 935–948, 1993.
15. E. M. McCreight: A space-economical suffix tree construction algorithm. J. ACM, 23, 262–
272, 1976.
16. S. Minato: Zero-suppressed BDDs and their applications. International Journal on Software
Tools for Technology Transfer, 3(2), 156-170, Springer, 2001.
17. S. Minato: SAPPORO BDD package. DCS, Hokkaido University, unreleased, 2011.
18. M. Mohri: On some applications of finite-state automata theory to natural language processing.
Natural Language Engineering, 2(1), 61–80, 1996.
19. M. Mohri, P. Moreno, and E. Weinstein: Factor automata of automata and applications.
Proc. CIAA 2007, 168-179, 2007.
20. D. Perrin: Finite Automata. Handbook of Theoretical Computer Science, Volume B: Formal
Models and Semantics, J. van Leeuwen (Eds.), Elsevier and MIT Press, 1–57, 1990.
21. I. Wegener: Branching Programs and Binary Decision Diagrams: Theory and Applications.
SIAM, 2000.
22. R. Yoshinaka J. Kawahara, S. Denzumi, H. Arimura, and S. Minato: Counter examples
to the long-standing conjecture on the complexity of BDD binary operations. Technical Report,
DCS, Hokkaido U., TCS-TR-A-11-52, April 2011. (submitting to international journal)