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/

[1] A. A. Markov, “Nevozmozhnost nekotorykh algorifmov v teorii assotsiativnykh sistem”, DAN SSSR, 55:7 (1947), 587–590

[2] E. L. Post, “Recursive unsolvability of a problem of Thue”, J. Symb. Log., 12:1 (1947), 1–11 | DOI | MR | Zbl

[3] P. S. Novikov, “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp”, Tr. MIAN SSSR, 44, 1955, 3–143 | MR

[4] G. S. Tseitin, “Assotsiativnoe ischislenie s nerazreshimoi problemoi ekvivalentnosti”, Problemy konstruktivnogo napravleniya v matematike. 1, Tr. MIAN SSSR, 52, 1958, 172–189 | Zbl

[5] G. S. Makanin, “K probleme tozhdestva v konechno-opredelennykh polugruppakh”, Dokl. AN SSSR, 171:2 (1966), 285–287 | MR | Zbl

[6] Yu. V. Matiyasevich, “Prostye primery nerazreshimykh kanonicheskikh ischislenii”, Problemy konstruktivnogo napravleniya v matematike. 4, Tr. MIAN SSSR, 93, 1967, 50–88 | Zbl

[7] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity, decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[8] W. Woess, “Cogrowth of groups and simple random walks”, Arch. Math., 41 (1983), 363–370 | DOI | MR | Zbl

[9] L. Bartholdi, “Counting paths in graphs”, Enseign. Math., II. Sér., 45:1/2 (1999), 83–131 | MR | Zbl

[10] R. I. Grigorchuk, “Symmetrical random walks on discrete groups”, Multicomponent random systems, Adv. Probab. Related Topics, 6, eds. R. L. Dobrushin et al., Marcel Dekker, Inc., New York, 1980, 285–325 | MR

[11] D. Won, Word problems on balanced semigroups and balanced groups, ProQuest Disser. Publ., No 3296964, City Univ. New York, 2008, 79 pp. | MR

[12] S. I. Adyan, V. G. Durnev, “Algoritmicheskie problemy dlya grupp i polugrupp”, UMN, 55:2(332) (2000), 3–94 | DOI | MR | Zbl

[13] C.-F. Nyberg-Brodda, “The word problem for one-relation monoids: a survey”, Semigroup Forum, 103:2 (2021), 297–355 | DOI | MR | Zbl

[14] A. Rybalov, “A generic algorithm for the word problem in semigroups and groups”, J. Physics: Conference Series, 1546, Proc. Theor. Comp. Sci., section of IV Int. sci. conf. "‘Mechanical Science and Technology Update"’ (2020), 012100, 1–10

[15] A. N. Rybalov, “Genericheskii algoritm dlya problemy ravenstva v nekotorykh polugruppakh”, Vestn. Omsk. un-ta, 26:1 (2021), 16–20 | DOI

[16] D. Hirschfeldt, “Some questions in computable mathematics”, Computability and complexity, Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, Lect. Notes Comput. Sci., 10010, eds. A. Day et al., Springer, Cham, 2017, 22–55 | DOI | MR | Zbl

[17] A. Meyer, “An open problem on creative sets”, Recursive Function Theory Newsletter, 4 (1973), 15–16

[18] A. Klifford, G. Preston, Algebraicheskaya teoriya polugrupp, v. 1, Mir, M., 1972

[19] U. Feller, Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 1, Mir, M., 1964 | MR

[20] A. I. Maltsev, “O gomomorfizmakh na konechnye gruppy”, Uch. zap. Ivanovsk. ped. in-ta, 18:5 (1958), 49–60

[21] A. G. Myasnikov, A. N. Rybalov, “Generic complexity of undecidable problems”, J. Symb. Log., 73:2 (2008), 656–673 | DOI | MR | Zbl