Отделимые алгоритмические представления классических систем и их приложения

Обложка

Цитировать

Полный текст

Аннотация

Излагаются основные результаты теории отделимых алгоритмических представлений классических алгебраических систем. Описываются важнейшие классы таких систем и их представления в нижних классах арифметической иерархии - позитивных и негативных. Особое внимание уделено алгоритмическим, структурным и топологическим свойствам отделимых представлений групп, колец и тел, а также эффективным аналогам теоремы А. И. Мальцева о вложимости колец в тела. Рассматриваются возможности применения изучаемых понятий в рамках теоретической информатики.

Об авторах

Н. Х. Касымов

Национальный университет Узбекистана им. М. Улугбека

Автор, ответственный за переписку.
Email: nadim59@mail.ru
Ташкент, Узбекистан

Р. Н. Дадажанов

Национальный университет Узбекистана им. М. Улугбека

Email: dadajonovrn@mail.ru
Ташкент, Узбекистан

Ф. Н. Ибрагимов

Национальный университет Узбекистана им. М. Улугбека

Email: farkh-i@yandex.com
Ташкент, Узбекистан

Список литературы

  1. Биркгоф Г. Теория решеток. - М.: Наука, 1984.
  2. Гончаров С. С. Модели данных и языки их описаний// Вычисл. системы. - 1985. -107. - С. 52-70.
  3. Гончаров С. С., Ершов Ю. Л. Конструктивные модели. - Новосибирск: Научная книга, 1999.
  4. Ершов Ю. Л. Теория нумераций. - М.: Наука, 1977.
  5. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. - М.: Наука, 1980.
  6. Касымов Н. Х. Алгебраическое описание рекурсивно перечислимых типов данных// Вычисл. системы. - 1984. -101. - С. 130-140.
  7. Касымов Н. Х. Логические программы без равенства и конструктивные представления// Вычисл. системы. - 1987. -122. - С. 3-18.
  8. Касымов Н. Х. Об алгебрах с финитно аппроксимируемыми позитивно представимыми обогащениями// Алгебра и логика. - 1987. -26, № 6. - С. 715-730.
  9. Касымов Н. Х. О неспецифицируемости эффективно представимых данных позитивными формулами// Докл. АН УзССР. - 1989. - № 6. - С. 4-5.
  10. Касымов Н. Х. Об одной двойственной задаче теории конструктивных моделей// Вычисл. системы. - 1989. -129. - С. 137-143.
  11. Касымов Н. Х. Финитная аппроксимируемость квазиэрбрановских моделей// Докл. АН УзССР. - 1989. - № 12. - С. 5-6.
  12. Касымов Н. Х. Позитивные модели и универсальные предложения// Вычисл. системы. - 1990. -133. - С. 3-13.
  13. Касымов Н. Х. Позитивные алгебры с конгруэнциями конечного индекса// Алгебра и логика. - 1991. - 30, № 3. - С. 293-305.
  14. Касымов Н. Х. Позитивные алгебры со счетными решетками конгруэнций// Алгебра и логика. - 1992. -31, № 1. - С. 21-37.
  15. Касымов Н. Х. Позитивные алгебры с нетеровыми решетками конгруэнций// Сиб. мат. ж. - 1992. - 33, № 2. - С. 181-185.
  16. Касымов Н. Х. О числе конгруэнций алгебр над простыми множествами// Мат. заметки. - 1992. -52, № 2. - С. 150-152.
  17. Касымов Н. Х. О гомоморфизмах на негативные алгебры// Алгебра и логика. - 1992. -31, № 2. - С. 132-144.
  18. Касымов Н. Х. О числе Q-конгруэнций позитивных алгебр// Алгебра и логика. - 1992. -31, № 3. - С. 297-305.
  19. Касымов Н. Х. О гомоморфизмах нумерованных алгебр с рекурсивно отделимыми классами// Докл. АН УзССР. - 1992. - № 6. - С. 3-4.
  20. Касымов Н. Х. Неконструктивные негативные алгебры с условиями конечности// Сиб. мат. ж. - 1992. -33, № 6. - С. 195-198.
  21. Касымов Н. Х. Совершенные нумерации алгебр// Узб. мат. ж. - 1993. - № 2. - С. 51-56.
  22. Касымов Н. Х. Аксиомы отделимости и разбиения натурального ряда// Сиб. мат. ж. - 1993. -34, № 3. - С. 81-85.
  23. Касымов Н. Х. Нумерованные алгебры с равномерно рекурсивно отделимыми классами// Сиб. мат. ж. - 1993. -34, № 5. - С. 85-102.
  24. Касымов Н. Х. Об алгебрах над негативными эквивалентностями// Алгебра и логика. - 1994. -33, № 1. - С. 76-80.
  25. Касымов Н. Х. Рекурсивно отделимые нумерованные алгебры// Усп. мат. наук. - 1996. -51, № 3. - С. 145-176.
  26. Касымов Н. Х. О полугруппах рекурсивных автоморфизмов нумерованных систем// Докл. АН РУз. - 1996. - № 12. - С. 3-4.
  27. Касымов Н. Х., Дадажанов Р. Н. О рекурсивно отделимых нумерациях, все рекурсивные автоморфизмы которых имеют неподвижные точки// Докл. АН РУз. - 2014. - № 1. - С. 5-7.
  28. Касымов Н. Х. О вычислимости негативных представлений стандартной модели арифметики Гончарова// Тез. докл. Межд. конф. «Алгебра, анализ и квантовая вероятность». - Ташкент, 2015. - С. 117-119.
  29. Касымов Н. Х., Дадажанов Р. Н. Позитивные и негативные линейные порядки и их вычислимо необратимые автоморфизмы// Вестн. НУУз. - 2015. - № 2. - С. 54-63.
  30. Касымов Н. Х. О точных представлениях линейных порядков над негативными эквивалентностями// Докл. АН РУз. - 2016. - № 1. - С. 9-12.
  31. Касымов Н. Х. О гомоморфизмах на эффективно отделимые алгебры// Сиб. мат. ж. - 2016. -57, № 1. - С. 47-66.
  32. Касымов Н. Х., Дадажанов Р. Н. Негативные плотные линейные порядки// Сиб. мат. ж. - 2017. -58, № 6. - С. 1306-1331.
  33. Касымов Н. Х., Дадажанов Р. Н. О вычислимости негативных представлений некоторых типов упорядоченных колец// Тез. докл. Межд. конф. «Алгебра и математическая логика: теория и приложения». - Казань, 2019. - С. 100-101.
  34. Касымов Н. Х., Ибрагимов Ф. Н. Структурная характеризация рекурсивно отделимых моделей// Докл. АН РУз. - 1998. - № 11. - С. 14-16.
  35. Касымов Н. Х., Ибрагимов Ф. Н. О негативности рекурсивно отделимых нумераций алгебр с артиновыми решетками конгруэнций// Докл. АН РУз. - 2013. - № 2. - С. 8-9.
  36. Касымов Н. Х., Ибрагимов Ф. Н. Сильно вычислимые нумерации и негативные эквивалентности// Докл. АН РУз. - 2014. - № 5. - С. 3-4.
  37. Касымов Н. Х., Ибрагимов Ф. Н. О непрерывности операций нумерованных алгебр в эффективно порожденных топологических пространствах// Докл. АН РУз. - 2016. - № 4. - С. 3-6.
  38. Касымов Н. Х., Ибрагимов Ф. Н. Вычислимо отделимые модели// Соврем. мат. Фундам. направл. - 2018. -64, № 4. - С. 682-705.
  39. Касымов Н. Х., Ибрагимов Ф. Н. Отделимые нумерации тел и эффективная вложимость в них колец// Сиб. мат. ж. - 2019. - 60, № 1. - С. 82-94.
  40. Касымов Н. Х., Куралов Ю. А. Вычислимость алгоритмических представлений упорядоченного кольца целых чисел// Вестн. НУУз. - 2017. - № 2. - С. 117-123.
  41. Касымов Н. Х., Морозов А. С. Логические программы без равенства и конструктивные представления// Вычисл. системы. - 1987. -122. - С. 73-96.
  42. Касымов Н. Х., Морозов А. С. Об определимости линейных порядков над негативными эквивалентностями// Алгебра и логика. - 2016. -55, № 1. - С. 37-57.
  43. Касымов Н. Х., Морозов А. С. О T1-отделимых нумерациях алгебр с артиновыми решетками конгруэнций// Тез. докл. Межд. конф. «Алгебра и математическая логика: теория и приложения». - Казань, 2019. - С. 118-120.
  44. Касымов Н. Х., Морозов А. С., Хо джамуратова И. А. О T1-отделимых нумерациях подпрямо неразложимых алгебр// Алгебра и логика. - 2021. -60, № 4. - С. 400-424.
  45. Касымов Н. Х., Хо джамуратова И. А. О компактных расширениях эффективных пространств// Докл. АН РУз. - 2017. - № 5. - С. 3-5.
  46. Касымов Н. Х., Хо джамуратова И. А. Топологические пространства над алгоритмическими представлениями универсальных алгебр// Итоги науки и техн. Соврем. пробл. мат. - 2018. -144. - С. 17-29.
  47. Касымов Н. Х., Хусаинов Б. М. Позитивные и негативные нумерации алгебр// Вычисл. системы. - 1991. -139. - С. 103-110.
  48. Касымов Н. Х., Хусаинов Б. М. Позитивные эквивалентности с конечными классами и алгебры над ними// Сиб. мат. ж. - 1992. -33, № 5. - С. 196-200.
  49. Кон П. М. Универсальная алгебра. - М.: Мир, 1968.
  50. Мальцев А. И. О вложении алгебраических колец в тела// Math. Ann. - 1937. -113. - С. 886-891.
  51. Мальцев А. И. К общей теории алгебраических систем// Мат. сб. - 1954. -35, № 1. - С. 3-20.
  52. Мальцев А. И. Конструктивные алгебры. I// Усп. мат. наук. - 1961. - 16, № 3. - С. 3-60.
  53. Мальцев А. И. Позитивные и негативные нумерации// Докл. АН СССР. - 1965. -160, № 2. - С. 278-280.
  54. Мальцев А. И. Алгебраические системы. - М.: Наука, 1970.
  55. Мальцев А. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.
  56. Мартин-Леф П. Очерки по конструктивной математике. - М.: Мир, 1975.
  57. Ро джерс Х. Д. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.
  58. Соар Р. И. Вычислимо перечислимые множества и степени. - Казань: Казанское мат. об-во, 2000.
  59. Успенский В. А. О вычислимых операциях// Докл. АН СССР. - 1955. - 103, № 5. - С. 773-776.
  60. Успенский В. А. Системы перечислимых множеств и их нумерации// Докл. АН СССР. - 1955. -105, № 6. - С. 1155-1158.
  61. Baur W. Rekursive Algebren mit Kettenbedingungen// Z. Math. Logik Grundl. Math. - 1974. - 20. - С. 37-46.
  62. Baur W. Uber recursive strukturen// Invent. Math. - 1974. -23, № 2. - С. 89-95
  63. 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. - 1980. -85. - С. 76-90.
  64. Broy M., Dosch W., Partsch H., Pepper P., Wirsing M. Existential quantifiers in abstract data types// Lecture Notes in Comput. Sci. - 1979. -71. - С. 73-81.
  65. Feiner L. Hierarchies of Boolean algebras// J. Symbolic Logic. - 1970. - 35, № 2. - С. 365-373.
  66. Fokina E. B., Khoussainov B., Semukhin P., Turetskiy D. Linear orders realized by C.E. equivalence relations// J. Symbolic Logic. - 2016. -81, № 2. - С. 463-482.
  67. Kamin S. Some definitions for algebraic data type specifications// SIGPLAN Notes. - 1979. - 14, № 3. - С. 28-37.
  68. Kasymov N. Kh., Dadajanov R. N., Ibragimov F. N. On the negativity of Hausdorff algorithmic representations of translational complete algebras// Тез. докл. Межд. конф. «Современные проблемы математики и физики». - Ташкент, 2019. - С. 78-79.
  69. Kasymov N. Kh., Dadajanov R. N., Karimova N. R. Effective compacts over coimmunne sets// Uzb. Math. J. - 2019. - № 3. - С. 26-32.
  70. Khoussainov B., Slaman T., Semukhin P. Presentasions of algebras// Arch. Math. Logic. - 2006. - 45, № 6. - С. 769-781.
  71. Morozov A. S., Truss J. K. On computable automorphisms of the rational numbers// J. Symbolic Logic. - 2001. -66, № 3. - С. 1458-1470.
  72. Nerode A. General topology and partial recursive functionals// Summaries Summer Inst. Symbolic Logic. - 1960. - 1957. - С. 247-251.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).