Krohn–Rhodes theory

Summary

Krohn–Rhodes theory studies finite semigroups and finite automata by decomposing them into simple building blocks. Its central result is the Krohn–Rhodes theorem. It says that every finite semigroup divides an iterated wreath product of finite simple groups and copies of the flip-flop, a monoid of resets. The simple groups in such a decomposition can be chosen among the simple groups that divide the semigroup. So every finite automaton can be built in a cascade from reversible parts, which are groups, and memory parts, which are flip-flops. The least number of group levels needed is the complexity of the semigroup, a central object of study in the theory.