Algorithmic problems for finite groups and finite \(0\)-simple semigroups
type: Item
instance of: scholarly article
title: Algorithmic problems for finite groups and finite \(0\)-simple semigroups
zbMATH Open document ID: 0880.20040
DOI: 10.1016/S0022-4049(96)00050-3
author: O. Diekmann
published in: Journal of Pure and Applied Algebra
publication date: 1998-02-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 20E10
Mathematics Subject Classification ID: 08C15
Mathematics Subject Classification ID: 08A50
zbMATH DE Number: 1025722
zbMATH Keywords: pseudovarieties of finite groups
zbMATH Keywords: recursive sets of finite subsemigroups
zbMATH Keywords: completely 0-simple semigroups
zbMATH Keywords: Brandt semigroups
zbMATH Keywords: finite 4-nilpotent subsemigroups
zbMATH Keywords: finite completely 0-simple semigroups
zbMATH Keywords: word problems
zbMATH Keywords: pseudovarieties of groups
zbMATH Keywords: finite direct products
zbMATH Keywords: pseudovarieties of finite semigroups
zbMATH Keywords: decidable membership problems
reviewed by: Peter R. Jones
MaRDI profile type: Publication
cites work: Q4848740
cites work: Q3934450
cites work: Q3848243
cites work: On pseudovarieties
cites work: The Word Problem for Abstract Algebras
cites work: Local varieties of completely regular monoids
cites work: Semidirect products of regular semigroups
cites work: Q3663518
cites work: THE WORD PROBLEM FOR SOLVABLE LIE ALGEBRAS AND GROUPS
cites work: ALGORITHMIC PROBLEMS IN VARIETIES
cites work: Q4302152
cites work: Q5813179
cites work: Q3765976
cites work: Unsolvability of the universal theory of finite groups
cites work: Categories as algebra: An essential ingredient in the theory of monoids
description: scientific article; zbMATH DE number 1025722