Prague Stringology Conference 2011

Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura and Shin-ichi Minato

Notes on Sequence Binary Decision Diagrams: Relationship to Acyclic Automata and Complexities of Binary Set Operations

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 and duplicated 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 then analyze the complexities of algorithms for Boolean set operations, called the binary synthesis. Finally, we show experimental results to confirm the results of the theoretical analysis on real data sets.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation