On the Complexity of Generalized Polynomials
of k-Valued Functions

S. N. Selezneva and A. B. Dainyak

Department of Mathematical Cybernetics, Faculty of Computational Mathematics and Cybernetics,
Moscow State University, Moscow, 119991 Russia

e-mail: mk@cs.msu.su

Received September 17, 2007

Abstract—Specification of k-valued functions with generalized polynomials (for simple k) is consid-
ered. A generalized polynomial is a mod k polynomial in which each variable may also occur with one
or several Post negations. The upper and lower estimates of the complexity of generalized polynomials
are found for k-valued functions.

DOI:10.3103/S0278641908030060

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.