The compressed word problem in relatively hyperbolic groups

2020/05/28 by Derek F. Holt, Sarah Rees, Holt, Derek +1
Mathematics · Computer Science · #Geometric and Algebraic Topology #semigroups and automata theory #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.2005.13917

Abstract

We prove that the compressed word problem in a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.

Related

• Compressed decision problems in hyperbolic groups
• Compressed word problems in HNN-extensions and amalgamated products
• Compressed words and automorphisms in fully residually free groups
• The generalised word problem in hyperbolic and relatively hyperbolic groups
• Polynomial-time word problems