Voir la notice de l'article provenant de la source Math-Net.Ru
@article{PDM_2021_2_a1,
author = {V. A. Roman'kov},
title = {Algorithmic theory of solvable groups},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {16--64},
publisher = {mathdoc},
number = {2},
year = {2021},
language = {en},
url = {http://geodesic.mathdoc.fr/item/PDM_2021_2_a1/}
}
V. A. Roman'kov. Algorithmic theory of solvable groups. Prikladnaâ diskretnaâ matematika, no. 2 (2021), pp. 16-64. http://geodesic.mathdoc.fr/item/PDM_2021_2_a1/
[1] Adian S. I., “Unsolvability of some algorithmic problems in the theory of groups”, Tr. Mosk. Mat. Obs., 6, 1957, 231–298 (in Russian)
[2] Adian S. I., Durnev V. G., “Decision problems for groups and semigroups”, Russian Math. Surveys, 55:2 (2000), 207–296
[3] Agalakov S. A., “Finite separability of groups and Lie algebras”, Algebra and Logic, 22:4 (1983), 261–268
[4] Amaglobeli M. G., “Varieties of exponential $MR$-groups”, Doklady Math., 101:1 (2020), 1–4
[5] Anissimov A., Seifert A. W., “Zur algebraischen Charakteristik der durch kontext-freie Sprachen definierten Gruppen”, Elektron. Inform. Verarb. Kybern., 11 (1975), 695–702 (in German)
[6] Assman B., Eick B., “Computing polycyclic presentations for polycyclic rational matrix groups”, J. of Symb. Comp., 40:6 (2005), 1269–1284
[7] Babai L, Beal R., Seress A., “Polynomial-time theory of matrix groups”, Proc. STOC'09 (May 31–June 2, 2009, Bethesda, Maryland), 55–64
[8] Bachmuth S., “Automorphisms of free metabelian groups”, Trans. Amer. Math. Soc., 118 (1965), 93–104
[9] Baumslag G., Lecture Notes on Nilpotent Groups, C.B.M.S. Regional Conf. Series, 2, Providence, 1971, 73 pp.
[10] Baumslag G., “Residually finite groups with the same finite images”, Compositio Math., 29 (1974), 249–252
[11] Baumslag G., Cannonito F. B., Robinson D. J. S., “The algorithmic theory of finitely generated metabelian groups”, Trans. Amer. Math. Soc., 344:2 (1994), 629–648
[12] Baumslag G., Cannonito F. B., Robinson D. J. S., Segal D., “The algorithmic theory of polycyclic-by-finite groups”, J. Algebra, 141 (1991), 118–149
[13] Baumslag G., Gildenhuys D., Strebel R., “Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I”, J. Pure Appl. Algebra, 39 (1986), 53–94
[14] Baumslag G., Gildenhuys D., Strebel R., “Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. II”, J. Algebra, 97 (1985), 278–285
[15] Baumslag G., Miller C. F. III, Ostheimer G., “Subgroups of free metabelian groups”, Groups Geom. Dyn., 4 (2010), 657–679
[16] Baumslag G., Miller C. F. III, Ostheimer G., “Decomposability of finitely generated torsion-free nilpotent groups”, Int. J. Algebra and Comput., 26:8 (2016), 1529–1546
[17] Baumslag G., Myasnikov A. G., Remeslennikov V. N., “Algebraic geometry over groups. I”, J. Algebra, 219 (1999), 16–79
[18] Bassino F., Kapovich I., Lohrey M., et al., Complexity and Randomness in Group Theory, GAGTA BOOK, Walter de Gruyter GmbH, Berlin–Boston, 2020, 386 pp.
[19] Bazhenova G. A., “Rational sets in finitely generated nilpotent groups”, Algebra and Logic, 39:4 (2000), 215–223
[20] Bazhenova G. A., “Closure of one class of groups under free product”, Siberian Math. J., 41:4 (2000), 611–613
[21] Beals R., “Algorithms for matrix groups and the Tits alternative”, J. Comput. System Sci., 58:2 (1999), 260–279
[22] Belegradek O. V., “The Mal'cev correspondence revisited”, Proc. Int. Conf. Algebra (Novosibirsk, 1989), v. 1, Contemp. Math., 131, Amer. Math. Soc., Providence, RI, 1992, 37–59
[23] Belegradek O. V., “The model theory of unitriangular groups”, Ann. Pure Appl. Logic, 68 (1994), 225–261
[24] Belegradek O. V., “Model theory of unitriangular groups”, Model Theory and Applications, Amer. Math. Soc. Transl. Ser. 2, 195, 1999, 1–116
[25] Benois M., “Parties rationnelles du groupe libre”, C. R. Acad. Sci., Paris, Ser. A, 269 (1969), 1188–1190 (in French)
[26] Bieri R., Neumann W. D., Strebel R., “A geometric invariant of discrete groups”, Invent. Math., 90:3 (1987), 451–477
[27] Bieri R., Strebel R., “Valuations and finitely presented metabelian groups”, Proc. London. Math. Soc., 41:1 (1980), 439–464
[28] Bieri R., Strebel R., “A geometric invariant for nilpotent-by-abelian-by-finite groups”, J. Pure Appl. Algebra, 25:1 (1982), 1–20
[29] Birget J. C., Olshanskii A. Y., Rips E., Sapir M. V., “Isoperimetric and isodiametric functions of groups and computational complexity of the word problem”, Ann. Math., 156:2 (2002), 467–518
[30] Birman J. S., Braids, Links and Mapping Class Groups, Ann. Math. Stud., 82, Princeton Univ. Press, Princeton, 1974, 237 pp.
[31] Blackburn S., “Conjugacy in nilpotent groups”, Proc. Amer. Math. Soc., 16 (1965), 143–148
[32] Bokut L. A., Kukin G. P., Algorithmic and Combinatorial Algebra, Math. and its Applications, 255, Springer, Netherlands, 1994, xvi+384 pp.
[33] Boone W. W., “The word problem”, Ann. Math., 70:2 (1959), 207–265
[34] Chandler B., Magnus W., The History of Combinatorial Group Theory. A Case Study in the History of Ideas, Studies in the History of Math. and Physical Sciences, 9, Springer Verlag, N.Y., 1982, viii+234 pp.
[35] Chapuis O., “Universal theory of certain solvable groups and bounded Ore group-rings”, J. Algebra, 176:2 (1995), 368–391
[36] Chapuis O., “$\forall$-free metabelian groups”, J. Symb. Logic, 62:1 (1997), 159–174
[37] Chapuis O., “On the theories of free solvable groups”, J. Pure Appl. Algebra, 131:1 (1998), 13–24
[38] Cadilhac M., Chistikov D., Zetzsche G., “Rational subsets of Baumslag — Solitar groups”, Proc. ICALP 2020, Dagstuhl Publ., Leibniz, 2020, 116, 16 pp.
[39] Dahmani F., Groves D., “The isomorphism problem for toral relatively hyperbolic groups”, Publications mathématiques de l'IHES, 107:1 (2008), 211–290
[40] Dahmani F., Guirardel D. V., “Foliations for solving equations in groups: free, virtually free, and hyperbolic groups”, J. Topology, 3:2 (2010), 343–404
[41] Danyarova E. Yu., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Systems, Siberian Branch of Russian Academy of Sciences Publ., Novosibirsk, 2016, 243 pp. (in Russian)
[42] Dehn M., “Über unendliche diskontinuierliche Gruppen”, Math. Ann., 71:1 (1911), 116–144 (in German)
[43] Detinko A. S., Eick B., Flanneri D. L., “Computing with matrix groups over infinite fields”, London Math. Soc. Lect. Note Ser., 387 (2011), 256–270
[44] Detinko A. S., Eick B., Flannery D. L., Nilmat — Computing with nilpotent matrix groups, A refereed GAP, 2007
[45] Diekert V., Gutierrez C., Hagenah C., “The existential theory of equations with rational constraints in free groups is PSPACE-complete”, Inform. and Computation, 202:2 (2005), 105–140
[46] Diekert V., Lohrey M., “Word equations over graph products”, Int. J. Algebra Comput., 18:3 (2008), 493–533
[47] Dixon J. D., Formanek E. W., Poland J. C., Ribes L., “Profinite completions and isomorphic finite quotients”, J. Pure Appl. Algebra, 23:3 (1982), 227–231
[48] Droms C., Lewin J., Servatius H., “The length of elements in free solvable groups”, Proc. Amer. Math. Soc., 119 (1993), 27–33
[49] Duchin M., Liang H., Shapiro M., “Equations in nilpotent groups”, Proc. Amer. Math. Soc., 143:11 (2015), 4723–4731
[50] Dyck W. von, “Analysis Situs I”, Math. Ann., 32 (1888), 457–512
[51] Ehrenfeucht A., Karhumaki J., Rozenberg G., “The (generalized) Post correspondence problem with lists consisting of two words is decidable”, Theoret. Comput. Sci., 21 (1982), 119–144
[52] Eick B., “Computing with infinite polycyclic groups”, Groups and Computations, Proc. Int. Conf. (Ohio State Univ., June 15–19, 1999), v. III, eds. G. R. Baker, W. D. Neumann, K. Rubin, Walter de Gruyterm, Berlin–New York, 139–154
[53] Eilenberg S., Schutzenberger M. P., “Rational sets in commutative monoids”, J. Algebra, 13 (1969), 173–191
[54] Eklof P. C., Fischer E. R., “The elementary theory of abelian groups”, Ann. Math. Logic, 4:2 (1972), 115–171
[55] Elder M., “A linear-time algorithm to compute geodesics in solvable Baumslag — Solitar groups”, Illinois J. Math., 54:1 (2010), 109–128
[56] Elder M., Rechnitzer A., “Some geodesic problems in groups”, Groups, Complexity, Cryptology, 2 (2010), 223–229
[57] Ershov Yu. L., “Elementary group theories”, Dokl. Akad. Nauk SSSR, 203:6 (1972), 1240–1243 (in Russian)
[58] Fedorov E. S., “Symmetry of regular systems of figures”, Zap. Imperatorsk. S-Peterburgsk. Mineral. Občestva Verhandl. d. Russisch-Kaiserl. Mineral. Gesellschaft zu St. Petersburg, 28 (1891), 1–146 (in Russian)
[59] Formanek E., “Conjugacy separability in polycyclic groups”, J. Algebra, 42 (1976), 1–10
[60] Furst M. L., Hopcroft J., Lucks E. M., “Polynomial-time algorithms for permutation groups”, ICEE C.S., 198, Proc. 21st FOCS (1980), 36–41
[61] Gaglione J. R. and Spellman D., “The persistence of universal formulae in free algebras.”, Bull. Austr. Math. Soc., 36 (1987), 11–17
[62] Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, N.Y., 1979, 338 pp.
[63] Garreta A., Miasnikov A., and Ovchinnikov D., “Random nilpotent groups, polycyclic presentations, and Diophantine problems”, Groups, Complexity, Cryptology, 9:2 (2017), 99–115
[64] Garreta A., Legarreta L., Miasnikov A., and Ovchinnikov D., “Metabelian groups: Full-rank presentations, randomness and Diophantine problems”, J. Group Theory, 2020 (to appear)
[65] Gersten S. M., “Dehn functions and $l_1$-norms for finite presentations”, Algorithms and Classification in Combinatorial Group Theory, MSRI Publ., 23, eds. G. Baumslag, C. F. Miller, Springer Verlag, Berlin, 1992
[66] Gilman R. H., “Formal languages and infinite groups”, Geometric and Computational Perspectives on Infinite Groups, DIMACS, Ser. Discr. Math. Theor. Comput. Sci., 25, Providence, 1996, 27–51
[67] Gilman R. H., “Formal languages and their application to combinatorial group theory”, Groups, Languages, Algorithms, Contemporary Math. Series, 378, Providence, 2005, 1–36
[68] Gromov M., “Asymptotic invariants of infinite groups.”, Geometric Group Theory, Cambridge Univ. Press, Cambridge, 1993, 1–295
[69] Grunewald F., Pickel P. F., Segal D., “Polycyclic groups with isomorphic finite quotients”, Ann. Math., 111 (1980), 155–195
[70] Grunewald F., Segal D., “The solubility of certain decision problems in arithmetic and algebra”, Bull. Amer. Math. Soc., 1:6 (1979), 915–918
[71] Grunewald F. and Segal D., “Some general algorithms. I. Arithmetic groups. II. Nilpotent groups”, Ann. Math., 112:3 (1980), 531–583
[72] Grunewald F., Zalesskii P., “Genus for groups”, J. Algebra, 326:1 (2011), 130–168
[73] Grunschlag Z., Algorithms in Geometric Group Theory, PhD. Thesis, University of California at Berkley, 1999, 127 pp.
[74] Gupta C. K., Timoshenko E. I., “Partially commutative metabelian groups: centralizers and elementary equivalence”, Algebra and Logic, 48:3 (2009), 173–192
[75] Gupta C. K., Timoshenko\:E. I., “Universal theories for partially commutative metabelian groups”, Algebra and Logic, 50:1 (2011), 3–25
[76] Gupta C. K., Timoshenko E.,I., “Properties and universal theories for partially commutative nilpotent metabelian groups”, Algebra and Logic, 51:4 (2012), 285–305
[77] Hall M. Jr., The Theory of Groups, Macmillan, N.Y., 1959, 434 pp.
[78] Hall P., “Finiteness conditions for soluble groups”, Proc. London Math. Soc., 4:3 (1954), 419–436
[79] Hall P., “Finite-by-nilpotent groups”, Proc. Cambridge Philos. Soc., 52 (1956), 611–616
[80] Hall P., “Some sufficient conditions for a group to be nilpotent”, Illinois J. Math., 2 (1958), 787–801
[81] Hall P., “On the finiteness of certain soluble groups”, Proc. London Math. Soc., 9:3 (1959), 595–622
[82] Hall P., The Edmonton Notes on Nilpotent Groups, Queen Mary College Math. Notes, Queen Mary College, London, 1969, 76 pp.
[83] Hall P., The collected Works of Philip Hall, Oxford Science Publications, Oxford University Press, N.Y., 1988, 776 pp.
[84] Higgins P. J., Lyndon R. C., “Equivalence of elements under automorphisms of a free group”, J. London Math. Soc., 8 (1974), 254–258
[85] Hirsch K. A., “On infinite soluble groups, I”, Proc. London Math. Soc., 44:2 (1938), 53–60
[86] Hirsch K. A., “On infinite soluble groups, II”, Proc. London Math. Soc., 44:2 (1938), 336–344
[87] Hirsch K. A., “On infinite soluble groups, III”, Proc. London Math. Soc., 49:2 (1946), 184–194
[88] Hirsch K. A., “On infinite soluble groups, IV”, Proc. London Math. Soc., 27:3 (1952), 81–85
[89] Hirsch K. A., “On infinite soluble groups, V”, Proc. London Math. Soc., 29:3 (1954), 250–261
[90] Holt D. F., Eick B., O'Brien E. A., Handbook of Computational Group Theory, Chapman and Hall/CRC, 2020, 536 pp.
[91] Kambites M., Silva P. V., Steinberg B., “On the rational subset problem for groups”, J. Algebra, 309:2 (2007), 622–639
[92] Kapovich I., Myasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694
[93] Kapovich I., Weidmann R., Myasnikov A., “Foldings, graphs of groups and the membership problem”, Int. J. Algebra and Comput., 15:1 (2005), 95–128
[94] Kargapolov M. I., Remeslennikov V. N., “Conjugacy in free solvable groups”, Algebra i Logika, 5:6 (1966), 15–25 (in Russian)
[95] Kargapolov M. I., Remeslennikov V. N., Romanovskii N. S., et al., “Algorithmic problems for $o$-powered groups”, Algebra and Logic, 8:6 (1969), 363–374
[96] Kargapolov M. I., Timoshenko E. I., “Some questions in the theory of soluble groups”, Lect. Notes in Math., 372, 1974, 389–394
[97] Kharlampovich O. G., “A finitely presented solvable group with undecidable word problem”, Math. USSR-Izvestiya, 19:1 (1982), 151–169
[98] Kharlampovich O. G., “Equality problem for subvarieties of the variety ${\mathfrak N}_2{\mathfrak A}$”, Algebra and Logic, 26:4 (1987), 284–299
[99] Kharlampovich O. G., “Finitely presented solvable groups and Lie algebras with unsolvable equality problem”, Math. Notes, 46:3 (1989), 731–739
[100] Kharlampovich O., López L., Myasnikov A., “The Diophantine problem in some metabelian groups”, Math. Comp., 89 (2020), 2507–2519
[101] Kharlampovich O., Myasnikov A., “Irreducible affine varieties over free groups, I: Irreducibility of quadratic equations and Nullstellensatz”, J. Algebra, 200:2 (1998), 472–516
[102] Kharlampovich O., Myasnikov A., “Irreducible affine varieties over free groups, II: Systems in triangular quasi-quadratic form and description of residually free groups”, J. Algebra, 200:2 (1998), 517–570
[103] Kharlampovich O., Sapir M., “Algorithmic problems in varieties, a survey”, Int. J. Algebra and Comp., 12 (1995), 379–602
[104] Kleiman Yu. G., “Identities and some algorithmic problems in groups”, Dokl. Akad. Nauk SSSR, 244:4 (1979), 814–818 (in Russian)
[105] Kleiman Yu. G., “On identities in groups”, Tr. Mosk. Mat. Obs., 44, 1982, 62–108 (in Russian)
[106] Klein F., “Vergleichende Betrachtungen über neuere geometrische Forschungen”, Math. Ann., 43 (1893), 63–100 (in German)
[107] Kopytov V. M., “Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers”, Algebra and Logic, 7:6 (1968), 388–393
[108] V. D. Mazurov, E. I. Khukhro (eds.), Kourovka Notebook. Unsolved problems in group theory, 19, Sobolev Institute of Math., Russian Academy of Sciences, Siberian Branch, Novosibirsk, 2018, 246 pp.
[109] Krasilnikov A. N., Shmel'kin A. L., “Applications of the Magnus embedding in the theory of varieties of groups and Lie algebras”, Fundam. Prikl. Mat., 5 (1999), 493–502 (in Russian)
[110] Kukina E. G., Roman'kov V. A., “Subquadratic growth of the averaged Dehn function for free Abelian groups”, Siberian Math. J., 44:4 (2003), 605–610
[111] Lashkhi A. A., Bokelavadze T. Z., “Subgroup lattices and the geometry of Hall $W$-power groups”, Doklady Math., 80:3 (2009), 731–734
[112] Lasserre C., Oger F., “Direct products and elementary equivalence of polycyclic-by-finite groups”, J. Algebra, 418 (2014), 213–226
[113] Lennox J. C., Robinson D. J. S., The Theory of Infinite Soluble Groups, Oxford Math. Monographs, Oxford Science Publ., Clarendon Press, Oxford, 2004, 342 pp.
[114] Lie S., Theorie der Transformationsgruppen, v. I, B. G. Teubner, Leipzig, 1888, 650 pp. (in German)
[115] Lo E. H., “Finding intersection and normalizer in finitely generated nilpotent groups”, J. Symb. Comput., 25 (1998), 45–59
[116] Lohrey M., The Compressed Word Problem for Groups, Springer Briefs in Math., Springer Science Business Media, Berlin, 2014, 153 pp.
[117] Lohrey M., “Rational subsets of unitriangular groups”, Int. J. Algebra and Comput., 25:01–02 (2015), 113–121
[118] Lohrey M., Steinberg B., “The submonoid and rational subset membership problems for graph groups”, J. Algebra, 320 (2008), 728–755
[119] Lohrey M., Steinberg B., “Tilings and submonoids of metabelian groups”, Theory of Comput. Systems, 48:2 (2011), 411–427
[120] Lohrey M., Steinberg B., Zetzsche G., “Rational subsets and submonoids of wreath products”, Inform. and Comput., 243 (2015), 191–204
[121] Luks E. M., “Computing in solvable matrix groups”, Proc. 33rd IEEE Symp. Foundations of Comput. Sci., 1992, 111–120
[122] Lyndon R. C., “The equation $a^2b^2 = c^2$ in free groups”, Michigan Math. J., 6 (1959), 89–95
[123] Lyndon R. C., “Equations in free groups”, Trans. Amer. Math. Soc., 96 (1960), 445–457
[124] Lyndon R. C., “Equations in free metabelian groups”, Proc. Amer. Math. Soc., 17 (1966), 728–730
[125] Lyndon R. C., Shupp P. E., Combinatorial Group Theory, Springer Verlag, Berlin–Heidelberg–New York, 1977, 339 pp.
[126] Lysenok I., Ushakov A., “Spherical quadratic equations in free metabelian groups”, Proc. Amer. Math. Soc., 144 (2016), 1383–1390
[127] Macdonald J., Myasnikov A., Nikolaev A., Vassileva S., Logspace and compressed-word computations in nilpotent groups, 12 Mar. 2015, 38 pp., arXiv: 1503.03888v1 [math.GR]
[128] Macdonald J., Miasnikov A., Ovchinnikov D., “Low-complexity computations for nilpotent subgroup problems”, Int. J. Algebra and Comput., 29:4 (2019), 639–661
[129] Magnus W., “Über diskontinuierliche Gruppen mit einer definierenden Relation (Der Freiheitssatz)”, J. Reine Angew. Math., 163 (1930), 141–165 (in German)
[130] Magnus W., “Das Identitätsproblem für Gruppen mit einer definierenden Relation.”, Math. Ann., 106:1 (1932), 295–307 (in German)
[131] Magnus W., “On a theorem of Marshall Hall”, Ann. Math., 40 (1939), 764–768
[132] Magnus W., Karrass A., Solitar D., Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, Wiley, N.Y., 1966, 444 pp.
[133] Magnus W., Collected Papers, eds. G. Baumslag, B. Chandler, Springer Verlag, N.Y., 1984, 726 pp.
[134] Majewicz S., “On classes of exponential $A$-groups”, Comm. in Algebra, 38:4 (2010), 1363–1384
[135] Majewicz S., Zyman M., “Power-commutative nilpotent $R$-powered groups”, Groups, Complexity, Cryptology, 1:2 (2009), 297–310
[136] Makanin A. G., “Residual finiteness of equations in finitely generated nilpotent groups”, Vestnik Moskov. Univ. Ser. 1, Mat. Mekh., 1992, no. 1, 48–51 (in Russian)
[137] Makanin G. S., “Equations in a free group”, Math. USSR-Izvestia, 21:3 (1983), 483–546
[138] Makanin G. S., “Decidability of universal and positive theories of a free group”, Math. USSR-Izvestia, 25:1 (1985), 75–88
[139] Mal'cev A. I., “On groups of finite rank”, Mat. Sb. (N.S.), 64:2 (1948), 351–352 (in Russian)
[140] Mal'cev A. I., “Nilpotent torsion-free groups”, Izv. Akad. Nauk SSSR, Ser. Mat., 13:3 (1949), 201–212 (in Russian)
[141] Mal'cev A. I., “On some classes of infinite soluble groups”, Mat. Sb. (N.S.), 28(70):3 (1951), 567–588 (in Russian)
[142] Mal'cev A. I., “Homomorphisms onto finite groups”, Ivanov. Gos. Ped. Inst. Uchen. Zap., 1958, no. 18, 49–60 (in Russian)
[143] Mal'cev A. I., “On free solvable groups”, Dokl. Akad. Nauk SSSR, 130:3 (1960), 495–498 (in Russian)
[144] Mal'cev A. I., “On the equation $zxyx^{-1}y^{-1} = aba^{-1}b^{-1}$ in a free group”, Algebra i Logika. Sem., 1:5 (1962), 45–50 (in Russian)
[145] Mal'cev A. I., “The elementary properties of linear groups”, A. I. Mal'cev. The Metamath. of Algebraic Systems. Collected papers: 1936–1967, Studies in Logic and Foundations of Math., 66, North-Holland Publ. Company, Amsterdam, 1971
[146] Mal'cev A. I., “On a certain correspondencece between rings and groups”, A. I. Mal'cev. The Metamath. of Algebraic Systems, Collected papers: 1936–1967, Studies in Logic and Foundations of Math., 66, North-Holland Publ. Company, Amsterdam, 1971
[147] Margolis S. W., Meakin J. C., Šuniḱ Z., “Distortion functions and the membership problem for submonoids of groups and monoids”, Geometric Methods in Group Theory, Contemporary Math., 372, Amer. Math. Soc., 2005, 109–129
[148] Matijasevič Yu. V., “Diophantine representation of enumerable predicates”, Math. USSR-Izvestiya, 5:1 (1971), 1–28
[149] Matiyasevich Yu., “Some purely mathematical results inspired by mathematical logic”, Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci. (London, Ont., 1995), 121–127
[150] Matiyasevich Yu., Senizergues G., “Decision problems for semi-Thue systems with a few rules”, LNCS, 96, 1996, 523–531
[151] Matiyasevich Yu., Senizergues G., “Decision problems for semi-Thue systems with a few rules”, Theor. Comput. Sci., 330 (2005), 145–169
[152] Mel'nikov O. V., Remeslennikov V. N., Roman'kov V. A., et al., General Algebra, v. 1, Nauka Publ., M., 1990, 591 pp. (in Russian)
[153] Menshov A. V., Myasnikov A. G., Ushakov A. V., “Algorithms for metabelian groups”, Vestnik Omskogo Universiteta, 23:2 (2018), 27–34
[154] Mikhailova K. A., “The occurrence problem for direct products of groups”, Mat. Sb. (N.S.), 70(112):2 (1966), 241–251 (in Russian)
[155] Mishchenko A. A. and Timoshenko E. I., “Universal equivalence of partially commutative nilpotent groups”, Siberian Math. J., 52:5 (2011), 884–891
[156] Mostowski A., “Computational algorithms for deciding some problems for nilpotent groups”, Fund. Math., 59:2 (1966), 137–152
[157] Myasnikov A. G., “Elementary theories and abstract isomorphisms of finite dimensional algebras and unipotent groups”, Dokl. Math., 36:3 (1988), 464–467
[158] Myasnikov A. G., “Elementary theory of a module over a local ring”, Siberian Math. J., 30:3 (1989), 403–412
[159] Myasnikov A. G., “The structure of models and a criterion for the decidability of complete theories of finite-dimensional algebras”, Math. USSR-Izvestia, 34:2 (1990), 389–407
[160] Myasnikov A. G., “The theory of models of bilinear mappings”, Siberian Math. J., 31:3 (1990), 439–451
[161] Myasnikov A. G., “Definable invariants of bilinear mappings”, Siberian Math. J., 31:1 (1990), 89–99
[162] Myasnikov A., Nikolaev A., Ushakov A., “The Post correspondence problem in groups”, J. Group Theory, 17 (2014), 991–1008
[163] Myasnikov A., Nikolaev A., Ushakov A., “Knapsack problems in groups”, Math. of Comput., 84:292 (2015), 987–1016
[164] Myasnikov A., Nikolaev A., Ushakov A., “Non-commutative lattice problems”, J. Group Theory, 19:3 (2016), 455–475
[165] Myasnikov A. G., Remeslennikov V. N., “Classification of nilpotent power groups by their elementary properties”, Trudy Inst. Mat. Sib. Otd. AN SSSR, 2 (1982), 56–87 (in Russian)
[166] Myasnikov A. G., Remeslennikov V. N., “Definability of the set of Mal'cev bases and elementary theories of finite-dimensional algebras. I”, Siberian Math. J., 23:5 (1982), 711–724
[167] Myasnikov A. G., Remeslennikov V. N., “Definability of the set of Mal'cev bases and elementary theories of finite-dimensional algebras. II”, Siberian Math. J., 24:2 (1983), 231–246
[168] Myasnikov A. G., Remeslennikov V. N., “Algebraic geometry over groups, II: Logical foundations”, J. Algebra, 234 (2000), 225–276
[169] Myasnikov A. G., Romanovskii N. S., “Universal theories for rigid soluble groups”, Algebra and Logic, 50:6 (2012), 539–552
[170] Myasnikov A., Roman'kov V., “On rationality of verbal subsets in a group”, Theory Comput. Syst., 52:4 (2013), 587–598
[171] Myasnikov A., Roman'kov V., Ushakov A., Vershik A., “The word and geodesic problems in free solvable groups”, Trans. Amer. Math. Soc., 362:9 (2010), 4655–4682
[172] Myasnikov A., Rybalov A., “Generic complexity of undecidable problems”, J. Symb. Logic, 73:2 (2008), 656–673
[173] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative Cryptography and Complexity of Group-theoretic Problems, Math. Surveys and Monographs, 177, Amer. Math. Soc., Providence, Rhode Island, 2011, 385 pp.
[174] Myasnikov A. G., Sohrabi M., “Groups elementarily equivalent to a free nilpotent group of finite rank”, Ann. Pure Appl. Logic, 162:11 (2011), 916–833
[175] Myasnikov A., Vassileva S., Weiss A., “The conjugacy problem in free solvable groups and wreath product of abelian groups is in TC$^0$”, Theory Comput. Syst., 63 (2019), 809–832
[176] Myasnikov A., Weiss A., TC$^0$ circuits for algorithmic problems in nilpotent groups, 2017, arXiv: 1702.06616 [math.GR]
[177] Nedbai M. Yu., “The rational subset problem for free products of groups”, Vestnik Omskogo Universiteta, 2000, no. 2, 17–18 (in Russian)
[178] Newman M. F., “On a class of nilpotent groups”, Proc. London Math. Soc., 10:3 (1960), 365–375
[179] Nielsen J., “Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien”, Math. Tidsskrift, B (1921), 77–94 (in Danish)
[180] Nielsen J., “Die isomorphismengruppe ger freien Gruppen”, Math. Ann., 91 (1924), 169–209 (in German)
[181] Nikolaev A., Ushakov A., “Subset sum problem in polycyclic groups”, J. Symb. Comput., 84 (2018), 84–94
[182] Nikolov N., Segal D., “On finitely generated profinite groups. I. Strong completeness and uniform bounds”, Ann. Math., 65:1 (2007), 171–238
[183] Noskov G. A., “Conjugacy problem in metabelian groups”, Math. Notes, 31:4 (1982), 252–258
[184] Noskov G. A., On the Genus of a Free Metabelian Group, Preprint No 84-509, Academy of Sciences USSR, Siberian Branch, Comput. Center, Novosibirsk, 1984, 18 pp. (in Russian)
[185] Noskov G. A., “On the elementary theory of a finitely generated almost solvable group”, Izv. Akad. Nauk SSSR Ser. Mat., 47:3 (1984), 465–482
[186] Noskov G. A., Remeslennikov V. N., Roman'kov V. A., “Infinite groups”, J. Soviet Math., 18:5 (1982), 669–735
[187] Novikov P. S., “On the algorithmic unsolvability of the word problem in group theory”, Trudy Mat. Inst. Steklov, 44, 1955, 143 pp.
[188] Novikov P. S., “Über einige algorithmische Probléme der Gruppentheorie”, Jber. Deutsch. Math. Verein, 61 (1958), 88–92 (in German)
[189] Oger F., “Elementary equivalence and isomorphism of finitely generated nilpotent groups”, Comm. Algebra, 12 (1984), 1899–1915
[190] Oger F., “Cancellation and elementary equivalence of finitely generated finite-by-nilpotent groups”, J. London Math. Soc., 44:2 (1991), 173–183
[191] Parry W., “Growth series of some wreath products”, Trans. Amer. Math. Soc., 331 (1992), 751–759
[192] Pickel P. F., “Finitely generated nilpotent groups with isomorphic finite quotients”, Trans. Amer. Math. Soc., 160 (1971), 327–341
[193] Pickel P. F., “Metabelian groups with the same finite quotients”, Bull. Austral. Math. Soc., 11 (1974), 115–120
[194] Plotkin B. I., “Varieties of algebras and algebraic varieties”, Izrael J. Math., 96:2 (1996), 511–522
[195] Plotkin B. I., “Varieties of algebras and algebraic varieties. Categories of algebraic varieties”, Siberian Adv. Math., 7:2 (1997), 64–97
[196] Plotkin B. I., “Geometrical equivalence, geometrical similarity, and geometrical compatibility of algebras”, J. Math. Sci., 140:5 (2007), 716–728
[197] Plotkin B., “Seven lectures on algebraic geometry”, Groups, Algebras and Identities, Research workshop of the Israel Science Foundation Honoring Boris Plotkin's 90th birthday (March 20–24, 2016), Contemporary Math., 726, ed. E. Plotkin, 2016, 143–211
[198] Poincaré H., “Sur l'Analysis situs”, Comptes Rendus, 115 (1892), 633–636 (in French)
[199] Poincaré H., “Analysis Situs.”, J. d'Ecole Polytechnique Normale, 1 (1895), 1–121 (in French)
[200] Post E. L., “A variant of a recursively unsolvable problem”, Bull. Amer. Math. Soc., 52 (1946), 264–268
[201] Rabin M. O., “Recursive unsolvability of group theoretic problems”, Ann. Math., 67:1 (1958), 172–194
[202] Rapaport E., “On free groups and their automorphisms”, Acta Math., 99 (1958), 139–163
[203] Reid A. W., “Profinite rigidity”, Proc. Int. Cong. Math. (Rio de Janeiro), v. 1, 2018, 1191–1214
[204] Reidemeister K., “Über unendliche discrete Gruppen”, Hamburg Abh., 3 (1926), 33–39 (in German)
[205] Reidemeister K., Einführung in die kombinatorische Topologie, Braunschweig, 1932, XII+209 pp. (in German); Translated and reprinted Chelsea, New York, 1952
[206] Remeslennikov V. N., “Conjugacy separability of groups”, Siberian Math. J., 12 (1971), 783–792
[207] Remeslennikov V. N., “Example of a group finitely generated in the variety ${\mathfrak A}^n, n \geq 5$, with the unsolvable word problem”, Algebra and Logic, 12:5 (1973), 327–346
[208] Remeslennikov V. N., “An algorithmic problem for nilpotent groups and rings”, Siberian Math. J., 20:5 (1979), 71–74
[209] Remeslennikov V. N., Romanovskii N. S., “Irreducible algebraic sets in metabelian groups”, Algebra and Logic, 44:5 (2005), 336–347
[210] Remeslennikov V. N., Roman'kov V. A., “Model-theoretic and algorithmic questions in group theory”, J. Soviet Math., 31:3 (1985), 2887–2939
[211] Remeslennikov V. N., Sokolov V. G., “Some properties of a Magnus embedding”, Algebra and Logic, 9:5 (1970), 342–349
[212] Remeslennikov V. N., Stöhr R., “On the quasivariety generated by a non-cyclic free metabelian group”, Alg. Colloq., 11:2 (2004), 191–214
[213] Repin N. N., “Equations with one unknown in nilpotent groups”, Math. Notes, 34:2 (1983), 582–585
[214] Repin N. N., “The solvability problem for equations in one unknown in nilpotent groups”, Math. USSR-Izv., 48:6 (1985), 1295–1313
[215] Rips E., “Subgroups of small cancellation groups”, Bull. London Math. Soc., 14:1 (1982), 45–47
[216] Romanovskii N. S., “Some algorithmic problems for solvable groups”, Algebra and Logic, 13:1 (1974), 13–16
[217] Romanovskii N. S., “Free subgroups of finitely presented groups”, Algebra and Logic, 16:1 (1977), 62–68
[218] Romanovskii N. S., “The occurrence problem for extensions of abelian groups by nilpotent groups”, Siberian Math. J., 21 (1980), 170–174
[219] Romanovskii N. S., “On the elementary theory of an almost polycyclic group”, Math. USSR-Sbornik, 39:1 (1981), 125–132
[220] Romanovskii N. S., “Algebraic sets in metabelian groups”, Algebra and Logic, 46:4 (2007), 503–513
[221] Romanovskii N. S., “Universal theories for free solvable groups”, Algebra and Logic, 51:3 (2012), 259–263
[222] Romanovskii N. S., Gupta C. K., “The word problem for polynilpotent groups with a single primitive defining relation”, Algebra and Logic, 45:1 (2006), 17–25
[223] Romanovskii N. S., Timoshenko E. I., “On some elementary properties of soluble groups of derived length 2”, Siberian Math. J., 44 (2003), 350–354
[224] Romanovskii N. S., Timoshenko E. I., “Elementary equivalence and direct product decompositions of partially commutative groups of varieties”, Siberian Math. J., 61:3 (2020), 538–541
[225] Roman'kov V. A., “Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings”, Algebra and Logic, 16:4 (1977), 310–320
[226] Roman'kov V. A., “Equations in free metabelian groups”, Siberian Math. J., 20:3 (1979), 469–471
[227] Roman'kov V. A., “Universal theory of nilpotent groups”, Math. Notes, 25:4 (1979), 253–258
[228] Roman'kov V. A., “Infinite generation of automorphism groups of free pro-$p$ groups”, Siberian Math. J., 34:4 (1993), 727–732
[229] Roman'kov V. A., “On the occurence problem for rational subsets of a group”, Int. Conf. on Comb. and Comput. Methods in Math., ed. V. Roman'kov, 1999, 76–81
[230] Roman'kov V. A., “Asymptotic growth of averaged Dehn function for nilpotent groups”, Algebra and Logic, 46:1 (2007), 37–45
[231] Roman'kov V. A., “The twisted conjugacy problem for endomorphisms of polycyclic groups”, J. Group Theory, 13:3 (2010), 355–364
[232] Roman'kov V. A., “Equations over groups.”, Groups, Complexity, Cryptology, 4:2 (2012), 191–239
[233] Roman'kov V. A., “The Post Correspondence Problem in metabelian and polycyclic groups”, Proc. Conference “Algebra and Math. Logic: Theory and Applications” (Kazan, June 2–6), Kazan Federal University, Kazan, 2014, 32–32
[234] Roman'kov V. A., The Post Correspondence Problem, , 2014 https://www.researchgate.net/publication/269169063_The_Post_Correspondence_Problem_PCP
[235] Roman'kov V. A., Rational Subsets in Groups, Omsk State Univrersity, Omsk, 2014, 176 pp. (in Russian)
[236] Roman'kov V. A., “Diophantine questions in the class of finitely generated nilpotent groups”, J. Group Theory, 19:3 (2016), 497–516
[237] Roman'kov V. A., “Rationality of verbal subsets of solvable groups”, Algebra and Logic, 57:1 (2018), 39–48
[238] Roman'kov V. A., “Polycyclic, metabelian, or soluble of type (FP)$_{\infty}$ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian”, Glasgow Math. J., 60:1 (2018), 209–218
[239] Roman'kov V. A., Essays in Group Theory and Cryptology. Solvable Groups, Omsk State University Publishing House, Omsk, 2017, 268 pp.
[240] Roman'kov V. A., “Nonsolvability of the submonoid membership problem for the free nilpotent group of class $l \geq 2$ of suffitiently large rank”, Izv. RAS, Ser. Math. (to appear)
[241] Sarkisjan R. A., “Algorithmic questions for linear algebraic groups, I”, Math. USSR-Sbornik, 41:2 (1982), 149–189
[242] Sarkisjan R. A., “Algorithmic questions for linear algebraic groups, II”, Math. USSR-Sbornik, 41:3 (1982), 329–359
[243] Schreier O., “Die Untergruppen der freien Gruppen”, Abh. Math. Sem. Univ. Hamburg, 5 (1927), 161–183 (in German)
[244] Segal D., “Decidable properties of polycyclic groups”, Proc. London Math. Soc., 61 (1990), 497–528
[245] Seress Á, Permutation Group Algorithms, Cambridge Tracts in Math., 152, Cambridge University Press, Cambridge, 2003, 264 pp.
[246] Shmel'kin A. L., “Wreath products and varieties of groups”, Math. USSR-Izvestia, 29 (1965), 433–434
[247] Shmel'kin A. L., “On complete nilpotent groups”, Algebra i Logika. Sem., 6:2 (1967), 111–114 (in Russian)
[248] Sims C. C., Computation with finitely presented groups, Encyclopedia of Math. and its Applications, 48, Cambridge University Press, Cambridge, 1994, 624 pp.
[249] Szmielew W., “Elementary properties of abelian groups”, Fund. Math., 41 (1955), 203–271
[250] Tietze H., “Über die topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten”, Monatsh. f. Math. u. Phys., 19 (1908), 1–118 (in German)
[251] Timoshenko E. I., “Preservation of elementary and universal equivalence under the wreath product”, Algebra and Logic, 7:4 (1968), 273–276
[252] Timoshenko E. I., “On the question of elementary equivalence of groups”, Algebra, v. 1, Irkutsk State University, Irkutsk, 1972, 92–96 (in Russian)
[253] Timoshenko E. I., “Algorithmic problems for metabelian groups”, Algebra and Logic, 12:2 (1973), 132–137
[254] Timoshenko E. I., “Universally equivalent solvable groups”, Algebra and Logic, 39:2 (2000), 131–138
[255] Timoshenko E. I., “Universal equivalence of partially commutative metabelian groups”, Algebra and Logic, 49:2 (2010), 177–196
[256] Timoshenko E. I., Endomorphisms and universal theories of solvable groups, Novosibirsk State Technical University, Novosibirsk, 2011, 327 pp. (in Russian)
[257] Timoshenko E. I., “Universal theory of a free polynilpotent group”, Izv. Math., 80:3 (2016), 623–632
[258] Timoshenko E. I., “A remark on spherical equations in free metabelian groups”, Groups, Complexity, Cryptology, 9:2 (2017), 155–158
[259] Timoshenko E. I., “On fragments of theories of some solvable or nilpotent groups”, Vestnik Omskogo universiteta, 23:2 (2018), 47–52 (in Russian)
[260] Timoshenko E. I., “Theories of relatively free solvable groups with extra predicate”, Algebra and Logic, 57:4 (2018), 295–308
[261] Umirbaev U. U., “Occurrence problem for free solvable groups”, Algebra and Logic, 34:2 (1995), 112–124
[262] Ushakov A., “Algorithmic theory of free solvable groups: randomized computations”, J. Algebra, 407:1 (2014), 178–200
[263] Vassileva S., “Polynomial time conjugacy in wreath products and free solvable groups”, Groups, Complexity, Cryptology, 3:1 (2011), 105–120
[264] Ventura E., Roman'kov V. A., “The twisted conjugacy problem for endomorphisms of metabelian groups”, Algebra and Logic, 48:2 (2009), 89–98
[265] Vollmer H., Introduction to Circuit Complexity, Springer, Berlin, 1999, 272 pp.
[266] Whitehead J. H. C., “On equivalent sets of elements in a free group”, Ann. Math., 37:4 (1936), 782–800
[267] S. I. Adian, W. W. Boone, G. Higman (eds.), Word problems, v. II, Studies in Logic and the Foundations of Math., 95, North-Holland, Amsterdam–N.Y.–Oxford, 1980, 578 pp.
[268] Zil'ber B. I., “An example of two elementarily equivalent but non-isomorphic finitely generated groups”, Algebra and Logic, 10:3 (1971), 192–197