Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with finite semigroups:
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

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 >>>

TR05-059 | 9th May 2005
Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

Tractable Clones of Polynomials over Semigroups

It is well known that coset-generating relations lead to tractable
constraint satisfaction problems. These are precisely the relations closed
under the operation $xy^{-1}z$ where the multiplication is taken in
some finite group. Bulatov et al. have on the other hand shown that
any clone containing the multiplication of some ``block-group'' ... more >>>

ISSN 1433-8092 | Imprint