All reports by Author Ondrej Klíma:

__
TR04-091
| 29th September 2004
__

Ondrej Klíma, Pascal Tesson, Denis Thérien#### Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

Ondrej Klíma, Pascal Tesson, Denis Thérien

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

more >>>