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

DOI10.1145/3274279zbMATH Open1407.68116OpenAlexW2910958598WikidataQ128553517 ScholiaQ128553517MaRDI QIDQ4617985FDOQ4617985

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

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

zbMATH Keywords

data structuresbinary decision diagramsCommon LispBoolean simplification

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

Cited In (6)

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• Tools and Algorithms for the Construction and Analysis of Systems
• On the Width of Ordered Binary Decision Diagrams
• MC/DC test cases generation based on BDDs
• The ROBDD size of simple CNF formulas
• 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)