On the number of maximal independent elements of partially ordered sets (the case of chains)

One of the central intractable problems of logical data analysis is considered — dualization over the product of partially ordered sets. The authors investigate an important special case where each order is a chain. If the power of each chain is two, then the problem under consideration is to construct the reduced disjunctive normal form of a monotone Boolean function given by a conjunctive normal form. This is equivalent to enumerating irreducible covers of a Boolean matrix. Provided the growth of the row's number of the Boolean matrix to be less than the growth of the column's number, the asymptotic for the typical number of irreducible covers is known. In the present work, a similar result is obtained for the dualization over the product of chains when the power of each chain is more than two. Obtaining such asymptotic estimates is a technically complex task and is necessary, in particular, to justify the existence of asymptotically optimal algorithms for the problem of monotonic dualization and various generalizations of this problem.