Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9947-2012-05520-6
PII: S 0002-9947(2012)05520-6
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.