Geodesic
On the problem of minimizing a~single set of Boolean functions
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 75-97.

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

We study the set of Boolean functions that consist of a single connected component, have minimal complexes of faces which are not shortest and do not satisfy the sufficient condition for minimality based on the notion of an independent set of vertices. The independent minimization for the connected components and feasibility of sufficient conditions for the minimality can not be applied to minimizing of such functions. For this set of functions, we obtain lower bounds on the power and maximal number of complexes of faces which are minimal with respect to additive measures of linear and polynomial complexity. Ill. 1, bibliogr. 8.
Keywords: Boolean function, unit cube, complex of faces, additive complexity measure, shortest complex of faces, minimal complex of faces.
Mots-clés : face 
@article{DA_2015_22_3_a4,
     author = {I. P. Chukhrov},
     title = {On the problem of minimizing a~single set of {Boolean} functions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {75--97},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_3_a4/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On the problem of minimizing a~single set of Boolean functions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 75
EP  - 97
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_3_a4/
LA  - ru
ID  - DA_2015_22_3_a4
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On the problem of minimizing a~single set of Boolean functions
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 75-97
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_3_a4/
%G ru
%F DA_2015_22_3_a4
I. P. Chukhrov. On the problem of minimizing a~single set of Boolean functions. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 75-97. http://geodesic.mathdoc.fr/item/DA_2015_22_3_a4/

[1] Yu. L. Vasil'ev, “Massive classes of dense Boolean functions”, Methods of Discrete Analysis in Synthesis of Control Systems, 32, Inst. Mat. SO AN SSSR, Novosibirsk, 1978, 21–33 | MR

[2] Yu. L. Vasil'ev, V. V. Glagolev, “Metric properties of disjunctive normal forms”, Discrete Mathematics and Mathematical Problems of Cybernetics, v. 1, Nauka, Moscow, 1974, 99–148

[3] A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov, “The set covering problem: complexity, algorithms, and experimental study”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:2 (2000), 22–46 | MR | Zbl

[4] V. K. Leont'ev, “Discrete optimization”, Comput. Math. Math. Phys., 47:2 (2007), 328–340 | MR | Zbl

[5] I. P. Chukhrov, “On minimal complexes of faces in the unit cube”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 79–99 | MR | Zbl

[6] I. P. Chukhrov, “On complexity measures of complexes of faces in the unit cube”, J. Appl. Ind. Math., 8:1 (2014), 9–19 | DOI | MR | Zbl

[7] Coudert O., “On solving covering problems”, Proc. 33rd Design Automation Conf. (Las Vegas, NV, June 3–7, 1996), ACM, New York, 1996, 197–202

[8] Coudert O., Sasao T., “Two-level logic minimization”, Logic synthesis and verification, Springer Int. Ser. Eng. Comp. Sci., 654, Kluwer Acad. Publ., Norwell, MA, 2001, 1–27