Dualization Problem over the Product of Chains: Asymptotic Estimates for the Number of Solutions

Abstract—A key intractable problem in logical data analysis, namely, dualization over the product of partial orders, is considered. The important special case where each order is a chain is studied. If the cardinality of each chain is equal to two, then the considered problem is to construct a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form, which is equivalent to the enumeration of irreducible coverings of a Boolean matrix. The asymptotics of the typical number of irreducible coverings is known in the case where the number of rows in the Boolean matrix has a lower order of growth than the number of columns. In this paper, a similar result is obtained for dualization over the product of chains when the cardinality of each chain is higher than two. Deriving such asymptotic estimates is a technically complicated task, and they are required, in particular, for proving the existence of asymptotically optimal algorithms for the problem of monotone dualization and its generalizations.