Geodesic
On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$
Diskretnaya Matematika, Tome 26 (2014) no. 3, pp. 3-9.

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

Polynomial normal forms for functions of $k$-valued logics (for prime values of $k$) are considered. A polynomial normal form modulo $k$ (p.n.f.) is the sum modulo $k$ of products of variables, or variables with one or several Post negations, taken with some coefficients. The length of a p.n.f. is the number of distinct terms that appear in the form with nonzero coefficients. If $k$ is a prime number, then each function of $k$-valued logic may be represented by various p.n.f. The length of a function of $k$-valued logic in the class of p.n.f. is the minimum length of a p.n.f. representing this function. The Shannon function $L_k^{p.n.f.}(n)$ of the length of functions of $k$-valued logic in the class of p.n.f. is the maximum length of a function in the class of p.n.f. among all $n$-ary functions of $k$-valued logic. In this work the order of growth of the Shannon function $L_k^{p.n.f}(n)$ is established (for prime values of $k$): $L_k^{p.n.f.}(n) = \Theta\left (\frac{k^n}{n}\right )$.
Keywords: function of $k$-valued logic, Boolean function, polynomial representation, polynomial normal form, length, Shannon function, shading set, covering, minimal covering. 
@article{DM_2014_26_3_a0,
     author = {M. A. Bashov and S. N. Selezneva},
     title = {On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$},
     journal = {Diskretnaya Matematika},
     pages = {3--9},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2014_26_3_a0/}
}
TY  - JOUR
AU  - M. A. Bashov
AU  - S. N. Selezneva
TI  - On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$
JO  - Diskretnaya Matematika
PY  - 2014
SP  - 3
EP  - 9
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2014_26_3_a0/
LA  - ru
ID  - DM_2014_26_3_a0
ER  - 
%0 Journal Article
%A M. A. Bashov
%A S. N. Selezneva
%T On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$
%J Diskretnaya Matematika
%D 2014
%P 3-9
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2014_26_3_a0/
%G ru
%F DM_2014_26_3_a0
M. A. Bashov; S. N. Selezneva. On the length of functions of $k$-valued logic in the class of polynomial normal forms modulo~$k$. Diskretnaya Matematika, Tome 26 (2014) no. 3, pp. 3-9. http://geodesic.mathdoc.fr/item/DM_2014_26_3_a0/

[1] Ugryumov E. P., Tsifrovaya skhemotekhnika, BKhV-Peterburg, SPb., 2004

[2] Astola J. T., Stankovich R. S., Fundamentals of Switching Theory and Logic Design, Springer, Dordrechht, The Netherlands, 2006

[3] Sasao T., Besslich P., “On the complexity of mod-2 sum PLA's”, IEEE Trans. Comput., 39:2 (1990), 262–266 | DOI

[4] Suprun V. P., “Slozhnost bulevykh funktsii v klasse kanonicheskikh polyarizovannykh polinomov”, Diskretnaya matematika, 5:2 (1993), 111–115 | MR | Zbl

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

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

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

[8] Selezneva S .N., Dainyak A. B., “O slozhnosti obobschennykh polinomov $k$-znachnykh funktsii”, Vestnik Moskovskogo universiteta. Seriya 15. Vychislitelnaya matematika i kibernetika, 2008, no. 3, 34–39 | MR

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, M., 2001

[10] Cooper J. N., Ellis R. B., Kahng A. B., “Asymmetric binary covering codes”, J. Comb. Theory Ser. A, 100:2 (2002), 232–249 | DOI | MR | Zbl

[11] Corless R. M., Gonnet G. H., Hare D. E., Jeffrey D. J., Knuth D. E., “On the Lambert $W$ function”, Adv. Comput. Math., 5:1 (1996), 329–359 | DOI | MR | Zbl