Let $F_n$ be the free group on the letters $x_1,...,x_n$. Given a set of elements $\{ w_1,...,w_m \} \subset F_n$ how can I tell if they generate $F_n$? Are there nice necessary/sufficient conditions?
Similarly I would like to be able to tell if a finite setoff elements in $F_n \times F_n$ generate the whole group? Is there an algorithmic way to do this?
On
Here's an answer to your question regarding $F_n$.
Nielsen's 1921 paper "On Calculation with non-commutative factors and its applications to group theory" gives an algorithmic answer to a special case of your question, namely when $w_1,...,w_m$ is a free basis of $F_n$. The modern approach to Nielsen's algorithm uses Stallings fold sequences, and furthermore that approach easily generates to an algorithm for deciding when $w_1,...,w_m$ generates $F_n$. The success of this algorithm is perhaps the best necessary and sufficient condition that I know.
The algorithm is topological in nature and that's the easiest way to describe it, although since it is entirely about finite graphs it is easily programmable.
Let $R_n$ be the rose graph with edges labelled $x_1,...,x_m$, hence $\pi_1(R_n)$ is identified with $F_n$.
Similarly let $R_m$ be the rose graph with edges labelled by abstract symbols $W_1,...,W_m$, hence $\pi_1(R_m)$ is identified with $F_m$. Here I am thinking of $W_i$ as an abstract symbol representing the word $w_i \in F_n$.
Let $f : R_m \to R_n$ the map which takes vertex to vertex and takes the edge of $R_m$ labelled $W_i$ to the edge path in $R_n$ labelled by letters of the word $w_i$.
Your question is equivalent to the following question: How can I tell that the induced map $f_* : \pi_1(R_m) \to \pi_1(R_n)$ is surjective?
The answer is:
Next let me describe Step 1, how to construct the Stallings fold factorization of $f$.
The word $w_i$ is a reduced word in the generators $x_1,..,x_m$ and their inverses. Let $L_i$ be the length of $w_i$. Subdivide the edge of $R_m$ labelled $W_i$ into $L_i$ oriented, labelled edgelets, where an edgelet is labelled $x_i$ if and only if the corresponding letter of $w_i$ is $x_i$ or $x_i^{-1}$, the orientation points forward if that letter is $x_i$, and backwards if that letter is $x_i^{-1}$.
The Stallings fold sequence is constructed inductively, starting from $$R_m = G_0 \xrightarrow{f = h_0} R_n $$ In the inductive step, given $$R_m = G_0 \xrightarrow{f_1} \cdots \xrightarrow{f_k} G_k \xrightarrow{h_k} R_n $$ one asks whether $h_k$ is a local injection. If so, the induction is complete. If not, then there are two oriented edgelets $e,e' \subset G_k$ with the same label and with the same initial or same terminal vertex. One may then factor $h_k : G_k \to R_n$ as $$G_k \xrightarrow{f_{k+1}} G_{k+1} \xrightarrow{h_{k+1}} R_n $$ where $f_{k+1}$ identifies $e$ and $e'$. Since $G_{k+1}$ has one fewer edgelet than $G_k$, the induction must stop. It's easy to see that $(f_k)_*$ and $(f_{k+1})_*$ have the same image, hence when the induction stops the maps $f_*$ and $h_*$ have the same image.
Finally let me justify Step 2. Since $h : G_K \to R_n$ is locally injective, it follows from simple topological arguments that there exists a connected covering map $\tilde h : \tilde G \to R_n$ and an embedding $i : G_K \hookrightarrow \tilde G$ such that $h = \tilde h \circ i$. This implies that $h_*$ fails to be surjective if and only if one of the following holds: the covering map $\tilde h$ has degree $d \ge 2$, or $\tilde h$ has degree $d=1$ and $\tilde G$ is a proper subgraph of $G_K$; equivalently, $h$ is not a homeomorphism.
For each generator $y_i$ of $F$ run two algorithms in parallel:
A. Enumerate all words $w=w(x_1,...,x_k)$ in the elements $x_1,...,x_k$, rewritten as reduced words in $y_1,...y_n$, and for each word check if $w$ equals $y_i$. If for some $w$ it is, then proceed to the next generator $y_{i+1}$. If for all $y_i$'s you conclude that such $w=w_i$ exists, then $x_1,...,x_k$ generate $F$. (This is the semidecidability Derek referred to: It works whenever the ambient group has solvable word problem, you do not need to assume that the group is free. For instance, $F_n\times F_n$ has solvable word problem, for obvious reason.)
B. For each permutation group $S_N$ enumerate all homomorphisms $\phi: F\to S_N$ and for each $\phi$ check if $\phi(y_i)$ belongs to the subgroup generated by $\phi(x_1),...,\phi(y_k)$. If for some $\phi$ it does not, then you are done: The elements $x_1,...,x_k$ do not generate $F$.
The point is that each free group $F$ is LERF: For every finitely generated subgroup $H<F$ and $y\in F \setminus H$ there exists a homomorphism $\phi: F\to S_N$ such that $\phi(y)\notin \phi(H)$. Hence, if $H=<x_1,...,x_k>$ is a proper subgroup of $F$ then some free generator $y_i$ is not in $H$. Hence, the above algorithm will eventually prove it.