most recent 30 from http://mathoverflow.net 2013-05-22T18:51:38Z http://mathoverflow.net/feeds/question/20539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20539/decidability-of-conjugacy-problem-for-finitely-generated-subgroups-of-free-groups Nick Hildebrand 2010-04-06T19:41:25Z 2010-04-16T16:38:14Z

<p>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.</p> <p>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!</p>

http://mathoverflow.net/questions/20539/decidability-of-conjugacy-problem-for-finitely-generated-subgroups-of-free-groups/20544#20544 Daniel Groves 2010-04-06T20:44:22Z 2010-04-06T20:53:25Z

<p>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 <a href="http://www.math.uiuc.edu/~kapovich/PAPERS/gr.pdf" rel="nofollow">here</a>, it is Corollary 7.8 on page 18.</p>