Geodesic
On a decomposition of Boolean functions
Diskretnaya Matematika, Tome 12 (2000) no. 3, pp. 114-123 
A. V. Chashkin. On a decomposition of Boolean functions. Diskretnaya Matematika, Tome 12 (2000) no. 3, pp. 114-123. http://geodesic.mathdoc.fr/item/DM_2000_12_3_a7/
@article{DM_2000_12_3_a7,
     author = {A. V. Chashkin},
     title = {On a decomposition of {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {114--123},
     year = {2000},
     volume = {12},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_3_a7/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On a decomposition of Boolean functions
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 114
EP  - 123
VL  - 12
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_3_a7/
LA  - ru
ID  - DM_2000_12_3_a7
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On a decomposition of Boolean functions
%J Diskretnaya Matematika
%D 2000
%P 114-123
%V 12
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2000_12_3_a7/
%G ru
%F DM_2000_12_3_a7

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

A special $(s,d,\varepsilon)$-decomposition of an arbitrary Boolean function $f$ of $n$ variables is considered. The elements of the decomposition are $s$, $s$, partial functions, each defined on a domain of cardinality $d$, where it coincides with $f$. The minimum possible $d$ is at most $n^3$ times greater than the circuit size of $f$. Criteria for the existence of $(s,d,\varepsilon)$-decompositions are obtained, and the properties of the latter are examined. The research was supported by the Russian Foundation for Basic Research, grant 99–01–01175, and by the Federal Program ‘Integration’, grant 473.

[1] Chashkin A. V., “O vychislenii bulevykh funktsii veroyatnostnymi programmam”, Diskretnyi analiz i issledovanie operatsii, 4:3 (1997), 49–68 | MR

[2] Chashkin A. V., “Lokalnaya slozhnost bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:3 (1997), 69–80 | MR | Zbl

[3] Chashkin A. V., “Samokorrektiruyuschiesya skhemy dlya funktsii polinomialnogo vesa”, Vestn. Mosk. univ., Ser. I: Matematika, Mekhanika, 1997, no. 5, 64–66 | MR | Zbl

[4] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Probl. kibernetiki, 14 (1965), 31–110 | MR | Zbl

[5] Chashkin A. V., “Nizhnie otsenki slozhnosti suzhenii bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:2 (1997), 75–111 | MR

[6] Chashkin A. V., “O srednem vremeni vychisleniya znachenii bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:1, (1997), 60–78 | MR | Zbl

[7] Sholomov L. A., “O realizatsii nedoopredelennykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Probl. kibernetiki, 21 (1969), 215–226 | Zbl

[8] Andreev A. E., “O slozhnosti realizatsii chastichnykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Diskretnaya matematika, 1:4 (1989), 36–45 | MR | Zbl