The completeness problem in the function algebra of linear integer-coefficient polynomials

A. I. Mamontov ; D. G. Meshchaninov

Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 64-82.

Résumé

In the algebra of linear integer-coefficient polynomials, we give a criterion of completeness in terms of precomplete classes and find the cardinality of bases.

Bibliographie

[1] Kudryavtsev V. B., Funktsionalnye sistemy, Izd-vo MGU, Moskva, 1982 | Zbl

[2] Kudryavtsev V. B., “Otnositelno funktsionalnykh sistem”, Probl. kibern., 41, 1984, 5–40 | MR | Zbl

[3] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1979 | MR

[4] Gavrilov G. P., Funktsionalnye sistemy diskretnoi matematiki, Izd-vo MGU, Moskva, 1985 | Zbl

[5] Freivald R. V., “Kriterii polnoty dlya chastichnykh funktsii algebry logiki i mnogoznachnoi logiki”, Doklady AN SSSR, 167:6 (1966), 1249–1250 | MR

[6] Freivald R. V., “Funktsionalnaya polnota dlya ne vsyudu opredelennykh funktsii algebry logiki”, Diskretnyi analiz, 8, 1966, 55–68 | MR | Zbl

[7] Romov B. A., “O maksimalnykh podalgebrakh algebry chastichnykh funktsii mnogoznachnoi logiki”, Kibernetika, 1980, no. 1, 28–36 | MR | Zbl

[8] Lo Chzhu Kai, “Maksimalnye zamknutye klassy v mnozhestve chastichnykh funktsii mnogoznachnoi logiki”, Kibern. sb., 25 (1988), 131–141

[9] Lo Chzhu Kai, “Teoriya polnoty dlya chastichnykh funktsii mnogoznachnoi logiki”, Kibern. sb., 25 (1988), 142–161

[10] Alekseev V. B., Voronenko A. A., “O nekotorykh zamknutykh klassakh v chastichnoi dvuznachnoi logike”, Diskretnaya matematika, 6:4 (1994), 58–79 | MR | Zbl

[11] Kudryavtsev V. B., “O funktsionalnoi sisteme $P_\Sigma$”, Doklady AN SSSR, 210:3 (1973), 521–522 | Zbl

[12] Kudryavtsev V. B., “Otnositelno funktsionalnoi sistemy $P_\Sigma$”, Zh. vychisl. matem. i matem. fiziki, 14:1 (1974), 198–208

[13] Taimanov V. A., “O dekartovykh stepenyakh $P_2$”, Doklady AN SSSR, 270:6 (1983), 1327–1330 | MR

[14] Romov B. A., “O polnote na kvadrate funktsii algebry logiki i v sisteme $P_k\times P_l$”, Kibernetika, 1987, no. 4, 9–14 | MR | Zbl

[15] Romov B. A., “Ob odnoi serii maksimalnykh podalgebr pryamykh proizvedenii algebr konechnoznachnykh logik”, Kibernetika, 1989, no. 3, 11–16 | MR | Zbl

[16] Marchenkov S. S., “O predpolnykh klassakh Slupetskogo v sistemakh $P_k\times\ldots\times P_l$”, Diskretnaya matematika, 4:3 (1992), 135–148 | MR | Zbl

[17] Marchenkov S. S., “O predpolnykh klassakh v dekartovykh proizvedeniyakh $P_2$ i $P_3$”, Diskretnaya matematika, 6:2 (1994), 21–42 | MR | Zbl

[18] Dou Zh., “Voprosy polnoty dlya konechno porozhdennykh funktsionalnykh sistem $\langle P_{k,E_2},\widetilde\Omega\rangle$ i $\langle P_{k,E_2},\widehat\Omega\rangle$”, Diskretnaya matematika, 2:3 (1990), 128–136 | MR | Zbl

[19] Dou Zh., “Voprosy polnoty dlya konechno porozhdennykh funktsionalnykh sistem $\langle P_{k,2},\widetilde\Omega\rangle$ i $\langle P_{k,2},\widehat\Omega\rangle$”, Diskretnaya matematika, 2:4 (1990), 116–124 | MR | Zbl

[20] Arutyunyan L. A., “O reshetke zamknutykh klassov neodnorodnykh funktsii so sledom tipa $C$”, Diskretnaya matematika, 5:1 (1993), 130–145 | MR | Zbl

[21] Arutyunyan L. A., “O moschnosti sledov klassov neodnorodnykh funktsii”, Diskretnaya matematika, 5:3 (1993), 35–39 | MR | Zbl

[22] Kolyada K. V., “O polnote regulyarnykh otobrazhenii”, Probl. kibern., 41, 1984, 41–47 | MR | Zbl

