RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Казанского университета. Серия Физико-математические науки // Архив

Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 2018, том 160, книга 4, страницы 731–737 (Mi uzku1491)

Эта публикация цитируется в 1 статье

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

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

a Софийский университет имени святого Климента Охридского, г. София, 1504, Болгария
b Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

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

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

УДК: 510.5

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



© МИАН, 2024