Algorithmic problems for finite groups and finite \(0\)-simple semigroups (Q1358940): Difference between revisions

The completely 0-simple semigroups are generally regarded, as befits their name, as a particularly simple and easily studied class of semigroups. Thus it came as a shock when S. I. Kublanovskii, in unpublished work, proved that the set of all subsemigroups of finite completely 0-simple semigroups is not recursive, in other words, membership in this set is undecidable. The main theorem of the paper under review strengthens this result by showing that, given any pseudovariety \(\mathcal V\) of finite groups, the set of finite subsemigroups of completely 0-simple semigroups over groups from \(\mathcal V\) is recursive if and only if the uniform word problem in \(\mathcal V\) is solvable. Many further equivalent conditions are found: among them is the equivalence of the recursiveness of the set of finite subsemigroups of Brandt semigroups over groups in \(\mathcal V\); another is that of the set of finite 4-nilpotent subsemigroups of finite completely 0-simple semigroups over groups in \(\mathcal V\). The number 4 is best possible in that context. Since the uniform word problem is undecidable in the class of all finite groups, Kublanovskii's theorem follows. However, many further such pseudovarieties of groups have the same property, as determined by Kharlampovich [see \textit{O. Kharlampovich} and \textit{M. Sapir}, Int. J. Algebra Comput. 5, No. 4-5, 379-602 (1995; Zbl 0837.08002)]. From another of the equivalent conditions follows a different result of Kublanovskii: the set of subsemigroups of finite direct products of finite completely 0-simple semigroups is not recursive. It is then all the more remarkable that the pseudovariety of finite semigroups generated by the completely 0-simple semigroups does have decidable membership problem (and similarly for that generated by the Brandt semigroups). Various further properties of these and related pseudovarieties are found.