|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2011, Number 1, Pages 22–26
(Mi vmumm650)
|
|
|
|
This article is cited in 3 scientific papers (total 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.
Received: 09.06.2010
Citation:
A. V. Kochergin, “On the depth of functions of $k$-valued logic in infinite bases”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2011, no. 1, 22–26; Moscow University Mathematics Bulletin, 66:1 (2011), 20–24
Linking options:
https://www.mathnet.ru/eng/vmumm650 https://www.mathnet.ru/eng/vmumm/y2011/i1/p22
|
Statistics & downloads: |
Abstract page: | 50 | Full-text PDF : | 28 |
|