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 31 scientific papers (total in 32 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:

Document Type: Article
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. Sossinsky A.B., “Undecidability of the freedom problem for 3-manifold groups”, Russ. J. Math. Phys., 7:4 (2000), 482–487  mathscinet  zmath  isi
    2. V. Yu. Popov, “Markov Properties of Burnside Varieties of Semigroups”, Algebra and Logic, 42:1 (2003), 54–60  mathnet  crossref  mathscinet  zmath  elib
    3. 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
    4. 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
    5. 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
    6. 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
    7. 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
    8. Adian S.I., “Divisibility problem for one relator monoids”, Theoret. Comput. Sci., 339:1 (2005), 3–6  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    9. 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
    10. 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
    11. 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
    12. 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
    13. 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
    14. E. N. Pavlovskii, “Algoritmicheskaya raspoznavaemost svoistva konechnosti konechno-opredelennykh sistem”, Vestn. NGU. Ser. matem., mekh., inform., 6:4 (2006), 83–92  mathnet
    15. 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
    16. 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
    17. S. I. Adian, “Groups with Periodic Defining Relations”, Math. Notes, 83:3 (2008), 293–300  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    18. 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
    19. 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
    20. 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
    21. Alexei Myasnikov, Denis Osin, “Algorithmically finite groups”, Journal of Pure and Applied Algebra, 2011  crossref  mathscinet  isi  scopus
    22. Alexei Myasnikov, Alexander Ushakov, “Random van Kampen diagrams and algorithmic problems in groups”, Groups – Complexity – Cryptology, 3:3 (2011), 121  crossref  mathscinet  zmath  scopus
    23. 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
    24. V. A. Romankov, “Diofantova kriptografiya na beskonechnykh gruppakh”, PDM, 2012, no. 2(16), 15–42  mathnet
    25. 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
    26. V. N. Bezverkhnii, I. V. Dobrynina, “O svobodnykh podgruppakh v gruppakh Artina s drevesnoi strukturoi”, Chebyshevskii sb., 15:1 (2014), 32–42  mathnet
    27. J.W.. Johnson, “Weight ideals associated to regular and log-linear arrays”, Journal of Symbolic Computation, 2014  crossref  mathscinet  isi  scopus  scopus
    28. 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
    29. 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
    30. 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
    31. 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
    32. 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
  • Number of views:
    This page:1267
    Full text:428
    First page:4

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019