Equations in free semigroups with involution and their relation to equations in free groups

AbstractA free semigroup with involution (FSI) is essentially the set of words over a given alphabet plus an operator which reverses words. The paper introduces equations in FSI and show that they are the right objects to deal with when studying the complexity of equations in free groups. On these lines, we generalize to FSI several results valid for word equations, like the overlapping lemma, the 2O(|E|)-bound on the exponent of periodicity of minimal solutions, and the NP-hard lower bound.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 FSI by a non-deterministic polynomial time transformation