Exact OBDD Bounds for Some Fundamental Functions

DOI10.1007/978-3-540-77566-9_15zbMath1132.68347OpenAlexW1570042645MaRDI QIDQ5448645

Beate Bollig, Ingo Wegener, Niko Range

Publication date: 7 March 2008

Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_15

zbMATH Keywords

ordered binary decision diagramslower boundsComputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items

On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ On the size of (generalized) OBDDs for threshold functions

Cites Work

• Unnamed Item
• Unnamed Item
• Reduction of OBDDs in linear time
• Exact OBDD bounds for some fundamental functions
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems