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

DOI10.1016/J.DAM.2014.11.022zbMATH Open1350.68066OpenAlexW1973311914MaRDI QIDQ313770FDOQ313770

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

Recommendations

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

zbMATH Keywords

minimizationBoolean set operationdeterministic finite automatonpersistent data structuresequence binary decision diagram

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph-Based Algorithms for Boolean Function Manipulation
• Algorithms on Strings, Trees and Sequences
• Branching Programs and Binary Decision Diagrams
• 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: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• Jewels of Stringology
• Suffix Arrays: A New Method for On-Line String Searches
• A Space-Economical Suffix Tree Construction Algorithm
• Making data structures persistent
• The smallest automaton recognizing the subwords of a text
• Title not available (Why is that?)
• Algorithms on Strings
• Zero-suppressed BDDs and their applications
• Transducers and repetitions
• Optimal bounds for the predecessor problem and related problems
• Factor Automata of Automata and Applications
• Title not available (Why is that?)
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Simple Confluently Persistent Catenable Lists
• Title not available (Why is that?)

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

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)