О сложности самокорректирующихся схем для одной последовательности булевых функций / В. М. Краснов. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 5. С. 55-57.
Рассматриваются k-самокорректирующиеся схемы из
функциональных элементов в базисе \{x_1\& x_2,\bar x\}.
Предполагается, что константные неисправности на выходах
элементов однотипные. Инверторы предполагаются надежными. Вес каждого инвертора
равен 1. Конъюнкторы могут быть надежными и ненадежными. Каждый
надежный конъюнктор реализует конъюнкцию двух переменных и имеет вес
p>k+2. Каждый ненадежный конъюнктор в исправном состоянии
реализует конъюнкцию, а в неисправном — булеву константу \delta
(\delta\in\{0,1\}). Вес каждого ненадежного конъюнктора равен 1.
Установлено, что сложность реализации такими схемами монотонных
пороговых симметрических функций
f_2^n(x_1,\dots,x_n)=\bigvee\limits_{\scriptscriptstyle 1\leq i < j
\leq n}x_ix_j, n=3,4,\ldots, асимптотически равна
(k+3)n.
Ключевые слова:
схемы из функциональных элементов, сложность схемы, булевы функции.
