Synthesis of binary programs with predominance of branching commands
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 163 (2021) no. 3, pp. 276-290
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
In this article, a model of binary programs that implement the logic algebra functions (Boolean functions) is considered. These programs consist of one or several modules, which include the following three types of commands: computational, branching, and procedure call commands. The model under study also allows recursive procedure calls. It means that the procedures can call themselves, either directly or through other procedures, during the program execution. The concept of an arbitrary basis for branching commands is introduced as a generalization of the known models. The methods for calculating the lower and upper bounds of the Shannon function for the complexity of Boolean functions implementation in the class of binary programs are presented. The complexity of a binary program is understood as the integral weight of all commands of its subprograms. The methods allow establishing the Shannon function asymptotic bounds in the case when the specific weight of branching commands is less than the specific weight of computational commands. The obtained results contribute substantially to further development of the theory of synthesis and complexity of discrete control systems.
Keywords:
binary programs, Shannon function, asymptotic bounds.
@article{UZKU_2021_163_3_a3,
author = {V. V. Zhukov},
title = {Synthesis of binary programs with predominance of branching commands},
journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
pages = {276--290},
publisher = {mathdoc},
volume = {163},
number = {3},
year = {2021},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/UZKU_2021_163_3_a3/}
}
TY - JOUR AU - V. V. Zhukov TI - Synthesis of binary programs with predominance of branching commands JO - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki PY - 2021 SP - 276 EP - 290 VL - 163 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/UZKU_2021_163_3_a3/ LA - ru ID - UZKU_2021_163_3_a3 ER -
%0 Journal Article %A V. V. Zhukov %T Synthesis of binary programs with predominance of branching commands %J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki %D 2021 %P 276-290 %V 163 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/UZKU_2021_163_3_a3/ %G ru %F UZKU_2021_163_3_a3
V. V. Zhukov. Synthesis of binary programs with predominance of branching commands. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 163 (2021) no. 3, pp. 276-290. http://geodesic.mathdoc.fr/item/UZKU_2021_163_3_a3/