Complexity of Finite Semigroups: History and Decidability

Abstract

In recent papers, Margolis, Rhodes and Schilling proved that the complexity of a finite semigroup is computable. This solved a problem that had been open for more than 50 years. The purpose of this paper is to survey the basic results of Krohn-Rhodes complexity of finite semigroups and to outline the proof of its computability.

arXiv commentarXiv admin note: text overlap with arXiv:2410.06668