Реферат: Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.

Библиографическая ссылка: Рыбалов А.Н.
О генерической сложности проблемы равенства в некоторых полугруппах
Алгебра и логика. 2022. Т.61. №6. С.766-783. DOI: 10.33048/alglog.2022.61.606 РИНЦ

Переводная: Rybalov A.N.
Generic Complexity of the Word Problem in Some Semigroups
Algebra and Logic. 2022. V.61. N6. P.524-536. DOI: 10.1007/s10469-023-09717-y WOS Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	29 апр. 2022 г.
Принята к публикации:	13 окт. 2023 г.
Опубликована в печати:	20 окт. 2023 г.
Опубликована online:	20 окт. 2023 г.

Идентификаторы БД:

РИНЦ:

54693363

Цитирование в БД: Пока нет цитирований

Альметрики: