AN O(NM)-TIME ALGORITHM FOR COMPUTING THE DUAL OF A REGULAR BOOLEAN FUNCTION

We consider the problem of dualizing a positive Boolean function f : B(n) --> B given in irredundant disjunctive normal form (DNF), that is, obtaining the irredundant DNF form of its dual f(d)(x) = f(x)BAR. The function f is said to be regular if there is a linear order greater than or similar to on {1, ..., n} such that i greater than or similar to j, x(i) = 0, and x(j) = 1 imply f(x) less-than-or-equal-to f(x + u(i) - u(j)), where u(k) denote unit vectors. A previous algorithm of the authors, the Hop-Skip-and-Jump algorithm, dualizes a regular function in polynomial time. We use this algorithm to give an explicit expression for the irredundant DNF of f(d) in terms of the one for f. We show that if the irredundant DNF for f has m greater-than-or-equal-to 2 terms, then the one for f(d) has at most (n - 2)m + 1, and can be computed in O(nm) time. This can be applied to solve regular set-covering problems in O(nm) time.