Главная \ Наука \ Научные издания КФУ \ Ученые записки Казанского университета \ Ученые записки Казанского университета. Серия Физико-математические науки \ Архив

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

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

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

²Казанский (Приволжский) федеральный университет, г. Казань, 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)

Аннотация

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

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

Литература

Калверт У., Камминс Д., Найт Дж.Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика. – 2004. – Т. 43, № 6. – C. 666–701.
Knight J.F., Miller S., Boom M.V. Turing computable embeddings // J. Symb. Logic. – 2007. – V. 72, No 3. – P. 901–918.
Rossegger D. On functors enumerating structures // Сиб. электрон. матем. изв. – Т. 14. – P. 690–702. – doi: 10.17377/semi.2017.14.059.
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.
Эндрюс У., Душенин Д.И., Хилл К., Найт Дж.Ф., Мельников А.Г. Сравнение классов конечных сумм // Алгебра и логика. – 2015. – Т. 54, № 6. – C. 748–768. – doi: 10.17377/alglog.2015.54.605.
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.
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.