Some sufficient conditions for uniformness of systems of multi-valued logic functions / P. B. Tarasov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 5. P. 41-46 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].

For any finite system A of functions of k-valued logic taking values in the set E_s={0,…,s-1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set E_s contains a near-unanimity function, it is proved that there exists constants c and d such that for an arbitrary function f ∈ [A] the depth D_A(f) and the complexity L_A(f) of f in the class of formulas over A satisfy the relation D_A(f) ≤ c log₂ L_A(f) + d.

Key words: uniform systems, many-valued logic, polynomially equivalent, near-unanimity function.