Graph driven BDDs -- a new data structure for Boolean functions
From MaRDI portal
Publication:673788
DOI10.1016/0304-3975(94)00078-WzbMath0873.68036OpenAlexW1968923513MaRDI QIDQ673788
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)00078-w
Related Items
The complexity of minimizing and learning OBDDs and FBDDs, Parity OBDDs cannot be handled efficiently enough, On the Complexity of the Hidden Weighted Bit Function for Various BDD Models, Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs, Efficient data structures for Boolean functions, Knowledge compilation meets database theory: compiling queries to decision diagrams, Unnamed Item, The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions, Formal verification based on Boolean expression diagrams, BDDs -- design, analysis, complexity, and applications., Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, New lower bounds and hierarchy results for restricted branching programs, Minimization problems for parity OBDDs, Lower bounds for restricted read-once parity branching programs, Boolean expression diagrams, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs, On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Completeness and non-completeness results with respect to read-once projections, Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs, The symbolic OBDD scheme for generating mechanical assembly sequences, AND/OR search spaces for graphical models, On the relative succinctness of sentential decision diagrams, On the relation between BDDs and FDDs, A very simple function that requires exponential size read-once branching programs., On the evolution of the worst-case OBDD size, Lower bounds for linearly transformed OBDDs and FBDDs
Cites Work
- Unnamed Item
- Unnamed Item
- On the size of binary decision diagrams representing Boolean functions
- Polynomial size \(\Omega\)-branching programs and their computational power
- Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
- Reduction of OBDDs in linear time
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Graph-Based Algorithms for Boolean Function Manipulation
- Binary decision tree test functions
- Binary Decision Diagrams