[23] Kudryavtsev V. B., “O funktsionalnoi sisteme $P_{k,\Pi}$”, Diskretnaya matematika, 3:3 (1991), 124–134 | MR | Zbl

[24] Kudryavtsev V. B., “O funktsionalnoi sisteme puchkov logicheskikh funktsii”, Fundamentalnaya i prikladnaya matematika, 5:1 (1999), 149–192 | MR | Zbl

[25] Buevich V. A., “O $\tau$-polnote v klasse avtomatnykh otobrazhenii”, Doklady AN SSSR, 252:5 (1980), 708–712 | MR

[26] Buevich V. A., Usloviya $A$-polnoty dlya konechnykh avtomatov, v. 1, Izd-vo MGU, Moskva, 1986; т. 2, 1987

[27] Golunkov Yu. V., “Approksimatsionnaya polnota v algebrakh chastichno rekursivnykh funktsii i predikatov”, Kibernetika, 1987, no. 6, 26–30 | MR | Zbl

[28] Marchenkov S. S., “$S$-klassifikatsiya funktsii mnogoznachnoi logiki”, Diskretnaya matematika, 9:3 (1997), 125–152 | MR | Zbl

[29] Marchenkov S. S., $S$-klassifikatsiya funktsii trekhznachnoi logiki, Fizmatlit, Moskva, 2001 | Zbl

[30] Tarasova O. S., “Klassy $k$-znachnoi logiki, zamknutye otnositelno rasshirennoi operatsii superpozitsii”, Vestnik MGU. Ser. 1. Matematika, mekhanika, 2001, no. 6, 54–57 | MR | Zbl

[31] Golunkov Yu. V., “K teorii sistem algoritmicheskikh algebr”, Doklady AN SSSR, 232:4 (1997), 749–752 | MR

[32] Golunkov Yu. V., “O polnote operatsii v sistemakh algoritmicheskikh algebr”, Algoritmy i avtomaty, Izd-vo Kazanskogo un-ta, Kazan, 1978, 11–53 | MR

[33] Glushkov V. M., Tseitlin G. E., Yuschenko E. L., Algebra. Yazyki. Programmirovanie, Naukova dumka, Kiev, 1978 | MR | Zbl

[34] Lisovik L. P., “Algebry polilineinykh preobrazovanii nad razmechennymi derevyami”, Vychislitelnye sistemy, 124, 1988, 114–143 | MR | Zbl

[35] Golunkov Yu. V., “Polnota sistem operatsii v operatornykh algebrakh, realizuyuschikh funktsii $k$-znachnoi logiki”, Veroyatnostnye metody i kibernetika, 17, 1980, 23–34 | MR | Zbl

[36] Andreeva O. V., Golunkov Yu. V., “Programmno-zamknutye klassy funktsii algebry logiki i predikatov”, Kibernetika, 1981, no. 1, 133

[37] Taimanov V. A., “O funktsionalnykh sistemakh $k$-znachnoi logiki s operatsiyami programmnogo tipa”, Doklady AN SSSR, 268:6 (1983), 1307–1310 | MR

[38] Golunkov Yu. V., “Polnota po modulyu ideala v funktsionalnykh sistemakh programmnogo tipa”, Diskretnaya matematika, 2:2 (1990), 112–120 | MR | Zbl

[39] Iordanskii M. A., “Funktsionalnyi podkhod k predstavleniyu grafov”, Doklady RAN, 353:3 (1997), 303–305 | MR

[40] Iordanskii M. A., “Struktura i sposoby porozhdeniya zamknutykh klassov grafov”, Diskretnaya matematika, 15:3 (2003), 105–116 | MR | Zbl

[41] Darsaliya V. Sh., “Usloviya polnoty dlya polinomov s naturalnymi, tselymi i ratsionalnymi koeffitsientami”, Fundamentalnaya i prikladnaya matematika, 2:2 (1996), 365–374 | MR | Zbl

[42] Darsaliya V. Sh., “O moschnostyakh mnozhestv vsekh predpolnykh klassov v funktsionalnykh sistemakh polinomov”, Teoreticheskie problemy informatiki i ee prilozheniya, 1997, no. 1, 35–44

[43] Darsaliya V. Sh., Problema polnoty dlya funktsionalnykh sistem polinomov, Diss. kand. fiz.-mat. nauk, Moskva, 1998

[44] Darsaliya V. Sh., “Ob algoritmicheskoi razreshimosti svoistva vyrazimosti dlya polinomov”, Fundamentalnaya i prikladnaya matematika, 5:3 (1999), 931–935 | MR | Zbl

