Geodesic
Asymptotically best method for synthesis of Boolean recursive circuits
Diskretnaya Matematika, Tome 31 (2019) no. 1, pp. 99-110.

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

Models of multi-output and scalar recursive Boolean circuits of bounded depth in an arbitrary basis are considered. Methods for lower and upper estimates for the Shannon function for the complexity of circuits of these classes are provided. Based on these methods, an asymptotic formula for the Shannon function is put forward. Moreover, in the above classes of recursive circuits, upper estimates for the complexity of implementation of some functions and systems of functions used in applications are obtained.
Keywords: recursive circuits of gates, complexity of Boolean functions, Shannon function, asymptotic estimates. 
@article{DM_2019_31_1_a5,
     author = {V. V. Zhukov and S. A. Lozhkin},
     title = {Asymptotically best method for synthesis of {Boolean} recursive circuits},
     journal = {Diskretnaya Matematika},
     pages = {99--110},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_1_a5/}
}
TY  - JOUR
AU  - V. V. Zhukov
AU  - S. A. Lozhkin
TI  - Asymptotically best method for synthesis of Boolean recursive circuits
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 99
EP  - 110
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_1_a5/
LA  - ru
ID  - DM_2019_31_1_a5
ER  - 
%0 Journal Article
%A V. V. Zhukov
%A S. A. Lozhkin
%T Asymptotically best method for synthesis of Boolean recursive circuits
%J Diskretnaya Matematika
%D 2019
%P 99-110
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2019_31_1_a5/
%G ru
%F DM_2019_31_1_a5
V. V. Zhukov; S. A. Lozhkin. Asymptotically best method for synthesis of Boolean recursive circuits. Diskretnaya Matematika, Tome 31 (2019) no. 1, pp. 99-110. http://geodesic.mathdoc.fr/item/DM_2019_31_1_a5/

[1] Shennon K., Raboty po teorii informatsii i kibernetike, Per. s angl., IL, M., 1963, 829 pp.

[2] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[3] Redkin N. P., Markovskii A. B., “O realizatsii bulevykh funktsii skhemami iz blokov”, Problemy kibernetiki, 1974, no. 28, 81–100, Nauka, M. | MR

[4] Lozhkin S. A., “Otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov”, Matematicheskie voprosy kibernetiki, 1996, no. 6, 189–214, Nauka. Fizmatlit, M. | MR

[5] Lozhkin S. A., Asimptoticheskie otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem, Diss. na soiskanie uchenoi stepeni doktora fiz.-matem. nauk, MGU im. M. V. Lomonosova, 1997

[6] Dančík V., “Complexity of Boolean functions with unbounded fan-in gates”, Inform. Proc. Letters, 57 (1996), 31–34 | DOI | MR | Zbl

[7] Nechiporuk E. I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 1962, no. 8, 123–160, Fizmatlit, M. | MR

[8] Gribok S. V., “Ob odnoi modeli rekursivnykh skhem iz funktsionalnykh elementov”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. i kibern., 2002, no. 4, 31–36 | MR | Zbl

[9] Gribok S. V., O realizatsii funktsii algebry logiki v nekotorykh klassakh programm, Diss. na soiskanie uchenoi stepeni kandidata fiz.-matem. nauk, MGU im. M. V. Lomonosova, 2003, 90 pp.

[10] Kasim-Zade O. M., “O slozhnosti realizatsii funktsii v odnom klasse algoritmov”, Mater. IX mezhgos. shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem”, Izd-vo mekh.-matem. f-ta MGU, M., 1999, 25–30

[11] Kuzmin V. A., “Otsenka slozhnosti realizatsii funktsii algebry logiki prosteishimi vidami binarnykh programm. Metody diskretnogo analizav teorii kodov i skhem”, Sb. tr. In-ta matem. SO AN SSSR, 1976, no. 29, 11–39, Novosibirsk | Zbl

[12] Blinov S. V., Lozhkin S. A., “O sinteze rekursivnykh skhem iz funktsionalnykh elementov s ogranichennoi glubinoi rekursii”, Mater. XI Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya”, Izd-vo mekh.-matem. f-ta MGU, M., 2012, 98–99

[13] Zhukov V. V., “Asimptoticheski nailuchshii metod sinteza bulevykh rekursivnykh skhem ogranichennoi glubiny”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. i kibern, 2017, no. 4, 29–35 | MR

[14] Lozhkin S. A., Lektsii po osnovam kibernetiki, Izd. otdel f-ta VMK MGU, M., 2004, 147 pp.

[15] Yablonskii S. V., Elementy matematicheskoi kibernetiki, Vysshaya shkola, M., 2007, 188 pp.