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/

[1] Korobkov V. K., “Realizatsiya simmetricheskikh funktsii v klasse $\pi$-skhem”, Dokl. AN SSSR, 109:2 (1956), 260–263 | MR | Zbl

[2] Krichevskii R. E., “Minimalnaya skhema iz zamykayuschikh kontaktov dlya odnoi bulevoi funktsii ot $n$ argumentov”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, 5 (1965), 89–92

[3] Hansel G., “Nombre de lettres nécessaire pour écrire une fonction symétrique de $n$ variables”, C. R. Acad. Sci. Paris, 261 (1965), 4297–4300 | MR | Zbl

[4] Kuznetsov S. E., “O slozhnosti realizatsii odnoi posledovatelnosti bulevykh funktsii formulami glubiny 3 v bazise $\{\,\vee,\neg\}$”, Veroyatnostnye metody i kibernetika, 19 (1983), 40–43 | Zbl

[5] Kuznetsov S. E., Nigmatullin N. R., “O slozhnosti realizatsii nekotorykh simmetricheskikh funktsii formulami glubiny 3 v bazise $\{\,\vee,\neg\}$”, Veroyatnostnye metody i kibernetika, 21 (1985), 36–54 | MR | Zbl

[6] Shumilina S. E., “O realizatsii odnoi simmetricheskoi funktsii formulami spetsialnogo vida”, Kombinatorno-algebraicheskie metody i ikh primenenie, GGU, Gorkii, 1987, 164–169

[7] Lupanov O. B., “O realizatsii funktsii algebry logiki formulami iz konechnykh klassov (formulami ogranichennoi glubiny) v bazise $\{\,\vee,\neg\}$”, Probl. kibern., 1961, no. 6, 5–14 | MR | Zbl

[8] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Probl. kibern., 1963, no. 10, 63–97 | MR | Zbl