The Word Problem in the Baumslag group with a non-elementary Dehn\n function is polynomial time decidable

2011/02/12 by Alexei Miasnikov, Miasnikov, Alexei, Alexander Ushakov +3 · 2 citations
Mathematics · Computer Science · #Geometric and Algebraic Topology #semigroups and automata theory #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.1102.2481

Abstract

We prove that the Word problem in the Baumslag group G(1,2) which has a\nnon-elementary Dehn function is decidable in polynomial time.\n

Cited by

• The Diophantine problem in the Baumslag-Gersten group
• Conjugator Length in the Baumslag-Gersten Group

Related

• Dehn Functions, the Word Problem, and the Bounded Word Problem For Decidable Group Presentations
• Taming the hydra: the word problem and extreme integer compression
• Asymptotic invariants, complexity of groups and related problems
• On Dehn functions of infinite presentations of groups
• On a generalization of Dehn's algorithm