Welcome to MathOverflow

Question

4

1

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-

flag	asked Jan 22 2012 at 13:53 Chris 43●2

See gap-system.org/Manuals/pkg/fga/doc/manual.pdf section 2.3 for a GAP implementation. – Guntram Jan 22 2012 at 17:14

Igor Rivin · Accepted Answer · 2012-01-22 14:18:31Z UTC

9

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.

answered Jan 22 2012 at 14:18

Igor Rivin
31.2k●3●37●71

2

Actually, he is asking for the uniform generalized word problem since he wants f as part if the input. – Benjamin Steinberg Jan 22 2012 at 19:07

Stallings algorithm does solve the uniform generalized word problem. – Lee Mosher Mar 2 2012 at 13:42

Algorithm for image of a free group homomorphism

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.