Krohn-Rhodes theory

Krohn-Rhodes theory is an approach to the study of finite semigroups, which seeks to decompose them in terms of finite aperiodic semigroups and finite groups.

An aperiodic semigroup is a semigroup with no non-trivial subgroups. In the 1960s, Krohn and Rhodes proved that every finite semigroup is a divisor (a homomorphic image of a subsemigroup) of a finite alternating wreath product of finite groups and finite aperiodic semigroups. This result, called the Krohn-Rhodes theorem, was (and is) surprising to many mathematicians, since it was (and is) widely believed that the semigroup axioms were too weak to admit a structure theorem of any strength.

The Krohn-Rhodes complexity (also called group complexity or just complexity) of a finite semigroup S is the least number of groups in a wreath product of finite groups and finite aperiodic semigroups of which S is a divisor.

All finite aperiodic semigroups have complexity 0, while non-trivial finite groups have complexity 1. In fact, there are semigroups of every non-negative integer complexity. For example, for any n greater than 1, the multiplicative semigroup of all (n+1)×(n+1) upper triangular matrices over any fixed finite field has complexity n.

A major open problem in finite semigroup theory is question of the decidability of complexity: is there an algorithm which, given the multiplication table for a finite semigroup, will compute its Krohn-Rhodes complexity?