Geodesic
Depth of functions of $k$-valued logic in finite bases
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2013), pp. 56-59 
A. V. Kochergin. Depth of functions of $k$-valued logic in finite bases. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2013), pp. 56-59. http://geodesic.mathdoc.fr/item/VMUMM_2013_1_a10/
@article{VMUMM_2013_1_a10,
     author = {A. V. Kochergin},
     title = {Depth of functions of $k$-valued logic in finite bases},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {56--59},
     year = {2013},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2013_1_a10/}
}
TY  - JOUR
AU  - A. V. Kochergin
TI  - Depth of functions of $k$-valued logic in finite bases
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2013
SP  - 56
EP  - 59
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2013_1_a10/
LA  - ru
ID  - VMUMM_2013_1_a10
ER  - 
%0 Journal Article
%A A. V. Kochergin
%T Depth of functions of $k$-valued logic in finite bases
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2013
%P 56-59
%N 1
%U http://geodesic.mathdoc.fr/item/VMUMM_2013_1_a10/
%G ru
%F VMUMM_2013_1_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

Realization of functions of $k$-valued logic by circuits is considered over an arbitrary finite complete basis $B$. Asymptotic behaviour of the Shannon function $D_B(n)$ of the circuit depth over $B$ is examined. The value $D_B(n)$ is the minimal depth sufficient to realize every function of $k$-valued logic on $n$ variables by a circuit over $B$. It is shown that for each natural $k\ge2$ and for any finite complete basis $B$ there exists a positive constant $\alpha_B$ such that $D_B(n)\sim\alpha_B n$ for $n\to\infty$.

[1] Lupanov O.B., “O skhemakh iz funktsionalnykh elementov s zaderzhkami”, Problemy kibernetiki, 1970, no. 23, 43–81

[2] Polia G., Sege G., Zadachi i teoremy iz analiza, v. 1, Nauka, M., 1978 | MR

[3] Lupanov O.B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, 1963, 64–97