Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard

DOI10.1007/11809678_51MaRDI QIDQ3591326zbMATH OpenOpenAlexFDO

Authors Jesper Kristensen, Peter Bro Miltersen

Publication date 10 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11809678_51

Mathematics Subject Classification ID

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

Recommendations

• On the hardness of approximating the minimum consistent OBDD problem
• On testing computability by small width OBDDs
• Lower Bounds for Testing Computability by Small Width OBDDs
• Extension of the hierarchy for k-OBDDs of small width
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• scientific article; zbMATH DE number 1670823
• On the size of (generalized) OBDDs for threshold functions
• The nonapproximability of OBDD minimization
• On approximation by \(^{\oplus}\)-OBDDs
• Mathematical Foundations of Computer Science 2004

This page was built for publication: Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard

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