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 ( 2 k 2 k 2 n ) time. This implies an O(n2logn) O ( n 2 log n ) algorithm for determining the self-duality of log n -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 ( n 4 ( c + 1 ) ) algorithm for determining self-duality.
dualization of monotone boolean functions hypergraph transversals