Groups with undecidable word problem and almost quadratic Dehn function

DOI10.1112/jtopol/jts020zbMath1264.20033arXiv1104.1476OpenAlexW3102739368MaRDI QIDQ4899004

Alexander Yu. Ol'shanskii

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

Turing machinesfinitely presented groupsrewriting systemsDehn functionsundecidable word problemcombs\(S\)-machinesalmost quadratic functionsquasicombs

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Asymptotic properties of groups (20F69) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40) Recursively (computably) enumerable sets and degrees (03D25) Cancellation theory of groups; application of van Kampen diagrams (20F06) Turing machines and related notions (03D10)

Related Items (6)

Polynomially-bounded Dehn functions of groups ⋮ On the geometry of Cayley automatic groups ⋮ Groups finitely presented in Burnside varieties ⋮ Popa superrigidity and countable Borel equivalence relations ⋮ Characterizations of the groups with almost layer-finite periodic parts ⋮ Conjugacy problem in groups with quadratic Dehn function

This page was built for publication: Groups with undecidable word problem and almost quadratic Dehn function