Geodesic
Functions without short implicents. Part II: Construction
Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 120-132 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is a continuation of the paper ‘Functions without short implicents. Part I: lower estimates of weights’. In Part II we propose various methods of construction of $n$-place Boolean functions not admitting implicents of $k$ variables. The first of the methods proposed is based on the gradient algorithm, the second and the third ones depend on a certain combinatorial principle of construction, while the fourth method is based on a random choice of elements in the function support. The above methods have different efficiency depending on the value of $k$. We give upper estimates for the minimal value $w\left( {n,\;k} \right)$ of weights of the so-constructed functions. Together with the lower estimates of $w\left( {n,\;k} \right)$ from the first part of the paper this allows us to obtain an asymptotically sharp estimate $w\left( {n,\;k} \right) = \Theta \left( {\ln n} \right)$ as $n \to \infty$.
Keywords: Boolean functions, methods of construction of functions, weight of a Boolean function.
Mots-clés : implicents 
@article{DM_2015_27_4_a8,
     author = {P. V. Roldugin and A. V. Tarasov},
     title = {Functions without short implicents. {Part} {II:} {Construction}},
     journal = {Diskretnaya Matematika},
     pages = {120--132},
     year = {2015},
     volume = {27},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_4_a8/}
}
TY  - JOUR
AU  - P. V. Roldugin
AU  - A. V. Tarasov
TI  - Functions without short implicents. Part II: Construction
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 120
EP  - 132
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_4_a8/
LA  - ru
ID  - DM_2015_27_4_a8
ER  - 
%0 Journal Article
%A P. V. Roldugin
%A A. V. Tarasov
%T Functions without short implicents. Part II: Construction
%J Diskretnaya Matematika
%D 2015
%P 120-132
%V 27
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2015_27_4_a8/
%G ru
%F DM_2015_27_4_a8
P. V. Roldugin; A. V. Tarasov. Functions without short implicents. Part II: Construction. Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 120-132. http://geodesic.mathdoc.fr/item/DM_2015_27_4_a8/

[1] Roldugin P.V., Tarasov A.V., “Funktsii bez korotkikh implitsent. Chast I: nizhnie otsenki vesov”, Diskretnaya matematika, 27:2 (2015), 94–105 | DOI

[2] Glushkov V.M., Sintez tsifrovykh avtomatov, GIFML, M., 1962

[3] Sachkov V.N., Tarakanov V.E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | MR

[4] Raigorodskii A. M., Sistemy obschikh predstavitelei i ikh prilozheniya v geometrii, MTsNMO, M., 2006

[5] Riordan Dzh., Kombinatornye tozhdestva, Nauka, M., 1982 | MR

[6] Kolchin V.F., Sevastyanov B.A., Chistyakov V.P., Sluchainye razmescheniya, Nauka, M., 1976 | MR