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

DOI10.1016/j.dam.2014.11.022zbMath1350.68066OpenAlexW1973311914MaRDI QIDQ313770

Hiroki Arimura, Shin-ichi Minato, Shuhei Denzumi, Ryo Yoshinaka

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

minimizationdeterministic finite automatonBoolean set operationpersistent data structuresequence binary decision diagram

Mathematics Subject Classification ID

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

Related Items

A finite state intersection approach to propositional satisfiability, DenseZDD: a compact and fast index for families of sets

Uses Software

• SAPPORO BDD

Cites Work

• The smallest automaton recognizing the subwords of a text
• Making data structures persistent
• Zero-suppressed BDDs and their applications
• Transducers and repetitions
• Optimal bounds for the predecessor problem and related problems
• Suffix Arrays: A New Method for On-Line String Searches
• Factor Automata of Automata and Applications
• Graph-Based Algorithms for Boolean Function Manipulation
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Jewels of Stringology
• Branching Programs and Binary Decision Diagrams
• Simple Confluently Persistent Catenable Lists
• Algorithms on Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item