Click here to flash read.
Given a finitely generated subgroup $H$ of a free group $F$, we present an
algorithm which computes $g_1,\ldots,g_m\in F$, such that the set of elements
$g\in F$, for which there exists a non-trivial $H$-equation having $g$ as a
solution, is, precisely, the disjoint union of the double cosets $H\sqcup
Hg_1H\sqcup \cdots \sqcup Hg_mH$. Moreover, we present an algorithm which,
given a finitely generated subgroup $H\leqslant F$ and an element $g\in F$,
computes a finite set of elements of $H * \langle x \rangle$ that generate (as
a normal subgroup) the ``ideal" $I_H(g) \unlhd H * \langle x \rangle$ of all
``polynomials" $w(x)$, such that $w(g)=1$. The algorithms, as well as the
proofs, are based on the graph-theory techniques introduced by Stallings and on
the more classical combinatorial techniques of Nielsen transformations. The key
notion here is that of dependence of an element $g\in F$ on a subgroup $H$. We
also study the corresponding notions of dependence sequence and dependence
closure of a subgroup.
No creative common's license