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

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

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

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

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