We show that a number of natural membership problems for classes associated with finite
semigroups are computationally difficult. In particular, we construct a 55-element semigroup …

We give a quadratic algorithm for the following structure identification problem: given a
Boolean relation R and a finite set S of Boolean relations, can the relation R be expressed …

The left regular band structure on a hyperplane arrangement and its representation theory
provide an important connection between semigroup theory and algebraic combinatorics. A …

Checking the admissibility of quasiequations in a finitely generated (ie, generated by a finite
set of finite algebras) quasivariety Q amounts to checking validity in a suitable finite free …

We describe which subdirectly irreducible flat algebras arise in the variety generated by an
arbitrary class of flat algebras with absorbing bottom element. This is used to give an …

Theoretical Computer Science A finite set of functions with an EXPTIME-complete composition
problem Page 1 Theoretical Computer Science 407 (2008) 330–341 Contents lists available at …

Complexity of the Identity Checking Problem for Finite Semigroups Page 1 Journal of
Mathematical Sciences, Vol. 158, No. 5, 2009 COMPLEXITY OF THE IDENTITY CHECKING …

We consider the problem, whose instance is a finite semigroup S and an identity I, and the
question is whether I is satisfied in S. We show that the question concerning computational …

We associate to each variety of algebras of finite signature a function on the positive integers
called the equational complexity of the variety. This function is a measure of how much of the …

The variety membership problem for two classes of non-finitely based semigroups is
considered. It is shown that a finite semigroup S belongs to the variety generated by one of …