Compressed words and automorphisms in fully residually free groups

2009/08/05 by Jeremy Macdonald, Macdonald, Jeremy
Computer Science · Mathematics · #20F10 #20F28 #Authorship Attribution and Profiling #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0908.0569

openalex publication_date 2009/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the compressed word problem in a finitely-generated fully residually free group (F -group) is decidable in polynomial time, and use the result to show that the word problem in the automorphism group of such a group is decidable in polynomial time.

Related

• Polynomial-time word problems
• Compressed primitivity problem in free groups
• The compressed word problem in relatively hyperbolic groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Compressed word problems in HNN-extensions and amalgamated products