Asymptotically best method for synthesis of Boolean recursive circuits

作     者：Zhukov, Vladimir V. Lozhkin, Sergey A. 

作者机构：Lomonosov Moscow State Univ Moscow Russia 

出 版 物：《DISCRETE MATHEMATICS AND APPLICATIONS》 (离散数学及应用)

年 卷 期：2020年第30卷第2期

页      面：137-146页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Russian Foundation for Basic Research [18-01-00800] 

主　　题：recursive circuits of gates complexity of Boolean functions Shannon function asymptotic estimates 

摘      要：Models of multi-output and scalar recursive Boolean circuits of bounded depth in an arbitrary basis are considered. Methods for lower and upper estimates for the Shannon function for the complexity of circuits of these classes are provided. Based on these methods, an asymptotic formula for the Shannon function is put forward. Moreover, in the above classes of recursive circuits, upper estimates for the complexity of implementation of some functions and systems of functions used in applications are obtained.