On the depth of functions of $k$-valued logic in infinite bases

A. V. Kochergin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2011), pp. 22-26

Résumé

The implementation 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 implement every function of the $k$-valued logic of $n$ variables by a circuit over $B$). It is shown that for each fixed $k\ge2$ and for any infinite complete basis $B$ either there exists a constant $\alpha\ge1$ such that $D_B(n)=\alpha$ for all sufficiently large $n$, or there exist constans $\beta$ ($\beta>0$), $\gamma$, $\delta$ such that $\beta\log_2n\le D_B(n)\le\gamma\log_2n\delta$ for all $n$.