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

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

Н. Х. Касымов

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

Автор, ответственный за переписку.
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
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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