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-блок, векторні булеві функції