Geodesic
Upper bound for the length of functions over a finite field in the class of pseudopolynomials
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 5, pp. 899-904 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An exclusive-OR sum of pseudoproducts (ESPP), or a pseudopolynomial over a finite field is a sum of products of linear functions. The length of an ESPP is defined as the number of its pairwise distinct summands. The length of a function $f$ over this field in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function $L_k^{\text{ESPP}}(n)$ on the set of functions over a finite field of $k$ elements in the class of ESPPs is considered; it is defined as the maximum length of a function of n variables over this field in the class of ESPPs. It is proved that $L_k^{\text{ESPP}}(n)=O(k^n/n^2)$. 
@article{ZVMMF_2017_57_5_a12,
     author = {S. N. Selezneva},
     title = {Upper bound for the length of functions over a finite field in the class of pseudopolynomials},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {899--904},
     year = {2017},
     volume = {57},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_5_a12/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - Upper bound for the length of functions over a finite field in the class of pseudopolynomials
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2017
SP  - 899
EP  - 904
VL  - 57
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_5_a12/
LA  - ru
ID  - ZVMMF_2017_57_5_a12
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T Upper bound for the length of functions over a finite field in the class of pseudopolynomials
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2017
%P 899-904
%V 57
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_5_a12/
%G ru
%F ZVMMF_2017_57_5_a12
S. N. Selezneva. Upper bound for the length of functions over a finite field in the class of pseudopolynomials. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 5, pp. 899-904. http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_5_a12/

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

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

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

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

[5] Ishikawa R., Hirayama T., Koda G., Shimizu K., “New three-level Boolean expression based on EXOR gates”, IEICE Trans. Inf. Syst., E87-D:5 (2004), 1214–1222

[6] Selezneva S. N., “O dline bulevykh funktsii v klasse polinomialnykh form s affinnymi mnozhitelyami v slagaemykh”, Vestn. Moskovskogo un-ta. Ser. 15. Vychisl. matem. i kibernetika, 2014, no. 2, 34–38

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

[8] Selezneva S. N., “O slozhnosti polyarizovannykh polinomov funktsii mnogoznachnykh logik, zavisyaschikh ot odnoi peremennoi”, Diskretnaya matem., 16:2 (2004), 117–121 | DOI

[9] Zinchenko A. S., Panteleev V. I., “Polinomialnye operatornye predstavleniya $k$-znachnoi logiki”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 13:3 (2006), 13–26

[10] Selezneva S. N., Dainyak A. B., “O slozhnosti obobschennykh polinomov $k$-znachnykh funktsii”, Vestn. Moskovskogo un-ta. Ser. 15. Vychisl. matem. i kibernetika, 3 (2008), 34–39

[11] Selezneva S. N., “O slozhnosti obobschenno-polyarizovannykh polinomov $k$-znachnykh funktsii”, Diskretnaya matem., 21:4 (2009), 20–29 | DOI | Zbl

[12] Markelov N. K., “Nizhnyaya otsenka slozhnosti funktsii trekhznachnoi logiki v klasse polyarizovannykh polinomov”, Vestn. Moskovskogo un-ta. Ser. 15. Vychisl. matem. i kibernetika, 3 (2012), 40–45

[13] Bashov M. A., Selezneva S. N., “O dline funktsii $k$-znachnoi logiki v klasse polinomialnykh normalnykh form po modulyu $k$”, Diskretnaya matem., 26:3 (2014), 3–9 | DOI

[14] Balyuk A. S., “O verkhnei otsenke slozhnosti zadaniya kvazipolinomami funktsii nad konechnymi polyami”, Izvestiya Irkutskogo gos. un-ta. Ser.: Matem., 10 (2014), 3–12

[15] Balyuk A. S., Yanushkovskii G. V., “Verkhnie otsenki slozhnosti funktsii nad konechnymi polyami v klassakh kronekerovykh form”, Izvestiya Irkutskogo gos. un-ta. Ser.: Matem., 14 (2015), 3–17

[16] Yablonskii S. V., Gavrilov G. P., Nabebin A. A., Predpolnye klassy v mnogoznachnykh logikakh, Izd-vo MEI, M., 1997

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