All reports by Author Denis Thérien:

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR05-059
| 9th May 2005
__

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien#### Tractable Clones of Polynomials over 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

__
TR01-040
| 16th May 2001
__

Pierre Péladeau, Denis Thérien#### On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

__
TR01-005
| 27th October 2000
__

Pascal Tesson, Denis Thérien#### The Computing Power of Programs over Finite Monoids

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

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

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

Pierre Péladeau, Denis Thérien

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

Pascal Tesson, Denis Thérien

The formalism of programs over monoids has been studied for its close

connection to parallel complexity classes defined by small-depth

boolean circuits. We investigate two basic questions about this

model. When is a monoid rich enough that it can recognize arbitrary

languages (provided no restriction on length is imposed)? When ...
more >>>