Abstract:
The paper presents a detailed survey of results concerning the main decision problems of group theory and semigroup theory, including the word problem, the isomorphism problem, recognition problems, and other algorithmic questions related to them. The well-known theorems of Markov–Post, P. S. Novikov, Adian–Rabin, Higman, Magnus, and Lyndon are given with complete proofs. As a rule, the proofs presented in this survey are substantially simpler than those given in the original papers. For the sake of completeness, we first prove the insolubility of the halting problem for Turing machines, on which the insolubility of the word problem for semigroups is based. Specific attention is also paid to the simplest examples of semigroups with insoluble word problem. We give a detailed proof of the significant result of Lyndon that, in the class of groups presented by a system of defining relations for which the maximum mutual overlapping of any two relators is strictly less than one fifth of their lengths, the word problem is soluble, while insoluble word problems can occur when non-strict inequality is allowed. A proof of the corresponding result for finitely presented semigroups is also given, when the corresponding fraction is one half.
\Bibitem{AdiDur00}
\by S.~I.~Adian, V.~G.~Durnev
\paper Decision problems for groups and semigroups
\jour Russian Math. Surveys
\yr 2000
\vol 55
\issue 2
\pages 207--296
\mathnet{http://mi.mathnet.ru/eng/rm267}
\crossref{https://doi.org/10.1070/rm2000v055n02ABEH000267}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1779941}
\zmath{https://zbmath.org/?q=an:0958.20029}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2000RuMaS..55..207A}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000089971300001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0034415361}
Linking options:
https://www.mathnet.ru/eng/rm267
https://doi.org/10.1070/rm2000v055n02ABEH000267
https://www.mathnet.ru/eng/rm/v55/i2/p3
This publication is cited in the following 53 articles:
Zbigniew Lipiński, Jolanta Mizera-Pietraszko, Jolanta Tańcula, “A Study of Cryptographic Algorithms on Special Linear Group Over Ring of Integers Modulo m”, IEEE Access, 13 (2025), 5606
Eylem Guzel Karpuz, Fatmanur Y{\i}ld{\i}z, “Complete Rewriting System of Schützenberger – Crossed Product of Monoids”, Karamanoğlu Mehmetbey Üniversitesi Mühendislik ve Doğa Bilimleri Dergisi, 6:2 (2024), 33
V. A. Roman'kov, “Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank”, Izv. Math., 87:4 (2023), 798–816
A. N. Rybalov, “Generic Complexity of the Word Problem in Some Semigroups”, Algebra Logic, 61:6 (2023), 524
M. Rybakov, “Computational complexity of the word problem in modal and pseudo-Boolean algebras
with a small number of generators”, Russian Math. (Iz. VUZ), 66:5 (2022), 33–48
V. A. Roman'kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Sib. elektron. matem. izv., 19:1 (2022), 387–403
I. V. Dobrynina, “O podgruppakh v gruppakh Artina s drevesnoi strukturoi”, Chebyshevskii sb., 23:3 (2022), 118–132
A. N. Rybalov, “O genericheskoi slozhnosti problemy ravenstva v nekotorykh polugruppakh”, Algebra i logika, 61:6 (2022), 766–783
Zbigniew Lipiński, Jolanta Mizera-Pietraszko, Lecture Notes in Computer Science, 13758, Intelligent Information and Database Systems, 2022, 643
V. A. Roman'kov, “Algorithmic theory of solvable groups”, PDM, 2021, no. 52, 16–64
M. N. Rybakov, “Slozhnost problemy ravenstva slov v mnogoobraziyakh modalnykh algebr”, Vestnik TvGU. Seriya: Prikladnaya matematika, 2021, no. 3, 5–17
Nyberg-Brodda C.-F., “The Word Problem For One-Relation Monoids: a Survey”, Semigr. Forum, 103:2 (2021), 297–355
Karpuz E.G., Ozalan N.U., “Word Problem For Special Braid Groups(1)”, Quaest. Math., 43:7 (2020), 931–957
Cevik A.S., Karpuz E.G., Alsulami H.H., Cetinalp E.K., “A Grobner-Shirshov Basis Over a Special Type of Braid Monoids”, AIMS Math., 5:5 (2020), 4357–4370
Cevik A.S., Albargi A.H., “A Solution of the Word Problem For Braid Groups Via the Complex Reflection Group G(12)”, Filomat, 34:2, SI (2020), 461–467
Rybalov A., Iv International Scientific and Technical Conference Mechanical Science and Technology Update (Mstu-2020), Journal of Physics Conference Series, 1546, IOP Publishing Ltd, 2020
Cetinalp E.K., Karpuz E.G., Cevik A.S., “Complete Rewriting System For the Schutzenberger Product of N Groups”, Asian-Eur. J. Math., 12:1 (2019), 1950012
Ozalan N.U., Wazzan S.A., Karpuz E.G., “Grobner-Shirshov Bases For Congruence Classes of Complex Reflection Groups”, Asian-Eur. J. Math., 12:6, SI (2019), 2040013
Cetinalp E.K., Karpuz E.G., Sahin R., Ates F., “Complete Rewriting System and Growth Series For Extended Generalized Hecke Groups”, J. Math. Ext., 13:4 (2019), 41–55
Karpuz E.G., Ates F., Urlu N., Cevik A.S., Cangul I.N., “A note on the Gröbner-Shirshov bases over ad-hoc extensions of groups”, Filomat, 30:4 (2016), 1037–1043
Citation in format AMSBIB
Contact us: