Undecidable problems for completely 0-simple semigroups.
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.
- Algorithmic problems for finite groups and finite \(0\)-simple semigroups
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- The pseudovariety generated by completely \(0\)-simple semigroups
- Subsemigroups of completely simple semigroups
- The 0-minimal ideal of the global of a combinatorial completely 0-simple semigroup
- On aperiodic relational morphisms.
- scientific article; zbMATH DE number 3865591
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- Lattice isomorphisms of completely 0-simple semigroups
- The homomorphic images of a completely 0-simple semigroup and some congruences on it.
- A Finitely Generated Infinite Simple Group
- A Variety Where the Set of Subalgebras of Finite Simple Algebras is Not Recursive
- Algorithmic problems for amalgams of finite semigroups
- Algorithmic problems for finite groups and finite \(0\)-simple semigroups
- ALGORITHMIC PROBLEMS IN VARIETIES
- Decidability of finite quasivarieties generated by certain transformation semigroups.
- Embeddability and the Word Problem
- Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings
- FAITHFUL FUNCTORS FROM CANCELLATIVE CATEGORIES TO CANCELLATIVE MONOIDS WITH AN APPLICATION TO ABUNDANT SEMIGROUPS
- scientific article; zbMATH DE number 3165575 (Why is no real title available?)
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 1157212 (Why is no real title available?)
- scientific article; zbMATH DE number 1972777 (Why is no real title available?)
- scientific article; zbMATH DE number 3803516 (Why is no real title available?)
- scientific article; zbMATH DE number 1563405 (Why is no real title available?)
- scientific article; zbMATH DE number 789816 (Why is no real title available?)
- scientific article; zbMATH DE number 864826 (Why is no real title available?)
- Potential Divisibility in Finite Semigroups is Undecidable
- Quasigroups. I
- Relatively inherently nonfinitely q-based semigroups
- Some undecidable embedding problems for finite semigroups
- Unsolvability of the universal theory of finite groups
- Algorithmic problems for finite groups and finite \(0\)-simple semigroups
- Classification systems based on combinatorial semigroups
- \(\aleph_0\)-categoricity of semigroups. II.
- Rees semigroups of digraphs for classification of data.
- Some undecidable embedding problems for finite semigroups
- scientific article; zbMATH DE number 1972777 (Why is no real title available?)
- scientific article; zbMATH DE number 1512762 (Why is no real title available?)
- Potential Divisibility in Finite Semigroups is Undecidable
- Undecidability of representability as binary relations
- OPTIMAL REES MATRIX CONSTRUCTIONS FOR ANALYSIS OF DATA
- Natural dualities, nilpotence and projective planes
- Undecidability of Algebras of Binary Relations
- Optimization of classifiers for data mining based on combinatorial semigroups
- Internet security applications of the Munn rings
- Automorphism group and Laplacian spectrum of a graph over Brandt semigroups
- Commuting graph of an aperiodic Brandt semigroup
- Minimal signatures with undecidability of representability by binary relations
This page was built for publication: Undecidable problems for completely 0-simple semigroups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1025071)
