Email this article High-Accuracy Bounds of the Shannon Function for Formula Complexity in Bases with Direct and Iterative Variables
- Authors: Konovodov V.A.1, Lozhkin S.A.2
-
Affiliations:
- Yandeks Technology
- Faculty of Computational Mathematics and Cybernetics, Moscow State University
- Issue: Vol 30, No 1 (2019)
- Pages: 26-35
- Section: Article
- URL: https://journals.rcsi.science/1046-283X/article/view/247822
- DOI: https://doi.org/10.1007/s10598-019-09431-4
- ID: 247822
Cite item
Open Access
Access granted
Subscription Access
Abstract
We consider the realization of Boolean functions by formulas with restrictions on superpositions of basis functions such that superposition is allowed only by iterative variables. For a number of special symmetrical bases, we establish new high-accuracy bounds of the Shannon function L(n) for the complexity of realization of Boolean functions dependent on n direct variables.
Keywords
About the authors
V. A. Konovodov
Yandeks Technology
Author for correspondence.
Email: vkonovodov@gmail.com
Russian Federation, Moscow
S. A. Lozhkin
Faculty of Computational Mathematics and Cybernetics, Moscow State University
Email: vkonovodov@gmail.com
Russian Federation, Moscow
Supplementary files
