Undecidable problems for completely 0-simple semigroups.
type: Item
instance of: scholarly article
title: Undecidable problems for completely 0-simple semigroups.
zbMATH Open document ID: 1179.20052
author: Marcel Jackson
author: M. V. Volkov
published in: Journal of Pure and Applied Algebra
publication date: 2009-06-18T00:00:00Z
review text: 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.
reviewed by: Peter R. Jones
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M17
Mathematics Subject Classification ID: 20M20
zbMATH DE Number: 5566284
zbMATH Keywords: completely 0-simple semigroups
zbMATH Keywords: pseudovarieties
zbMATH Keywords: word problem
zbMATH Keywords: finite semigroups
zbMATH Keywords: algorithmic solvability
zbMATH Keywords: finite membership problem
zbMATH Keywords: decidability
zbMATH Keywords: finite regular semigroups
MaRDI profile type: Publication
full work available at URL: j.jpaa.2009.02.011
OpenAlex ID: W1975682685
cites work: Quasigroups. I
cites work: Q3934450
cites work: Embeddability and the Word Problem
cites work: FAITHFUL FUNCTORS FROM CANCELLATIVE CATEGORIES TO CANCELLATIVE MONOIDS WITH AN APPLICATION TO ABUNDANT SEMIGROUPS
cites work: Algorithmic problems for finite groups and finite \(0\)-simple semigroups
cites work: A Finitely Generated Infinite Simple Group
cites work: Q4846425
cites work: Some undecidable embedding problems for finite semigroups
cites work: Q4761443
cites work: Relatively inherently nonfinitely q-based semigroups
cites work: ALGORITHMIC PROBLEMS IN VARIETIES
cites work: Q4421568
cites work: A Variety Where the Set of Subalgebras of Finite Simple Algebras is Not Recursive
cites work: Potential Divisibility in Finite Semigroups is Undecidable
cites work: Q4748198
cites work: Q4872067
cites work: Eventually \({\mathcal H}\)-related sets and systems of equations over finite semigroups and rings
cites work: Algorithmic problems for amalgams of finite semigroups
cites work: Q3283927
cites work: Q4391164
cites work: Unsolvability of the universal theory of finite groups
cites work: Decidability of finite quasivarieties generated by certain transformation semigroups.
DOI: 10.1016/J.JPAA.2009.02.011
Recommended article: Algorithmic problems for finite groups and finite \(0\)-simple semigroups
Recommended article: Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
Recommended article: The pseudovariety generated by completely \(0\)-simple semigroups
Recommended article: Subsemigroups of completely simple semigroups
Recommended article: The 0-minimal ideal of the global of a combinatorial completely 0-simple semigroup
Recommended article: On aperiodic relational morphisms.
Recommended article: Q3333246
Recommended article: UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
Recommended article: Lattice isomorphisms of completely 0-simple semigroups
Recommended article: Q3513481
description: scientific article; zbMATH DE number 5566284