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

✍ Scribed by Claudio Gutiérrez

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 130 KB
• Volume: 297
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00642-4

✦ Synopsis

A 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 2 O(|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 satisÿability of equations in free groups to the satisÿability of equations in FSI by a non-deterministic polynomial time transformation.