Отделимые нумерации универсальных алгебр
https://doi.org/10.26907/2949-3919.2024.4.66-102
Аннотация
В обзоре излагаются основы теории отделимых нумераций универсальных алгебр.
Ключевые слова
отделимо нумерованная алгебра,
эффективно отделимая нумерация,
негативная и эффективно отделимая аппроксимируемость,
трансляционно полная и предполная алгебра,
топологическая нумерованная алгебра,
подпрямая неразложимость,
артинова решетка конгруэнций,
алгебраические и логические спецификации структуры данных
При поддержке: Работа выполнена в рамках реализации Программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2024-1438).
Об авторе
Н. Х. Касымов
Национальный университет Узбекистана им. Мирзо Улугбека
Узбекистан
Узбекистан
Надимулла Хабибуллаевич Касымов
ул. Университетская, д. 4, г. Ташкент, 100174
Список литературы
1. А.И. Мальцев, Конструктивные алгебры. I, УМН 16 (3), 3–60 (1961). URL: https://www.mathnet.ru/rus/rm6619
2. Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, Наука, М., 1980.
3. Yu.L. Ershov, Theory of numberings, in: E.R.Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Elsevier, Amsterdam, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5
4. С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научная книга, Новосибирск, 1999.
5. Н.Г. Хисамиев, Арифметическая иерархия абелевых групп, Сиб. матем. журн. 29 (6), 144–159 (1988). URL: https://www.mathnet.ru/rus/smj7527
6. С.П. Одинцов, В.Л. Селиванов, Арифметическая иерархия и идеалы нумерованных булевых алгебр, Сиб. матем. журн. 30 (6), 140–149 (1989). URL: https://www.mathnet.ru/rus/smj4672
7. В.А. Успенский, О вычислимых операциях, ДАН СССР 103 (5), 773–776 (1955). URL: https://archive.org/details/uspensky-1955-dan-103-5-computable-operations/Uspensky_1955_DAN_103_5_Typeset_by_Zolin/mode/2up
8. В.А. Успенский, Системы перечислимых множеств и их нумерации, ДАН СССР 105 (6), 1155–1158 (1955). URL: https://archive.org/details/uspensky-1955-dan-105-6-enumerable-sets-numerations/Uspensky_1955_DAN_105_6_Typeset_by_Zolin/mode/2up
9. A. Nerode, General topology and partial recursive functionals, Summaries Summer Inst. Symbolic Logic 1957, 247–251 (1960).
10. А.И. Мальцев, К теории вычислимых семейств объектов, Алгебра и логика 3 (4), 5–31 (1964). URL: https://www.mathnet.ru/rus/al1010
11. Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.
12. Н.Х. Касымов, Рекурсивно отделимые нумерованные алгебры, УМН 51 (3), 145–176 (1996). DOI: https://doi.org/10.4213/rm971
13. А.И. Мальцев, Позитивные и негативные нумерации, ДАН СССР 160 (2), 278–280 (1965). URL: https://www.mathnet.ru/rus/dan30557
14. А.С. Морозов, Об одном вопросе Хигмэна, Алгебра и логика 29 (1), 29–34 (1990). URL: https://www.mathnet.ru/rus/al2089
15. W. Baur, Rekursive Algebren mit Kettenbedingungen, Z. Math. Logik Grundlag. Math. 20 (1–3), 37–46 (1974). DOI: https://doi.org/10.1002/malq.19740200105
16. W. Baur, Über rekursive Strukturen, Invent. Math. 23 (2), 89–95 (1974). DOI: https://doi.org/10.1007/BF01405162
17. В.А. Успенский, А.Л. Семенов, Теория алгоритмов: основные открытия и приложения, Наука, М., 1987.
18. J.C.C. McKinsey, The decision problem for some classes of sentences without quantifiers, J. Symbol. Logic 8 (3), 61–76 (1943). DOI: https://doi.org/10.2307/2268172
19. J.A. Bergstra, J.V. Tucker, A characterization of computable data types by means of a finite, equational specification method, Lecture Notes in Comput. Sci. 85, 76–90 (1980). DOI: https://doi.org/10.1007/3-540-10003-2_61
20. Н.Х. Касымов, О гомоморфизмах на негативные алгебры, Алгебра и логика 31 (2), 132–144 (1992). URL: https://www.mathnet.ru/rus/al2186
21. Н.Х. Касымов, О гомоморфизмах на эффективно отделимые алгебры, Сиб. матем. журн. 57 (1), 47–66 (2016). DOI: https://doi.org/10.17377/smzh.2016.57.105
22. Н.Х. Касымов, Об одной двойственной задаче теории конструктивных моделей, Вычисл. системы 129, 137–143 (1989). URL: https://zbmath.org/1052.03527
23. U. Andrews, S. Lempp, J.S. Miller, K.M. Ng, L.S. Mauro, A. Sorbi, Universal computably enumerable equivalence relations, J. Symb. Logic 79 (1), 60–88 (2014). DOI: http://doi.org/10.1017/jsl.2013.8
24. U.Andrews, A. Sorbi, Joins and meets in the structure of ceers, Computability 8 (3–4), 193–241 (2019). DOI: https://doi.org/10.3233/COM-180098
25. U. Andrews, D.F. Belin, L. San Mauro, On the structure of computable reducibility on equivalence relations of natural numbers, J. Symb. Logic 88 (3), 1038–1063 (2023). DOI: https://doi.org/10.1017/jsl.2022.28
26. Н.Х. Касымов, Ф.Н. Ибрагимов, Отделимые нумерации тел и эффективная вложимость в них колец, Сиб. матем. журн. 60 (1), 82–94 (2019). DOI: https://doi.org/10.33048/smzh.2019.60.107
27. Н.Х. Касымов, А.С. Морозов, И.А. Ходжамуратова, О T<sub>1</sub>-отделимых нумерациях подпрямо неразложимых алгебр, Алгебра и логика 60 (4), 400–424 (2021). DOI: https://doi.org/10.33048/alglog.2021.60.402
28. Н.Х. Касымов, Р.Н. Дадажанов, С.Л. Джавлиев, Uniform m-equivalences and numberings of classical systems, Сиб. электрон. матем. известия 19 (1), 49–65 (2022). DOI: http://doi.org/10.33048/semi.2022.19.005
29. Н.Х. Касымов, Нумерованные алгебры с равномерно рекурсивно отделимыми классами, Сиб. матем. журн. 34 (5), 85–102 (1993). URL: https://www.mathnet.ru/rus/smj836
30. Н.Х. Касымов, Позитивные алгебры с конгруэнциями конечного индекса, Алгебра и логика 30 (3), 293–305 (1991). URL: https://www.mathnet.ru/rus/al2151
31. Н.Х. Касымов, Позитивные алгебры с нетеровыми решетками конгруэнций, Сиб. матем. журн. 33 (2), 181–185 (1992). URL: https://www.mathnet.ru/rus/smj3208
32. Н.Х. Касымов, Позитивные алгебры со счетными решетками конгруэнций, Алгебра и логика 31 (1), 21–37 (1992). URL: https://www.mathnet.ru/rus/al2179
33. Р.Н. Дадажанов, Н.Х. Касымов, И.А. Ходжамуратова, Равномерно вычислимо отделимые алгебры с эффективно расщепляемыми семействами негативных конгруэнций, Сиб. матем. журн. 63 (3), 562–575 (2022). DOI: https://doi.org/10.33048/smzh.2022.63.307
34. C.G. Jockusch, Semurecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (2), 420–436 (1968). DOI: https://doi.org/10.2307/1994957
35. C.G. Jockusch, J.C. Owings, Weakly semirecursive sets, J. Symb. Logic 55 (2), 637–644 (1990). DOI: https://doi.org/10.2307/2274653
36. Н.Х. Касымов, А.С. Морозов, Нижние полурешетки отделимых конгруэнций нумерованных алгебр, Сиб. матем. журн. 64 (4), 753–769 (2023). DOI: https://doi.org/10.33048/smzh.2023.64.408
37. Н.Х. Касымов, Вычислимо отделимые нумерации локально финитно отделимых алгебр, Сиб. электрон. матем. изв. 21 (1), 315–346 (2024). DOI: https://doi.org/10.33048/semi.2024.21.024
38. Н.Х. Касымов, Локально конечные и финитно аппроксимируемые уноиды над вычислимо отделимыми эквивалентностями, Математика и теоретические компьютерные науки 2 (1), 55–74 (2024). DOI: https://doi.org/10.26907/2949-3919.2024.1.55-73
39. Н.Х. Касымов, Аксиомы отделимости и разбиения натурального ряда, Сиб. матем. журн. 34 (3), 81–85 (1993). URL: https://www.mathnet.ru/rus/smj1654
40. Н.Х. Касымов, И.А. Ходжамуратова, Топологические пространства над алгоритмическими представлениями универсальных алгебр, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз. 144, 17–29 (2018). URL: https://www.mathnet.ru/rus/into268
41. R.N. Dadazhanov, N.R. Karimova, N.Kh. Kasymov, Effective compacts over co-immune sets, Uzbek Math. J. 63 (3), 26–32 (2019). DOI: https://doi.org/10.29229/uzmj.2019-3-3
42. B. Khoussainov, T. Slaman, P. Semukhin, ∏<sup>0</sup><sub>1</sub>-Presentasions of Algebras, Arch. Math. Logic 45 (6), 769–781 (2006). DOI: https://doi.org/10.1007/s00153-006-0013-3
43. A.I. Malcev, On the immersion of an algebraic ring into a field, Math. Ann. 113 (1), 686–691 (1937). URL: https://doi.org/10.1007/BF01571659
44. S. Kamin, Some definitions for algebraic data type specifications, SIGPLAN Notes 14 (3), 28–37 (1979). DOI: https://doi.org/10.1145/988071.988075
45. J.A. Goguen, J. Meseguer, Completeness of many-sorted equational logic, Houston J. Math. 11 (3), 307–334 (1985).
46. M. Broy, W. Dosch, H. Partsch, P. Pepper, M. Wirsing, Existential quantifiers in abstract data types, Lect. Notes in Comp. Sci. 71, 73–87, (1979). DOI: https://doi.org/10.1007/3-540-09510-1_7
47. С.С. Гончаров, Модели данных и языки их описаний, Вычисл. системы 107, 52–70, (1985). URL: https://zbmath.org/0621.68020
48. Н.Х. Касымов, А.С. Морозов, Логические аспекты теории абстрактных типов данных, Вычисл. системы 122, 73–96 (1987). URL: https://zbmath.org/0712.68067
49. M. Majster, Data types, abstract data types and their specification problem, Theor. Comp. Sci. 8 (1), 89–127 (1979). DOI: https://doi.org/10.1016/0304-3975(79)90059-8
50. D. Kapur, Specifications of Majster’s traversable stack and Veloso’s traversable stack, SIGPLAN Notes 14 (5), 46–53 (1979). DOI: https://doi.org/10.1145/988090.988096
51. Н.Х. Касымов, Об алгебрах с финитно аппроксимируемыми позитивно представимыми обогащениями, Алгебра и логика 26 (6), 715–730 (1987). URL: https://www.mathnet.ru/rus/al1999
52. J.W. Lloyd, Foundations of logic programming, Springer-Verlag, Berlin, 1987. DOI: https://doi.org/10.1007/978-3-642-83189-8
53. Н.Х. Касымов, Позитивные модели и универсальные предложения, Вычисл. системы 133, 3–13 (1990). URL: https://zbmath.org/?q=an:0752.03016
54. А.И. Мальцев, Алгебраические системы, Наука, М., 1970.
55. А.И. Мальцев, Алгоритмы и рекурсивные функции, Наука, М., 1986.
56. Н.Х. Касымов, Ф.Н. Ибрагимов, Вычислимо отделимые модели, СМФН 64 (4), 682–705 (2018). DOI: https://doi.org/10.22363/2413-3639-2018-64-4-682-705
57. Н.Х. Касымов, О числе Q-конгруэнций позитивных алгебр, Алгебра и логика 31 (3), 297–305 (1992). URL: https://www.mathnet.ru/rus/al2194
58. N. Kasymov, N. Karimova, B. Khoussainov, Defining algorithmically presented structures in first-order logic, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–13, art. No. 47 (2024). DOI: https://doi.org/10.1145/3661814.3662120
59. Н.Х. Касымов, Б.М. Хусаинов, Конечно порожденные перечислимые и абсолютно локально конечные алгебры, Вычисл. системы 116, 3–15 (1986). URL: http://old.math.nsc.ru/journals/vs/vs-cont1.html
60. Н.Х. Касымов, Об алгебрах над негативными эквивалентностями, Алгебра и логика 33 (1), 76–80 (1994). URL: https://www.mathnet.ru/rus/al2257
61. Н.Х. Касымов, Логические спецификации эффективно отделимых моделей данных, Изв. вузов. Матем. (6), 15–26 (2024). DOI: https://doi.org/10.26907/0021-3446-2024-6-15-26
Рецензия
Для цитирования:
Касымов Н.Х. Отделимые нумерации универсальных алгебр. Математика и теоретические компьютерные науки. 2024;2(4):66-102. https://doi.org/10.26907/2949-3919.2024.4.66-102
For citation:
Kasymov N.Kh. Separable numberings of universal algebras. Mathematics and Theoretical Computer Science. 2024;2(4):66-102. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.66-102
Просмотров:
233
Послать статью по эл. почте 