50 Years of the Krohn-Rhodes Theorem

A little over 50 years ago (1962), we had the first nontrivial theorem which used an algebraic approach to automata theory: Schuetzenberger's theorem giving an algorithm to check whether a given regular language is definable using a starfree expression. The same year saw the announcement of the extension of the classification of finite groups to finite semigroups: the Krohn-Rhodes theorem showing that the semigroups which are groupfree can be composed using just one three-element "prime", the remaining primes being the finite simple groups. The journal paper appeared in 1965. (The complexity of this decomposition remains open.) In 1997, a new proof was found for Schuetzenberger's theorem. Recently this has led to new proofs for the Krohn-Rhodes theorem. It would be too much to pack all this into one talk, so we will give an overview, and explain all the required algebra.