RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2012, Volume 19, Number 3, Pages 79–99 (Mi da692)  

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^{n-1}$ 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 79--99
\mathnet{http://mi.mathnet.ru/da692}
\mathscinet{http://www.ams.org/mathscinet-getitem?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 42--55
\crossref{https://doi.org/10.1134/S1990478912010061}


Linking options:
  • http://mi.mathnet.ru/eng/da692
  • http://mi.mathnet.ru/eng/da/v19/i3/p79

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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:
    1. I. P. Chukhrov, “On complexity measures for complexes of faces in the unit cube”, J. Appl. Industr. Math., 8:1 (2014), 9–19  mathnet  crossref  mathscinet
    2. I. P. Chukhrov, “Minimalnye kompleksy granei sluchainoi bulevoi funktsii”, Diskretn. analiz i issled. oper., 21:5 (2014), 76–94  mathnet  mathscinet
    3. I. P. Chukhrov, “On the problem of minimizing a single set of Boolean functions”, J. Appl. Industr. Math., 9:3 (2015), 335–350  mathnet  crossref  crossref  mathscinet  elib
  • Дискретный анализ и исследование операций
    Number of views:
    This page:528
    Full text:49
    References:27
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020