A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams

DOI10.1145/3274279MaRDI QIDQ4617985zbMATHOpenAlexWikidataFDO

Authors Jim Newton, Didier Verna

Publication date 7 February 2019

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3274279

zbMATH Keywords

data structuresbinary decision diagramsCommon LispBoolean simplification

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• scientific article; zbMATH DE number 1948534
• scientific article; zbMATH DE number 1150567
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• BDDs -- design, analysis, complexity, and applications.
• On the size of binary decision diagrams representing Boolean functions

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1424030 (Why is no real title available?)
• A New Look at BDDs for Pseudo-Boolean Constraints
• BDD-based Boolean functional synthesis
• Binary Decision Diagrams
• Chain reduction for binary and zero-suppressed decision diagrams
• EXACT COMPUTATION OF THE BIFURCATION POINT B₄ OF THE LOGISTIC MAP AND THE BAILEY–BROADHURST CONJECTURES
• Graph-Based Algorithms for Boolean Function Manipulation
• High accuracy asymptotic bounds on the BDD size and weight of the hardest functions
• Least upper bounds on OBDD sizes
• Mersenne twister
• On the evolution of the worst-case OBDD size
• Ordered binary decision diagrams and the Shannon effect
• Purely Functional Data Structures
• Regular expression types for XML
• The ROBDD size of simple CNF formulas
• 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.
• Theoretical insights and algorithmic tools for decision diagram-based optimization

Cited in

(7)

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• An iterative approach for counting reduced ordered binary decision diagrams
• MC/DC test cases generation based on BDDs
• The ROBDD size of simple CNF formulas
• Tools and Algorithms for the Construction and Analysis of Systems
• On the Width of Ordered Binary Decision Diagrams
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making

This page was built for publication: A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams

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