OBDDs of a Monotone Function and Its Prime Implicants

Coudert made a breakthrough in the two-level logic minimization problem with Ordered Binary Decision Diagrams (OBDDs for short) recently 3]. This paper discusses the relationship between the two OBDDs of a monotone function and its prime implicant set to clarify the complexity of this practically efficient method. We show that there exists a monotone function which has an O(n) size sum-of-products but cannot be represented by a polynomial size OBDD. In other words, we cannot obtain the OBDD of the prime implicant set of a monotone function in an output-size sensitive manner once we have constructed the OBDD of that function as in 3], in the worst case. A positive result is also given for a meaningful class of matroid functions. Received April 1997, and in revised form December 1997, and in final form February 1998.