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

DOI10.1016/J.DAM.2014.11.022MaRDI QIDQ313770zbMATH OpenOpenAlexFDO

Authors Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-Ichi Minato

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.11.022

zbMATH Keywords

minimizationBoolean set operationdeterministic finite automatonpersistent data structuresequence binary decision diagram

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05)

Recommendations

• New algorithms for manipulating sequence BDDs
• Sequence sentential decision diagrams
• String-matching with OBDDs
• BDDs -- design, analysis, complexity, and applications.
• Binary decision diagrams

Cites work

• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 2173815 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Branching Programs and Binary Decision Diagrams
• Factor Automata of Automata and Applications
• Graph-Based Algorithms for Boolean Function Manipulation
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Jewels of Stringology
• Making data structures persistent
• Optimal bounds for the predecessor problem and related problems
• Simple Confluently Persistent Catenable Lists
• Suffix Arrays: A New Method for On-Line String Searches
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
• The smallest automaton recognizing the subwords of a text
• Transducers and repetitions
• Zero-suppressed BDDs and their applications

Cited in

(4)

• Sequence sentential decision diagrams
• DenseZDD: a compact and fast index for families of sets
• A finite state intersection approach to propositional satisfiability
• New algorithms for manipulating sequence BDDs

Describes a project that uses

Uses Software

• SAPPORO BDD

This page was built for publication: Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313770)