
This article is cited in 3 scientific papers (total in 3 papers)
On minimal complexes of faces in the unit cube
I. P. Chukhrov^{} ^{} Institute of Automatization of Designing, RAS, Moscow, Russia
Abstract:
We consider the problem of construction of minimal complexes of faces in the unit $n$dimensional cube for the class of complexity measures such that the complexity of a complex does not change upon replacement of some faces with faces isomorphic with respect to permutation of coordinates. This class contains all known complexity measures used in the minimization of Boolean functions in the class of DNF. It is shown that the number of complexes of faces of dimension at most $k$ which are minimal for all complexity measures of this class has the same order as the logarithm of the number of complexes of no more than $2^{n1}$ different faces of dimension at most $k$ for $1\le k\le c\cdot n$ and $c<0.5$. The number of functions with “large” number of minimal complexes has the same order as the logarithm of the number of all functions. Similar estimates are valid for the maximum number of DNF Boolean functions which are minimal for all complexity measures of this class. These results show that the problem of complexity in the minimization of Boolean functions are determined by the structural properties of the set of vertices of a Boolean function in the unit cube, i.e. the properties of domain in which the functional is minimized rather than the properties of the complexity measure functional. Ill. 1, bibliogr. 9.
Keywords:
face, interval, complex of faces in $n$dimensional unit cube, Boolean function, complexity measure, minimal covering, number of minimal complexes of faces.
Full text:
PDF file (493 kB)
References:
PDF file
HTML file
English version:
Journal of Applied and Industrial Mathematics, 2012, 6:1, 42–55
Bibliographic databases:
UDC:
519.95 Received: 18.06.2011
Citation:
I. P. Chukhrov, “On minimal complexes of faces in the unit cube”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 79–99; J. Appl. Industr. Math., 6:1 (2012), 42–55
Citation in format AMSBIB
\Bibitem{Chu12}
\by I.~P.~Chukhrov
\paper On minimal complexes of faces in the unit cube
\jour Diskretn. Anal. Issled. Oper.
\yr 2012
\vol 19
\issue 3
\pages 7999
\mathnet{http://mi.mathnet.ru/da692}
\mathscinet{http://www.ams.org/mathscinetgetitem?mr=2986643}
\zmath{https://zbmath.org/?q=an:06460012}
\elib{http://elibrary.ru/item.asp?id=17723717}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 1
\pages 4255
\crossref{https://doi.org/10.1134/S1990478912010061}
Linking options:
http://mi.mathnet.ru/eng/da692 http://mi.mathnet.ru/eng/da/v19/i3/p79
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:

I. P. Chukhrov, “On complexity measures for complexes of faces in the unit cube”, J. Appl. Industr. Math., 8:1 (2014), 9–19

I. P. Chukhrov, “Minimalnye kompleksy granei sluchainoi bulevoi funktsii”, Diskretn. analiz i issled. oper., 21:5 (2014), 76–94

I. P. Chukhrov, “On the problem of minimizing a single set of Boolean functions”, J. Appl. Industr. Math., 9:3 (2015), 335–350

Number of views: 
This page:  528  Full text:  49  References:  27  First page:  3 
