Geodesic
Complexity of Boolean functions' representations in classes of extended pair-generated operator forms
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 523-541.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2019_16_a66,
     author = {A. S. Frantseva},
     title = {Complexity of {Boolean} functions' representations in classes of extended pair-generated operator forms},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {523--541},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a66/}
}
TY  - JOUR
AU  - A. S. Frantseva
TI  - Complexity of Boolean functions' representations in classes of extended pair-generated operator forms
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 523
EP  - 541
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a66/
LA  - ru
ID  - SEMR_2019_16_a66
ER  - 
%0 Journal Article
%A A. S. Frantseva
%T Complexity of Boolean functions' representations in classes of extended pair-generated operator forms
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 523-541
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a66/
%G ru
%F SEMR_2019_16_a66
A. S. Frantseva. Complexity of Boolean functions' representations in classes of extended pair-generated operator forms. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 523-541. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a66/

[1] A.S. Baliuk, S.F. Vinokurov, “The Shannon function for some classes of operator polynomial forms”, Optimization, Control, Intellect, 5 (2000), 167–180

[2] A.S. Kazimirov, S.Y. Reimerov, “Computation complexity bounding of polynomial representation of Boolean functions”, News of the Irkutsk state university, Series «Mathematics», 3 (2010), 33–43 | Zbl

[3] L.V. Ryabets, S.F. Vinokurov, “An Algorithm of Exact Minimization of Boolean Functions in the Class of Kronecker Forms”, Algebra and Model Theory, 4 (2003), 148–159

[4] K.D. Vinokurov, “Upper bound for the complexity of polynomial normal forms of Boolean functions”, Discrete Math., 17 (2005), 80–88

[5] N.A. Peryazev, “The complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and logic, 34 (1995), 323–326 | DOI | MR | Zbl

[6] Vinokurov S. F., Peryazev N. A. (eds.), Selected problems of the theory of Boolean functions, Fizmatlit, M., 2001 | Zbl

[7] S. F. Vinokurov, A.S. Kazimirov, “Enumeration of operator classes of Boolean functions”, News of the Irkutsk state university, Series «Mathematics», 2 (2009), 40–55

[8] S. F. Vinokurov, A.S. Frantseva, “The Complexity of the Representation of Multiple-Output Boolean Functions”, News of the Irkutsk state university, Series «Mathematics», 16 (2016), 30–42 | Zbl