Данный сайт более не обновляется.
Актуальная информация - по адресу vestnik.math.msu.su

УДК 511

Инверсионная сложность самокорректирующихся схем для одной последовательности булевых функций  / Т. И. Краснова // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2012. № 3. С. 58-61.

Для последовательности булевых функций ƒ_n²(x₁,...,x_n)=∨_{(1≤i<j≤n)}x_ix_j при любых фиксированных k, p ≥ 1 и растущем n установлена асимптотика L_k^-(ƒ_n²)∼n min{k+1, p}, где L_k^-(ƒ_n²) - инверсионная сложность реализации функции ƒ_n² k-самокорректирующимися схемами из функциональных элементов в базисе B={&,-}, p - вес надежного инвертора.

Ключевые слова: схемы из функциональных элементов, монотонные симметрические булевы функции, инверсионная сложность, самокорректирующаяся схема.

Библиогр. 6.