MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

Is there an algorithm which takes such an $f$ and a word $w\in H$ and tells if $w \in f(G)$?

Is there such an algorithm in the special case where $G=H$?


share|cite|improve this question
See section 2.3 for a GAP implementation. – Guntram Jan 22 '12 at 17:14
up vote 10 down vote accepted

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 generalized word problem 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.

share|cite|improve this answer
Actually, he is asking for the uniform generalized word problem since he wants f as part if the input. – Benjamin Steinberg Jan 22 '12 at 19:07
Stallings algorithm does solve the uniform generalized word problem. – Lee Mosher Mar 2 '12 at 13:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.