|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2013, Number 5, Pages 41–46
(Mi vmumm437)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
Certain sufficient conditions of uniformity for systems of functions of many-valued logic
P. B. Tarasov Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
For any finite system $A$ of functions of $k$-valued logic taking values in the set $E_s={\{0,1,\ldots, s-1\}}$, $k\geq s\geq2$, such that the closed class generated by restriction of functions from $A$ on the set $E_s$ contains a near-unanimity function, it is proved that there exists constants $c$ and $d$ such that for an arbitrary function $f \in [A]$ the depth $D_A(f)$ and the complexity $L_A(f)$ of $f$ in the class of formulas over $A$ satisfy the relation ${D_A(f) \leq c\log_2 L_A(f)+d}$.
Key words:
uniform systems, many-valued logic, polynomially equivalent, near-unanimity function.
Received: 22.02.2013
Citation:
P. B. Tarasov, “Certain sufficient conditions of uniformity for systems of functions of many-valued logic”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013, no. 5, 41–46; Moscow University Mathematics Bulletin, 68:5 (2013), 253–257
Linking options:
https://www.mathnet.ru/eng/vmumm437 https://www.mathnet.ru/eng/vmumm/y2013/i5/p41
|
Statistics & downloads: |
Abstract page: | 96 | Full-text PDF : | 39 | References: | 25 |
|