4
$\begingroup$

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-

$\endgroup$
1

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Actually, he is asking for the uniform generalized word problem since he wants f as part if the input. $\endgroup$ Jan 22, 2012 at 19:07
  • $\begingroup$ Stallings algorithm does solve the uniform generalized word problem. $\endgroup$
    – Lee Mosher
    Mar 2, 2012 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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