Реферат: Generic algorithms decide problems on sets of almost all inputs, outputting an indefinite answer for other rare inputs. We will prove that the word problem is generically decidable in finitely generated semigroups S, for which there exists a congruence θ such that the semigroup S/θ is an infinite residually finite monoid with cancellation property and decidable word problem. This generalizes the author’ earlier result on generic decidability of the word problem in finitely presented semigroups that remain infinite when adding commutativity and cancelling properties. Examples of such semigroups are one-relator semigroups as well as so-called balanced semigroups, for which generic decidability of the word problem has been proved by Won. In particular, balanced are Tseitin and Makanin’s classical semigroups with undecidable word problem.

Библиографическая ссылка: 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

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

Даты:

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

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

Web of science:	WOS:001102170100001
Scopus:	2-s2.0-85176769806
РИНЦ:	64589526
OpenAlex:	W4388697737

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

Альметрики: