The finite basis problem for finite semigroups: a survey (Q2709049)

In 1985, \textit{L. N. Shevrin} and \textit{M. V. Volkov} [Izv. Vyssh. Uchebn. Zaved., Mat. 1985, No. 11(282), 3-47 (1985; Zbl 0629.20029)] published a survey of results on identities of semigroups. Unfortunately, the English translation of this [Sov. Math. 29, No. 11, 1-64 (1985)] is not readily accessible, so, in this sequel, the author not only brings us up-to-date on the more restricted topic of the finite basis problem for finite semigroups, but includes several results from the original paper in order to make the picture complete.NEWLINENEWLINENEWLINEThe underlying question as whether there is an algorithm that, given the Cayley table of a finite semigroup, will determine whether or not it has a finite basis for its laws remains open. \textit{R. McKenzie}'s result that the equivalent problem for groupoids is undecidable [Int. J. Algebra Comput. 6, No. 1, 49-104 (1996; Zbl 0844.08011)] suggests the answer may be ``no''. On the other hand, the existence of an algorithm that determines whether or not a finite semigroup is inherently nonfinitely based casts a ray of sunshine into the gloom (the equivalent problem for groupoids is undecidable).NEWLINENEWLINENEWLINEThis is an immensely valuable paper, for the author does not merely list the known results, but attempts to impress some order on the seemingly heterogeneous methods that have been used to show that particular finite semigroups do not have a finite basis for their laws. He describes three main methods. Firstly, the ``Syntactical method'', which works with the laws and produces an infinite basis. Secondly, the ``Critical semigroup method'', which produces for every \(n\) a semigroup in \(V^{(n)}\setminus V\), where \(V\) is the variety generated by the semigroup, and \(V^{(n)}\) the variety determined by the \(n\)-variable laws of \(V\). Thirdly the ``Inherently non-finitely-based method'' which works by attempting to prove the stronger result that the semigroup is actually inherently non-finitely based.NEWLINENEWLINENEWLINESome other methods that have not yet found wide application are also mentioned. There is also a briefer section on the problem of proving that a finite semigroup has a finite basis (this direction has progressed relatively slowly since the time of the original survey) and the final section gives some concrete problems, listing three series of finite semigroups for which the finite basis problem remains open. Of course, there is a magnificent bibliography.NEWLINENEWLINEFor the entire collection see [Zbl 0954.00028].