Space functions of groups

DOI10.1090/S0002-9947-2012-05520-6zbMath1287.20045arXiv1011.0118MaRDI QIDQ2841376

Alexander Yu. Ol'shanskii

Publication date: 25 July 2013

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.0118

zbMATH Keywords

finitely generated groups; finitely presented groups; isoperimetric functions; generators and relations; recursively presented groups; space complexity; van Kampen diagrams; Higman embedding theorem; algorithmic word problem; decidability of word problem; space functions of groups

Mathematics Subject Classification ID

20F05: Generators, relations, and presentations of groups

20F65: Geometric group theory

03D15: Complexity of computation (including implicit computational complexity)

20F69: Asymptotic properties of groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D40: Word problems, etc. in computability and recursion theory

20F06: Cancellation theory of groups; application of van Kampen diagrams

03D10: Turing machines and related notions