Synthesis of binary programs with predominance of branching commands

V.V. Zhukov

Moscow State University, Moscow, 119991 Russia

E-mail: zhvv117@gmail.com

Received August 23, 2021

ORIGINAL ARTICLE

Full text PDF

DOI: 10.26907/2541-7746.2021.3-4.276-290

For citation: Zhukov V.V. Synthesis of binary programs with predominance of branching commands. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2021, vol. 163, no. 3–4, pp. 276–290. doi: 10.26907/2541-7746.2021.3-4.276-290. (In Russian)

Abstract

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

Acknowledgments. This study was supported by the Ministry of Education and Science of the Russian Federation as part of the program of the Moscow Center for Fundamental and Applied Mathematics under agreement no. 075-15-2019-1621.

References

1. Shannon C. Raboty po teorii informatsii i kibernetike [Papers in Information Theory and Cybernetics]. Moscow, Izd. Inostr. Lit., 1963. 830 p. (In Russian)
2. Gribok S.V. On the implementation of logic algebra functions in some classes of programs. Cand. Phys.-Math. Sci. Diss. Moscow, 2003. 90 p. (In Russian)
3. Zhukov V.V. Ways of synthesizing binary programs admitting recursive call of procedures. Moscow Univ. Comput. Math. Cybern., 2021, vol. 45, no. 3, pp. 87–95. doi: 10.3103/S0278641921030079.
4. Zhukov V.V. Synthesis of some types of binary programs admitting recursive call of procedures with limited depth. Problemy teoreticheskoi kibernetiki: Materialy XIX mezhdunar. konf. [Problems of Theoretical Cybernetics: Proc. XIX Int. Conf.]. Kazan, Kazan. Fed. Univ., 2021, pp. 53-55. (In Russian)
5. Lozhkin S.A. Lektsii po osnovam kibernetiki [Lectures on the Principles of Cybernetics]. Moscow, Izd. Itd. Fak. VMiK MGU, 2004. 235 p. (In Russian)
6. Lupanov O.B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotic Complexity Bounds of Control Systems]. Moscow, Izd. MGU, 1984. 137 p. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.