Detecting/Characterising positive elements in free groups Let $X$ be a set, and let $F(X)$ be the free group generated by $X$.
I will say that an element of $F(X)$ is positive if it is in the monoid generated by all the conjugates in $F(X)$ of every member of $X$.
For example, if $X=\left\{a,b\right\}$ then $a, b, a^2 b a^{-1}$  are positive, but $aba^{-1}b^{-1}$ is not positive.
Is there any algorithm that can detect, given an element of $F(X)$, whether is it positive?
 A: Yes, there is an algorithm. This is based on the following simple fact: Any positive element can be reached (but in non-reduced form usually) by only applying the operations right multiplication by a generator $R_g(x)=xg$ and conjugation by a generator $C_g^{\pm}(x)=g^{\pm 1}xg^{\mp 1}$.
To see this, just rewrite
$$
xax^{-1}yby^{-1} \ldots wpw^{-1}zqz^{-1} = zz^{-1}ww^{-1} \ldots yy^{-1} xax^{-1}yby^{-1} \ldots wpw^{-1}zqz^{-1}
$$
(here $a,b, \ldots ,p,q\in X$, while $x,y,\ldots$ are general elements of $F(X)$).
Note that this at most doubles the length of our word.
Conversely, it's easy to see that any word reached by a combination of these operations will be positive.
This gives the following procedure: (1) Given a word $W$, list all non-reduced words of length $\le 2|W|$ that represent the same element; (2) for each such word $W'$, find all $W''$ (if any) with $W'=O(W'')$, with $O$ one of the operations from above; (3) repeat with these new words $W''$ etc.
$W$ is positive precisely if the empty word ever shows up in this list. The algorithm terminates because undoing a multiplication or conjugation reduces the length of a word.
