RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2007, том 19, выпуск 4, страницы 132–138 (Mi dm982)

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

Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина

В. В. Баев


Аннотация: Булева функция $g$ называется аннигилятором булевой функции $f$, если $fg=0$. В некоторых задачах анализа конечных автоматов требуется найти для функции $f$ ненулевые аннигиляторы низкой алгебраической степени.
В статье представлен алгоритм M2, вычисляющий для многочлена Жегалкина функции $f$ базис пространства ее аннигиляторов степени, не превосходящей $d$. Алгоритм M2 является усовершенствованием разработанного ранее алгоритма и позволяет в ряде случаев сократить вычисления. При этом общая оценка сложности алгоритма M2 та же, что и для прежнего алгоритма.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 07-01-00154.

УДК: 519.7

Статья поступила: 18.05.2007

DOI: 10.4213/dm982


 Англоязычная версия: Discrete Mathematics and Applications, 2007, 17:5, 533–538

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


© МИАН, 2024