Geodesic
About complexity of implementing threshold functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2017), pp. 41-49.

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

We study properties and ways of classification of threshold functions as well as known estimates of complexity of implementing in the functional elements type of circuits. We determine a dependence of the maximum values of variables weights on their number. Using the intermediate conversion method we obtain a precise upper bound of complexity of implementing arbitrary threshold functions in the functional elements type of circuits.
Keywords: threshold functions, functional elements, complexity. 
@article{IVM_2017_7_a4,
     author = {O. N. Muzychenko},
     title = {About complexity of implementing threshold functions},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {41--49},
     publisher = {mathdoc},
     number = {7},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2017_7_a4/}
}
TY  - JOUR
AU  - O. N. Muzychenko
TI  - About complexity of implementing threshold functions
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2017
SP  - 41
EP  - 49
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2017_7_a4/
LA  - ru
ID  - IVM_2017_7_a4
ER  - 
%0 Journal Article
%A O. N. Muzychenko
%T About complexity of implementing threshold functions
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2017
%P 41-49
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2017_7_a4/
%G ru
%F IVM_2017_7_a4
O. N. Muzychenko. About complexity of implementing threshold functions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2017), pp. 41-49. http://geodesic.mathdoc.fr/item/IVM_2017_7_a4/

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

[2] Korshunov A. D., “Monotonnye bulevy funktsii”, UMN, 58:5 (2003), 89–162 | DOI | Zbl

[3] Ugolnikov A. B., “O realizatsii monotonnykh funktsii skhemami iz funktsionalnykh elementov”, Probl. kibernetiki, 1976, no. 31, 167–185

[4] Pippenger N., “The complexity of monotone Boolean functions”, Math. Syst. Theory, 11 (1977/78), 289–316 | DOI | MR

[5] Muzychenko O. N., Spetsializirovannye metody sinteza logicheskikh skhem, v. 1, Metody sinteza logicheskikh skhem simmetrichnykh i porogovykh funktsii, Baltiisk. gos. tekhn. un-t, SPb., 2004

[6] Muzychenko O. N., “Uproschenie porogovykh skhem, sinteziruemykh metodom promezhutochnogo preobrazovaniya”, Avtomatika i telemekhanika, 1990, no. 12, 164–170

[7] Muzychenko O. N., “Sintez skhem simmetrichnykh funktsii kombinirovannym metodom”, Avtomatika i telemekhanika, 1995, no. 5, 137–149 | Zbl

[8] Zuev Yu. A., “Porogovye funktsii i porogovye predstavleniya bulevykh funktsii”, Matem. vopr. kibernetiki, 1994, no. 5, 5–61

[9] Shabanin O. V., “O slozhnosti predstavleniya porogovykh funktsii v traditsionnykh bazisakh”, Vestn. Moskovsk. gos. un-ta lesa, 2006, no. 1, 152–155

[10] Dertouzos M., Porogovaya logika, Mir, M., 1967

[11] Butakov E. A., Metody sinteza releinykh ustroistv na porogovykh elementakh, Energiya, M., 1970