Geodesic
An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 132-138

Voir la notice de l'article provenant de la source Math-Net.Ru

A Boolean function $g$ is said to be an annihilator of a Boolean function $f$ if $fg=0$. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function $f$. In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function $f$, yields a basis of the space of its annihilators of degree not exceeding $d$. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm. 
@article{DM_2007_19_4_a8,
     author = {V. V. Baev},
     title = {An enhanced algorithm to search for low-degree annihilators for {a~Zhegalkin} polynomial},
     journal = {Diskretnaya Matematika},
     pages = {132--138},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/}
}
TY  - JOUR
AU  - V. V. Baev
TI  - An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 132
EP  - 138
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/
LA  - ru
ID  - DM_2007_19_4_a8
ER  - 
%0 Journal Article
%A V. V. Baev
%T An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial
%J Diskretnaya Matematika
%D 2007
%P 132-138
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/
%G ru
%F DM_2007_19_4_a8
V. V. Baev. An enhanced algorithm to search for low-degree annihilators for a~Zhegalkin polynomial. Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 132-138. http://geodesic.mathdoc.fr/item/DM_2007_19_4_a8/