Compressed conjugacy and the word problem for outer automorphism groups of graph groups

2010/03/05 by Niko Haubold, Haubold, Niko, Markus Lohrey +3
Computer Science · Mathematics · #20F10 #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Group Theory (math.GR) #math.GR #msc:20F10 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1003.1233

arxiv created 2010/03/05 · arxiv updated 2010/03/05 · openalex publication_date 2010/03/05 · openalex created_date 2023/02/18 · openalex updated_date 2026/07/28

Abstract

It is shown that for graph groups (right-angled Artin groups) the conjugacy problem as well as a restricted version of the simultaneous conjugacy problem can be solved in polynomial time even if input words are represented in a compressed form. As a consequence it follows that the word problem for the outer automorphism group of a graph group can be solved in polynomial time.

Related

• Polynomial-time word problems
• Compressed words and automorphisms in fully residually free groups
• An automata theoretic approach to the generalized word problem in graphs of groups
• Logspace computations in graph products
• The conjugacy problem in right-angled Artin groups and their subgroups