Narrow Results

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 complexity of this problem is much harder, when restricted to commutative semigroups. We provide a relatively simple proof that in general the problem is co-NP-complete, and demonstrate, using some structure theory, that for a fixed commutative semigroup the problem can be solved in polynomial time. The complexity status of the general problem remains open.

Let A be a finitely generated commutative algebra over a field K with a presentation A = K 〈X₁,…, X_n | R〉, where R is a set of monomial relations in the generators X₁,…, X_n. So A = K[S], the semigroup algebra of the monoid S = 〈X₁,…, X_n | R〉. We characterize, purely in terms of the defining relations, when A is an integrally closed domain, provided R contains at most two relations. Also the class group of such algebras A is calculated.

It is easy to show that a pseudovariety which is reducible with respect to an implicit signature $\sigma$ for the equation $x=y$ can also be defined by $\sigma$-identities. We present several negative examples for the converse using signatures in which the pseudovarieties are usually defined. An ordered example issue from the extended Straubing–Thérien hierarchy of regular languages is also shown to provide a positive example for the inequality $x\le y$.