Geodesic
Generic complexity of word problem in some semigroups
Algebra i logika, Tome 61 (2022) no. 6, pp. 766-783

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathfrak{S}$, for which there exists a congruence $\theta$ such that the semigroup $\mathfrak{S}/ \theta$ 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.
Keywords: word problem, generic decidability, finitely generated semigroup. 
@article{AL_2022_61_6_a6,
     author = {A. N. Rybalov},
     title = {Generic complexity of word problem in some semigroups},
     journal = {Algebra i logika},
     pages = {766--783},
     publisher = {mathdoc},
     volume = {61},
     number = {6},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2022_61_6_a6/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic complexity of word problem in some semigroups
JO  - Algebra i logika
PY  - 2022
SP  - 766
EP  - 783
VL  - 61
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2022_61_6_a6/
LA  - ru
ID  - AL_2022_61_6_a6
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic complexity of word problem in some semigroups
%J Algebra i logika
%D 2022
%P 766-783
%V 61
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2022_61_6_a6/
%G ru
%F AL_2022_61_6_a6
A. N. Rybalov. Generic complexity of word problem in some semigroups. Algebra i logika, Tome 61 (2022) no. 6, pp. 766-783. http://geodesic.mathdoc.fr/item/AL_2022_61_6_a6/