Exponential codimension growth of P.I. algebras: an exact estimate // Adv. <...> Codimensions of algebras and growth functions // Adv. <...> An example of a variety of Lie algebras with a fractional exponent // J. <...> Exponents of varieties of Lie algebras with a nilpotent commutator subalgebra // Communs Algebra. <...> Целочисленность экспонент роста тождеств конечномерных алгебр Ли // Изв. <...> Поступила в редакцию 27.02.2011 УДК 519.95 О ЕДИНИЧНЫХ ПРОВЕРЯЮЩИХ ТЕСТАХ ДЛЯ КОНСТАНТНЫХ НЕИСПРАВНОСТЕЙ НА ВЫХОДАХ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С. С. <...> Коляда1 Рассматриваются схемы в базисах из функциональных элементов, имеющих не более двух входов. <...> Устанавливается возможность реализации любой булевой функции от n переменных схемой, допускающей при константных неисправностях единичные проверяющие тесты линейной по n длины. <...> Ключевые слова: схемы из функциональных элементов, единичные проверяющие тесты, константные неисправности. <...> В работе рассматривается задача построения легкотестируемых схем из функциональных элементов [1] в базисах из элементов, имеющих не более двух входов. <...> Допускаются единичные произвольные константные неисправности на выходах элементов [2–4], когда в неисправное состояние может перейти ровно один элемент схемы, который вне зависимости от того, что подается на его входы, выдает некоторую булеву константу δ,где δ ∈{0, 1}. <...> Схему x). σl} называется единичным проверяющим тестом для схемы S,реаσ из неизбыточная схема в базисе Bi, реализующая данную функцию и допускающая единичный проверяющий тест, длина которого не превосходит n+3. <...> 1Коляда Сергей Сергеевич — асп. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: kolyadass@mail.ru. <...> №6 Аналогичная оценка для схем в базисеЖегалкина получена в [7], однако метод построения легкотестируемых схем из [7] годится только для базисов, содержащих конъюнкцию и линейную функцию(x⊕y или x⊕y ⊕1). <...> Доказательство теоремы проводится конструктивно, т.е. при каждом i для произвольной булевой функции f(x1,. ,xn) строится схема в базисе Bi и представляется единичный проверяющий тест, удовлетворяющий условиям теоремы. <...> Без ограничения общности можно <...>