Geodesic
On the recognition problem for algebraic threshold functions
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 206-211.

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

We prove the existence of recognition algorithm for algebraic Boolean threshold functions by calculating upper bounds of absolute values of modulo and coefficients of a linear form. The modulo bound looks like $(n+3)^{(n+5)/2}/2^{n+2}$ and the bound of algorithm complexity is O$(({{n}/{2}})^{n^2})$.
Keywords: recognition problem, algebraic threshold functions. 
@article{PDMA_2019_12_a57,
     author = {S. V. Jenevsky and S. L. Melnikov and A. N. Shurupov},
     title = {On the recognition problem for algebraic threshold functions},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {206--211},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a57/}
}
TY  - JOUR
AU  - S. V. Jenevsky
AU  - S. L. Melnikov
AU  - A. N. Shurupov
TI  - On the recognition problem for algebraic threshold functions
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 206
EP  - 211
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a57/
LA  - ru
ID  - PDMA_2019_12_a57
ER  - 
%0 Journal Article
%A S. V. Jenevsky
%A S. L. Melnikov
%A A. N. Shurupov
%T On the recognition problem for algebraic threshold functions
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 206-211
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a57/
%G ru
%F PDMA_2019_12_a57
S. V. Jenevsky; S. L. Melnikov; A. N. Shurupov. On the recognition problem for algebraic threshold functions. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 206-211. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a57/

[1] Soshin D. A., “Konstruktivnyi metod sinteza sbalansirovannykh $k$-znachnykh algebraicheskikh porogovykh funktsii”, Computational Nanotechnology, 2015, no. 4, 31–36

[2] Zolotykh N. Yu., Rasshifrovka porogovykh i blizkikh k nim porogovykh funktsii mnogoznachnoi logiki, dis. \ldots kand. fiz.-mat. nauk, Nizhegorodskii gosuniversitet, N. Novgorod, 1998

[3] Burdelev A. V., Nikonov V. G., “O postroenii analiticheskogo zadaniya $k$-znachnoi porogovoi funktsii”, Computational Nanotechnology, 2015, no. 2, 5–13

[4] Crama Y., Hammer P. L., Boolean Functions: Theory, Algorithms and Applications, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2011 | MR | Zbl

[5] Antony M., Discrete Mathematics of Neural Networks: Selected Topics, SIAM, Philadelphia, 2001 | MR