Dependence over subgroups of free groups

Given a finitely generated subgroup H of a free group F, we present an algorithm which computes Formula: see text, such that the set of elements Formula: see text, for which there exists a non-trivial H-equation having g as a solution is precisely the disjoint union of the double cosets Formula: see text. Moreover, we present an algorithm which, given a finitely generated subgroup Formula: see text and an element Formula: see text, computes a finite set of elements from Formula: see text (of the minimum possible cardinality) generating, as a normal subgroup, the “ideal” Formula: see text of all “polynomials” Formula: see text, such that Formula: see text. The algorithms, as well as the proofs, are based on the graph-theoretic 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 Formula: see text on a subgroup H. We also study the corresponding notions of dependence sequence and dependence closure of a subgroup.