Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Thanks-

share|improve this question
    
See gap-system.org/Manuals/pkg/fga/doc/manual.pdf section 2.3 for a GAP implementation. –  Guntram Jan 22 '12 at 17:14

1 Answer 1

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|improve this answer
2  
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

 
discard

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.