At a conference in 1962,
Kenneth Krohn and
John Rhodes announced a method for decomposing a
(deterministic) finite automaton into "simple" components that are themselves finite automata. This joint work, which has implications for philosophy, comprised both Krohn's doctoral thesis at
Harvard University and Rhodes' doctoral thesis at
MIT. Simpler proofs, and generalizations of the theorem to infinite structures, have been published since then (see Chapter 4 of Rhodes and Steinberg's 2009 book
The q-Theory of Finite Semigroups for an overview). In the 1965 paper by Krohn and Rhodes, the proof of the theorem on the decomposition of finite automata (or, equivalently
sequential machines) made extensive use of the algebraic
semigroup structure. Later proofs contained major simplifications using finite
wreath products of finite transformation semigroups. The theorem generalizes the
Jordan–Hölder decomposition for finite groups (in which the primes are the finite simple groups), to all finite transformation semigroups (for which the primes are again the finite simple groups plus all subsemigroups of the "flip-flop" (see above)). Both the group and more general finite automata decomposition require expanding the state-set of the general, but allow for the same number of input symbols. In the general case, these are embedded in a larger structure with a hierarchical "coordinate system". One must be careful in understanding the notion of "prime" as Krohn and Rhodes explicitly refer to their theorem as a "prime decomposition theorem" for automata. The components in the decomposition, however, are not prime automata (with
prime defined in a naïve way); rather, the notion of
prime is more sophisticated and algebraic: the semigroups and groups associated to the constituent automata of the decomposition are prime (or irreducible) in a strict and natural algebraic sense with respect to the wreath product (
Eilenberg, 1976). Also, unlike earlier decomposition theorems, the Krohn–Rhodes decompositions usually require expansion of the state-set, so that the expanded automaton covers (emulates) the one being decomposed. These facts have made the theorem difficult to understand and challenging to apply in a practical way—until recently, when computational implementations became available (Egri-Nagy & Nehaniv 2005, 2008). H.P. Zeiger (1967) proved an important variant called the
holonomy decomposition (Eilenberg 1976). The holonomy method appears to be relatively efficient and has been implemented computationally by A. Egri-Nagy (Egri-Nagy & Nehaniv 2005). Meyer and Thompson (1969) give a version of Krohn–Rhodes decomposition for finite automata that is equivalent to the decomposition previously developed by Hartmanis and Stearns, but for useful decompositions, the notion of
expanding the state-set of the original automaton is essential (for the non-permutation automata case). Many proofs and constructions now exist of Krohn–Rhodes decompositions (e.g., [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), with the holonomy method the most popular and efficient in general (although not in all cases). [Zimmermann 2010] gives an elementary proof of the theorem. Owing to the close relation between
monoids and
categories, a version of the Krohn–Rhodes theorem is applicable to
category theory. This observation and a proof of an analogous result were offered by Wells (1980). The Krohn–Rhodes theorem for semigroups/monoids is an analogue of the
Jordan–Hölder theorem for finite groups (for semigroups/monoids rather than groups). As such, the theorem is a deep and important result in semigroup/monoid theory. The theorem was also surprising to many mathematicians and computer scientists since it had previously been widely believed that the semigroup/monoid axioms were too weak to admit a structure theorem of any strength, and prior work (Hartmanis & Stearns) was only able to show much more rigid and less general decomposition results for finite automata. Work by Egri-Nagy and Nehaniv (2005, 2008–) continues to further automate the holonomy version of the Krohn–Rhodes decomposition extended with the related decomposition for finite groups (so-called
Frobenius–Lagrange coordinates) using the
computer algebra system GAP. Applications outside of the semigroup and monoid theories are now computationally feasible. They include computations in
biology and biochemical systems (e.g. Egri-Nagy & Nehaniv 2008),
artificial intelligence, finite-state
physics,
psychology, and
game theory (see, for example, Rhodes 2009). ==See also==