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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






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


Sib. Èlektron. Mat. Izv., 2019, Volume 16, Pages 523–541 (Mi semr1076)  

Discrete mathematics and mathematical cybernetics

Complexity of Boolean functions' representations in classes of extended pair-generated operator forms

A. S. Frantseva

Irkutsk State University, 1, Karl Marx str., Irkutsk, 664003, Russia

Abstract: In this paper, we study the problem of receiving the complexity's value of Boolean functions' representations in some classes of polynomial normal forms or exclusive-or sum-of-products expressions (ESOPs). These classes are extensions of known classes of polarized Zhegalkin polynomials or Reed-Muller forms and the Kronecker forms' class. An operator approach for the ESOPs classes' description is used in the work. A Boolean function is represented as a sum of operator images with respect to some basis function. If we consider the product's function as the basic function, then the classes of operator forms are becoming the ESOPs. In this paper, we received estimates of the complexity's value in various classes of extended pair-generated operator forms. The lower bound of the complexity's value to the class of all extended pair-generated operator forms (A. Baliuk and S. Vinokourov, 2001) was improved.

Keywords: Boolean functions, polynomial normal forms, exclusive-or sum-of-products expressions, extended pair-generated operator forms.

DOI: https://doi.org/10.33048/semi.2019.16.034

Full text: PDF file (205 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.714.4
MSC: 06E30
Received July 26, 2019, published April 19, 2019

Citation: A. S. Frantseva, “Complexity of Boolean functions' representations in classes of extended pair-generated operator forms”, Sib. Èlektron. Mat. Izv., 16 (2019), 523–541

Citation in format AMSBIB
\Bibitem{Fra19}
\by A.~S.~Frantseva
\paper Complexity of Boolean functions' representations in classes of extended pair-generated operator forms
\jour Sib. \`Elektron. Mat. Izv.
\yr 2019
\vol 16
\pages 523--541
\mathnet{http://mi.mathnet.ru/semr1076}
\crossref{https://doi.org/10.33048/semi.2019.16.034}


Linking options:
  • http://mi.mathnet.ru/eng/semr1076
  • http://mi.mathnet.ru/eng/semr/v16/p523

    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:38
    Full text:7
    References:13

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