The asymptotically best method for synthesizing limited-depth Boolean recursive schemes |
| |
Authors: | V. V. Zhukov |
| |
Affiliation: | 1.Faculty of Computational Mathematics and Cyberntics,Moscow State University,Moscow,Russia |
| |
Abstract: | A model of limited-depth recursive schemes for the functions of Boolean algebra (Boolean functions), constructed from multi-output functional elements, is considered. A lower estimate of the Shannon function for the complexity of schemes of this class is derived. Upper estimates for the complexity of some specific functions and systems of functions in this class of schemes are obtained. A method is proposed for synthesizing schemes of this class for arbitrary functions that allow us (using the derived lower estimate) to determine the asymptotics of the Shannon function for their complexity. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|