Finite complete rewriting systems for graphs of free groups with applications to free-by-cyclic, one-relator, and three-manifold groups

We prove that any finite graph of finitely generated free groups admits a finite complete rewriting system after possibly taking a free product with a free group of rank two.

As a corollary we obtain that any HNN-extension of a finitely generated free group over a finitely generated subgroup admits a finite complete rewriting system.

We then use this result, and other tools, to give partial solutions to several fundamental open problems about finite complete rewriting systems for hyperbolic, one-relator, fully residually free, and three-manifold groups.

In particular we prove that if $G = \langle \mathbb{F} , t \mid t^{-1}ft = \psi(f), \, \forall f\in \mathbb{F} \rangle$ is the mapping torus of an injective endomorphism $\psi$ of a free group $\mathbb{F} $ (of possibly infinite rank) then every finitely generated subgroup of $G$ admits a finite complete rewriting system.

It follows that any finitely generated virtually free-by-cyclic group, and any finitely generated subgroup of such a group, admits a finite complete rewriting system.

We apply this to show that every finitely generated subgroup of a locally quasi-convex hyperbolic and virtually compact special group admits a finite complete rewriting system.

This includes all one-relator groups with torsion (and all their finitely generated subgroups) and all hyperbolic fully residually free groups.

Moreover, we show there is an algorithm that computes a finite complete rewriting system for any such group, given a presentation for its containing group and a finite list of generators for the subgroup.

We also prove that for every compact three-manifold $M$, the group $\pi_1(M) \ast \mathbb{Z}$ admits a finite complete rewriting system.

Furthermore, we show that the fundamental group of any compact three-manifold is autostackable and thus has a rational cross section and admits a bounded regular convergent prefix-rewriting system.