Geodesic
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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2021},
     volume = {163},
     number = {3},
     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
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
%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/

[1] Shannon C., Papers in Information Theory and Cybernetics, Izd. Inostr. Lit., M., 1963, 830 pp. (In Russian)

[2] Gribok S. V., On the implementation of logic algebra functions in some classes of programs, Cand. Phys.-Math. Sci. Diss., M., 2003, 90 pp. (In Russian)

[3] Zhukov V. V., “Ways of synthesizing binary programs admitting recursive call of procedures”, Moscow Univ. Comput. Math. Cybern., 45:3 (2021), 87–95 | DOI | MR | Zbl

[4] Zhukov V. V., “Synthesis of some types of binary programs admitting recursive call of procedures with limited depth”, Problems of Theoretical Cybernetics, Proc. XIX Int. Conf., Kazan. Fed. Univ., Kazan, 2021, 53–55 (In Russian)

[5] Lozhkin S. A., Lectures on the Principles of Cybernetics, Izd. Itd. Fak. VMiK MGU, M., 2004, 235 pp. (In Russian)

[6] Lupanov O. B., Asymptotic Complexity Bounds of Control Systems, Izd. MGU, M., 1984, 137 pp. (In Russian)