RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013 Number 1, Pages 56–59 (Mi vmumm380)

This article is cited in 3 papers

Short notes

Depth of functions of $k$-valued logic in finite bases

A. V. Kochergin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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$.

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

UDC: 519.71

Received: 20.06.2012


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2013, 68:1, 77–79

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024