Space functions of groups.

DOI10.1090/S0002-9947-2012-05520-6MaRDI QIDQ2841376zbMATH OpenOpenAlexFDO

Authors Alexander Y. Olshanskii

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

algorithmic word problemdecidability of word problemfinitely generated groupsfinitely presented groupsgenerators and relationsHigman embedding theoremisoperimetric functionsrecursively presented groupsspace complexityspace functions of groupsvan Kampen diagrams

Mathematics Subject Classification ID

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

Abstract: We consider space functions $s(n)$ of finitely presented groups $G=<AmidR>.$ (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 obtained results is the following criterion: A finitely generated group $H$ has 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.

Recommendations

• Space functions and space complexity of the word problem in semigroups.
• Space complexity and word problems of groups
• Isoperimetric and isodiametric functions of groups
• On Dehn functions of infinite presentations of groups.
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

Cites work

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

Cited in

(14)

• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Scanning of two-dimensional space groups.
• On spaces of group-valued functions
• Clebsch-Gordan Coefficients for Space Groups
• Asymptotic invariants, complexity of groups and related problems.
• Group Embeddings with Algorithmic Properties
• scientific article; zbMATH DE number 3959758 (Why is no real title available?)
• Space functions and space complexity of the word problem in semigroups.
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• Groups with undecidable word problem and almost quadratic Dehn function. (With an appendix written by M. V. Sapir)
• Topology and non-deterministic polynomial time computation: avoidance of the misbehaviour of hub-free diagrams and consequences
• Space complexity and word problems of groups

This page was built for publication: Space functions of groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841376)