Geodesic
Implementation complexity of Boolean functions with a small number of ones
Diskretnaya Matematika, Tome 32 (2020) no. 2, pp. 32-43 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the class $F_{n,k}$ consisting of $n$-ary Boolean functions that take the value one on exactly $k$ input tuples. For small values of $k$ the class $F_{n,k}$ is splitted into subclasses, and for every subclass we find the asymptotics of the Shannon function of circuit implementation in the basis $\{x\,\overline x\}$ (or in the basis $\{x\vee y,\overline x\}$); the weights of the basic gates are arbitrary strictly positive numbers.} \classification[Funding]{Research was supported by Russian Foundation for Basic Research (project No. 8.01.00337 “Problems of synthesis, complexity and reliability in theory of control systems”).
Keywords: Boolean function, Boolean circuit, Shannon function. 
@article{DM_2020_32_2_a2,
     author = {N. P. Red'kin},
     title = {Implementation complexity of {Boolean} functions with a small number of ones},
     journal = {Diskretnaya Matematika},
     pages = {32--43},
     year = {2020},
     volume = {32},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_2_a2/}
}
TY  - JOUR
AU  - N. P. Red'kin
TI  - Implementation complexity of Boolean functions with a small number of ones
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 32
EP  - 43
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_2_a2/
LA  - ru
ID  - DM_2020_32_2_a2
ER  - 
%0 Journal Article
%A N. P. Red'kin
%T Implementation complexity of Boolean functions with a small number of ones
%J Diskretnaya Matematika
%D 2020
%P 32-43
%V 32
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2020_32_2_a2/
%G ru
%F DM_2020_32_2_a2
N. P. Red'kin. Implementation complexity of Boolean functions with a small number of ones. Diskretnaya Matematika, Tome 32 (2020) no. 2, pp. 32-43. http://geodesic.mathdoc.fr/item/DM_2020_32_2_a2/

[1] Finikov B. I., “Ob odnom semeistve klassov funktsii algebry logiki i ikh realizatsii v klasse P-skhem”, Dokl. AN SSSR, 115:2 (1957), 247–248

[2] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14 (1965), 31–110

[3] Redkin N. P., “On the complexity of Boolean functions with small number of ones”, Discrete Math. Appl., 14:6 (2004), 619–630 | DOI

[4] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984, 138 pp.

[5] Redkin N. P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23 (1970), 83–101