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