|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2013, Number 1, Pages 56–59
(Mi vmumm380)
|
|
|
|
This article is cited in 3 scientific papers (total 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.
Received: 20.06.2012
Citation:
A. V. Kochergin, “Depth of functions of $k$-valued logic in finite bases”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013, no. 1, 56–59; Moscow University Mathematics Bulletin, 68:1 (2013), 77–79
Linking options:
https://www.mathnet.ru/eng/vmumm380 https://www.mathnet.ru/eng/vmumm/y2013/i1/p56
|
Statistics & downloads: |
Abstract page: | 159 | Full-text PDF : | 47 | References: | 39 |
|