most recent 30 from http://mathoverflow.net 2013-05-21T13:17:43Z http://mathoverflow.net/feeds/question/86372 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86372/algorithm-for-image-of-a-free-group-homomorphism Chris 2012-01-22T13:53:10Z 2012-01-22T14:18:31Z

<p>Let $G$ and $H$ be finitely generated free groups, and let $f:G\to H$ be a homomorphism specified by giving the images of the generators of $G$. </p> <p>Is there an algorithm which takes such an $f$ and a word $w\in H$ and tells if $w \in f(G)$? </p> <p>Is there such an algorithm in the special case where $G=H$? </p> <p>Thanks-</p>

http://mathoverflow.net/questions/86372/algorithm-for-image-of-a-free-group-homomorphism/86374#86374 Igor Rivin 2012-01-22T14:18:31Z 2012-01-22T14:18:31Z

<p>You are asking whether an element in a free group lies in the span of a set of elements (the images of the generators). This is the <em>generalized word problem</em> which is known to be decidable for free groups (for an algorithm, see, for example: Stallings' "Topology of finite graphs" (Inventiones, 1983), though the result is several decades older.</p>