Krohn–Rhodes theory

Krohn–Rhodes theory

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

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] ).

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.

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.]

References

* Dömösi, P.; and 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.; 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. (2008, in press). "The "q"-Theory of Finite Semigroups", Springer Verlag
* 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. 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: 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 (plus erratum)

External links

* [http://math.berkeley.edu/~rhodes/ Prof. John L. Rhodes, University of California webpage]
* [http://mathstat.carleton.ca/~bsteinbg/qtheor.html See Introduction to "q"-Theory for Benjamin Steinberg's history of semigroup theory]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Krohn — Family name Meaning Middle High German word kran or kron ; crane Region of origin Schleswig Holstein Krohn is the surname of several people: Lars Monrad Krohn, a Norwegian engineer Kristin Krohn Devold, a Norwegian politician Michae …   Wikipedia

  • John Rhodes — may refer to: * John Rhodes (17th century), theatrical figure in London * John Rhodes (driver) (born 1927), British Formula One driver * John Rhodes (sailor) (1870 1947), British Olympic gold medalist in 1908 * John Rhodes (mathematician), co… …   Wikipedia

  • Semigroup action — In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup (using… …   Wikipedia

  • List of abstract algebra topics — Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. The phrase abstract algebra was coined at the turn of the 20th century to distinguish this …   Wikipedia

  • Semigroup — This article is about the algebraic structure. For applications to differential equations, see C0 semigroup. In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup… …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

  • Transformation semigroup — In algebra, a transformation semigroup (or composition semigroup) is a collection of functions from a set to itself which is closed under function composition. If it includes the identity function, it is a transformation (or composition) monoid.… …   Wikipedia

  • Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… …   Wikipedia

  • Monoid — This article is about the mathematical concept. For the alien creatures in the Doctor Who adventure, see The Ark (Doctor Who). Coherence law for monoid unit In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a… …   Wikipedia

  • Aperiodic monoid — In mathematics, an aperiodic semigroup is a semigroup S such that for every x ∈ S , there exists a nonnegative integer n such that xn = xn + 1 .An aperiodic monoid is an aperiodic semigroup which is a monoid. This notion is in some sense… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”