On Primitive Words I: A New Algorithm

2011/03/21 by Puder, Doron
#Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1103.4061

Abstract

Let F_k be the free group on k generators, and let H≤ J≤ \F_k be subgroups of finite rank. We present a new elementary algorithm to determine whether H is a free factor of J. In particular, this algorithm can determine whether a given element w∈ F_k is primitive, i.e. whether it belongs to some basis of F_k.

Related

• A fine property of Whitehead's algorithm
• An algorithm to recognize echelon subgroups of a free group
• Algorithmic constructions and primitive elements in the free group of rank 2
• The Strong Primitive Normal Basis Theorem
• Computing fixed closures in free groups