On Certain Approaches to Obtaining Asymptotic Complexity Estimates for the Implementation of Systems of Boolean Functions in the Cellular Circuit Model

Lozhkin Sergey Andreevich; Zizov Vadim Sergeevich

On Certain Approaches to Obtaining Asymptotic Complexity Estimates for the Implementation of Systems of Boolean Functions in the Cellular Circuit Model

Lozhkin S. A., Zizov V. S.

Lozhkin Sergey Andreevich

Professor, Doctor of Physics and Mathematics, Head of the Chair of Mathematical Cybernetics, Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University.

0000-0002-8952-6046

Zizov Vadim Sergeevich

Chair of Mathematical Cybernetics, Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University.

0000-0002-4053-4803

Received: 12 Feb 2026 Revised: 09 Mar 2026 Accepted: 19 Mar 2026

Published: 2026, vol. 30, issue 1, pp. 151–163

Download full text (In Russian)

Abstract

The paper addresses the problem of asymptotic complexity of implementing systems of Boolean functions in the model of cellular circuits composed of functional and switching elements. The main focus is on deriving high-accuracy asymptotic estimates for the area of cellular circuits realizing sufficiently large classes of Boolean functions. Methods for obtaining upper and lower asymptotic bounds applicable to wide classes of functions are formulated. As a consequence of these methods, high-accuracy asymptotic estimates are obtained for the system of all self-dual Boolean functions. Upper bounds are derived using a constructive approach based on reducing the considered classes of functions to universal multipoles of smaller order and subsequent modification of the corresponding cellular circuits. As a result, matching upper and lower asymptotic bounds on the circuit area are established for the class of self-dual Boolean functions, leading to an asymptotic equality for the order of growth of their implementation complexity in the cellular circuit model.

Keywords: cellular circuits, circuit area, asymptotic bounds, high-accuracy asymptotic bounds, systems of Boolean functions, self-dual functions, universal multipole

BibTeX

@article{IS-Lozhkin-Zizov2026,
  author  = {Lozhkin, Sergey Andreevich and Zizov, Vadim Sergeevich},
  title   = {{On Certain Approaches to Obtaining Asymptotic Complexity Estimates for the Implementation of Systems of Boolean Functions in the Cellular Circuit Model}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {1},
  pages   = {151--163},
}

AMSBIB

\Bibitem{IS-Lozhkin-Zizov2026}
\by S.\,A.~Lozhkin, V.\,S.~Zizov
\paper On Certain Approaches to Obtaining Asymptotic Complexity Estimates for the Implementation of Systems of Boolean Functions in the Cellular Circuit Model
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 1
\pages 151--163
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue