Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations
Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations
复制标题
DOI：
10.1016/j.dam.2014.11.022
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Shuhei Denzumi;Ryo Yoshinaka;Hiroki Arimura;S. Minato
中科院分区：
文献类型：
--
作者：
Shuhei Denzumi;Ryo Yoshinaka;Hiroki Arimura;S. Minato
大序列数据的操作是字符串处理中最重要的问题之一。在本文中，我们讨论了一种用于存储和操作字符串集的新数据结构，称为序列二元决策图（序列 BDD），该结构最近由 Loekito 等人引入。 (2010) 作为非循环 DFA (ADFA) 和二元决策图 (BDD) 的后代。序列 BDD 可以紧凑地表示类似于最小 ADFA 的序列集，并允许从 BDD 继承的高效集合操作。我们研究序列 BDD 的基本属性，例如通过简化序列 BDD 来表征最小序列 BDD、最小序列 BDD 和最小 ADFA 大小之间的非平凡关系、最小化的复杂性、布尔集运算和序列 BDD 构造。我们还展示了真实和人工数据集的实验结果。
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, calledSequence 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.