On the size of binary decision diagrams representing Boolean functions
From MaRDI portal
Publication:673087
DOI10.1016/0304-3975(94)00181-HzbMATH Open0874.68283OpenAlexW2054195481MaRDI QIDQ673087FDOQ673087
Authors: Yuri Breitbart, H. B. III Hunt, Daniel J. Rosenkrantz 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00181-h
Recommendations
- scientific article; zbMATH DE number 1555979
- Size of ordered binary decision diagrams representing threshold functions
- scientific article; zbMATH DE number 1543030
- On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
- On the Width of Ordered Binary Decision Diagrams
- Minimization of binary decision diagrams for systems of incompletely defined Boolean functions
- scientific article; zbMATH DE number 1294417
- Decomposition of systems of Boolean functions determined by binary decision diagrams
- scientific article; zbMATH DE number 1948534
- On the complexity of Boolean functions with small number of ones
Cites Work
- Graph-Based Algorithms for Boolean Function Manipulation
- Title not available (Why is that?)
- A lower bound for read-once-only branching programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of branching programs and decision trees for clique functions
- Title not available (Why is that?)
- Bounds for Width Two Branching Programs
- Binary Decision Diagrams
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Time-space trade-offs for branching programs
- Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
- Functional test generation using binary decision diagrams
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Lower bounds for depth-restricted branching programs
- Some bounds on the complexity of predicate recognition by finite automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Binary decision tree test functions
- Title not available (Why is that?)
- Finding the optimal variable ordering for binary decision diagrams
- Polynomial size \(\Omega\)-branching programs and their computational power
Cited In (46)
- Infinitary relations and their representation.
- Title not available (Why is that?)
- On the relative succinctness of sentential decision diagrams
- Size of OBDD representation of 2-level redundancies functions
- On the computational power of binary decision diagram with redundant variables.
- Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
- On the evolution of the worst-case OBDD size
- Lower bounds for linearly transformed OBDDs and FBDDs
- On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
- Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
- On the relation between BDDs and FDDs
- Lower bounds on the OBDD size of two fundamental functions' graphs
- Ordered binary decision diagrams and the Shannon effect
- Real numbers and BDDs
- Efficient data structures for Boolean functions
- Realization of Boolean functions by BDDs embeded into a unit cube
- On the Width of Ordered Binary Decision Diagrams
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Graph driven BDDs -- a new data structure for Boolean functions
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams
- On the OBDD representation of some graph classes
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- On efficient implicit OBDD-based algorithms for maximal matchings
- On the descriptive and algorithmic power of parity ordered binary decision diagrams
- On a class of decision diagrams
- The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- Free binary decision diagrams for the computation of \(\text{EAR}_{ n }\)
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- High accuracy asymptotic bounds on the BDD size and weight of the hardest functions
- Bounds on the OBDD-size of integer multiplication via universal hashing
- An improved hierarchy result for partitioned BDDs
- Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- On the structure of counterexamples to symmetric orderings for BDD's
- Decomposable structures, Boolean function representations, and optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the computational power of Boolean decision lists
- Symbolic topological sorting with OBDDs
- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimization of free BDDs
This page was built for publication: On the size of binary decision diagrams representing Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673087)
