RUS  ENG
Full version
JOURNALS // Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki // Archive

Zh. Vychisl. Mat. Mat. Fiz., 2005 Volume 45, Number 5, Pages 935–940 (Mi zvmmf660)

This article is cited in 7 papers

On the number of irreducible coverings of an integer matrix

E. V. Dyukova

Dorodnicyn Computing Center Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119991, Russia

Abstract: The metric (quantitative) properties of the set of coverings of an integer matrix are examined. an asymptotic estimate for the logarithm of the typical number of irredundant $\sigma$-coverings is obtained in the case when the number of rows in the matrix is not smaller than the number of its columns. as a consequence, a similar estimate is derived for the number of maximal conjunctions of a boolean function of $n$ variables with the number of zeros no less than $n$.

Key words: discrete recognition procedures, irredundant covering of an integer matrix, metric properties of a set of coverings, metric properties of disjunctive normal forms.

UDC: 519.6:519.712.63

Received: 26.11.2004


 English version:
Computational Mathematics and Mathematical Physics, 2005, 45:5, 903–908

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025