Depth of Functions of the k-Valued Logic in Infinite Bases / Kochergin A.V. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2011. ? 1. P. 22-26 [Moscow Univ. Math. Bulletin. Vol. 66, No 1, 2011. P. 20-24].

The realization of functions of the k-valued logic by circuits is considered over an arbitrary infinite complete basis B. The Shannon function D_B(n) of the circuit depth over B is examined (for any positive integer n the value D_B(n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B). It is shown that for each fixed k ≥ 2 and for any infinite complete basis B either there exists a constant α ≥ 1 such that D_B(n) = α for all sufficiently large n, or there exist constants β (β > 0), γ, δ such that β log₂n ≤ D_B(n) ≤ γ log₂n + δ for all n.

Key words: k-valued logics, circuit depth, infinite basis.