An efficient algorithm for finding a basis of the fixed point subgroup of an automorphism of a free group

Abstract

We prove that for any automorphism $\alpha$ of a free group F of finite rank, one can efficiently compute a basis of the fixed point subgroup Fix(α).

68 pages, 23 figures. Added: Splitting Lemma in Section 11, and an algorithm for finding of normal verices in Section 7