Geodesic
Computational bound on complexity of polynomial representations of Boolean functions
The Bulletin of Irkutsk State University. Series Mathematics, Tome 3 (2010) no. 4, pp. 33-43 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper concerns complexity of exclusive-or-sum-of-products expressions representing Boolean functions. Conditions for functions having complexity over a given number are introduced. Genetic minimization algorithm gave obtained upper bounds on complexity of such functions. As a result a new upper bound on complexity for all Boolean functions is obtained.
Keywords: boolean functions; ESOPs; exclusive-or-sum-of-products; minimization; genetic algorithms. 
@article{IIGUM_2010_3_4_a3,
     author = {A. S. Kazimirov and S. Yu. Reymerov},
     title = {Computational bound on complexity of polynomial representations of {Boolean} functions},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {33--43},
     year = {2010},
     volume = {3},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a3/}
}
TY  - JOUR
AU  - A. S. Kazimirov
AU  - S. Yu. Reymerov
TI  - Computational bound on complexity of polynomial representations of Boolean functions
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2010
SP  - 33
EP  - 43
VL  - 3
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a3/
LA  - ru
ID  - IIGUM_2010_3_4_a3
ER  - 
%0 Journal Article
%A A. S. Kazimirov
%A S. Yu. Reymerov
%T Computational bound on complexity of polynomial representations of Boolean functions
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2010
%P 33-43
%V 3
%N 4
%U http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a3/
%G ru
%F IIGUM_2010_3_4_a3
A. S. Kazimirov; S. Yu. Reymerov. Computational bound on complexity of polynomial representations of Boolean functions. The Bulletin of Irkutsk State University. Series Mathematics, Tome 3 (2010) no. 4, pp. 33-43. http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a3/

[1] S. F. Vinokurov, A. S. Kazimirov, “Verkhnyaya otsenka slozhnosti bulevykh funktsii v klasse PNF”, Algebra and Model Theory 4, Novosibirsk State Tech. University, Novosibirsk, 2003, 160–165

[2] A. S. Kazimirov, “Otsenka chisla klassov LP-ekvivalentnosti bulevykh funktsii”, Vestn. Buryat. un-ta. Ser. 13, Matematika i informatika, 2005, no. 2, 17–22

[3] A. S. Kazimirov, “Parallelnye geneticheskie algoritmy v zadachakh minimizatsii bulevykh funktsii”, Vestn. TGU. Prilozhenie, 2006, no. 17, 226–230

[4] K. D. Kirichenko, “Verkhnyaya otsenka slozhnosti polinomialnykh normalnykh form bulevykh funktsii”, Diskretnaya matematika, 17:3 (2005), 80–88 | DOI | MR | Zbl

[5] S. Yu. Reimerov, “O slozhnosti polinomialnykh predstavlenii bulevykh funktsii 7 peremennykh”, Student i nauchno-tekhnicheskii progress: Matematika, materialy XLVIII mezhdunar. nauch. stud. konf., Novosib. gos. un-t, Novosibirsk, 2010, 177

[6] L. V. Ryabets, “Nakhozhdenie minimalnykh polinomov bulevykh funktsii s ispolzovaniem spetsialnoi operatornoi formy”, Tekhnologii Microsoft v teorii i praktike programmirovaniya, tez. dokl. (Novosibirsk, 2006), 215–217

[7] Even S., “On minimal modulo 2 sums of products for switching functions”, IEEE Trans. Electron. Comput., EC-16:10 (1967), 671–674 | DOI | Zbl

[8] A. Gaidukov, “Algorithm to derive minimum ESOPs for 6-variable functions”, Proceedings of the 5th International Workshop on Boolean Problems 2002 (Freiberg, Germany, Sept. 19–20, 2002), 141–148