Вычислимая вложимость классов алгебраических структур с отношением конгруэнтности

С. Ватев1, Х. Ганчев1, И.Ш. Калимуллин2

1Софийский университет имени святого Климента Охридского, г. София, 1504, Болгария

2Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF

Для цитирования: Ватев С., Ганчев Х., Калимуллин И.Ш. Вычислимая вложимость классов алгебраических структур с отношением конгруэнтности // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2018. – Т. 160, кн. 4. – С. 731–737.

For citation: Vatev S., Ganchev H., Kalimullin I.Sh. Computable embedding of classes of algebraic structures with congruence relation. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 4, pp. 731–737. (In Russian)

Аннотация

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

Ключевые слова: оператор перечисления, тьюринговый оператор, алгебраическая структура, атомная диаграмма

Литература

  1. Калверт У., Камминс Д., Найт Дж.Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика. – 2004. – Т. 43, № 6. – C. 666–701.
  2. Knight J.F., Miller S., Boom M.V. Turing computable embeddings // J. Symb. Logic. – 2007. – V. 72, No 3. – P. 901–918.
  3. Rossegger D. On functors enumerating structures // Сиб. электрон. матем. изв. – Т. 14. – P. 690–702. – doi: 10.17377/semi.2017.14.059.
  4. Ocasio-Gonzalez V.A. Turing computable embeddings and coding families of sets // Cooper S.B., Dawar A., Lowe B. (Eds.) How the World Computes. CiE 2012. Lecture Notes in Computer Science, V. 7318. – Berlin, Heidelberg: Springer, 2012. – P. 539–548. – doi: 10.1007/978-3-642-30870-3_54.
  5. Эндрюс У., Душенин Д.И., Хилл К., Найт Дж.Ф., Мельников А.Г. Сравнение классов конечных сумм // Алгебра и логика. – 2015. – Т. 54, № 6. – C. 748–768. – doi: 10.17377/alglog.2015.54.605.
  6. Bazhenov N. Turing computable embeddings, computable infinitary equivalence, and linear orders // Kari J., Manea F., Petre I. (Eds.) Unveiling Dynamics and Complexity. CiE 2017. Lecture Notes in Computer Science, V. 10307. – Cham: Springer, 2017. – P. 141–151. – doi: 10.1007/978-3-319-58741-7_15.
  7. Kalimullin I.Sh. Computable embeddings of classes of structures under enumeration and turing operators // Lobachevskii J. Math. – 2018. – V. 39, No 1. – P. 84–88. – doi: 10.1134/S1995080218010146.

Поступила в редакцию

11.09.18

 

Ватев Стефан, PhD, главный ассистент

Софийский университет имени святого Климента Охридского

бул. Цар Освободител, д. 15, г. София, 1504, Болгария

 

Ганчев Христо, PhD, профессор

Софийский университет имени святого Климента Охридского

бул. Цар Освободител, д. 15, г. София, 1504, Болгария

Калимуллин Искандер Шагитович, доктор физико-математических наук, главный научный сотрудник кафедры алгебры и математической логики

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: ikalimul@gmail.com

 

Контент доступен под лицензией Creative Commons Attribution 4.0 License.