[45] Darsaliya V. Sh., “O bazisakh funktsionalnykh sistem polinomov”, Fundamentalnaya i prikladnaya matematika, 7:3 (2001), 673–682 | MR | Zbl

[46] Darsaliya V. Sh., “Otnositelnaya polnota dlya funktsionalnykh sistem polinomov”, Fundamentalnaya i prikladnaya matematika, 8:4 (2002), 967–977 | MR | Zbl

[47] Kuznetsov A. V., “O problemakh tozhdestva i funktsionalnoi polnoty dlya algebraicheskikh sistem”, Trudy III Vsesoyuznogo matem. s'ezda, v. 2, Izd-vo AN SSSR, 1956, 145–146

[48] Kuznetsov A. V., “Struktury s zamykaniem i kriterii funktsionalnoi polnoty”, Uspekhi matem. nauk, 16:2 (1961), 201–202

[49] Gavrilov G. P., Voprosy vyrazimosti i moschnostnoi kharakterizatsii dlya diskretnykh funktsionalnykh sistem s operatsiei superpozitsii, Diss. dokt. fiz.-mat. nauk, Moskva, 1997

[50] Post E. L., “Introduction to a general theory of elementary propositions”, Amer. J. Math., 43:3 (1921), 163–185 | DOI | MR | Zbl

[51] Post E. L., The two-valued iterative systems of mathematical logic, Princeton Univ. Press, Princeton, 1941 | MR | Zbl

[52] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy Matematicheskogo instituta im. V. A. Steklova AN SSSR, 51, 1958, 5–142 | MR | Zbl

[53] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, Moskva, 1966 | MR

[54] Gavrilov G. P., “Induktivnoe predstavlenie bulevykh funktsii i konechnaya porozhdaemost klassov Posta”, Algebra i logika, 23:1 (1984), 3–26 | MR | Zbl

[55] Marchenkov S. S., “K suschestvovaniyu konechnykh bazisov v zamknutykh klassakh bulevykh funktsii”, Algebra i logika, 23:1 (1984), 88–99 | MR | Zbl

[56] Ugolnikov A. B., “O zamknutykh klassakh Posta”, Izvestiya vuzov. Matematika, 1988, no. 7, 79–88 | MR

[57] Marchenkov S. S., Ugolnikov A. B., Zamknutye klassy bulevykh funktsii, IPM AN SSSR, Moskva, 1990 | MR

[58] Marchenkov S. S., Zamknutye klassy bulevykh funktsii, Fizmatlit, Moskva, 2000 | MR | Zbl

[59] Yablonskii S. V., Voprosy funktsionalnoi polnoty v $k$-znachnom ischislenii, Diss. kand. fiz.-mat. nauk, Moskva, 1953

[60] Yablonskii S. V., “O funktsionalnoi polnote v trekhznachnom ischislenii”, Doklady AN SSSR, 92:6 (1954), 1153–1156 | MR

[61] Slupecki J., “Kryterium pelnosci wielowar-tosciowych systemów logiki zdań”, C. R. Soc. Sci. Lett. Varsovie Cl. III, 32 (1939), 102–109

[62] Zakharova E. Yu., Kudryavtsev V. B., Yablonskii S. V., “O predpolnykh klassakh v $k$-znachnykh logikakh”, Doklady AN SSSR, 186:3 (1969), 509–512 | Zbl

[63] Rosenberg I. G., “La structure des fonctions de plusieurs variables sur un ensemble fini”, C. R. Acad. Sci. Paris, 260 (1965), 3817–3819 | MR | Zbl

[64] Rosenberg I. G., “Über die funktionale Vollständigkeit in den mehrvertigen Logiken”, Rozpr. Česk. Akad. Věd Řada Mat. Přír. Věd, 80:4 (1970), 3–39 | MR

[65] Yablonskii S. V., Gavrilov G. P., Nabebin A. A., Analiz i sintez skhem v mnogoznachnykh logikakh, v. I, Izd-vo MEI, Moskva, 1989

[66] Marchenkov S. S., “Predpolnota zamknutykh klassov v $P_k$: predikatnyi podkhod”, Matem. voprosy kibern., 6, 1996, 117–132 | MR | Zbl

[67] Yablonskii S. V., Gavrilov G. P., Nabebin A. A., Predpolnye klassy v mnogoznachnykh logikakh, Izd-vo MEI, Moskva, 1997 | MR

[68] Yanov Yu. I., Muchnik A. A., “O suschestvovanii $k$-znachnykh zamknutykh klassov, ne imeyuschikh konechnogo bazisa”, Doklady AN SSSR, 127:1 (1959), 44–46 | Zbl

