一覧に戻る

タイトル
  • en Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations
作成者
アクセス権 open access
権利情報
  • en © 2014. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
  • http://creativecommons.org/licenses/by-nc-nd/4.0/
  • en Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
主題
  • Other en Sequence binary decision diagram
  • Other en Persistent data structure
  • Other en Deterministic finite automaton
  • Other en Minimization
  • Other en Boolean set operation
  • NDC 548
内容注記
  • Abstract en 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. (C) 2014 Elsevier B.V. All rights reserved.
出版者 en Elsevier
日付
    Issued2016-10-30
言語
  • eng
資源タイプ journal article
出版タイプ AM
資源識別子 HDL http://hdl.handle.net/2115/71749
関連
  • isVersionOf DOI https://doi.org/10.1016/j.dam.2014.11.022
収録誌情報
    • PISSN 0166-218X
      • en Discrete applied mathematics
      • 巻212 開始ページ61 終了ページ80
ファイル
コンテンツ更新日時 2023-07-26