Geodesic
The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 285-299 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

An approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced. The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of $n$-ary functions over an arbitrary finite field $\mathbb F_q$. The value found is equal to $q^{n-1}$. The previously known result for Boolean functions was generalized.
Keywords: finite field, computational complexity, free-Kronecker forms, pseudo-Kronecker forms. 
@article{UZKU_2020_162_3_a3,
     author = {A. S. Baliuk},
     title = {The complexity of {pseudo-Kronecker} and {free-Kronecker} forms of functions over finite fields},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {285--299},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a3/}
}
TY  - JOUR
AU  - A. S. Baliuk
TI  - The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 285
EP  - 299
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a3/
LA  - ru
ID  - UZKU_2020_162_3_a3
ER  - 
%0 Journal Article
%A A. S. Baliuk
%T The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 285-299
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a3/
%G ru
%F UZKU_2020_162_3_a3
A. S. Baliuk. The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 285-299. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a3/

[1] Green D. H., “Families of Reed-Muller canonical forms”, Int. J. Electron., 70:2 (1991), 259–280 | DOI | MR | Zbl

[2] Sasao T., “Representations of logic functions using EXOR operators”, Representations of Discrete Functions, Kluwer Acad. Publ., Boston, 1996, 29–54 | DOI | Zbl

[3] Ho P., Perkowski M., “Free Kronecker decision diagrams and their application to Atmel 6000 series FPGA mapping”, Proc. Conf. on European Design Automation (Grenoble, France, 1994), 8–13 | DOI

[4] Al-Rabadi A. N., “An extended Green-Sasao hierarchy of canonical ternary Galois forms and Universal Logic Modules”, Facta Univ., Ser.: Electron. Energ., 30:1 (2017), 49–66 | DOI

[5] Vinokurov S. F., Peryazev N. A. (eds.), Selected Problems in the Theory of Boolean Functions, Fizmatlit, M., 2001, 192 pp. (In Russian)

[6] Baliuk A. S., Vinokurov S. F., “The Shannon function for some classes of operator polynomial forms”, Optim., Upr., Intellekt, 5:1 (2000), 111–121 (In Russian)

[7] Baliuk A. S., Zinchenko A. S., “Lower bounds of complexity for polarized polynomials over finite fields”, Sib. Math. J., 60:1 (2019), 1–9 | DOI | MR

[8] Mullen G. L., Panarino D., Handbook of Finite Fields, Chapman and Hall/CRC, N. Y., 2013, 1068 pp. | DOI

[9] Baluck A. S., Vinokurov S. F., “Classes of operator forms”, 5th Int. Workshop on Boolean Problems (Freiberg, Germany, 2002), 76–83

[10] Peryazev N. A., “Complexity of Boolean functions in the class of polarized polynomial forms”, Algebra Logic, 34:3 (1995), 177–179 | DOI | MR | Zbl

[11] Selezneva S. N., “On the complexity of the representation of functions of many-valued logics by polarized polynomials”, Discrete Math. Appl., 12:3 (2002), 229–234 | DOI | MR | Zbl

[12] Alekseev V. B., Voronenko A. A., Selezneva S. N., “On the complexity of realization of functions of a $k$-valued logic with polarized polynomials”, Proc. 5th Int. Conf. "Discrete Models in Theory of Control Systems" (Ratmino, 2003), 8–9 (In Russian)

[13] Baliuk A. S., Yanushkovsky G. V., “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, Izv. Irkutsk. Gos. Univ. Ser. “Mat.”, 2015, no. 14, 3–17 (In Russian) | Zbl

[14] Kazimirov A. S., Reymerov S.Yu., “On upper bounds of the complexity of functions over non-prime finite fields in some classes of polarized polynomials”, Izv. Irkutsk. Gos. Univ. Ser. “Mat.”, 2016, no. 17, 37–45 (In Russian) | Zbl

[15] Markelov N. K., “A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials”, Moscow Univ. Comput. Math. Cybern., 36:3 (2012), 150–154 | DOI | MR | Zbl

[16] Selezneva S. N., “On the complexity of k-valued functions in a class of polynomials”, Problems of Theoretical Cybernetics, Proc. XVI Int. Conf. (Nizhny Novgorod, 2011), 430–434 (In Russian)

[17] Baliuk A. S., “On upper bound of the complexity of quasi polynomial representations of functions over finite fields”, Izv. Irkutsk. Gos. Univ. Ser. “Mat.”, 2014, no. 10, 3–12 (In Russian) | Zbl

[18] Baliuk A. S., “Methods for assessing the complexity of Kronecker forms of functions over finite fields”, Proc. X Int. Conf. “Discrete Models in the Theory of Control Systems” (Moscow and Moscow Region, 2018), 46–49 (In Russian)

[19] Zierler N., “Linear recurring sequences”, J. Soc. Ind. Appl. Math., 7:1 (1959), 31–48 | DOI | MR