This article is cited in 1 paper

Short notes

Inversion complexity of self-correcting circuits for a certain sequence of Boolean functions

T. I. Krasnova

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: It is stated that the inversion complexity $L_k^{-}(f^n_2)$ of monotone symmetric Boolean functions $f_2^n(x_1,\ldots,x_n)=\bigvee \limits_{1\leq i<j\leq n}x_i x_j$ by $k$-self-correcting schemes in the basis $B=\{\&,-\}$ for growing $n$ asymptotically equals $n\min\{k+1,p\}$ when the price of a reliable inventor $p\geq1$ and $k$ are fixed.

Key words: circuits of functional elements, monotonic symmetric Boolean functions, inversion complexity, self-correcting circuit.

UDC: 511

Received: 20.06.2011

 English version: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2012, 67:3, 133–135

Bibliographic databases:

• 
• 
•