On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics
https://doi.org/10.22405/2226-8383-2022-23-2-121-150
Abstract
The paper is an attempt both to give an overview of the results of OM 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.
About the Author
Vadim Vasil’evich Kochergin
Lomonosov Moscow State University
Russian Federation
Russian Federation
doctor of physical and mathematical sciences
References
1. Amanzhaev, G. G. 1995, “On the closure of the nonzero invariant Yablonski˘ı class by the variable identification operation”, Moscow Univ. Math. Bull., vol. 50, no. 3, pp. 43–45.
2. Va˘ıncva˘ıg, M. N. 1961, “On the power of networks of functional elements”, Soviet Physics Dokl., vol. 6, pp. 545–547.
3. Gilbert, E. N. 1954, “Lattice Theoretic Properties of Frontal Switching Functions”, J. Math. Phys., vol. 33, no. 1, pp. 57–67.
4. Goryashko, A. P. 1969, “Energy bounds of complexity of functioning of logical networks”, Izvestiya AN SSSR. Ser. Tekhn. Kibernetika, no. 2, pp. 86–95.
5. Goryashko, A. P. 1982, Logicheskie skhemy i real’nye ogranicheniya [Logic Circuits and Real Restrictions], Moscow, Energoizdat.
6. Danil’chenko, A. F. 1977, “On parametric expressibility of functions of three-valued logic”, Algebra i logika, vol. 16, no. 4, pp. 397–416.
7. Debrev, E. B. 2002, “On a combinatorial search problem”, Discrete Math. Appl., vol. 12, no. 4, pp. 325–335.
8. Debrev, E. B. 2002, “On distinguishing graphs from certain families by unconditional edge tests”, Mat. Vopr. Kibern., vol. 11, pp. 177–192.
9. Debrev, E. B. 2003, “On unconditional edge tests for some families of graphs”, Diskretn. Anal. Issled. Oper. Ser. 1, vol. 10, no. 4, pp. 8–30.
10. Ermakova, D. I. 2008, “On the complexity of realization a system of constants of 𝑃3 in some bases”, Mat. Vopr. Kibern., vol. 17, pp. 137–158.
11. Zakirov, N. R. 2006, “On representing an arbitrary algebraic number as a periodic branching continuous fraction”, Mat. Vopr. Kibern., vol. 15, pp. 65–78.
12. Zakirov, N. R. 2007, “On the representation of algebraic numbers by periodic branching continued fractions”, Moscow Univ. Math. Bull., vol. 62, no. 4, pp. 148–152.
13. Alekseyev, V. M. (ed.) 1977, Izbrannye zadachi iz zhurnala «American Mathematical Monthly» [Favorites problems from the journal «American Mathematical Monthly»], Mir, Moscow.
14. Karpova, N. A. 1970, “Some properties of Shannon functions”, Math. Notes, vol. 8, no. 5, pp. 843– 849.
15. Kochergin, A. V. 2011, “On the depth of functions of 𝑘-valued logic in infinite bases”, Moscow Univ. Math. Bull., vol. 66, no. 1, pp. 20–24.
16. Kochergin, A. V. 2013, “Depth of functions of 𝑘-valued logic in finite bases”, Moscow Univ. Math. Bull., vol. 68, no. 1, pp. 77–79.
17. Kochergin, A. V. 2018, “On the depth of 𝑘-valued logic functions over arbitrary bases”, J. Math. Sci., vol. 233, no. 1, pp. 100–102.
18. Kochergin, V. V. & Mikhailovich, A. V. 2018, “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Ind. Math., vol. 12, pp. 40–58.
19. Kochergin, V. V. & Mikhailovich, A. V. 2019, “Circuit complexity of k-valued logic functions in one infinite basis”, Comput. Math. and Mod., vol. 30, no. 1, pp. 13–25.
20. Kuz’min, V. A. 1976, “Bound of realization complexity of logic algebra functions by the simplest types of binary programs”, Metody diskretnogo analiza v teorii kodov i skhem, vol. 29, pp. 11–39.
21. Kuznetsov, A. V. 1979, “On the means for detecting non-derivability or inexpressibility”, Logicheskij Vyvod, Nauka, Moscow, pp. 5–33.
22. Kuznetsov, Yu. V. 1986, “On classes of Boolean functions which are invariant with respect to identification of variables”, Sov. Math., Dokl., vol. 34, pp. 339–344.
23. Kuznetsov, Yu. V. 1987, Issledovanie invariantnyh klassov, svyazannyh s funkcional’nymi sistemami [Study of invariant classes related to functional systems], Dissertation for the Degree of Candidate of Physical and Mathematical Sciences, MGU, Moscow.
24. Lozhkin, S. A. 1976, “Asymptotic behavior of Shannon functions for the delays of schemes of functional elements”, Math. Notes, vol. 19, no. 6, pp. 548–555.
25. Lupanov, O. B. 1958, “A method of circuit synthesis”, Izvesitya VUZ, Radiofiz., vol. 1, pp. 120–140.
26. Lupanov, O. B. 1963, “On the synthesis of some classes of control systems”, Probl. Kibern., vol. 10, pp. 63–97.
27. Lupanov, O. B. 1973, “The synthesis of circuits from threshold elements”, Probl. Kibern., vol. 26, pp. 109–140.
28. Lupanov, O. B. 1984, Asimptoticheskie Ocenki Slozhnosti Upravlyayushchih Sistem [Asymptotic Estimates of Complexity of Control Systems], MSU, Moscow.
29. Lyapunov, A. A. 1958, “On logic circuits of programs”, Probl. Kibern., vol. 1, pp. 46–74.
30. Markov, A. A. 1958, “On the inversion complexity of a system of functions”, J. ACM, vol. 5, no. 4, pp. 331–334.
31. Markov, A. A. 1963, “On the inversion complexity of systems of Boolean functions”, Sov. Math. Dokl., vol. 4, pp. 694–696.
32. Mikhailets, E. V. 2008, “A rank of implicit representations over a class of three-valued logic functions”, Moscow Univ. Math. Bull., vol. 63, no. 5, pp. 221–223.
33. Nechiporuk, E. I. 1962, “On the complexity of circuits in some bases containing nontrivial elements with zero weights”, Probl. Kibern., vol. 8, pp. 123–160.
34. Nechiporuk, E. I. 1964, “On a synthesis of schemes of threshold elements”, Probl. Kibern., vol. 11, pp. 49–62.
35. Orekhova, E. A. 2003, “On a criterion for implicit completeness in three-valued logic”, Mat. Vopr. Kibern., vol. 12, pp. 27–74.
36. Orekhova, E. A. 2003, “A criterion for the implicit Sheffer property in three-valued logic”, Diskretn. Anal. Issled. Oper. Ser. 1 , vol. 10, no. 3, pp. 82–105.
37. Podolskaya, O. V. 2013, “Lower estimates of circuit complexity in the basis of antichain functions”, Moscow Univ. Math. Bull., vol. 68, no. 2, pp. 98–103.
38. Podolskaya, O. V. 2016, “Circuit complexity of symmetric Boolean functions in antichain basis”, Discrete Math. Appl., vol. 26, no. 1, pp. 31–39.
39. Podolskaya, O. V. 2016, “On bounds of Shannon functions of circuit complexity in some infinite bases”, Proc. Academician O. B. Lupanov XII International Seminar “Discrete Mathematics and
40. its Applications“, pp. 150–152.
41. Proskuryakov, A. I. 2002, “On the complexity of the realization of some functions by networks of elements that perform analytic operations”, Mat. Vopr. Kibern., vol. 11, pp. 262–269.
42. Sapozhenko, A. A. & Lozhkin, S. A. 1983, “Methods of logical design and evaluation of the complexity of circuits on complementary MOSFETs”, Mikroelektronika, vol. 12, no. 1, pp. 42– 47.
43. Starostin, M. V., 2018, “Implicit precomplete classes and a criterion of implicit completeness in the three-valued logic”, Moscow Univ. Math. Bull., vol. 73, no. 2, pp. 82–84.
44. Starostin, M. V. 2021, “Implicit completeness criterion in three-valued logic in terms of maximal classes”. Available at: https://arxiv.org/abs/2103.16631
45. Yablonskiy, S. V. 1959, “On algorithmic difficulties in the synthesis of minimal contact circuits”, Probl. Kibern., vol. 2, pp. 75–121.
46. Yablonskiy, S. V., Gavrilov G.P. & Kudryavcev V. B. 1966, Funkcii Algebry Logiki i Klassy Posta [Logic Algebra Functions and Post Classes], Nauka, Moscow.
47. Yaglom, I. M. 1968, Kak razrezat’ kvadrat? [How to cut a square?], Nauka, Moscow.
48. Yashunsky, A. D. 2007, “Asymptotics of the probability of values of random Boolean expressions”, J. Appl. Industr. Math., vol. 1, no. 4, pp. 509–531.
49. Yashunsky, A. D. 2019, “Polynomial transformations of random variables on finite sets”, Math. Notes, vol. 106, no. 6, pp. 1025–1027.49. Yashunsky, A. D. 2020, “On necessary conditions of probability limit theorems in finite algebras”,
50. Doklady Mathematics, vol. 102, no. 1, pp. 301–303.
51. Yashunsky, A. D. 2021, Issledovaniya po teorii iterativnyh sistem, porozhdaemyh konechnymi sluchajnymi velichinami. Arifmeticheskij i kombinatorno-logicheskij podhod [Research on the theory of iterative systems generated by finite random variables. Arithmetic and combinatoriallogical approach], Dissertation for the degree of doctor of physical and mathematical sciences. Available at: https://istina.msu.ru/dissertations/364891994/
52. Burks, A. W. &Wright, J. B. 1953, “Theory of logical nets”, Proc. IRE., vol. 41, no. 10, pp. 1357–1365.
53. Вuггis, S. & Willагd, R. 1987, “Finitely many primitive positive clones”, Proc. of the American Mathematical Society, vol. 101, no. 3, pp. 427–430.
54. Lee, C. Y. 1959, “Representation of switching circuits by binary-decision programs”, Bell System Technical Journal, vol. 38, no. 4, pp. 985–1000.
55. Muller, D. E. 1958, “Complexity in electronic switching circuits”, RE Trans. on Electronic Computers, vol. EC-5, no. 1, pp. 15–19.
56. Shannоn, C. E. 1941, “Mathematical theory of the differential analyzer”, J. Math, and Phys., vol. 20, no. 4, pp. 337–354.
57. Shepherdson, J. & Sturgis, H. 1963, “Computability of recursive functions”, Journal of the Association for Computer Machinery, vol. 10, no. 2, pp. 217–255.
58. Yashunskiy, A. D. 2019, “Clone-induced approximation algebras of Bernoulli distributions”, Algebra Univers., vol. 80, no. 5.
Review
For citations:
Kochergin V.V. On the papers of O. M. Kasim-Zade in field of complexity theory and theory of multivalued logics. Chebyshevskii Sbornik. 2022;23(2):121-150. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-2-121-150
Views:
315
Email this article 