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 t han or similar to on {1, ..., n} such that i greater than or similar t o 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 express ion 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 te rms, then the one for f(d) has at most (n - 2)m + 1, and can be comput ed in O(nm) time. This can be applied to solve regular set-covering pr oblems in O(nm) time.