# Decidability of conjugacy problem for finitely generated subgroups of free groups

The conjugacy problem for a free group $F_n$ on $n$ letters has an easy solution. Each element of $F_n$ is conjugate to a unique and easily computable "cyclically reduced element" (this means that if you arrange the word around a circle, then there are no cancellations), so two elements of $F_n$ are conjugate if and only if they have the same cyclically reduced conjugates.

I've been trying unsuccessfully to generalize this to solve the following problem. Let $\{x_1,\ldots,x_k\}$ and $\{y_1,\ldots,y_{k'}\}$ be two finite sets of elements of $F_n$. Let $G_x$ and $G_y$ be the subgroups of $F_n$ generated by the $x_i$ and the $y_i$, respectively. Is there an algorithm to decide if $G_x$ and $G_y$ are conjugate? Does anyone know how to do this? Thank you very much!

-

There is an algorithm to do this. I would have thought that it was classical, but in any case an algorithm is given in: I. Kapovich and A. Myasnikov "Stallings foldings and the subgroup structure of free groups", J. Algebra 248 (2002), no 2, pp. 608-668. In the online version I found here, it is Corollary 7.8 on page 18.

-
I fixed your link. – Andy Putman Apr 6 '10 at 20:53
Thanks very much, Andy! – Daniel Groves Apr 6 '10 at 23:05