3. Krohn—Rhodes Theory and Complete Classes
Society for Industrial and Applied Mathematics eBooks · 2005
While the fundamental information concerning complete classes with respect to homomorphic representations under the general (Gluškov-type) product is concentrated in the celebrated classical criterion of A. A. Letichevsky, the well-known Krohn—Rhodes decomposition theorem is the basis for studying the cascade product of automata. The cascade product of automata is a general model of automata networks without feedback, and the theorem describes how to synthesize any finite state automaton using such a cascade, and, moreover, it describes the necessary irreducible components in detail. We shall derive the Krohn—Rhodes decomposition theorem from a sophisticated result called the holonomy decomposition theorem, which generally yields much more efficient decompositions than in the original proofs of the former. Characterization of homomorphic representation is important since one of the major tools for representations is homomorphism. While it is not too general, it is powerful enough. We study homomorphic representation in networks of automata with no feedback (cascade and quasi-direct products) and with low bounds on feedback length (αi-products for i ≤ 2) here. 3.1 Krohn—Rhodes and Holonomy Decomposition Theorems Theorem 3.1 (Krohn—Rhodes decomposition theorem). Given a finite automaton , let F be the flip-flop monoid (the smallest monoid with two right-zero elements); moreover, let G1, …, Gn denote all simple groups that divide the characteristic semigroup S. Then can be represented homomorphically by a cascade product of components from { F, G1,…, Gn}. Moreover, if is a nontrivial permutation automaton, then the factor F may be excluded. Conversely, let ℬ = ℬ1 × … × ℬn(X, (φ1, …, φn)) be a cascade product of automata which homomorphically represents the automaton If a subsemigroup S of the flip-flop monoid or a simple group S is a homomorphic image of a subsemigroup of S, then S is a homomorphic image of a subsemigroup of S(ℬt) for some component automaton ℬt (t ∈ {1, …, n}).