Geodesic
On kernel and shortest complexes of faces in the unit cube
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 75-94 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Studying extreme kernel complexes of faces of given dimension, we obtain lower estimates of the number of shortest complexes of faces in the unit $n$-dimensional cube. It is shown that the number of shortest complex $k$-dimensional faces is of the same logarithm order as the number of complexes consisting of no more than $2^{n-1}$ different faces of dimension $k$, with $1\le k\le c\cdot n$ and $c<0.5$. This implies similar lower bounds for the maximum length of kernel and the number of shortest DNF Boolean functions. Bibliogr. 15.
Mots-clés : face, interval, kernel face
Keywords: complex of faces in $n$-dimensional unit cube, Boolean function, shortest covering. 
@article{DA_2011_18_2_a6,
     author = {I. P. Chukhrov},
     title = {On kernel and shortest complexes of faces in the unit cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {75--94},
     year = {2011},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On kernel and shortest complexes of faces in the unit cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 75
EP  - 94
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/
LA  - ru
ID  - DA_2011_18_2_a6
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On kernel and shortest complexes of faces in the unit cube
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 75-94
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/
%G ru
%F DA_2011_18_2_a6
I. P. Chukhrov. On kernel and shortest complexes of faces in the unit cube. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 75-94. http://geodesic.mathdoc.fr/item/DA_2011_18_2_a6/

[1] Andreev A. E., “Ob odnoi modifikatsii gradientnogo algoritma”, Vestn. MGU. Ser. Matematika. Mekhanika, 1985, no. 3, 29–35 | MR | Zbl

[2] Vasilev Yu. L., “K voprosu o chisle minimalnykh i tupikovykh diz'yunktivnykh normalnykh form”, Diskret. analiz, 2, In-t matematiki SO AN SSSR, Novosibirsk, 1964, 3–9 | MR

[3] Vasilev Yu. L., Glagolev V. V., “Metricheskie svoistva diz'yunktivnykh normalnykh form”, Diskret. matematika i mat. voprosy kibernetiki, v. 1, Nauka, M., 1974, 99–148

[4] Glagolev V. V., “Nekotorye otsenki d.n.f. bulevykh funktsii algebry logiki”, Problemy kibernetiki, 19, 1967, 75–94 | MR | Zbl

[5] Zhuravlev Yu. I., “Otsenka dlya chisla tupikovykh d.n.f. funktsii algebry logiki”, Sib. mat. zhurn., 3:5 (1962), 802–804 | Zbl

[6] Zhuravlev Yu. I., “Algoritmy postroeniya minimalnykh d.n.f.”, Diskret. matematika i mat. voprosy kibernetiki, v. 1, Nauka, M., 1974, 67–98

[7] Korshunov A. D., “Sravnenie slozhnosti dlinneishikh i kratchaishikh d.n.f. i nizhnyaya otsenka chisla tupikovykh d.n.f. dlya pochti vsekh bulevykh funktsii”, Kibernetika, 4, 1969, 1–11 | Zbl

[8] Korshunov A. D., “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form bulevykh funktsii”, Metody diskret. analiza v izuchenii bulevykh funktsii, 37, In-t matematiki SO AN SSSR, Novosibirsk, 1981, 9–41 | MR

[9] Kuznetsov S. E., “O nizhnei otsenke dliny kratchaishei d.n.f. pochti vsekh bulevykh funktsii”, Veroyatnost. metody i kibernetika, 19, Izd-vo Kazanskogo un-ta, Kazan, 1983, 44–47 | MR

[10] Nigmatullin R. G., “Variatsionnyi printsip v algebre logiki”, Diskret. analiz, 10, In-t matematiki SO AN SSSR, Novosibirsk, 1967, 69–89 | MR

[11] Sapozhenko A. A., Chukhrov I. P., “Minimizatsiya bulevykh funktsii v klasse diz'yunktivnykh normalnykh form”, Itogi nauki i tekhniki. Ser. Teoriya veroyatnosti. Mat. statistika. Teoret. kibernetika, 25, 1987, 68–116 | MR | Zbl

[12] Chukhrov I. P., “Otsenki chisla minimalnykh diz'yunktivnykh normalnykh form dlya poyaskovoi funktsii”, Metody diskret. analiza v issledovaniyakh funktsion. sistem, 36, In-t matematiki SO AN SSSR, Novosibirsk, 1981, 74–92 | MR

[13] Chukhrov I. P., “O chisle minimalnykh diz'yunktivnykh normalnykh form”, Dokl. AN SSSR, 276:6 (1984), 1335–1339 | MR | Zbl

[14] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vyssh. shk., M., 2003, 384 pp. | MR

[15] Pippenger N., “The shortest disjunctive normal form of a random Boolean function”, Random structures algorithms, 22:2 (2003), 161–186 | DOI | MR | Zbl