Geodesic
Implementation complexity of Boolean functions with a small number of ones
Diskretnaya Matematika, Tome 32 (2020) no. 2, pp. 32-43

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

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},
     publisher = {mathdoc},
     volume = {32},
     number = {2},
     year = {2020},
     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
PB  - mathdoc
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
%I mathdoc
%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/