Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418945 | Discrete Applied Mathematics | 2008 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daya Ram Gaur, Ramesh Krishnamurti,