On the size of binary decision diagrams representing Boolean functions
From MaRDI portal
Recommendations
- Publication:4525752
- Size of ordered binary decision diagrams representing threshold functions
- Publication:4520480
- 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
- Publication:4246551
- Decomposition of systems of Boolean functions determined by binary decision diagrams
- Publication:4412138
- On the complexity of Boolean functions with small number of ones
Cites work
- scientific article; zbMATH DE number 3890736 (Why is no real title available?)
- scientific article; zbMATH DE number 3913677 (Why is no real title available?)
- scientific article; zbMATH DE number 3919835 (Why is no real title available?)
- scientific article; zbMATH DE number 3937107 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 4094813 (Why is no real title available?)
- scientific article; zbMATH DE number 18624 (Why is no real title available?)
- scientific article; zbMATH DE number 3594626 (Why is no real title available?)
- scientific article; zbMATH DE number 3607492 (Why is no real title available?)
- scientific article; zbMATH DE number 3353170 (Why is no real title available?)
- A lower bound for read-once-only branching programs
- Binary Decision Diagrams
- Binary decision tree test functions
- Bounds for Width Two Branching Programs
- Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
- Finding the optimal variable ordering for binary decision diagrams
- Functional test generation using binary decision diagrams
- Graph-Based Algorithms for Boolean Function Manipulation
- Lower bounds for depth-restricted branching programs
- On the complexity of branching programs and decision trees for clique functions
- Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
- Polynomial size \(\Omega\)-branching programs and their computational power
- Some bounds on the complexity of predicate recognition by finite automata
- Time-space trade-offs for branching programs
Cited in
(48)- Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
- scientific article; zbMATH DE number 1421023 (Why is no real title available?)
- Symbolic topological sorting with OBDDs
- On the relative succinctness of sentential decision diagrams
- An iterative approach for counting reduced ordered binary decision diagrams
- High accuracy asymptotic bounds on the BDD size and weight of the hardest functions
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
- On the descriptive and algorithmic power of parity ordered binary decision diagrams
- scientific article; zbMATH DE number 1555979 (Why is no real title available?)
- Representation of graphs by OBDDs
- Size of OBDD representation of 2-level redundancies functions
- The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions
- A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams
- Decomposable structures, Boolean function representations, and optimization
- On the OBDD size for graphs of bounded tree- and clique-width
- scientific article; zbMATH DE number 1929956 (Why is no real title available?)
- The size-cost of Boolean operations on constant height deterministic pushdown automata
- Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
- Realization of Boolean functions by BDDs embeded into a unit cube
- Infinitary relations and their representation.
- Bounds on the OBDD-size of integer multiplication via universal hashing
- Real numbers and BDDs
- On the relation between BDDs and FDDs
- Efficient data structures for Boolean functions
- Graph driven BDDs -- a new data structure for Boolean functions
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- An improved hierarchy result for partitioned BDDs
- Minimization of free BDDs
- Lower bounds on the OBDD size of two fundamental functions' graphs
- On the OBDD representation of some graph classes
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- On the evolution of the worst-case OBDD size
- Lower bounds for linearly transformed OBDDs and FBDDs
- Free binary decision diagrams for the computation of \(\text{EAR}_{ n }\)
- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
- On the Width of Ordered Binary Decision Diagrams
- On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
- On a class of decision diagrams
- On the computational power of binary decision diagram with redundant variables.
- On the structure of counterexamples to symmetric orderings for BDD's
- On the computational power of Boolean decision lists
- On efficient implicit OBDD-based algorithms for maximal matchings
- scientific article; zbMATH DE number 1948534 (Why is no real title available?)
- scientific article; zbMATH DE number 1543030 (Why is no real title available?)
- Ordered binary decision diagrams and the Shannon effect
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
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)
