Efficient data structures for Boolean functions

DOI10.1016/0012-365X(95)90790-RzbMath0939.68597MaRDI QIDQ1344625

Ingo Wegener

Publication date: 4 July 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30) Data structures (68P05)

Related Items

On the Influence of the State Encoding on OBDD-Representations of Finite State Machines ⋮ Randomization and nondeterminism are comparable for ordered read-once branching programs ⋮ A lower bound on branching programs reading some bits twice ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ Completeness and non-completeness results with respect to read-once projections ⋮ On the relative succinctness of sentential decision diagrams ⋮ On the influence of the variable ordering for algorithmic learning using OBDDs ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of binary decision diagrams representing Boolean functions
• Graph driven BDDs -- a new data structure for Boolean functions
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• The graph of multiplication is equivalent to counting
• Symbolic model checking: \(10^{20}\) states and beyond
• Reduction of OBDDs in linear time
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Binary decision tree test functions
• Lower bounds on the complexity of real-time branching programs
• A method for obtaining digital signatures and public-key cryptosystems
• Binary Decision Diagrams
• The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
• On the OBDD-representation of general Boolean functions
• Finding the optimal variable ordering for binary decision diagrams