How can I tell if elements generate or $F_n$ or $F_n \times F_n$? 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?
 A: 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: 


*

*Construct a Stallings fold factorization of the map $f$:
$$R_m = G_0 \xrightarrow{f_1} G_1 \xrightarrow{f_2} \cdots \xrightarrow{f_K} G_K \xrightarrow{h} R_n
$$
I'll say what this is in a minute, but suffice it for the moment to say that this is a sequence of finite connected graphs and maps which is easily calculated from the original map $f : R_m \to R_n$, the final map $h : G_K \to R_n$ is a local injection, and the induced fundamental group homomorphisms of these two maps have the same image in $\pi_1(R_n)=F_n$, that is, $\text{image}(f_*)=\text{image}(h_*)$. 

*Check whether the final map $h : G_K \to R_n$ is a homeomorphism. If so then $\text{image}(f_*) = \pi_1(R_n)=F_n$ and hence $\{w_1,...,w_m\}$ generates $F_n$. If not then $\text{image}(f_*)$ is a proper subgroup of $F_n$ and hence $\{w_1,...,w_m\}$ does not generate $F_n$.


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.
A: *

*There are several algorithms for deciding if a finite set of elements $x_1,...,x_k$ generates the free group $F=F(y_1,...,y_n)$. Here is one (another algorithm I know is based on quasiconvexity):


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. 


*As for $F_n\times F_n$, there exist a family of finitely-generated normal subgroups $K< G=F_n\times F_n$ such that for the finitely-presented groups $Q=G/K$ it is undecidable if such a group group is trivial or not. (This is Mikhailova's construction). Therefore, it is undecidable if the generators of $K$ generate $G$. 

