TR04-091 Authors: Ondrej Klíma, Pascal Tesson, Denis Thérien

Publication: 3rd November 2004 21:15

Downloads: 1953

Keywords:

We consider the problem of testing whether a given system of equations

over a fixed finite semigroup S has a solution. For the case where

S is a monoid, we prove that the problem is computable in polynomial

time when S is commutative and is the union of its subgroups

but is NP-complete otherwise. When S is a monoid or a

regular semigroup, we obtain similar dichotomies for the restricted

version of the problem where no variable occurs on the right-hand side

of each equation.