Geodesic
On the complexity of representation of $k$-valued functions by generalised polarised polynomials
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 20-29 
S. N. Selezneva. On the complexity of representation of $k$-valued functions by generalised polarised polynomials. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 20-29. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a1/
@article{DM_2009_21_4_a1,
     author = {S. N. Selezneva},
     title = {On the complexity of representation of $k$-valued functions by generalised polarised polynomials},
     journal = {Diskretnaya Matematika},
     pages = {20--29},
     year = {2009},
     volume = {21},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a1/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On the complexity of representation of $k$-valued functions by generalised polarised polynomials
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 20
EP  - 29
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a1/
LA  - ru
ID  - DM_2009_21_4_a1
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On the complexity of representation of $k$-valued functions by generalised polarised polynomials
%J Diskretnaya Matematika
%D 2009
%P 20-29
%V 21
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a1/
%G ru
%F DM_2009_21_4_a1

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

We consider generalised polarised polynomials for $k$-valued functions (for prime $k$). It is proved that each $k$-valued function is represented by some unique generalised polarised polynomial for each polarisation vector. We find upper and lower bounds for the Shannon functions of degree and length of the generalised polarised polynomials of $k$-valued functions.

[1] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 2001 | MR

[2] Peryazev N. A., “Slozhnost bulevykh funktsii v klasse polinomialnykh polyarizovannykh form”, Algebra i logika, 34:3 (1995), 323–326 | MR | Zbl

[3] Selezneva S. N., “O slozhnosti predstavleniya funktsii mnogoznachnykh logik polyarizovannymi polinomami”, Diskretnaya matematika, 14:2 (2002), 48–53 | MR | Zbl

[4] Kirichenko K. D., “Verkhnyaya otsenka slozhnosti polinomialnykh normalnykh form bulevykh funktsii”, Diskretnaya matematika, 17:3 (2005), 80–88 | MR | Zbl

[5] Selezneva S. N., Dainyak A. B., “O slozhnosti obobschennykh polinomov $k$-znachnykh funktsii”, Vestnik Moskovskogo Universiteta, ser. 15: vychisl. matem. i kibern., 2008, no. 3, 34–39 | MR

[6] Alekseev V. B., Voronenko A. A., Selezneva S. N., “O slozhnosti realizatsii funktsii $k$-znachnoi logiki polyarizovannymi polinomami”, Trudy V Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem”, MGU, Moskva, 2003, 8–9

[7] Selezneva S. N., “O slozhnosti polyarizovannykh polinomov funktsii mnogoznachnykh logik, zavisyaschikh ot odnoi peremennoi”, Diskretnaya matematika, 16:2 (2004), 117–120 | MR | Zbl