Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Space functions of groups

Author: A. Yu. Olshanskii
Journal: Trans. Amer. Math. Soc. 364 (2012), 4937-4985
MSC (2010): Primary 20F05, 20F06, 20F65, 20F69, 03D15, 03D40, 03D10
Published electronically: April 25, 2012
MathSciNet review: 2922615
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider space functions $ s(n)$ of finitely presented groups $ G=\langle A\mid R\rangle .$ (These functions have a natural geometric analog.) To define $ s(n)$ we start with a word $ w$ over $ A$ of length at most $ n$ equal to $ 1$ in $ G$ and use relations from $ R$ for elementary transformations to obtain the empty word; $ s(n)$ bounds from above the tape space (or computer memory) one needs to transform any word of length at most $ n$ vanishing in $ G$ to the empty word. One of the main results obtained is the following criterion: A finitely generated group $ H$ has a decidable word problem of polynomial space complexity if and only if $ H$ is a subgroup of a finitely presented group $ G$ with a polynomial space function.

References [Enhancements On Off] (What's this?)

  • 1. G. Baumslag, A non-cyclic one-relator group all of whose finite quotients are cyclic. J. Austral. Math. Soc., 10 (1969), 497-498. MR 0254127 (40:7337)
  • 2. J.-C. Birget, Time-complexity of the word problem for semigroups and the Higman embedding theorem, Internat. J. Algebra Comput. 8 (1998), 235-294. MR 1620347 (99e:20069)
  • 3. J.-C. Birget, Functions on groups and computational complexity, Internat. J. Algebra Comput., 14 (2004), no. 4, 409-429. MR 2084376 (2005h:20077)
  • 4. J.-C. Birget, A. Yu. Olshanskii, E. Rips, M. V. Sapir, Isoperimetric functions of groups and computational complexity of the word problem. Ann. of Math. (2) 156 (2002), no. 2, 467-518. MR 1933724 (2005b:20077b)
  • 5. N. Brady and M. Bridson, There is only one gap in the isoperimetric spectrum, Geometric and Functional Analysis, 10 (2000), 1053-1070. MR 1800063 (2001j:20046)
  • 6. N. Brady, T. Riley, and H. Short, The geometry of the word problem for finitely generated groups, Advanced Courses in Mathematics, CRM Barselona, Birkhauser-Verlag, Basel, 2007, x+206 p.p. MR 2281936 (2009j:20053)
  • 7. M.R. Bridson, T.R. Riley, Free and fragmenting filling length, Journal of Algebra, 307(1) (2007), 171-190. MR 2278048 (2007i:20066)
  • 8. D.E. Cohen, K. Madlener, and F. Otto, Separating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups, Math. Logic Quart, 39, no. 2 (1993), 143-157. MR 1269904 (96a:20044)
  • 9. Ding-Zhu Du, Ker-I Ko, Theory of Computational Complexity, Wiley-Interscience Publ., N.Y.,2000, 512 p.p. MR 1789501 (2001k:68036)
  • 10. S. M. Gersten, Dehn functions and l1-norms of finite presentations. Algorithms and Classification in Combinatorial Group Theory, Springer, Berlin, 1992, 195225. MR 1230635 (94g:20049)
  • 11. S.M. Gersten, Isoperimetric and isodiametric functions. In G. Niblo and M. Roller editors, Geometric group theory I, Lecture Notes of LMS, 181, Camb. Univ. Press, 1993. MR 1238517 (94f:20066)
  • 12. S.M. Gersten, T.R. Riley, Filling length in finitely presentable groups, Geometricae Dedicata, 92(1) (2002), 41-58. MR 1934008 (2003i:20051)
  • 13. M. Gromov, Hyperbolic groups, in: Essays in Group Theory (S.M. Gersten, ed.), M.S.R.I. Pub. 8, Springer, 1987, 75-263. MR 919829 (89e:20070)
  • 14. M. Gromov, Asymptotic invariants of infinite groups, in: Geometric Group Theory. Vol. 2 (G.A. Niblo and M.A. Roller, eds.), London Math. Soc. Lecture Notes Ser., 182 (1993), 1-295. MR 1253544 (95m:20041)
  • 15. V. Guba, M. Sapir, On Dehn functions of free products of groups, Proc. Amer. Math. Soc. 127 (1999), 1885-1891. MR 1469408 (99j:20044)
  • 16. R. Lipton, Y. Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach., 24 (1977), no. 3, 522-526. MR 0445901 (56:4234)
  • 17. R.C. Lyndon, P.E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977. MR 0577064 (58:28182)
  • 18. K. Madlener, F. Otto, Pseudo-natural algorithms for the word problem for finitely presented monoids and groups, J. Symbolic Computation 1(1985), 383-418. MR 849044 (87h:03067)
  • 19. A.G. Miasnikov, A. Ushakov, and Dong Wook Won, The word problem in the Baumslag-Gersten group with a non-elementary Dehn function is polynomial time decidable, arXiv:1102.2481v1 (2011).
  • 20. A. Yu. Olshanskii, On the subgroup distortion in finitely presented groups, Matem. Sbornik, 188 (1997), N 11, 73-120 (in Russian). MR 1601512 (99a:20038)
  • 21. A. Yu. Olshanskii, Space functions of semigroups and the complexity of the word problem, arXiv:1111:1458 (2011).
  • 22. A. Yu. Olshanskii and M.V. Sapir, Length and area functions in groups and quasi-isometric Higman embeddings, Intern. J. Algebra and Comput., 11 (2001), no. 2 , 137-170. MR 1829048 (2002b:20058)
  • 23. A. Yu. Olshanskii and M.V. Sapir, Non-amenable finitely presented torsion-by-cyclic groups, Publ. Math. IHES, 96 (2003), no. 6, pp. 43-169. MR 1985031 (2004f:20061)
  • 24. A. Yu. Olshanskii and M.V. Sapir, Conjugacy problem and Higman embeddings, ``Memoirs of the AMS'' 170(2004), no. 804 pp. vii+131 MR 2052958 (2005f:20062)
  • 25. A. Yu. Olshanskii and M.V. Sapir, Groups with small Dehn functions and bipartite chord diagrams, Geometric and Functional Analysis, 16 (2006), 1324-1376 MR 2276542 (2008k:20053)
  • 26. A.N. Platonov, Isoperimetric function of the Baumslag-Gersten group, (Russian) Vestnik Moskov. Univ. Ser. I Mat. Mekh. (2004), p. 1217.
  • 27. J. Rotman, An introduction to the theory of groups, 3d edition, Allyn and Bacon Inc., Boston, Mass, 1984. MR 745804 (85f:20001)
  • 28. M.V. Sapir, J.-C. Birget, E. Rips, Isoperimetric and isodiametric functions of groups, Annals of Mathematics, 157, 2(2002), 345-466. MR 1933723 (2005b:20077a)
  • 29. B.A. Trakhtenbrot, On the complexity of reduction algorithms in Novikov - Boone constructions, Algebra i Logika 8(1969), no. 1, pp. 93-128; English translation in: Algebra and Logic, 8(1969), no. 1, pp. 50-71. MR 0285389 (44:2608)
  • 30. M.K. Valiev, On the complexity of the identity problem for finitely defined groups, Algebra i Logika 8(1969), no. 1, pp. 5-43; English translation in: Algebra and Logic, 8(1969), no. 1, pp. 2-21. MR 0306334 (46:5460)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20F05, 20F06, 20F65, 20F69, 03D15, 03D40, 03D10

Retrieve articles in all journals with MSC (2010): 20F05, 20F06, 20F65, 20F69, 03D15, 03D40, 03D10

Additional Information

A. Yu. Olshanskii
Affiliation: Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240

Keywords: Generators and relations in groups, space complexity, algorithmic word problem, van Kampen diagram
Received by editor(s): October 6, 2010
Received by editor(s) in revised form: December 3, 2010
Published electronically: April 25, 2012
Additional Notes: The author was supported in part by the NSF grant DMS 0700811 and by the Russian Fund for Basic Research grant 08-01-00573
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society