Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations

详细信息    查看全文

• 作者：Shuhei Denzumi^a ; ^{denzumi@ist.hokudai.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Ryo Yoshinaka^b ; ^{ry@i.kyoto-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Hiroki Arimura^a ; ^{arim@ist.hokudai.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Shin-ichi Minato^a ; ^c ; ^{minato@ist.hokudai.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Sequence binary decision diagram ; Persistent data structure ; Deterministic finite automaton ; Minimization ; Boolean set operation
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 October 2016
• 年：2016
• 卷：212
• 期：Complete
• 页码：61-80
• 全文大小：1374 K

文摘

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.