Geodesic
Generalization of complexity estimates for flat circuits realizing partial Boolean operators
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2018), pp. 60-64 
G. V. Kalachev. Generalization of complexity estimates for flat circuits realizing partial Boolean operators. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2018), pp. 60-64. http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a9/
@article{VMUMM_2018_3_a9,
     author = {G. V. Kalachev},
     title = {Generalization of complexity estimates for flat circuits realizing partial {Boolean} operators},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {60--64},
     year = {2018},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a9/}
}
TY  - JOUR
AU  - G. V. Kalachev
TI  - Generalization of complexity estimates for flat circuits realizing partial Boolean operators
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2018
SP  - 60
EP  - 64
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a9/
LA  - ru
ID  - VMUMM_2018_3_a9
ER  - 
%0 Journal Article
%A G. V. Kalachev
%T Generalization of complexity estimates for flat circuits realizing partial Boolean operators
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2018
%P 60-64
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a9/
%G ru
%F VMUMM_2018_3_a9

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

In this paper we consider the Shannon function of plain circuit activity for class of partial Boolean operators with restrictions on the number of different operator values. It is proved that for the class of partial operators with $m$ outputs, domain of cardinality $d$, and the number of different values not exceeding $r$ the mean and maximal orders of activity are equal to $(\sqrt{d}+m\sqrt{r}/\log r)\sqrt{\log r}$ by the order.

[1] Kravtsov S.S., “O realizatsii funktsii algebry logiki v odnom klasse skhem iz funktsionalnykh i kommutatsionnykh elementov”, Problemy kibernetiki, 19, Nauka, M., 1967, 285–293

[2] Albrekht A., “O skhemakh iz kletochnykh elementov”, Problemy kibernetiki, 33, Nauka, M., 1977, 209–214

[3] Shkalikova N.A., “O realizatsii bulevykh funktsii skhemami iz kletochnykh elementov”, Matematicheskie voprosy kibernetiki, 2, Nauka, M., 1989, 177–197 | MR

[4] Zhukov D.A., “O vychislenii chastichnykh bulevykh funktsii kletochnymi skhemami”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 11:2 (2004), 32–40 | MR | Zbl

[5] Vaintsvaig M.N., “Ob odnovremennoi minimizatsii slozhnosti i moschnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 33, Nauka, M., 1977, 215–220

[6] Kasim-Zade O.M., “Ob odnovremennoi minimizatsii slozhnosti i moschnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 33, Nauka, M., 1977, 215–220

[7] Kasim-Zade O.M., “Ob odnoi mere slozhnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 38, Nauka, M., 1981, 117–179

[8] Kasim-Zade O.M., “Ob odnoi mere aktivnosti skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 4, Nauka, M., 1992, 218–228 | MR

[9] Cheremisin O.V., “Ob aktivnosti skhem iz kletochnykh elementov, realizuyuschikh sistemu vsekh kon'yunktsii”, Diskretn. matem., 15:2 (2003), 113–122 | DOI | MR | Zbl

[10] Kalachev G.V., “Poryadok moschnosti ploskikh skhem, realizuyuschikh bulevy funktsii”, Diskretn. matem., 26:1 (2014), 49–74 | DOI | Zbl

[11] Kalachev G.V., “Nizhnie otsenki moschnosti ploskikh skhem, realizuyuschikh chastichnye bulevy operatory”, Intellektualnye sistemy. Teoriya i prilozheniya, 18:2 (2014), 279–322 | MR

[12] Kalachev G.V., “Ob odnovremennoi minimizatsii ploschadi, moschnosti i glubiny ploskikh skhem, realizuyuschikh chastichnye bulevy operatory”, Intellektualnye sistemy. Teoriya i prilozheniya, 20:2 (2016), 203–266 | MR