RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
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., 2018, Volume 25, Number 3, Pages 126–151 (Mi da904)  

On the complexity of minimizing quasicyclic Boolean functions

I. P. Chukhrov

Institute of Computer Aided Design RAS, 19/18 Vtoraya Brestskaya St., 123056 Moscow, Russia

Abstract: We investigate the Boolean functions that combine various properties: the extremal values of complexity characteristics of minimization, the inapplicability of local methods for reducing the complexity of the exhaustion, and the impossibility to efficiently use sufficient minimality conditions. Some quasicyclic functions are constructed that possess the properties of cyclic and zone functions, the dominance of vertex sets, and the validity of sufficient minimality conditions based on independent families of sets. For such functions, we obtain the exponential lower bounds for the extent and special sets and also a twice exponential lower bound for the number of shortest and minimal complexes of faces with distinct sets of proper vertices. Bibliogr. 13.

Keywords: minimization of Boolean functions, complexity, extent, domination, independent family of sets.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-01-00593а
Russian Academy of Sciences - Federal Agency for Scientific Organizations 115022670011
The authors were supported by the Russian Foundation for Basic Research (project no. 16-01-00593a) and The Federal Agency for Scientific Organizations (State Assignment no. 115022670011).


DOI: https://doi.org/10.17377/daio.2018.25.601

Full text: PDF file (396 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:3, 426–441

Document Type: Article
UDC: 519.714.7
Received: 24.11.2017
Revised: 19.01.2018

Citation: I. P. Chukhrov, “On the complexity of minimizing quasicyclic Boolean functions”, Diskretn. Anal. Issled. Oper., 25:3 (2018), 126–151; J. Appl. Industr. Math., 12:3 (2018), 426–441

Citation in format AMSBIB
\Bibitem{Chu18}
\by I.~P.~Chukhrov
\paper On the complexity of minimizing quasicyclic Boolean functions
\jour Diskretn. Anal. Issled. Oper.
\yr 2018
\vol 25
\issue 3
\pages 126--151
\mathnet{http://mi.mathnet.ru/da904}
\crossref{https://doi.org/10.17377/daio.2018.25.601}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 3
\pages 426--441
\crossref{https://doi.org/10.1134/S1990478918030043}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85052092377}


Linking options:
  • http://mi.mathnet.ru/eng/da904
  • http://mi.mathnet.ru/eng/da/v25/i3/p126

    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
  • Дискретный анализ и исследование операций
    Number of views:
    This page:14
    References:2

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