Groups with undecidable word problem and almost quadratic Dehn function. (With an appendix written by M. V. Sapir)

DOI10.1112/JTOPOL/JTS020MaRDI QIDQ4899004zbMATH OpenOpenAlexFDO

Authors Alexander Y. Olshanskii

Publication date 4 January 2013

Published in Journal of Topology (Search for Journal in Brave)

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

zbMATH Keywords

\(S\)-machinesalmost quadratic functionscombsDehn functionsfinitely presented groupsquasicombsrewriting systemsTuring machinesundecidable word problem

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Recursively (computably) enumerable sets and degrees (03D25) 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)

Abstract: We construct a finitely presented group with undecidable word problem and with Dehn function bounded by a quadratic function on an infinite set of positive integers.

Recommendations

• Algorithmic problems in groups with quadratic Dehn function
• Space functions of groups.
• On Dehn functions of infinite presentations of groups.
• Isoperimetric and isodiametric functions of groups
• scientific article; zbMATH DE number 1530302

Cited in

(17)

• Popa superrigidity and countable Borel equivalence relations
• Polynomially-bounded Dehn functions of groups
• Isoperimetric and isodiametric functions of groups
• Dehn functions of finitely presented metabelian groups
• Groups finitely presented in Burnside varieties
• Characterizations of the groups with almost layer-finite periodic parts
• Algorithmic problems in groups with quadratic Dehn function
• scientific article; zbMATH DE number 3959758 (Why is no real title available?)
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• scientific article; zbMATH DE number 1530302 (Why is no real title available?)
• Conjugacy problem in groups with quadratic Dehn function
• On the geometry of Cayley automatic groups
• GROUPS WITH QUADRATIC-NON-QUADRATIC DEHN FUNCTIONS
• A semigroup with linearithmic Dehn function
• Torsion subgroups of groups with quadratic Dehn function
• On Dehn functions of infinite presentations of groups.
• Groups with small Dehn functions and bipartite chord diagrams.

This page was built for publication: Groups with undecidable word problem and almost quadratic Dehn function. (With an appendix written by M. V. Sapir)

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