Geodesic
On complexity measures for complexes of faces in the unit cube
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 77-94.

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

We study the problem of proving that the complex of faces is minimal in the unit $n$-dimensional cube. We formulate sufficient conditions which enable us to prove that a complex of faces is minimal using the ordinal properties of the complexity measure functional and structural properties of Boolean functions. It makes it possible to expand the set of complexes of faces which are proven to be minimal with respect to complexity measures satisfying certain properties. We prove the strict inclusion for the following sets of complexes of faces: kernel, minimal for any complexity measure and minimal for any complexity measure, which is invariant under the replacement faces on isomorphic faces. Ill. 2, bibliogr. 10.
Mots-clés : face
Keywords: complex of faces in the $n$-dimensional unit cube, Boolean function, complexity measure, minimal complex of faces. 
@article{DA_2013_20_6_a5,
     author = {I. P. Chukhrov},
     title = {On complexity measures for complexes of faces in the unit cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {77--94},
     publisher = {mathdoc},
     volume = {20},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_6_a5/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On complexity measures for complexes of faces in the unit cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 77
EP  - 94
VL  - 20
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_6_a5/
LA  - ru
ID  - DA_2013_20_6_a5
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On complexity measures for complexes of faces in the unit cube
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 77-94
%V 20
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_6_a5/
%G ru
%F DA_2013_20_6_a5
I. P. Chukhrov. On complexity measures for complexes of faces in the unit cube. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 6, pp. 77-94. http://geodesic.mathdoc.fr/item/DA_2013_20_6_a5/

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

[2] Veber K., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Probl. kibernetiki, 36, 1979, 129–158 | MR | Zbl

[3] Zhuravlev Yu. I., “O razlichnykh ponyatiyakh minimalnosti d.n.f.”, Sib. mat. zhurn., 1:4 (1960), 609–611

[4] Zhuravlev Yu. I., “Algoritmy postroeniya minimalnykh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, M., 1974., 67–98

[5] Lin Sin-Lyan, “O sravnenii slozhnostei minimalnykh i kratchaishikh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Probl. kibernetiki, 18, 1967, 11–44 | MR

[6] 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

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

[8] Chukhrov I. P., “O yadrovykh i kratchaishikh kompleksakh granei v edinichnom kube”, Diskret. analiz i issled. operatsii, 18:2 (2011), 75–94 | MR | Zbl

[9] Chukhrov I. P., “O minimalnykh kompleksakh granei v edinichnom kube”, Diskret. analiz i issled. operatsii, 19:3 (2012), 79–99 | MR | Zbl

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