Abstract

The main result of the paper is the reduction of the problem of satisfiability of equations in free groups to the satisfiability of equations in free semigroups with anti-involution (SGA), by a non-deterministic polynomial time transformation. A free SGA is essentially the set of words over a given alphabet plus an operator which reverses words. We study equations in free SGA, generalizing several results known for equations in free semigroups, among them that the exponent of periodicity of a minimal solution of an equation E in free SGR is bounded by 2(O(/E /)).