Krohn-Rhodes theory
From Wikipedia, the free encyclopedia
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").
Contents |
[edit] History and Applications
At a conference in 1962, Kenneth Krohn and John Rhodes announced that they had found a beautiful method to decompose any (deterministic) finite automaton into "simple" components (each itself a finite automaton). Unusually, their unexpected result was joint work and merited the award of two PhDs: Krohn was awarded a PhD from Harvard and Rhodes from MIT. The result was hailed as a major advance, for both theory and practice, and also had implications for philosophy. Many simpler versions of the theorem's proof and generalizations to infinite structures have been published since then [Steinberg & Rhodes, in press], and recently computationally feasible decompositions comprise an active area of research as the decomposition generally requires increase of the automaton's state-set.
When Krohn and Rhodes published the paper on their work, in 1965, the theorem presented their method to decompose finite automata (or, equivalently sequential machines) making essential use of 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 (although in the general case these are embedded in a larger structure, with a hierarchical "coordinate system" on it). Some confusion occurs for automata theorists in that Krohn & 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 naive way) but, 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. His proof contained an error but a correct version appears, e.g. in [Eilenberg, 1976, Dömösi & Nehaniv 2005]. 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 & 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 correlation between monoids and categories, a version of the Krohn-Rhodes theorem is also applicable to category theory. This observation was made, and the analogous result proved, 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 semigroup and monoid theory are now becoming computationally feasible and include computation in biology and biochemical systems (e.g. Egri-Nagy & Nehaniv 2008]), artificial intelligence, finite-state physics, psychology, and game theory (see e.g. [Rhodes, in press]).
[edit] Description of the Krohn-Rhodes Theorem
A semigroup S is said to be a divisor of another semigroup T if S is a homomorphic image of a subsemigroup 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 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.
[edit] 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 question of 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 asserted that problem is decidable and has been writing up a proof since the late 1990s, but it remains to be published.]
[edit] References
- Dömösi P., Nehaniv C.L. (2005), Algebraic Theory of Automata Networks (SIAM).
- Egri-Nagy A. and Nehaniv C.L. (2004), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn-Rhodes Theory", in Implementation and Application of Automata: 9th International Conference, 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, 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).
- 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., 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., Rhodes J.L. (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (editor—Fox J.), (Wiley–Interscience).
- Krohn K., Rhodes J. (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., 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., Thompson C. (1969), "Remarks on algebraic decomposition of automata", Mathematical Systems Theory, 3: 110-118.
- Steinberg B, Rhodes J. (2008, in press). The q-Theory of Finite Semigroups, Springer Verlag.
- Straubing H., 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. L. (2008, in press). Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games, editor: C. L. Nehaniv, foreword by M. W. Hirsch, World Scientific Press.
- Tilson B (1989), "Categories as algebra: an essential ingredient in the theory of monoids", J. Pure Appl. 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. (plus erratum)
