T. I. Krasnova, “The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold <nobr>$2$</nobr>”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2014, Number 3,Pages <nobr>50

This article is cited in 2 papers

Short notes

The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold $2$

T. I. Krasnova

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: It is stated that the conjunction 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$ realized by $k$-self-correcting circuits in the basis $B=\{\&,-\}$ asymptotically equals $(k+2)n$ for growing $n$ when the price of a reliable conjunctor is $\geq k+2$.

Key words: circuits, monotonic symmetric Boolean functions, conjunction complexity, self-correcting circuit.

UDC: 511

Received: 13.04.2012