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

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

Translated: 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

Dates:

Submitted:	Apr 29, 2022
Accepted:	Oct 13, 2023
Published print:	Oct 20, 2023
Published online:	Oct 20, 2023

Identifiers:

Elibrary:

54693363

Citing: Пока нет цитирований

Altmetrics: