On the number of functions of k-valued logic which are polynomials modulo composite k

被引：2

作者：

Selezneva S.N. ^{[1
]}

机构：

[1] Moscow State University, Moscow

来源：

Discrete Mathematics and Applications | 2017年 / 27卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

Asymptotic behaviour; Function of k-valued logic; Numeric functions; Polynomial; Polynomial function;

D O I：

10.1515/dma-2017-0002

中图分类号：

学科分类号：

摘要：

A function of k-valued logic is called polynomial if it may be represented by a polynomial modulo k. For any composite number k we propose a uniquely defined canonical form of polynomials for polynomial functions of k-valued logic depending on an arbitrary number of variables. This canonical form is used to find, for any composite k, a formula for the number of n-place polynomial functions of k-valued logic. As a corollary, for any composite k we find the asymptotic behaviour of the logarithm of the number of n-place polynomial functions of k-valued logic. © 2017 Walter de Gruyter GmbH, Berlin/Boston.

引用

页码：7 / 14

页数：7

共 10 条

[1]

Yablonskii S.V., Functional constructions in a k-valued logic, Trudy Mat. Inst. Steklov, 51, pp. 5-142, (1958)

[2]

Meshchaninov D.G., A method for constructing polynomials of k-valued logic functions, Discrete Math. Appl., 5, 4, pp. 333-346, (1995)

[3]

Selezneva S.N., A fast algorithm for the construction of polynomials modulo k for k-valued functions for composite k, Discrete Math. Appl., 21, 5-6, pp. 651-674, (2011)

[4]

Selezneva S.N., Constructing polynomials for functions over residue rings modulo a composite number in linear time, Lect. Notes Comput. Sci., 7353, pp. 303-312, (2012)

[5]

Selezneva S.N., The circuit complexity of checking polynomiality for functions over a residue ring modulo a composite number is linear, Moscow Univ. Comput. Math. and Cybernetics, 37, 1, pp. 21-25, (2013)

[6]

Niven I., Warren L.J., A generalization of Fermat's theorem, Proc. Amer. Math. Soc., 8, pp. 306-313, (1957)

[7]

Keller G., Olson F.R., Counting polynomial functions (mod pn), Duke Math. J., 35, 4, pp. 835-838, (1968)

[8]

Ayzenberg N.N., Semyon I.V., Tsitkin A.I., The cardinality of the class of k-valued logic n variables function which are represented by polynomials modulo k, Mnogoustoychivye Elementy i Ikh Primenenie, M. : Sov. Radio, pp. 79-83, (1971)

[9]

Singmaster D., On polynomial functions (mod m), J. Number Theory, 6, 5, pp. 345-352, (1974)

[10]

Ayzenberg N.N., Semyon I.V., Some criteria for the representability of k-valued logic function by polynomials modulo k, Mnogoustoychivye Elementy i Ikh Primenenie, M. : Sov. Radio, pp. 84-88, (1971)

← 1 →