Dehn Functions, the Word Problem, and the Bounded Word Problem For Decidable Group Presentations

2012/12/10 by Desmond Cummins, Cummins, Desmond
Computer Science · Mathematics · #20F05 #20F06 #20F10 #Computability, Logic, AI Algorithms #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1212.2024

openalex publication_date 2012/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct examples of finitely generated decidable group presentations that satisfy certain combinations of solvability for the word problem, solvability for the bounded word problem, and computablity for the Dehn function. We prove that no finitely generated decidable presentations exist satisfying the combinations for which we do not provide examples. The presentations we construct are also minimal. These constructions answer an open question asked by R.I. Grigorchuk and S.V. Ivanov. Our approach uses machinery developed by Birget, Ol'shanskii, Rips, and Sapir for constructing finite group presentations that simulate Turing machines. We generalize this machinery to construct finitely generated decidable group presentations that simulate computing objects similar to oracle Turing machines.

Related

• On Dehn functions of infinite presentations of groups
• The Word Problem in the Baumslag group with a non-elementary Dehn\n function is polynomial time decidable
• An application of the Deutsch-Josza algorithm to formal languages and the word problem in groups
• Taming the hydra: the word problem and extreme integer compression
• The bounded and precise word problems for presentations of groups