Krohn-Rhodes theory
|
|
Krohn-Rhodes theory is an approach to the study of finite semigroups and automata, 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. Also, in computer science, the theory gave new, unexpected methods to build any finite state automaton using series-parallel emulation by simple components.
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?