
> 
> Let $S$ be a finite set and $F$ is the free group on that set. Is there an algorithm which takes as input a sequence of $w,w\_1,\ldots,w\_k\in F$ and decides whether $w\in \langle w\_1,\ldots,w\_k\rangle$?
> 
> 
> 


This question keeps appearing in some of my work. My intuition is that this has been solved somewhere. It seems very related to the Nielsen-Schreier theorem and, to my understanding, Nielsen's proof of this theorem gave an algorithm for finding a free generating set for any finitely generated subgroup of a free group - which is very closely related to this problem. I also have found various literature referring to this as a "generalized word problem" and various undecidability results relating to the problem in general - but, even though nothing suggests that this is undecidable for a free group, I've not come across any algorithm for deciding it.



Is there an algorithm to decide if a word is in a finitely generated subgroup of a free group?
Let $T$ be a finite subset of the free group on a set $S$. Nielsen's original proof (described nicely in the beginning of Lyndon and Schupp's book) gives an algorithmic process to find a free generating set $T'$ for the subgroup generated by $T$ with the following very nice property: for a word $u$ in $T'$, the $T'$-length $|u|\_{T'}$ of $u$ is at least the $S$-length $|u|\_S$ of $u$. To recognize if a word $w$ in $S$ lies in the subgroup generated by $T$, it is thus enough to check whether it equals any of the finitely many words of length at most $|w|\_S$ in $T'$.


But of course there are much faster and better ways to do this. The nicest algorithm (which runs very fast) is based on Stallings folding and can be found in


Stallings, John R.
Topology of finite graphs. 
Invent. Math. 71 (1983), no. 3, 551–565. 


I don't have the paper handy right now, so I'm not sure if the algorithm is made explicit in it, but if you understand this paper then it should be clear how to do what you want.


