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

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2011 Number 1, Pages 22–26 (Mi vmumm650)

This article is cited in 3 papers

Mathematics

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

A. V. Kochergin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

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

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

UDC: 519.71

Received: 09.06.2010


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2011, 66:1, 20–24

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024