Finding Maximal Independent Elements of Products of Partial Orders (The Case of Chains)

Abstract

We consider one of the central intractable problems of logical data analysis – finding maximal independent elements of partial orders (dualization of a product of partial orders). An important particular case is considered with each order a chain. If each chain is of cardinality 2, the problem involves the construction of a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form. An asymptotic expression is obtained for a typical number of maximal independent elements of products for a large number of finite chains. The derivation of such asymptotic bounds is a technically complex problem, but it is necessary for the proof of existence of asymptotically optimal algorithms for the monotone dualization problem and the generalization of this problem to chains of higher cardinality. An asymptotically optimal algorithm is described for the problem of dualization of a product of finite chains.