Certain sufficient conditions of uniformity for systems of functions of many-valued logic

P. B. Tarasov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2013), pp. 41-46

Résumé

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}$.

Bibliographie

[1] Yablonskii S.V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, M., 2001 | MR

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

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

[4] Yablonskii S.V., Kozyrev V.P., “Matematicheskie voprosy kibernetiki”, Informatsionnye 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 Periodicals Company, 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”, Inform. Proces. Lett., 16 (1983), 41–42 | DOI | MR

[8] Ugolnikov A.B., “O sootnoshenii mezhdu glubinoi i slozhnostyu formul dlya zamknutykh klassov dvuznachnoi logiki”, IV Vsesoyuz. konf. “Primenenie metodov matematicheskoi logiki”, tez. dokl., Tallin, 1986, 184

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

[10] Ragaz M.E., “Parallelizable algebras”, Arch. fur math. Log. und Grundlagenforsch., 26 (1986/87), 77–99 | DOI | MR

[11] Akhmetova L.I., “O glubine formul dlya predpolnykh klassov trekhznachnoi logiki”, Metody i sistemy tekhnicheskoi diagnostiki, 18, Izd-vo Saratov. un-ta, Saratov, 1993, 19–20

[12] Safin R.F., “O glubine i slozhnosti formul v nekotorykh klassakh $k$-znachnoi logiki”, Vestn. Mosk. un-ta. Matem. Mekhan., 2000, no. 6, 65–68 | MR

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

[14] Safin R.F., “O ravnomernosti sistem monotonnykh funktsii”, Vestn. Mosk. un-ta. Matem. Mekhan., 2003, no. 2, 15–20

[15] Rosenberg L., “La structure des fonctions de plusieurs variables sur un ensemble fini”, C. r. Acad. sci. Paris. Ser. A, 260 (1965), 3817–19 | MR

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

[17] Tarasov P.B., “O ravnomernosti nekotorykh sistem funktsii mnogoznachnoi logiki”, Vestn. Mosk. un-ta. Matem. Mekhan., 2013, no. 2, 61–64

[18] Ugolnikov A.B., “O zamknutykh klassakh Posta”, Izv. vuzov. Matematika, 7 (1988), 79–88 | MR

[19] Ugolnikov A.B., Klassy Posta, Izd-vo TsPI pri mekh.-mat. f.-te MGU, M., 2008

[20] Post E.L., “Two-valued iterative systems of mathematical logic”, Ann. Math. Stud., 5 (1941) | MR

[21] Yablonskii S.V., Gavrilov G.P., Kudryavtsev V.B., Funktsii algebry logiki i klassy Posta, Nauka, M., 1966, 3–15 | MR

[22] Marchenkov S.S., “Ob id-razlozheniyakh klassa $P_k$ nad predpolnymi klassami”, Diskret. matem., 5:2 (1993), 98–110