Abstract: 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.

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

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

Dates:

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

Identifiers:

Web of science:	WOS:001102170100001
Scopus:	2-s2.0-85176769806
Elibrary:	64589526
OpenAlex:	W4388697737

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

Altmetrics: