Algorithmic constructions of relative train track maps and CTs

Abstract

Building on [BH92, BFH00], we proved in [FH11] that every element $\psi$ of the outer automorphism group of a finite rank free group is represented by a particularly useful relative train track map. In the case that $\psi$ is rotationless (every outer automorphism has a rotationless power), we showed that there is a type of relative train track map, called a CT, satisfying additional properties. The main result of this paper is that the constructions of these relative train tracks can be made algorithmic. A key step in our argument is proving that it is algorithmic to check if an inclusion $\mathcal{F}⊏{\mathcal{F}}^{\prime }$ of $\varphi$-invariant free factor systems is reduced. We also give applications of the main result.