Self-duality of bounded monotone boolean functions and related problems

In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k   literals can be determined in O(2k2k2n)O(2k2k2n) time. This implies an O(n2logn)O(n2logn) algorithm for determining the self-duality of logn-DNF functions. We also consider the version where any two disjuncts have at most c   literals in common. For this case we give an O(n4(c+1))O(n4(c+1)) algorithm for determining self-duality.