|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2014, Number 3, Pages 50–54
(Mi vmumm322)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Received: 13.04.2012
Citation:
T. I. Krasnova, “The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold $2$”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2014, no. 3, 50–54; Moscow University Mathematics Bulletin, 69:3 (2014), 121–124
Linking options:
https://www.mathnet.ru/eng/vmumm322 https://www.mathnet.ru/eng/vmumm/y2014/i3/p50
|
Statistics & downloads: |
Abstract page: | 102 | Full-text PDF : | 27 | References: | 28 |
|