RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2012, номер 3, страницы 58–61 (Mi vmumm500)

Эта публикация цитируется в 1 статье

Краткие сообщения

Инверсионная сложность самокорректирующихся схем для одной последовательности булевых функций

Т. И. Краснова

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Для последовательности булевых функций $f_2^n(x_1,\ldots,x_n)=\bigvee\limits_{1\leq i<j\leq n}x_i x_j$ при любых фиксированных $k$, $p\geq1$ и растущем $n$ установлена асимптотика $L_k^{-}(f^n_2)\thicksim n\min\{k+1,p\}$, где $L_k^{-}(f^n_2)$ — инверсионная сложность реализации функции $ f^n_2$ $k$-самокорректирующимися схемами из функциональных элементов в базисе $B=\{\&,-\} $, $p$ — вес надежного инвертора.

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

УДК: 511

Поступила в редакцию: 20.06.2011


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2012, 67:3, 133–135

Реферативные базы данных:


© МИАН, 2024