|
Diskretnyi Analiz i Issledovanie Operatsii, 2011, Volume 18, Issue 2, Pages 75–94
(Mi da648)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
On kernel and shortest complexes of faces in the unit cube
I. P. Chukhrov Institute of Automatization of Designing, RAS, Moscow, Russia
Abstract:
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.
Keywords:
face, interval, kernel face, complex of faces in $n$-dimensional unit cube, Boolean function, shortest covering.
Received: 02.11.2010
Citation:
I. P. Chukhrov, “On kernel and shortest complexes of faces in the unit cube”, Diskretn. Anal. Issled. Oper., 18:2 (2011), 75–94; J. Appl. Industr. Math., 6:1 (2012), 42–55
Linking options:
https://www.mathnet.ru/eng/da648 https://www.mathnet.ru/eng/da/v18/i2/p75
|
Statistics & downloads: |
Abstract page: | 390 | Full-text PDF : | 89 | References: | 50 | First page: | 2 |
|