The finite basis problem for finite semigroups: a survey

From MaRDI portal





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. The 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). This 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. Some 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. For the entire collection see [Zbl 0954.00028].











This page was built for publication: The finite basis problem for finite semigroups: a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2709049)