#Trivial finite state automata plus#

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. In the general case, these are embedded in a larger structure with a hierarchical 'coordinate system'. 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.

#Trivial finite state automata plus#

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)). Later proofs contained major simplifications using finite wreath products of finite transformation semigroups. 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. 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). This joint work, which has implications for philosophy, comprised both Krohn's doctoral thesis at Harvard University, and Rhodes' doctoral thesis at MIT.

History and applications Īt 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. Rhodes has conjectured that the problem is decidable. Upper bounds and ever more precise lower bounds on complexity have been obtained (see, e.g. 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).Ī major open problem in finite semigroup theory is the decidability of complexity: is there an algorithm that will compute the Krohn–Rhodes complexity of a finite semigroup, given its multiplication table? In fact, there are semigroups of every non-negative integer 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.Īll finite aperiodic semigroups have complexity 0, while non- trivial finite groups have complexity 1. 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. Here, both the states and inputs of the cascaded automata have a very special hierarchical coordinate form. The new automaton A' has the same input and output symbols as A. 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 that are banks of flip-flops running in parallel. 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 groups, each a divisor of S, and finite aperiodic semigroups (which contain no nontrivial subgroups).

1 Definitions and description of the Krohn–Rhodes theoremĭefinitions and description of the Krohn–Rhodes theorem Ī semigroup S that is a homomorphic image of a subsemigroup of T is said to be a divisor of T.