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
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2008},
     volume = {20},
     number = {1},
     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
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
%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