Article collection "Mathematical Problems of Cybernetics" №17, Moscow, 2008

Authors:Dyukova E.V., Inyakin A.S.

On asymptotically optimal constructing irreducible integer matrix coverings

Abstract:

In this paper we construct an asymptotically optimal algorithm for enumerating irreducible integer matrix coverings. The algorithm has a polynomial delay at each step and the number of the algorithm steps is almost always asymptotically equal to the number of irreducible coverings. This algorithm is a modification of our asymptotically optimal algorithm (algorithm OPT) that was suggested earlier for enumerating special irreducible Boolean matrix coverings . The experimental estimations of the statistical efficiency of both OPT algorithm and several other algorithms for solving the same problem (including asymptotically optimal algorithms) are obtained. Similar results were obtained for the problem of enumerating maximal conjunctions of two-valued logic function.

Keywords:

logical recognition procedure, the complexity of enumeration problems, irreducible integer matrix covering, irreducible Boolean matrix covering, the maximum conjunction, algorithm with polynomial delay, the conversion of normal forms of logic function