Synthesis of binary programs with predominance of branching commands
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 stud...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2021-12-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2021-3-4-4.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849220859764408320 |
|---|---|
| author | V.V. Zhukov |
| author_facet | V.V. Zhukov |
| author_sort | V.V. Zhukov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-bf69d67c622d4d9c8bcfda13d3f5537a |
| institution | Kabale University |
| issn | 2541-7746 2500-2198 |
| language | English |
| publishDate | 2021-12-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета: Серия Физико-математические науки |
| spelling | doaj-art-bf69d67c622d4d9c8bcfda13d3f5537a2024-12-02T08:55:13ZengKazan Federal UniversityУчёные записки Казанского университета: Серия Физико-математические науки2541-77462500-21982021-12-011633-427629010.26907/2541-7746.2021.3-4.276-290Synthesis of binary programs with predominance of branching commandsV.V. Zhukov0Moscow State University, Moscow, 119991 RussiaIn 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.https://kpfu.ru/uz-eng-phm-2021-3-4-4.htmlbinary programsshannon functionasymptotic bounds |
| spellingShingle | V.V. Zhukov Synthesis of binary programs with predominance of branching commands Учёные записки Казанского университета: Серия Физико-математические науки binary programs shannon function asymptotic bounds |
| title | Synthesis of binary programs with predominance of branching commands |
| title_full | Synthesis of binary programs with predominance of branching commands |
| title_fullStr | Synthesis of binary programs with predominance of branching commands |
| title_full_unstemmed | Synthesis of binary programs with predominance of branching commands |
| title_short | Synthesis of binary programs with predominance of branching commands |
| title_sort | synthesis of binary programs with predominance of branching commands |
| topic | binary programs shannon function asymptotic bounds |
| url | https://kpfu.ru/uz-eng-phm-2021-3-4-4.html |
| work_keys_str_mv | AT vvzhukov synthesisofbinaryprogramswithpredominanceofbranchingcommands |