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

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

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},
     publisher = {mathdoc},
     volume = {3},
     number = {4},
     year = {2010},
     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
PB  - mathdoc
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
%I mathdoc
%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/