The decidability of Krohn-Rhodes complexity for all finite semigroups

The Krohn-Rhodes Theorem shows that every finite semigroup S divides, that is, is a quotient of a subsemigroup of a wreath product of simple groups that are Jordan-Holder factors of the subgroups of S and the 3-element monoid U consisting of two right-zeroes and an identity element. We call a finite semigroup prime if whenever it divides a wreath product of two finite semigroups then it divides one of the factors.  Then the Krohn-Rhodes Theorem also shows that a semigroup is prime if and only if it is a simple group or is a subsemigroup of U.

In particular, every aperiodic semigroup, that is, semigroup in which each subgroup is trivial, divides a wreath product of copies of U. The Krohn-Rhodes complexity of a finite semigroup S is the least number of groups in any decomposition of S as a divisor of a wreath product of groups and aperiodic semigroups. Margolis, Rhodes, and Schilling recently proved that it is decidable to compute the complexity of a finite semigroup. This settled a problem in finite semigroup theory that had been open for 62 years.

The purpose of this talk is to give a gentle overview of the mathematics behind the solution of this problem. LIke many important open problems, the lack of a solution led to the creation of many tools used to approach the problem and are now important tools in semigroup theory and its applications. We'll discuss some of these as well.

This is joint work with John Rhodes and Anne Schilling.