TY - JOUR

T1 - Sequence binary decision diagram

T2 - Minimization, relationship to acyclic automata, and complexities of Boolean set operations

AU - Denzumi, Shuhei

AU - Yoshinaka, Ryo

AU - Arimura, Hiroki

AU - Minato, Shin ichi

N1 - Funding Information:
The authors are grateful to anonymous reviewers of this paper and anonymous referees of PSC’11 of the earlier version of this paper for many useful comments and suggestions, which have improved 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 .
Publisher Copyright:
© 2014 Elsevier B.V.

PY - 2016/10/30

Y1 - 2016/10/30

N2 - The manipulation of large sequence data is one of the most important problems in string processing. In this paper, we discuss a new data structure for storing and manipulating sets of strings, called Sequence Binary Decision Diagrams (sequence BDDs), which has recently been introduced by Loekito et al. (2010) as a descendant of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). Sequence BDDs can compactly represent sets of sequences similarly to minimal ADFAs, and allow efficient set operations inherited from BDDs. We study fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs by reduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal ADFAs, the complexities of minimization, Boolean set operations, and sequence BDD construction. We also show experimental results for real and artificial data sets.

AB - The manipulation of large sequence data is one of the most important problems in string processing. In this paper, we discuss a new data structure for storing and manipulating sets of strings, called Sequence Binary Decision Diagrams (sequence BDDs), which has recently been introduced by Loekito et al. (2010) as a descendant of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). Sequence BDDs can compactly represent sets of sequences similarly to minimal ADFAs, and allow efficient set operations inherited from BDDs. We study fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs by reduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal ADFAs, the complexities of minimization, Boolean set operations, and sequence BDD construction. We also show experimental results for real and artificial data sets.

KW - Boolean set operation

KW - Deterministic finite automaton

KW - Minimization

KW - Persistent data structure

KW - Sequence binary decision diagram

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

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

U2 - 10.1016/j.dam.2014.11.022

DO - 10.1016/j.dam.2014.11.022

M3 - Article

AN - SCOPUS:84919346253

SN - 0166-218X

VL - 212

SP - 61

EP - 80

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -