Space functions of groups

DOI10.1090/S0002-9947-2012-05520-6zbMath1287.20045arXiv1011.0118OpenAlexW2962988727MaRDI 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 groupsfinitely presented groupsisoperimetric functionsgenerators and relationsrecursively presented groupsspace complexityvan Kampen diagramsHigman embedding theoremalgorithmic word problemdecidability of word problemspace functions of groups

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Complexity of computation (including implicit computational complexity) (03D15) Asymptotic properties of groups (20F69) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Word problems, etc. in computability and recursion theory (03D40) Cancellation theory of groups; application of van Kampen diagrams (20F06) Turing machines and related notions (03D10)

Related Items (3)

Group Embeddings with Algorithmic Properties ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Filling length in finitely presentable groups.
• The geometry of the word problem for finitely generated groups.
• Free and fragmenting filling length.
• Groups with small Dehn functions and bipartite chord diagrams.
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Non-amenable finitely presented torsion-by-cyclic groups.
• There is only one gap in the isoperimetric spectrum
• Isoperimetric functions of groups and computational complexity of the word problem
• Word Problems Solvable in Logspace
• On Dehn functions of free products of groups
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• On subgroup distortion in finitely presented groups
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• The conjugacy problem and Higman embeddings
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• A non-cyclic one-relator group all of whose finite quotients are cyclic

This page was built for publication: Space functions of groups