Geodesic
Several conditions for uniformity of a finite system of many-valued logic
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 123-131 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the relation between depth and complexity of many-valued logic functions over finite functional systems. The functional system $A$ is called quasi-uniform if there exist constants $c$ and $d$ such that for an arbitrary function $f$ from the closure of $A$ the inequality $D_A(f)\leq c\log_2^2L_A(f)+d$ holds, where $D_A(f)$ and $L_A(f)$ are the depth and the complexity of realization of the function $f$ by formulas over the finite system $A$. In this paper we provide some conditions for the quasi-uniformity of systems of functions of many-valued logic that take two values $0$ and $1$ and are monotone on the partially ordered set $\{0,\ldots,k-1\}$, where $1>0$ and all other elements are incomparable.
Keywords: many-valued logic, depth, complexity, uniformity, parallelizing. 
@article{UZKU_2014_156_3_a12,
     author = {P. B. Tarasov},
     title = {Several conditions for uniformity of a~finite system of many-valued logic},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {123--131},
     year = {2014},
     volume = {156},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a12/}
}
TY  - JOUR
AU  - P. B. Tarasov
TI  - Several conditions for uniformity of a finite system of many-valued logic
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 123
EP  - 131
VL  - 156
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a12/
LA  - ru
ID  - UZKU_2014_156_3_a12
ER  - 
%0 Journal Article
%A P. B. Tarasov
%T Several conditions for uniformity of a finite system of many-valued logic
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 123-131
%V 156
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a12/
%G ru
%F UZKU_2014_156_3_a12
P. B. Tarasov. Several conditions for uniformity of a finite system of many-valued logic. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 123-131. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a12/

[1] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vyssh. shk., M., 2001, 384 pp. | MR

[2] Lau D., Function Algebras on Finite Sets, Springer-Verlag, Berlin–Heidelberg, 2006, 684 pp. | MR

[3] Ugolnikov A. B., “O glubine i polinomialnoi ekvivalentnosti formul dlya zamknutykh klassov dvuznachnoi logiki”, Matem. zametki, 42:4 (1987), 603–612 | MR | Zbl

[4] Yablonskii S. V., Kozyrev V. P., “Matematicheskie voprosy kibernetiki”, Inform. materialy Nauchnogo soveta po kompleksnoi probleme “Kibernetika” AN SSSR, 19a, M., 1968, 3–15

[5] Spira R. M., “On time-hardware complexity tradeoffs for Boolean functions”, Proc. 4th Hawai Symp. on System Sciences, Western Period. Comp., North Hollywood, 1971, 525–527

[6] Khrapchenko V. M., “O sootnoshenii mezhdu slozhnostyu i glubinoi formul”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, 32, IM SO AN SSSR, Novosibirsk, 1978, 76–94 | MR

[7] Wegener I., “Relating monotone formula size and monotone depth of Boolean functions”, Inf. Process. Lett., 16:1 (1983), 41–42 | DOI | MR | Zbl

[8] Ugolnikov A. B., “O polinomialnoi ekvivalentnosti formul dlya zamknutykh klassov dvukhznachnoi logiki”, VII Vsesoyuz. konf. “Problemy teoreticheskoi kibernetiki”, Tez. dokl., Ch. 1, Izd-vo Irkut. gos. un-ta, Irkutsk, 1985, 194–195

[9] Ragaz M., “Parallelizable algebras”, Arch. fur math. Log. und Grundlagenforsch., 26:1 (1987), 77–99 | DOI | MR | Zbl

[10] Safin R. F., “O sootnoshenii mezhdu glubinoi i slozhnostyu formul dlya predpolnykh klassov $k$-znachnoi logiki”, Matem. voprosy kibernetiki, 13, Fizmatlit, M., 2004, 223–278 | MR

[11] Dudakova O. S., “O klassakh funktsii $k$-znachnoi logiki, monotonnykh otnositelno mnozhestv shiriny 2”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekhanika, 2008, no. 1, 31–37 | MR | Zbl

[12] Tarasov P. B., “O ravnomernosti nekotorykh sistem funktsii mnogoznachnoi logiki”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekhanika, 2013, no. 2, 61–64 | MR | Zbl

[13] Tarasov P. B., “O nekotorykh dostatochnykh usloviyakh ravnomernosti sistem funktsii mnogoznachnoi logiki”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekhanika, 2013, no. 5, 41–46 | MR

[14] Ugolnikov A. B., Klassy Posta, Izd-vo TsPI pri mekh.-mat. fak. MGU, M., 2008, 64 pp.