Geodesic
About complexity of implementing threshold functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2017), pp. 41-49 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2017},
     number = {7},
     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
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
%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