Geodesic
On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics
Čebyševskij sbornik, Tome 23 (2022) no. 2, pp. 121-150.

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

The paper is an attempt both to give an overview of the results of O M Kasim-Zade, the largest specialist in discrete mathematics and mathematical cybernetics, and to understand his scientific legacy in fields such as research measures the circuit complexity of Boolean functions related to the operation of the circuits, the problems of implicit and parametric expressibility in finite-valued logics, the questions of the depth and the complexity of Boolean functions and functions of multivalued logics in infinite bases.
Keywords: circuits complexity, actiyvity, power, depth, infinite basis, implicit expressibility parametric expressibility. 
@article{CHEB_2022_23_2_a7,
     author = {V. V. Kochergin},
     title = {On the papers of {O.} {M.} {Kasim-Zade} in field of complexity theory and theory of multivalued logics},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {121--150},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2022_23_2_a7/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics
JO  - Čebyševskij sbornik
PY  - 2022
SP  - 121
EP  - 150
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2022_23_2_a7/
LA  - ru
ID  - CHEB_2022_23_2_a7
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics
%J Čebyševskij sbornik
%D 2022
%P 121-150
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2022_23_2_a7/
%G ru
%F CHEB_2022_23_2_a7
V. V. Kochergin. On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics. Čebyševskij sbornik, Tome 23 (2022) no. 2, pp. 121-150. http://geodesic.mathdoc.fr/item/CHEB_2022_23_2_a7/

[1] Amanzhaev G. G., “O zamykanii nenulevogo invariantnogo klassa Yablonskogo po operatsii otozhdestvleniya peremennykh”, Vestnik MGU. Matematika. Mekhanika, 1995, no. 3, 76–79 | MR | Zbl

[2] Vaintsvaig M. N., “O moschnosti skhem iz funktsionalnykh elementov”, Doklady AN SSSR, 139:2 (1961), 320–323 | MR

[3] Gilbert E. N., “Teoretiko-strukturnye svoistva zamykayuschikh pereklyuchatelnykh funktsii”, Kiberneticheskii sbornik, 1, Izd-vo inostannoi literatury, M., 1960, 175–188

[4] Goryashko A. P., “Energeticheskie otsenki slozhnosti funktsionirovaniya logicheskikh setei”, Izvestiya AN SSSR. Ser. tekhn. kibernetika, 1969, no. 2, 86–95 | Zbl

[5] Goryashko A. P., Logicheskie skhemy i realnye ogranicheniya, Energoizdat, M., 1982 | MR

[6] Danilchenko A. F., “O parametricheskoi vyrazimosti funktsii trekhznachnoi logiki”, Algebra i logika, 16:4 (1977), 397–416 | MR | Zbl

[7] Debrev E. V., “Ob odnoi zadache kombinatornogo poiska”, Diskretnaya matemematika, 14:3 (2002), 8–17 | DOI | MR | Zbl

[8] Debrev E. V., “O razlichenii grafov iz nekotorykh mnozhestv posredstvom bezuslovnykh rebernykh testov”, Matematicheskie voprosy kibernetiki, 11, Nauka, M., 2002, 177–192 | MR

[9] Debrev E. V., “O bezuslovnykh rebernykh testakh dlya nekotorykh semeistv grafov”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 10:4 (2003), 8–17 | MR

[10] Ermakova D. I., “O slozhnosti realizatsii sistemy konstant $P_3$ v nekotorykh bazisakh”, Matematicheskie voprosy kibernetiki, 17, FIZMATLIT, M., 2008, 137–158

[11] Zakirov N. R., “O predstavlenii proizvolnogo algebraicheskogo chisla periodicheskoi vetvyascheisya tsepnoi drobyu”, Matematicheskie voprosy kibernetiki, 15, FIZMATLIT, M., 2006, 65–78

[12] Zakirov N. R., “O predstavlenii algebraicheskikh chisel periodicheskimi vetvyaschimisya tsepnymi drobyami”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 2007, no. 4, 24–29 | MR | Zbl

[13] Izbrannye zadachi iz zhurnala «American Mathematical Monthly», Mir, M., 1977

[14] Karpova N. A., “O nekotorykh svoistvakh funktsii Shennona”, Matem. zametki, 8:5 (1970), 663–674 | Zbl

[15] Kochergin A. V., “O glubine funktsii $k$-znachnoi logiki v beskonechnykh bazisakh”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2011, no. 1, 22–26 | Zbl

[16] Kochergin A. V., “O glubine funktsii $k$-znachnoi logiki v konechnykh bazisakh”, Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika, 2013, no. 1, 56–59 | Zbl

[17] Kochergin A. V., “O glubine funktsii $k$-znachnoi logiki nad proizvolnymi bazisami”, Fundament. i prikl. matem., 20:6 (2015), 155–158

[18] Kochergin V. V., Mikhailovich A. V., “O slozhnosti funktsii mnogoznachnoi logiki v odnom beskonechnom bazise”, Diskretnyi analiz i issledovanie operatsii, 25:1 (2018), 42–74 | Zbl

[19] Kochergin V. V., Mikhailovich A. V., “O skhemnoi slozhnosti funktsii $k$-znachnoi logiki v odnom beskonechnom bazise”, Prikladnaya matematika i informatika, 2018, no. 58, 21–34

[20] Kuzmin V. A., “Otsenka slozhnosti realizatsii funktsii algebry logiki prosteishimi vidami binarnykh programm”, Metody diskretnogo analiza v teorii kodov i skhem, 29, Novosibirsk, 1976, 11–39 | Zbl

[21] Kuznetsov A. V., “O sredstvakh dlya obnaruzheniya nevyvodimosti ili nevyrazimosti”, Logicheskii vyvod, Nauka, M., 1979, 5–33

[22] Kuznetsov Yu. V., “O klassakh bulevykh funktsii, invariantnykh otnositelno otozhdestvleniya peremennykh”, Doklady AN SSSR, 290:4 (1986), 780–785 | MR

[23] Kuznetsov Yu. V., Issledovanie invariantnykh klassov, svyazannykh s funktsionalnymi sistemami, Dissertatsiya na soiskanie uchenoi stepeni kandidata fiziko-matematicheskikh nauk, MGU, M., 1987

[24] Lozhkin S. A., “Asimptoticheskoe povedenie funktsii Shennona dlya zaderzhek skhem iz funktsionalnykh elementov”, Matem. zametki, 19:6 (1976), 939–951 | MR | Zbl

[25] Lupanov O. B., “Ob odnom metode sinteza skhem”, Izv. vuzov. Ser. radiofizika, 1958, no. 1, 120–140

[26] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, M., 1963, 63–97

[27] Lupanov O. B., “O sinteze skhem iz porogovykh elementov”, Problemy kibernetiki, 26, Nauka, M., 1973, 109–140

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

[29] Lyapunov A. A., “O logicheskikh skhemakh programm”, Problemy kibernetiki, 1, Fizmatgiz, M., 1958, 46–74

[30] Markov A. A., “Ob inversionnoi slozhnosti sistem funktsii”, Dokl. AN SSSR, 116:6 (1957), 917–919 | Zbl

[31] Markov A. A., “Ob inversionnoi slozhnosti sistem bulevykh funktsii”, Dokl. AN SSSR, 150:3 (1963), 477–479 | Zbl

[32] Mikhailets E. V., “O range neyavnykh predstavlenii nad odnim klassom funktsii trekhznachnoi logiki”, Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika, 2008, no. 5, 65–67 | Zbl

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

[34] Nechiporuk E. I., “O sinteze skhem iz porogovykh elementov”, Problemy kibernetiki, 11, Nauka, M., 1964, 49–62 | MR

[35] Orekhova E. A., “Ob odnom kriterii neyavnoi polnoty v trekhznachnoi logike”, Matematicheskie voprosy kibernetiki, 12, Fizmatlit, M., 2003, 27–74

[36] Orekhova E. A., “O kriterii neyavnoi shefferovosti v trekhznachnoi logike”, Diskretnyi analiz i issledovanie operatsii. Seriya 1, 10:3 (2003), 82–105 | MR | Zbl

[37] Podolskaya O. V., “O nizhnikh otsenkakh slozhnosti skhem v bazise antitsepnykh funktsii”, Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika, 2013, no. 2, 17–23 | MR | Zbl

[38] Podolskaya O. V., “Slozhnost realizatsii simmetricheskikh bulevykh funktsii skhemami v bazise antitsepnykh funktsii”, Diskretnaya matemematika, 27:3 (2015), 95–107 | DOI

[39] Podolskaya O. V., “Ob otsenkakh funktsii Shennona slozhnosti skhem v nekotorykh beskonechnykh bazisakh”, Materialy XII Mezhdunarodnogo seminara «Diskretnaya matematika i ee prilozheniya» imeni akademika O. B. Lupanova, M., 2016, 150–152

[40] Proskuryakov A. I., “O slozhnosti realizatsii nekotorykh funktsii setyami iz elementov, osuschestvlyayuschikh analiticheskie operatsii”, Matematicheskie voprosy kibernetiki, 11, FIZMATLIT, M., 2002, 262–269 | MR

[41] Sapozhenko A. A., Lozhkin S. A., “Metody logicheskogo proektirovaniya i otsenki slozhnosti skhem na dopolnyayuschikh MOP-tranzistorakh”, Mikroelektronika, 12:1 (1983), 42–47

[42] Starostin M. V., “Neyavno predpolnye klassy i kriterii neyavnoi polnoty v trekhznachnoi logike”, Vestnik MGU. Seriya 1. Matematika. Mekhanika, 2018, no. 2, 56–59 | Zbl

[43] Starostin M. V., Kriterii neyavnoi polnoty v trekhznachnoi logike v terminakh predpolnykh klassov, arXiv: (data obrascheniya: 30.03.2021) 2103.16631

[44] Yablonskii S. V., “Ob algoritmicheskikh trudnostyakh sinteza minimalnykh kontaktnykh skhem”, Problemy kibernetiki, 2, Nauka, M., 1959, 75–121

[45] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, M., 1966 | MR

[46] Yaglom I. M., Kak razrezat kvadrat?, Nauka, M., 1968 | MR

[47] Yashunskii A. D., “Ob asimptotike veroyatnosti znachenii sluchainykh bulevykh vyrazhenii”, Diskretnyi analiz i issledovanie operatsii, 13:2 (2006), 59–99 | MR

[48] Yashunskii A. D., “Polinomialnye preobrazovaniya sluchainykh velichin na konechnykh mnozhestvakh”, Matem. zametki, 106:6 (2019), 951–954 | DOI | MR | Zbl

[49] Yashunskii A.D., “O neobkhodimykh usloviyakh predelnykh veroyatnostnykh teorem v konechnykh algebrakh”, Doklady Rossiiskoi akademii nauk. Matematika, informatika, protsessy upravleniya, 493:1 (2020), 47–50 | DOI | MR

[50] Yashunskii A. D., Issledovaniya po teorii iterativnykh sistem, porozhdaemykh konechnymi sluchainymi velichinami. Arifmeticheskii i kombinatorno-logicheskii podkhod, Dissertatsiya na soiskanie uchenoi stepeni doktora fiziko-matematicheskikh nauk, M., 2021 https://istina.msu.ru/dissertations/364891994/ | Zbl

[51] Burks A. W., Wright J. B., “Theory of logical nets”, Proc. IRE, 41:10 (1953), 1357–1365 | DOI | MR

[52] Vuggis S., Willagd R., “Finitely many primitive positive clones”, Proc. of the American Mathematical Society, 101:3 (1987), 427–430 | DOI | MR | Zbl

[53] Lee C. Y., “Representation of switching circuits by binary-decision programs”, Bell System Technical Journal, 38:4 (1959), 985–1000 | DOI | MR | Zbl

[54] Muller D. E., “Complexity in electronic switching circuits”, IRE Trans. on Electronic Computers, EC-5:1 (1958), 15–19 | DOI

[55] Shannon C. E., “Mathematical theory of the differential analyzer”, J. Math. and Phys., 20:4 (1941), 337–354 | DOI | MR | Zbl

[56] Shepherdson J., Sturgis H., “Computability of recursive functions”, Journal of the Association for Computer Machinery, 10:2 (1963), 217–255 | DOI | MR | Zbl

[57] Yashunsky A. D., “Clone-induced approximation algebras of Bernoulli distributions”, Algebra Univers., 80:5 (2019) | MR | Zbl