Geodesic
On complexity of realisation of a~class of almost symmetric functions by formulas of depth~3
Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 120-130

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

We consider the class of almost symmetric Boolean functions. For any function of this class, the values on all tiers except the second one coincide with the values of a monotone symmetric function with threshold 3. The values on the second tier are arbitrary. We study realisation of functions of this class by $\\vee\$- formulas over the basis $\{\,\vee\}$. We obtain a sharp bound for the minimum complexity of the functions of this class (the function of minimum complexity is explicitly written out) and an asymptotic estimate of complexity of a monotone symmetric function with threshold 3 which is maximal in order of complexity in the class under consideration. 
@article{DM_2008_20_1_a10,
     author = {S. E. Cherukhina},
     title = {On complexity of realisation of a~class of almost symmetric functions by formulas of depth~3},
     journal = {Diskretnaya Matematika},
     pages = {120--130},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_1_a10/}
}
TY  - JOUR
AU  - S. E. Cherukhina
TI  - On complexity of realisation of a~class of almost symmetric functions by formulas of depth~3
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 120
EP  - 130
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_1_a10/
LA  - ru
ID  - DM_2008_20_1_a10
ER  - 
%0 Journal Article
%A S. E. Cherukhina
%T On complexity of realisation of a~class of almost symmetric functions by formulas of depth~3
%J Diskretnaya Matematika
%D 2008
%P 120-130
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_1_a10/
%G ru
%F DM_2008_20_1_a10
S. E. Cherukhina. On complexity of realisation of a~class of almost symmetric functions by formulas of depth~3. Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 120-130. http://geodesic.mathdoc.fr/item/DM_2008_20_1_a10/