Logical specifications of effectively separable data models

N. Kh. Kasymov

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2024), pp. 15-26

Résumé

It is established that any effectively separable many-sorted universal algebra has an enrichment that is the only (up to isomorphism) model constructed from constants for a suitable computably enumerable set of sentences.

Détail

Keywords: effectively separable many-sorted algebra, data model, specification.

Bibliographie

[1] Ershov Yu.L., Teoriya numeratsii, Nauka, M., 1977 | MR

[2] Goncharov S.S., Ershov Yu.L., Konstruktivnye modeli, Nauchn. kn., Novosibirsk, 1999

[3] Soar R.I., Vychislimo perechislimye mnozhestva i stepeni, Kazansk. matem. o-vo, Kazan, 2000

[4] Bergstra J.A., Tucker J.V., “A characterization of computable data types by means of a finite equational specification method”, Lecture Notes in Comput. Sci., 85, 1980, 76–90 | DOI | MR | Zbl

[5] Goncharov S.S., “Modeli dannykh i yazyki ikh opisanii”, Vychisl. sistemy, 122, IM SO AN SSSR, 1987, 73–96

[6] Kasymov N.Kh., Morozov A.S., “Logicheskie aspekty teorii abstraktnykh tipov dannykh”, Vychisl. sistemy, 107, IM SO AN SSSR, 1987, 52–70

[7] Kasymov N.Kh., “Rekursivno otdelimye numerovannye algebry”, Uspekhi matem. nauk, 51:3 (1996), 145–176 | DOI | MR | Zbl

[8] Kasymov N.Kh., Dadazhanov R.N., Ibragimov F.N., “Otdelimye algoritmicheskie predstavleniya klassicheskikh sistem i ikh prilozheniya”, Sovremennaya matem. Fundament. napravl., 67, no. 4, 2021, 707–754

[9] Maltsev A.I., Algebraicheskie sistemy, Nauka, M., 1970 | MR

[10] Kasymov N.Kh., “Ob algebrakh s finitno-approksimiruemymi pozitivno predstavimymi obogascheniyami”, Algebra i logika, 26:6 (1987), 715–730 | MR

[11] Khoussainov B.M., “Randomness, computability, and algebraic specifications”, Ann. Pure and Applied Logic, 91:1 (1998), 1–15 | DOI | MR | Zbl

[12] Khoussainov B.M., Miasnikov A.G., “Finitely presented expansions of groups, semigroups, and algebras”, Trans. Amer. Math. Soc., 366:3 (2014), 1455–1474 | DOI | MR | Zbl

[13] Kasymov N.Kh., “Aksiomy otdelimosti i razbieniya naturalnogo ryada”, Sib. matem. zhurn., 34:3 (1993), 81–85 | MR | Zbl

[14] Kasymov N.Kh., “Numerovannye algebry s ravnomerno rekursivno otdelimymi klassami”, Sib. matem. zhurn., 34:5 (1993), 85–102 | MR | Zbl

[15] Kasymov N.Kh., “O gomomorfizmakh na negativnye algebry”, Algebra i logika, 31:2 (1992), 132–144 | MR | Zbl

[16] Kasymov N.Kh., “Ob algebrakh nad negativnymi ekvivalentnostyami”, Algebra i logika, 33:1 (1994), 76–80 | MR | Zbl

[17] Kasymov N.Kh., “Pozitivnye algebry s kongruentsiyami konechnogo indeksa”, Algebra i logika, 30:3 (1991), 293–305 | MR

[18] Kasymov N.Kh., “Pozitivnye algebry so schetnymi reshetkami kongruentsii”, Algebra i logika, 31:1 (1992), 21–37 | MR | Zbl

[19] Khoussainov B.M., Slaman T., Semukhin P., “$\prod_1^0$-Presentasions of Algebras”, Archive for Math. Logic, 45:6 (2006), 769–781 | DOI | MR | Zbl

[20] Kasymov N.Kh., Dadazhanov R.N., Dzhavliev S.K., “Struktury stepenei negativnoi predstavimosti lineinykh poryadkov”, Izv. vuzov. Matem., 2021, no. 12, 31–55 | Zbl

[21] Kasymov N.Kh., Dadazhanov R.N., “Negativnye plotnye lineinye poryadki”, Sib. matem. zhurn., 58:6 (2017), 1306–1331 | MR | Zbl

[22] Kasymov N.Kh., Morozov A.S., “Ob opredelimosti lineinykh poryadkov nad negativnymi ekvivalentnostyami”, Algebra i logika, 55:1 (2016), 37–57 | MR | Zbl

[23] Kasymov N.Kh., “O gomomorfizmakh na effektivno otdelimye algebry”, Sib. matem. zhurn., 57:1 (2016), 47–66 | MR | Zbl

[24] Kasymov N.Kh., Morozov A.S., Khodzhamuratova I.A., “O $T_1$-otdelimykh numeratsiyakh podpryamo nerazlozhimykh algebr”, Algebra i logika, 60:4 (2021), 400–424 | Zbl

[25] Andrews U., Sorbi A., “Joins and meets in the structure of ceers”, Computability, 8:3–4 (2019), 193–241 | DOI | MR | Zbl

[26] Andrews U., Belin D., San Mauro L., “On the structure of computable reducibility on equivalence relations of natural numbers”, J. Symb. Logic, 88:3 (2023), 1038–1063 | DOI | MR | Zbl

[27] Dadazhanov R.N., “Vychislimost i universalnaya opredelimost negativno predstavimykh modelei”, Izv. vuzov. Matem., 2022, no. 10, 22–32 | MR