Krohn–Rhodes theory

This article may require copy-editing for grammar, style, cohesion, tone or spelling. You can assist by editing it. (September 2008)

In mathematics and computer science, Krohn–Rhodes theory is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These turn out to correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner (called a "wreath product" or "cascade").

History and Applications

Kenneth Krohn and John Rhodes announced at a conference in 1962 a method for decomposing a (deterministic) finite automaton into "simple" components that are themselves finite automata. This joint work, which has implications for philosophy, merited the award of two PhDs: to Krohn by Harvard and to Rhodes by MIT. Simpler proofs and generalizations of the theorem to infinite structures have been published since then (see Chapter 4 of [Steinberg & Rhodes, 2009] 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 so-called "flip-flop" (the two-state automaton with three inputs: the identity and the two reset operations). 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".

Some confusion occurs for automata theorists in that Krohn and Rhodes explicitly refer to their theorem as a prime decomposition theorem for automata. The components in the decomposition, however, were not prime automata (with "prime" defined in a naïve way); rather, the notion of prime is more sophisticated and algebraic: it is the case that the semigroups and groups associated to the constituent automata of the decomposition are prime (or irreducible) in a strict and natural algebraic sense [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 have become available.

H.P. Zeiger [1967] proved an important variant called the Holonomy Decomposition (Eilenberg 1976, Dömösi & Nehaniv 2005 present proofs that correct an error in the Zeiger's paper). The holonomy method appears to be relatively efficient and has been implemented computationally by A. Egri-Nagy [Egri-Nagy & Nehaniv 2005]. Meyer & 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]), with the holonomy method the most popular and efficient in general (although not in all cases). Due 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]; see also [Tilson 1989].

The Krohn–Rhodes theorem for semigroups/monoids turns out to be essentially the 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, since it had previously been widely believed that the semigroup/monoid axioms were too weak to admit a structure theorem of any strength.

To summarize, Krohn and Rhodes found a general decomposition for finite automata. In doing their research, though, the authors discovered and proved an unexpected major result in finite semigroup theory, revealing a deep connection between finite automata and semigroups. Presently work by Egri-Nagy and Nehaniv is going ahead 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 presently becoming 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 e.g. [Rhodes 2009]).

Description of the Krohn–Rhodes Theorem

A semigroup S that is a homomorphic image of a subsemigroup of T is said to be a divisor of T. The Krohn–Rhodes theorem for semigroups states that every finite semigroup S is a divisor of a finite alternating wreath product of finite simple groups, each a divisor of S, and finite aperiodic semigroups (which contain no nontrivial subgroups).

In the automata formulation, given a finite automaton A with states Q and input set I, output alphabet U, then one can expand the states to Q' such that the new automaton A' embeds into a cascade of "simple", irreducible automata: In particular, A is emulated by a cascade of automata whose transitions semigroups are either (1) finite simple groups or (2) subsemigroups of the flip-flop (see above). The new automaton A' has the same input and output symbols as A. Here both the states and inputs of the cascaded automata have a very special hierarchical coordinate form.

Moreover, each simple group (prime) or non-group irreducible semigroup (subsemigroup of the flip-flop monoid) that divides the transformation semigroup of A must divide the transition semigroup of some component of the cascade, and only the primes that must occur as divisors of the components are those that divide A 's transition semigroup.

Group complexity

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 [Kambites, 2007].

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

References

• Dömösi, P.; and Nehaniv, C. L. (2005), Algebraic Theory of Automata Networks (SIAM) ISBN 978-0-898715-69-9
• Egri-Nagy, A.; and Nehaniv, C. L. (2004), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory", in 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, July 22-24, 2004, Revised Selected Papers, Editors: Domaratzki, M.; Okhotin, A.; Salomaa, K.; et al.; Springer Lecture Notes in Computer Science, Vol. 3317, pp. 315-316, 2005
• Egri-Nagy, A.; and Nehaniv, C. L. (2008), "Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks", Artificial Life — Special Issue on the Evolution of Complexity, 14(3): 299-312
• Eilenberg, S. (1976), Automata, Languages and Machines (Academic Press)
• Ésik, Z. (2005), "A proof of the Krohn-Rhodes Decomposition Theorem", Theoretical Computer Science, 234:287-300
• Hartmanis, J.; and Stearns, R. E. (1966), Algebraic Structure Theory of Sequential Machines (Prentice Hall)
• Kambites, M. (2007), "On the Krohn-Rhodes complexity of semigroups of upper triangular matrices", International Journal of Algebra and Computation, 17: 187-201
• Krohn, K. R.; and Rhodes, J. L. (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (editor: Fox, J.), (Wiley–Interscience)
• Krohn, K. R.; and Rhodes, J. L. (1965), "Algebraic theory of machines I: prime decomposition theorems for finite semigroups and machines", Transactions of the American Mathematical Society, 116: 450-464
• Krohn, K. R.; Rhodes, J. L.; and Tilson, B. R. (1968). "The Prime Decomposition Theorem of the Algebraic Theory of Machines", in Algebraic Theory of Machines, Languages, and Semigroups (editor: Arbib, M. A.), chapter 5, pages 81–125. Academic Press
• Lallement, G. (1971), "On the prime decomposition theorem for finite monoids", Mathematical Systems Theory, 5: 8-12
• Meyer, A. R.; and Thompson, C. (1969), "Remarks on algebraic decomposition of automata", Mathematical Systems Theory, 3: 110-118
• Steinberg, B.; and Rhodes, J. L. (2009). The q-Theory of Finite Semigroups, Springer Monographs in Mathematics, Springer Verlag. ISBN 978-0-387-09780-0
• Straubing, H.; and Thérien, D. (2002), "Weakly iterated block products of finite monoids", LNCS 2286: LATIN 2002—Theoretical Informatics (editor: Rajsbaum, S.), 91-104 (Springer)
• Rhodes, J. (2009). Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games, editor: Nehaniv, C. L.; foreword by Hirsch, M. W.; World Scientific Press
• Tilson, B. (1989), "Categories as algebra: an essential ingredient in the theory of monoids", Journal of Pure and Applied Algebra, 48: 83-198
• Wells, C. (1980), "A Krohn-Rhodes theorem for categories", Journal of Algebra, 64: 37-45
• Zeiger, H. P. (1967), "Cascade synthesis of finite state machines", Information and Control, 10:419-433. Erratum: Information and Control 11(4): 471 (1967).

Further reading

• John Rhodes Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games, editor: Nehaniv, C. L.; foreword by Hirsch, M. W.; World Scientific Press, 2009, ISBN 978-981-283-696-0 (hardcover ed.), ISBN 978-981-283-697-7 (paperback ed.)
• John Rhodes, Benjamin Steinberg, The q-theory of finite semigroups, Springer, 2009, ISBN 0387097805

External links

• Prof. John L. Rhodes, University of California webpage
• See Introduction to q-Theory for Benjamin Steinberg's history of semigroup theory