Krohn-Rhodes theory
Encyclopedia
In mathematics
and computer science
, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroup
s and automata
that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner (called a "wreath product
" or "cascade").
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.
S that is a homomorphic image of a subsemigroup of T is said to be a divisor of T.
The Krohn–Rhodes theorem for finite semigroups states that every finite semigroup S is a divisor of a finite alternating wreath product
of finite simple group
s, each a divisor of S, and finite aperiodic semigroups (which contain no nontrivial subgroups).
In the automata formulation, the Krohn-Rhodes theorem for finite automata states that 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 feed-forward cascade of (1) automata whose transitions semigroups are finite simple groups and (2) automata which are banks of flip-flops running in parallel.The flip-flop is the two-state automaton with three input operations: the identity (which leaves its state unchanged) and the two reset operations (which overwrite the current state by a resetting to a particular one of the two states). This can be considered a one-bit
read-write storage unit: the identity corresponds to reading the bit (while leaving its value unaltered), and the two resets to setting the value of the bit to 0 or 1. Note that a reset is an irreversible operator as it destroys the currently stored bit value. NB: The semigroup of the flip-flop and all its subsemigroups are irreducible. 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.
) 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?
Upper bounds and ever more precise lower bounds on complexity have been obtained (see, e.g. Rhodes & Steinberg, 2009). Rhodes has conjectured that the problem is decidable.J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 March 1997.
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
.Morris W. Hirsch, "Foreword to Rhodes' Applications of Automata Theory and Algebra". In J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games", (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010. Simpler proofs, and generalizations of the theorem to infinite structures, have been published since then (see Chapter 4 of Steinberg and Rhodes' 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 product
s 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".
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: 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 became available (Egri-Nagy & Nehaniv 2005, 2008).
H.P. Zeiger (1967) proved an important variant called the holonomy decomposition (Eilenberg 1976).Eilenberg 1976, as well as Dömösi and Nehaniv, 2005, present proofs that correct an error in 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 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]), 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 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 scientistsC.L. Nehaniv, Preface to (Rhodes, 2009) 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).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
s and automata
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner (called a "wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
" or "cascade").
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.
Definitions and Description of the Krohn-Rhodes Theorem
A semigroupSemigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
S that is a homomorphic image of a subsemigroup of T is said to be a divisor of T.
The Krohn–Rhodes theorem for finite semigroups states that every finite semigroup S is a divisor of a finite alternating wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
of finite simple group
Simple group
In mathematics, a simple group is a nontrivial group whose only normal subgroups are the trivial group and the group itself. A group that is not simple can be broken into two smaller groups, a normal subgroup and the quotient group, and the process can be repeated...
s, each a divisor of S, and finite aperiodic semigroups (which contain no nontrivial subgroups).
In the automata formulation, the Krohn-Rhodes theorem for finite automata states that 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 feed-forward cascade of (1) automata whose transitions semigroups are finite simple groups and (2) automata which are banks of flip-flops running in parallel.The flip-flop is the two-state automaton with three input operations: the identity (which leaves its state unchanged) and the two reset operations (which overwrite the current state by a resetting to a particular one of the two states). This can be considered a one-bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
read-write storage unit: the identity corresponds to reading the bit (while leaving its value unaltered), and the two resets to setting the value of the bit to 0 or 1. Note that a reset is an irreversible operator as it destroys the currently stored bit value. NB: The semigroup of the flip-flop and all its subsemigroups are irreducible. 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 complexityComplexity
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 science there are at this time a number of approaches to characterizing complexity, many of which are...
) of a finite semigroup S is the least number of groups in a wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
of finite groups and finite aperiodic semigroups of which S is a divisor.
All finite aperiodic semigroups have complexity 0, while non-trivial
Trivial (mathematics)
In mathematics, the adjective trivial is frequently used for objects that have a very simple structure...
finite groups have complexity 1. In fact, there are semigroups of every non-negative integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
complexity. For example, for any n greater than 1, the multiplicative semigroup of all (n+1)×(n+1) upper triangular matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
over any fixed finite field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
has complexity n (Kambites, 2007).
A major open problem in finite semigroup theory is the decidability of complexity: given the multiplication table
Multiplication table
In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....
for a finite semigroup, is there an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that will compute its Krohn–Rhodes complexity?
Upper bounds and ever more precise lower bounds on complexity have been obtained (see, e.g. Rhodes & Steinberg, 2009). Rhodes has conjectured that the problem is decidable.J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 March 1997.
History and applications
At a conference in 1962, Kenneth Krohn and John RhodesJohn Rhodes (mathematician)
John L. Rhodes is a mathematician known for work in the theory of semigroups, finite state automata, and algebraic approaches to differential equations.- Publications :...
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
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, and Rhodes' doctoral thesis at MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
.Morris W. Hirsch, "Foreword to Rhodes' Applications of Automata Theory and Algebra". In J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games", (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010. Simpler proofs, and generalizations of the theorem to infinite structures, have been published since then (see Chapter 4 of Steinberg and Rhodes' 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
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
structure. Later proofs contained major simplifications using finite wreath product
Wreath product
In mathematics, the wreath product of group theory is a specialized product of two groups, based on a semidirect product. Wreath products are an important tool in the classification of permutation groups and also provide a way of constructing interesting examples of groups.Given two groups A and H...
s 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".
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: 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 became available (Egri-Nagy & Nehaniv 2005, 2008).
H.P. Zeiger (1967) proved an important variant called the holonomy decomposition (Eilenberg 1976).Eilenberg 1976, as well as Dömösi and Nehaniv, 2005, present proofs that correct an error in 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 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]), 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
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. 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 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 scientistsC.L. Nehaniv, Preface to (Rhodes, 2009) 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
Computer algebra system
A computer algebra system is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.-Symbolic manipulations:...
GAP
GAP computer algebra system
GAP is a computer algebra system for computational discrete algebra with particular emphasis on computational group theory.-History:...
.
Applications outside of the semigroup and monoid theories are now computationally feasible. They include computations in biology
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...
and biochemical systems (e.g. Egri-Nagy & Nehaniv 2008), artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, finite-state physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
, psychology
Psychology
Psychology is the study of the mind and behavior. Its immediate goal is to understand individuals and groups by both establishing general principles and researching specific cases. For many, the ultimate goal of psychology is to benefit society...
, and game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
(see, for example, Rhodes 2009).
External links
- Prof. John L. Rhodes, University of California at Berkeley webpage
- SgpDec: Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups, developed by A. Egri-Nagy and C. L. Nehaniv. Open-source software package for the GAPGap-General:* Gap , a spacing between large trees in a forest* Gap , a mountain pass, often carved by a river* Gap year, a prolonged period between a life stage-Places:* Gap, Hautes-Alpes, France* Gap, Pennsylvania, United States...
computer algebra system.