RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1988, том 27, номер 4, страницы 440–463 (Mi al2026)

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

Алгоритмические проблемы в многообразиях полугрупп

М. В. Сапир


Аннотация: Для любого многообразия полугрупп $\mathfrak{M}$ через $\mathrm{KO}(\mathfrak{M})$ и $\mathrm{KO}\cap(\mathfrak{M})$ соответственно обозначим классы конечно определенных в $\mathfrak{M}$ полугрупп и конечно определенных полугрупп, попавших в $\mathfrak{M}$. Обозначим через $K$ (через $L$) класс многообразий, не содержащих бесконечных периодических конечно-порожденных групп (полугрупп). В статье описаны конечнобазируемые многообразия полугрупп из $K$ с разрешимой проблемой равенства, т.е. такие многообразия $\mathfrak{M}$, что в каждой полугруппе из $\mathrm{KO}(\mathfrak{M})$ проблема равенства слов разрешима. Оказалось, что разрешимость проблемы равенства в конечнобазируемых многообразиях из $K$ эквивалентна финитной аппроксимируемости, представимости матрицами и разрешимости элементарной теории каждой полугруппы из $\mathrm{KO}(\mathfrak{M})$. Для многообразий $\mathfrak{M}$ из класса $L$ каждое из перечисленных выше условий эквивалентно разрешимости проблемы равенства и элементарной теории, финитной аппроксимируемости и представимости матрицами полугрупп из $\mathrm{KO}(\mathfrak{M})$, а также разрешимости универсальной теории множества конечных полугрупп из $\mathfrak{M}$.

УДК: 512.53

Поступило: 03.04.1985
Окончательный вариант: 19.03.1986


 Англоязычная версия: DOI: 10.1007/BF01978400

Реферативные базы данных:


© МИАН, 2024