Undecidable problems for completely 0-simple semigroups. (Q1025071)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Undecidable problems for completely 0-simple semigroups. |
scientific article |
Statements
Undecidable problems for completely 0-simple semigroups. (English)
0 references
18 June 2009
0 references
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.
0 references
completely 0-simple semigroups
0 references
pseudovarieties
0 references
word problem
0 references
finite semigroups
0 references
algorithmic solvability
0 references
finite membership problem
0 references
decidability
0 references
finite regular semigroups
0 references
0 references
0 references