[69] Gavrilov G. P., “O funktsionalnoi polnote v schetnoznachnoi logike”, Probl. kibern., 15, 1965, 5–64 | MR | Zbl

[70] Perfileva I. G., “Postroenie giperkontinualnogo semeistva predpolnykh klassov schetnoznachnoi logiki”, Probl. kibern., 35, 1979, 29–44 | MR

[71] Kudryavtsev V. B., “O moschnostyakh mnozhestv predpolnykh klassov nekotorykh funktsionalnykh sistem, svyazannykh s avtomatami”, Doklady AN SSSR, 151:3 (1963), 493–496

[72] Kratko M. I., “Algoritmicheskaya nerazreshimost problemy raspoznavaniya polnoty dlya konechnykh avtomatov”, Doklady AN SSSR, 155:1 (1964), 35–37 | MR | Zbl

[73] Letichevskii A. A., “Usloviya polnoty dlya konechnykh avtomatov”, Zh. vychisl. matem. i matem. fiziki, 1961, no. 4, 702–710

[74] Chasovskikh A. A., “Ob algoritmicheskoi razreshimosti problemy polnoty dlya lineinykh avtomatov”, Vestnik MGU. Ser. 1. Matematika, mekhanika, 1985, no. 3, 82–84 | MR

[75] Babin D. N., “Razreshimyi sluchai zadachi o polnote avtomatnykh funktsii”, Diskretnaya matematika, 4:4 (1992), 41–55 | MR | Zbl

[76] Babin D. N., “O razreshimosti problemy polnoty dlya spetsialnykh sistem avtomatov”, Diskretnaya matematika, 8:4 (1996), 79–91 | MR | Zbl

[77] Babin D. N., “Effektivnaya proveryaemost polnoty sistem avtomatnykh funktsii s polnoi bulevoi chastyu”, Diskretnaya matematika, 15:1 (2003), 110–130 | MR | Zbl

[78] Malyugin V. D., Parallelnye logicheskie vychisleniya pocredstvom arifmeticheskikh polinomov, Nauka, Moskva, 1997 | Zbl

[79] Vykhovanets V. S., Malyugin V. D., “Multiplikativnaya algebra i ee primenenie v logicheskoi obrabotke dannykh”, Problemy upravleniya, 2004, no. 3, 67–77

[80] Vatolin D., Ratushnyak A., Smirnov M., Yukin V., Metody szhatiya dannykh. Ustroistvo arkhivatorov, szhatie izobrazhenii i video, Dialog–MIFI, Moskva, 2002

[81] Krokhin A. A., Safin K. L., Sukhanov E. V., “O stroenii reshetki zamknutykh klassov polinomov”, Diskretnaya matematika, 9:2 (1997), 24–39 | MR | Zbl

[82] Meschaninov D. G., “O pervykh $d$-raznostyakh funktsii $k$-znachnoi logiki”, Matem. voprosy kibern., 7, 1998, 265–280

[83] Meschaninov D. G., “O zamknutykh klassakh $k$-znachnykh funktsii, sokhranyayuschikh pervye $d$-raznosti”, Matem. voprosy kibern., 8, 1999, 219–230

[84] Mamontov A. I., “Issledovanie struktury podalgebr v algebrakh polinomov s tselymi koeffitsientami”, Tezisy dokladov IX Mezhdunarodnoi nauchno-tekhnicheskoi konferentsii “Radioelektronika, elektrotekhnika i energetika”, v. 1, Izd-vo MEI, Moskva, 2003, 263–264

[85] Mamontov A. I., “Kriterii polnoty v algebre lineinykh polinomov s tselymi koeffitsientami”, Tezisy dokladov X Mezhdunarodnoi nauchno-tekhnicheskoi konferentsii “Radioelektronika, elektrotekhnika i energetika”, v. 1, Izd-vo MEI, Moskva, 2004, 286–287

[86] Mamontov A. I., Meschaninov D. G., “Problema polnoty v funktsionalnoi sisteme lineinykh polinomov s tselymi koeffitsientami”, Trudy VI Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem”, Izd. otdel f-ta VMiK MGU, Moskva, 2004, 50–52

[87] Mamontov A. I., “Nekotorye vozmozhnye primeneniya algebr polinomov s tselymi koeffitsientami”, Nauchnaya sessiya MIFI' 2005, Sbornik nauchnykh trudov, v. 14, MIFI, Moskva, 2005, 52–53

[88] Marchenkov S. S., Funktsionalnye sistemy s operatsiei superpozitsii, Fizmatlit, Moskva, 2004 | MR | Zbl