Undecidable problems for completely 0-simple semigroups. (Q1025071)

The authors of the ground-breaking paper [\textit{T. E. Hall, S. I. Kublanovsky, S. Margolis, M. V. Sapir} and \textit{P. G. Trotter}, J. Pure Appl. Algebra 119, No. 1, 75-96 (1997; Zbl 0880.20040)] on completely 0-simple semigroups established a series of remarkable results indicating that these semigroups are much more complex than their name suggests. Among these results was a series of twelve statements on the recursiveness of the set of finite semigroups embeddable in various classes of completely 0-simple semigroups, each over a fixed pseudovariety \(\mathcal V\) of finite groups. Their theorem (Theorem A in the paper under review) states that each is equivalent to the algorithmic solvability of the uniform word problem in \(\mathcal V\). The classes range between that of all such semigroups and that of all finite 3-nilpotent subsemigroups of \(m\times m\) Brandt semigroups. In this paper, the authors correct a flaw in the proof of equivalence of one of the twelve conditions and demonstrate that another equivalence is false. This forms the starting point for a number of contrasting new results, several of which (Theorem B) prove that in certain cases the finite membership problem is solvable in polynomial time, independent of the underlying group pseudovariety. In addition, quite surprising results are found concerning the decidability of membership in the class of finite semigroups embeddable in some quite broad classes of finite regular semigroups.