Repetition-free decomposition of strongly dependent functions

A. V. Cheremushkin

Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 3-42.

Résumé

Some results on decomposition of boolean functions are generalised to the case of discrete $k$-valued functions. Autotopy and isostrophy groups and parameters of functions with non-trivial decompositions are considered.

Bibliographie

[1] Shennon K., “Sintez dvukhpolyusnykh pereklyuchatelnykh skhem”, Raboty po teorii informatsii i kibernetike, IL, Moskva, 1963, 59–105

[2] Kuznetsov A. V., “O bespovtornykh kontaktnykh skhemakh i bespovtornykh superpozitsiyakh funktsii algebry logiki”, Trudy MIAN SSSR, 51, 1958, 186–225 | Zbl

[3] Ashenhurst R. L., “The decomposition of switching functions”, Ann. Comput. Labor., 29 (1959), 74–116, Harvard Univ. | MR

[4] Zakrevskii A. D., “Algoritm razdeleniya bulevykh funktsii”, Trudy Sib. fiz.-tekhn. in-ta, 3:44 (1964), 5–16

[5] Tase A., “A fast algoritm for the proper decomposition of boolean functions”, Philips Res. Repts, 27 (1972), 140–150 | MR

[6] Vaschenko V. P., “Metod sinteza odnogo klassa skhem na osnove funktsionalnoi razdelimosti”, Kibernetika, 1969, no. 1, 32–40 | Zbl

[7] Shurupov A. N., “O funktsionalnoi razdelimosti bulevykh porogovykh funktsii”, Diskretnaya matematika, 9:2 (1997), 59–73 | MR | Zbl

[8] Yablonskii S. V., “Ob algoritmicheskikh trudnostyakh sinteza minimalnykh kontaktnykh skhem”, Problemy kibernetiki, 2 (1959), 75–121

[9] Peryazev N. A., “Realizatsiya bulevykh funktsii bespovtornymi formulami”, Diskretnaya matematika, 7:3 (1995), 61–68 | MR | Zbl

[10] Vinokurov S. F., Peryazev N. A., Izbrannye voprosy teorii bulevykh funktsii, Fizmatlit, Moskva, 2001 | Zbl

[11] Belousov V. D., “Uravnoveshennye tozhdestva v kvazigruppakh”, Matem. sb., 70(112):1 (1966), 55–97 | MR | Zbl

[12] Belousov V. D., Livshits E. S., “Uravnoveshennye funktsionalnye uravneniya na kvazigruppakh lyuboi arnosti”, Kvazigruppy i kombinatorika, Matem. issledovaniya, 43, 1966, 9–29

[13] Gorbatov A. V., Kharakterizatsionnaya teoriya sinteza funktsionalnykh dekompozitsii v $k$-znachnykh logikakh, Fizmatlit, Moskva, 2000

[14] Belousov V. D., $n$-arnye kvazigruppy, Shtiintsa, Kishinev, 1972 | MR

[15] Cheremushkin A. V., “Kanonicheskaya dekompozitsiya $n$-arnykh kvazigrupp”, Issledovanie operatsii i kvazigrupp, Matem. issledovaniya, 102, 1988, 97–105 | MR | Zbl

[16] Sokhatskii F. N., “Obobschenie dvukh teorem Belousova dlya silno zavisimykh funktsii $k$-znachnoi logiki”, Issledovaniya po teorii kvazigrupp i lup, Shtiintsa, Kishinev, 1985, 105–115 | MR

[17] Belousov V. D., Osnovy teorii kvazigrupp i lup, Nauka, Moskva, 1967 | MR

[18] Kurosh A. G., Obschaya algebra, Nauka, Moskva, 1974 | MR | Zbl

[19] Cheremushkin A. V., “Gruppy avtostrofii razdelimykh silno zavisimykh funktsii”, Kvazigruppy i ikh sistemy, Matem. issledovaniya, 113, 1990, 119–123 | MR | Zbl

[20] Kolbin S. L., “O nekotorykh svoistvakh vzaimno-obratnykh sistem funktsii”, Diskretnaya matematika, 6:2 (1994), 145–149 | MR | Zbl

[21] Davio M., Deschamps J. P., Thayse A., Discrete and switching functions, 1974, Academiai Kiado, Budapest

[22] Moraga C., “Complex spectral logic”, Proc. 8th Int. Symp. Multiple-Valued Logic, New York, 1978, 149–156 | MR