Space functions of groups

Olshanskii, A.

doi:10.1090/S0002-9947-2012-05520-6

Space functions of groups
HTML articles powered by AMS MathViewer

by A. Yu. Olshanskii PDF

Trans. Amer. Math. Soc. 364 (2012), 4937-4985 Request permission

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

Gilbert Baumslag, A non-cyclic one-relator group all of whose finite quotients are cyclic, J. Austral. Math. Soc. 10 (1969), 497–498. MR 0254127
Jean-Camille Birget, Time-complexity of the word problem for semigroups and the Higman embedding theorem, Internat. J. Algebra Comput. 8 (1998), no. 2, 235–294. MR 1620347, DOI 10.1142/S0218196798000132
Jean-Camille Birget, Functions on groups and computational complexity, Internat. J. Algebra Comput. 14 (2004), no. 4, 409–429. MR 2084376, DOI 10.1142/S0218196704001815
J.-C. Birget, A. Yu. Ol′shanskii, E. Rips, and 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, DOI 10.2307/3597196
N. Brady and M. R. Bridson, There is only one gap in the isoperimetric spectrum, Geom. Funct. Anal. 10 (2000), no. 5, 1053–1070. MR 1800063, DOI 10.1007/PL00001646
Noel Brady, Tim Riley, and Hamish Short, The geometry of the word problem for finitely generated groups, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser Verlag, Basel, 2007. Papers from the Advanced Course held in Barcelona, July 5–15, 2005. MR 2281936
Martin R. Bridson and Tim R. Riley, Free and fragmenting filling length, J. Algebra 307 (2007), no. 1, 171–190. MR 2278048, DOI 10.1016/j.jalgebra.2006.05.030
Daniel E. Cohen, Klaus Madlener, and Friedrich Otto, Separating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups, Math. Logic Quart. 39 (1993), no. 2, 143–157. MR 1269904, DOI 10.1002/malq.19930390117
Ding-Zhu Du and Ker-I Ko, Theory of computational complexity, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1789501, DOI 10.1002/9781118032916
S. M. Gersten, Dehn functions and $l_1$-norms of finite presentations, Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989) Math. Sci. Res. Inst. Publ., vol. 23, Springer, New York, 1992, pp. 195–224. MR 1230635, DOI 10.1007/978-1-4613-9730-4_{9}
Steve M. Gersten, Isoperimetric and isodiametric functions of finite presentations, Geometric group theory, Vol. 1 (Sussex, 1991) London Math. Soc. Lecture Note Ser., vol. 181, Cambridge Univ. Press, Cambridge, 1993, pp. 79–96. MR 1238517, DOI 10.1017/CBO9780511661860.008
Steve M. Gersten and Tim R. Riley, Filling length in finitely presentable groups, Geom. Dedicata 92 (2002), 41–58. Dedicated to John Stallings on the occasion of his 65th birthday. MR 1934008, DOI 10.1023/A:1019682203828
M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
M. Gromov, Asymptotic invariants of infinite groups, Geometric group theory, Vol. 2 (Sussex, 1991) London Math. Soc. Lecture Note Ser., vol. 182, Cambridge Univ. Press, Cambridge, 1993, pp. 1–295. MR 1253544
V. S. Guba and M. V. Sapir, On Dehn functions of free products of groups, Proc. Amer. Math. Soc. 127 (1999), no. 7, 1885–1891. MR 1469408, DOI 10.1090/S0002-9939-99-04579-7
Richard J. Lipton and Yechezkel Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach. 24 (1977), no. 3, 522–526. MR 445901, DOI 10.1145/322017.322031
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
Klaus Madlener and Friedrich Otto, Pseudonatural algorithms for the word problem for finitely presented monoids and groups, J. Symbolic Comput. 1 (1985), no. 4, 383–418. MR 849044, DOI 10.1016/S0747-7171(85)80022-5
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).
A. Yu. Ol′shanskiĭ, On the distortion of subgroups of finitely presented groups, Mat. Sb. 188 (1997), no. 11, 51–98 (Russian, with Russian summary); English transl., Sb. Math. 188 (1997), no. 11, 1617–1664. MR 1601512, DOI 10.1070/SM1997v188n11ABEH000276
A. Yu. Olshanskii, Space functions of semigroups and the complexity of the word problem, arXiv:1111:1458 (2011).
Alexander Yu. Ol′shanskii and Mark V. Sapir, Length and area functions on groups and quasi-isometric Higman embeddings, Internat. J. Algebra Comput. 11 (2001), no. 2, 137–170. MR 1829048, DOI 10.1142/S0218196701000401
Alexander Yu. Ol′shanskii and Mark V. Sapir, Non-amenable finitely presented torsion-by-cyclic groups, Publ. Math. Inst. Hautes Études Sci. 96 (2002), 43–169 (2003). MR 1985031
A. Yu. Ol′shanskii and M. V. Sapir, The conjugacy problem and Higman embeddings, Mem. Amer. Math. Soc. 170 (2004), no. 804, viii+133. MR 2052958, DOI 10.1090/memo/0804
A. Yu. Ol′shanskii and M. V. Sapir, Groups with small Dehn functions and bipartite chord diagrams, Geom. Funct. Anal. 16 (2006), no. 6, 1324–1376. MR 2276542, DOI 10.1007/s00039-006-0580-9
A.N. Platonov, Isoperimetric function of the Baumslag-Gersten group, (Russian) Vestnik Moskov. Univ. Ser. I Mat. Mekh. (2004), p. 1217.
Joseph J. Rotman, An introduction to the theory of groups, 3rd ed., Allyn and Bacon, Inc., Boston, MA, 1984. MR 745804
Mark V. Sapir, Jean-Camille Birget, and Eliyahu Rips, Isoperimetric and isodiametric functions of groups, Ann. of Math. (2) 156 (2002), no. 2, 345–466. MR 1933723, DOI 10.2307/3597195
B. A. Trahtenbrot, The complexity of reduction algorithms in Novikov-Boone constructions. , Algebra i Logika 8 (1969), 93–128 (Russian). MR 0285389
M. K. Valiev, The complexity of the word problem for finitely presented groups, Algebra i Logika 8 (1969), 5–43 (Russian). MR 0306334