HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem

Abstract

Let $G=F{\ast }_{\phi }t$ be an HNN extension of a free group $F$ with two equal associated normal subgroups $H_1=H_2$ of finite index. We prove that the word problem in $G$ is decidable in polynomial time. This result extends to the case where the subgroups $H_1=H_2$ are not normal, provided that the isomorphism $\phi :H_1\to H_2$ satisfies an additional condition described in Section 5.