TY - GEN

T1 - Notes on sequence binary decision diagrams

T2 - Prague Stringology Conference 2011, PSC 2011

AU - Denzumi, Shuhei

AU - Yoshinaka, Ryo

AU - Arimura, Hiroki

AU - Minato, Shin ichi

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84861213080&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861213080&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84861213080

SN - 9788001048702

T3 - Proceedings of the Prague Stringology Conference 2011

SP - 147

EP - 161

BT - Proceedings of the Prague Stringology Conference 2011

Y2 - 29 August 2011 through 31 August 2011

ER -