KIAM Main page Web Library  •  Publication Searh  Русский 

Conference material: "Academician O.B. Lupanov XIV International Scientific Seminar "Discrete Mathematics and Its Applications" (20-25 June 2022, Moscow)"
Authors: Zhukov V.V.
Synthesis method and complexity bounds for programms with some structural restrictions
The work is devoted to the study of various classes of software circuits. type that implement Boolean functions, and the establishment of asymptotic estimates of Shannon functions for the complexity of implementing Boolean functions in schema classes. Models are introduced and explored reflexive-recursive schemes of functional elements and programs, in which recursive procedure calls are allowed. Influence is being explored the depth of recursion on the complexity of the implementation of the functions of the algebra of logic. For considered models, methods for the synthesis of schemes and programs are proposed, implementing arbitrary Boolean functions, as well as getting methods lower bounds for the Shannon function for the complexity of implementing Boolean functions, with the help of which, under certain restrictions, it was the asymptotic behavior of the corresponding Shannon functions is established.
Boolean functions, boolean circuits
Publication language: russian,  pages: 4 (p. 65-68)
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Zhukov Vladimir Vladimirovich,  Lomonosov Moscow State University