1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 1(108)'2013
  5. ПРОВЕРКА ВЕКТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ НА ОГРАНИЧЕННУЮ РАСШИРЕННО АФИННУЮ ЭКВИВАЛЕНТНОСТЬ

ПРОВЕРКА ВЕКТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ НА ОГРАНИЧЕННУЮ РАСШИРЕННО АФИННУЮ ЭКВИВАЛЕНТНОСТЬ

Л. Будагян, А. Казимиров
Аннотации на языках:

В статье представлены алгоритмы для решения проблемы ограниченной расширенно аффинной эквивалентности (ОРА-эквивалентности) в случае произвольной m-мерной векторной булевой функции от n переменных. Лучший из предложенных алгоритмов имеет сложность 2n 1O(2 ) для ОРА-эквивалентности 1 2 3 1F(x) M G(x V ) M x V      . Сложности разработанных методов сравниваются с предложенными ранее Бирюковым и др. алгоритмами для решения проблем линейных и аффинных эквивалентностей.
Ключевые слова: РА-эквивалентность, матричное представление, S-блок, векторные булевы функции