Uspekhi Matematicheskikh Nauk
General information
Latest issue
Impact factor
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Uspekhi Mat. Nauk:

Personal entry:
Save password
Forgotten password?

Uspekhi Mat. Nauk, 2000, Volume 55, Issue 2(332), Pages 3–94 (Mi umn267)  

This article is cited in 39 scientific papers (total in 40 papers)

Decision problems for groups and semigroups

S. I. Adiana, V. G. Durnevb

a Steklov Mathematical Institute, Russian Academy of Sciences
b P. G. Demidov Yaroslavl State University

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.


Full text: PDF file (665 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2000, 55:2, 207–296

Bibliographic databases:

UDC: 510.53+512.53+512.54
MSC: Primary 20F10, 20M05; Secondary 20E06, 03D40, 03D10
Received: 26.01.2000

Citation: S. I. Adian, V. G. Durnev, “Decision problems for groups and semigroups”, Uspekhi Mat. Nauk, 55:2(332) (2000), 3–94; Russian Math. Surveys, 55:2 (2000), 207–296

Citation in format AMSBIB
\by S.~I.~Adian, V.~G.~Durnev
\paper Decision problems for groups and semigroups
\jour Uspekhi Mat. Nauk
\yr 2000
\vol 55
\issue 2(332)
\pages 3--94
\jour Russian Math. Surveys
\yr 2000
\vol 55
\issue 2
\pages 207--296

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Karpuz E.G., Ozalan N.U., “Word Problem For Special Braid Groups(1)”, Quaest. Math., 1–27  crossref  isi  scopus
    2. Sossinsky A.B., “Undecidability of the freedom problem for 3-manifold groups”, Russ. J. Math. Phys., 7:4 (2000), 482–487  mathscinet  zmath  isi
    3. V. Yu. Popov, “Markov Properties of Burnside Varieties of Semigroups”, Algebra and Logic, 42:1 (2003), 54–60  mathnet  crossref  mathscinet  zmath  elib
    4. S. I. Adian, F. Grunevald, J. Mennicke, “On Prime Quaternions, Hurwitz Relations, and a New Operation of Group Extension”, Proc. Steklov Inst. Math., 242 (2003), 3–17  mathnet  mathscinet  zmath
    5. Leksin V.P., Chernavskii A.V., “Unrecognizability of manifolds. On Novikov's theorem on the unrecognizability of the sphere $\mathbb S^n$ for $n\ge 5$”, Dokl. Math., 68:1 (2003), 89–92  mathnet  mathscinet  mathscinet  zmath  isi  elib
    6. Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694  crossref  mathscinet  zmath  isi  elib  scopus
    7. Bokut L., Fong Y., Shiao L.S., “Grobner-Shirshov bases for algebras, groups, and semigroups”, Proceedings of the Third International Algebra Conference, 2003, 17–32  crossref  mathscinet  zmath  isi
    8. M. A. Shtan'ko, “Markov's theorem and algorithmically non-recognizable combinatorial manifolds”, Izv. Math., 68:1 (2004), 205–221  mathnet  crossref  crossref  mathscinet  zmath  isi
    9. Adian S.I., “Divisibility problem for one relator monoids”, Theoret. Comput. Sci., 339:1 (2005), 3–6  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    10. Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Average-case complexity and decision problems in group theory”, Adv. Math., 190:2 (2005), 343–359  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    11. L. D. Beklemishev, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, M. R. Pentus, A. A. Razborov, A. L. Semenov, V. A. Uspenskii, “Sergei Ivanovich Adian (on his 75th birthday)”, Russian Math. Surveys, 61:3 (2006), 575–588  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    12. Chernavsky A.V., Leksine V.P., “Unrecognizability of manifolds”, Ann. Pure Appl. Logic, 141:3 (2006), 325–335  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    13. Kreuzer M., Myasnikov A., Rosenberger G., Ushakov A., “Quotient tests and Grobner bases”, Combinatorial Group Theory, Discrete Groups, and Number Theory, Contemporary Mathematics Series, 421, 2006, 187–200  crossref  mathscinet  zmath  isi
    14. Borovik A.V., Myasnikov A.G., “Quotient tests and random walks in computational group theory”, Topological and Asymptotic Aspects of Group Theory, Contemporary Mathematics Series, 394, 2006, 31–45  crossref  mathscinet  zmath  isi
    15. E. N. Pavlovskii, “Algoritmicheskaya raspoznavaemost svoistva konechnosti konechno-opredelennykh sistem”, Vestn. NGU. Ser. matem., mekh., inform., 6:4 (2006), 83–92  mathnet
    16. Borovik A.V., Myasnikov A.G., Remeslennikov V.N., “The conjugacy problem in amalgamated products. I. Regular elements and black holes”, Internat. J. Algebra Comput., 17:7 (2007), 1299–1333  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    17. Myasnikov A., “Generic Complexity of Undecidable Problems”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 4649, eds. Diekert V., Volkov M., Voronkov A., Springer-Verlag Berlin, 2007, 407–417  crossref  zmath  isi
    18. S. I. Adian, “Groups with Periodic Defining Relations”, Math. Notes, 83:3 (2008), 293–300  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    19. Myasnikov A.G., Rybalov A.N., “Generic Complexity of Undecidable Problems”, J. Symb. Log., 73:2 (2008), 656–673  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    20. Cain A.J., Maltcev V., “Decision problems for finitely presented and one-relation semigroups and monoids”, Internat. J. Algebra Comput., 19:6 (2009), 747–770  crossref  mathscinet  zmath  isi  scopus  scopus
    21. Karpuz E.G., Çevik A.S., “The word and generalized word problem for semigroups under wreath products”, Bull. Math. Soc. Sci. Math. Roum., Nouv. Sér., 52:2 (2009), 151–160  zmath  isi
    22. Alexei Myasnikov, Denis Osin, “Algorithmically finite groups”, Journal of Pure and Applied Algebra, 2011  crossref  mathscinet  isi  scopus
    23. Alexei Myasnikov, Alexander Ushakov, “Random van Kampen diagrams and algorithmic problems in groups”, Groups – Complexity – Cryptology, 3:3 (2011), 121  crossref  mathscinet  zmath  scopus
    24. A. G. Myasnikov, V. N. Remeslennikov, E. V. Frenkel, “Amalgamated Free Product of Groups: Normal Forms and Measures”, Math. Notes, 91:4 (2012), 592–596  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    25. V. A. Romankov, “Diofantova kriptografiya na beskonechnykh gruppakh”, PDM, 2012, no. 2(16), 15–42  mathnet
    26. E. G. Karpuz, A. S. Cevik, “Gröbner–Shirshov Bases for Extended modular, Extended Hecke, and Picard Groups”, Math. Notes, 92:5 (2012), 636–642  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    27. V. N. Bezverkhnii, I. V. Dobrynina, “O svobodnykh podgruppakh v gruppakh Artina s drevesnoi strukturoi”, Chebyshevskii sb., 15:1 (2014), 32–42  mathnet
    28. J.W.. Johnson, “Weight ideals associated to regular and log-linear arrays”, Journal of Symbolic Computation, 2014  crossref  mathscinet  isi  scopus  scopus
    29. V. G. Durnev, O. V. Zetkina, “Nekotorye rezultaty, poluchennye v Yaroslavskom otdelenii algebraicheskoi shkoly M. D. Grindlingera”, Chebyshevskii sb., 15:4 (2014), 5–31  mathnet
    30. Karpuz E.G., Ates F., Cevik A.S., “Grobner-Shirshov Bases of Some Weyl Groups”, 45, no. 4, 2015, 1165–1175  crossref  mathscinet  zmath  isi  scopus  scopus
    31. 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  crossref  mathscinet  zmath  isi  elib  scopus
    32. Szabo P., Siekmann J., Hoche M., “What Is Essential Unification?”, Martin Davis on Computability, Computational Logic, and Mathematical Foundations, Outstanding Contributions to Logic, 10, eds. Omodeo E., Policriti A., Springer International Publishing Ag, 2016, 285–314  crossref  mathscinet  isi
    33. 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  crossref  mathscinet  zmath  isi  scopus
    34. 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  crossref  isi
    35. 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  isi
    36. 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  crossref  mathscinet  isi
    37. 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  crossref  mathscinet  isi
    38. 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  crossref  isi
    39. V. A. Roman'kov, “Algorithmic theory of solvable groups”, PDM, 2021, no. 52, 16–64  mathnet  crossref  elib
    40. M. N. Rybakov, “Slozhnost problemy ravenstva slov v mnogoobraziyakh modalnykh algebr”, Vestnik TvGU. Seriya: Prikladnaya matematika, 2021, no. 3, 5–17  mathnet  crossref  elib
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:1619
    Full text:624
    First page:4

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022