Exact OBDD Bounds for Some Fundamental Functions

DOI10.1007/978-3-540-77566-9_15MaRDI QIDQ5448645zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Niko Range, Ingo Wegener

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

Computational complexitylower boundsordered binary decision diagrams

Mathematics Subject Classification ID

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

Recommendations

• Exact OBDD bounds for some fundamental functions
• scientific article; zbMATH DE number 1670823
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• SOFSEM 2005: Theory and Practice of Computer Science
• Lower bounds on the OBDD size of two fundamental functions' graphs

Cites work

• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Exact OBDD bounds for some fundamental functions
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Reduction of OBDDs in linear time

Cited in

(14)

• OBDDs of a monotone function and its prime implicants
• Size of ordered binary decision diagrams representing threshold functions
• Lower bounds for linearly transformed OBDDs and FBDDs
• Exact OBDD bounds for some fundamental functions
• scientific article; zbMATH DE number 1670823 (Why is no real title available?)
• Worst case examples for operations on OBDDs
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Least upper bounds on OBDD sizes
• scientific article; zbMATH DE number 1543030 (Why is no real title available?)
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Size of OBDD representation of 2-level redundancies functions
• Lower bounds on the OBDD size of two fundamental functions' graphs
• On the size of (generalized) OBDDs for threshold functions

This page was built for publication: Exact OBDD Bounds for Some Fundamental Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448645)