Geodesic
On the minimization of Boolean functions for~additive complexity measures
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 115-140

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of minimizing Boolean functions for additive complexity measures in a geometric interpretation, as covering a subset of vertices in the unit cube by faces, is a special type of a combinatorial statement of the weighted problem of a minimal covering of a set. Its specificity is determined by the family of covering subsets, the faces of the unit cube, that are contained in the set of the unit vertices of the function, as well as by the complexity measure of the faces, which determines the weight of the faces when calculating the complexity of the covering. To measure the complexity, we need nonnegativity, monotonicity in the inclusion of faces, and equality for isomorphic faces. For additive complexity measures, we introduce a classification in accordance with the order of the growth of the complexity of the faces depending on the dimension of the cube and study the characteristics of the complexity of the minimization of almost all Boolean functions. Bibliogr. 11.
Keywords: face of a Boolean cube, face complex, Boolean function, complexity measure, minimal face complex. 
@article{DA_2019_26_3_a5,
     author = {I. P. Chukhrov},
     title = {On the minimization of {Boolean} functions for~additive complexity measures},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {115--140},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_3_a5/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On the minimization of Boolean functions for~additive complexity measures
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 115
EP  - 140
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_3_a5/
LA  - ru
ID  - DA_2019_26_3_a5
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On the minimization of Boolean functions for~additive complexity measures
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 115-140
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_3_a5/
%G ru
%F DA_2019_26_3_a5
I. P. Chukhrov. On the minimization of Boolean functions for~additive complexity measures. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 115-140. http://geodesic.mathdoc.fr/item/DA_2019_26_3_a5/