{'fraction_non_alphanumeric': 0.06450599272792566, 'fraction_numerical': 0.009606320420164296, 'mean_word_length': 3.5069795670645356, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Krohn-Rhodes Theorem and Local Divisors

We give a new proof of the Krohn-Rhodes Theorem using local divisors. The proof provides nearly as good a decomposition in terms of size as the holonomy decomposition of Eilenberg, avoids induction on the size of the state set, and works exclusively with monoids with the base case of the induction being that of a group.


Introduction
The Krohn-Rhodes theorem is one of the fundamental results in finite semigroup theory. It asserts that a finite semigroup can be decomposed in a suitable sense into a wreath product of well-controlled finite simple groups and copies of a 3-element monoid, all of whose elements are idempotents. In addition to the elegance of the result, it has a number of important applications. For instance, it can be used as an induction scheme for proving Schützenberger's celebrated theorem on star-free languages [19], as well as generalizations due to Straubing [20].
There are a number of proofs of the theorem in the literature, see e.g. [5,6,8,9,11,12,13,16,18,21,22]. They tend to fall into three classes. The first class consists of fundamentally algebraic proofs. These proofs follow the line of proof of Krohn and Rhodes from [11]. They are based on induction on the size of the semigroup and rely on the non-obvious Trichotomy Lemma of Krohn and Rhodes which states that a finite semigroup is either left simple, cyclic or can be written as V ∪ T where V is a proper left ideal and T is a proper subsemigroup. The basis of the induction then becomes left simple semigroups and cyclic groups. These proofs use transformation semigroups only to adjoin constant maps and to keep the wreath product decompositions simpler. The state set of the transformation semigroup does not play a role in the induction. Lallement attempted an approach using exclusively monoids and avoiding transformation representations [12], but it had a flaw that can only be fixed by passing to transformation monoids [13].
The second type of proof uses transformation semigroups and performs an induction based on both semigroup size and state size. A typical example is the first of the two proofs of the Krohn-Rhodes theorem given by Eilenberg in [5]. The induction scheme relies on working with semigroups rather than monoids and essentially throws the Trichotomy Lemma into the states. These proofs tend to have a very large blow up in the state size. This approach also tends to be more technical (and less conceptual) than the algebraic approach above.
The third type of proof is based on Zeiger's method [22]. The definitive form of this approach is the holonomy theorem of Eilenberg [5]. This approach does not use induction at all. It provides instead a direct decomposition of a transformation semigroup into a wreath product of permutation groups with adjoined constant maps. This proof keeps better control over the state set and seems to give the most efficient decomposition. It is however the most technical argument.
Our proof is based on the notion of local divisors and encompasses features of all the above proofs. Like Lallement's proof, we avoid semigroups. Like the algebraic proofs, we avoid putting the state set into the induction scheme. However, we avoid the Trichotomy Lemma: the base case of our argument is that of groups. A local divisor is a monoidal generalization of a Schützenberger group; the latter appears implicitly in the holonomy proof.
The concept of a local divisor is an old one. In commutative algebra it has been introduced by Meyberg in 1972, see [7,14]. In finite semigroup theory and formal language the explicit definition of a local divisor was first given in [3]. It was used for proving that local temporal logics are expressively complete for partially commutative monoids [3]. In [4] it has been used for the same purpose in the context of finite and infinite words. A category generalization is being used by Costa and the third author in the context of symbolic dynamics (unpublished).
The key idea of local divisors is the following. If e is an idempotent of a monoid M , then eM e = eM ∩ M e is a subsemigroup which is a monoid with identity e. The group of units of eM e is the H-class of e. If M acts faithfully on the right of a set X, then eM e acts faithfully on the right of Xe. Schützenberger famously put a group structure on the H-class of an arbitrary element c ∈ M with c as the identity [1,18]. The local divisor construction extends this, by a multiplication •, to a monoid structure on cM ∩ M c whose group of units is the Schützenberger group. The monoid (cM ∩ M c, •) acts faithfully on Xc whenever M acts faithfully on X. We shall use the submonoid (cM c ∪ {c}, •) in this paper since it might have a smaller cardinality than cM ∩ M c.

Preliminaries
Apart from basic knowledge about monoids, we have tried to keep this paper selfcontained. In particular, we give a short introduction to transformation monoids in Section 2.1; and we present the wreath product construction and some of its basic prop-erties in Sections 2.2 through 2.4. These first few sections of the preliminaries are only slight adaptations of standard notions. Section 2.5 explains the notion of local divisor and its basic properties. It is a main tool used in our proof of the Krohn-Rhodes Theorem. Some standard proofs from this section are relegated to the appendix, Section 5.

Transformation monoids
A right action of a monoid M on a nonempty set X is a mapping X × M → X, written (x, m) → x · m, satisfying x · 1 = x and (x · m 1 ) · m 2 = x · (m 1 m 2 ) for all x ∈ X and m 1 , m 2 ∈ M . An action is therefore the same thing as a homomorphism of σ : M → T (X). Here and in the following T (X) denotes the monoid of all mappings from X to itself. It is a monoid by letting f g = h where h is defined by h(x) = g(f (x)) for f, g ∈ T (X) and x ∈ X. The action of M is faithful if σ is injective. Thus, the action is faithful, if each m ∈ M is uniquely determined by knowing x · m for all x ∈ X. The pair (X, M ) is called a transformation monoid. We do not require the action of transformation monoids to be faithful. Left actions are defined symmetrically.
The pair ({1} , M ) is a transformation monoid, but the action is not faithful unless M is trivial. The multiplication defines the faithful transformation monoid (M, M ). The pair (X, T (X)) is another faithful transformation monoid. The monoid T (X) acts on the right, which justifies to write xf instead of f (x). This suffix-notation turns out to be convenient in the following.
A morphism between transformation monoids (Y, N ) and (X, M ) is a pair (ϕ, ψ) where ϕ : Y → X is a mapping and ψ : N → M is a homomorphism such that ϕ(y · n) = ϕ(y) · ψ(n) for all y ∈ Y and n ∈ N . It is called surjective (resp. injective) if both mappings ϕ and ψ are surjective (resp. injective). It is an isomorphism, if ϕ and ψ are bijections. The transformation monoid (X, M ) is called finite if both X and M are finite.

Wreath products
Let (X, M ) and (Y, N ) be transformation monoids. For a moment let + denote the multiplication in M (which might be non-commutative). The functions M Y from Y to M form a monoid by componentwise multiplication. That is, f + g is defined by y(f + g) = yf + yg for y ∈ Y and f, g ∈ M Y . As N acts on Y on the right, it induces a left-action * of N on M Y defined by: With this definition we turn the set M Y × N into a monoid as a semidirect product denoted by M Y ⋊ N . The multiplication in M Y ⋊ N is given by: The multiplication is associative and we have (f, n) · (g, k) · (h, ℓ) = (f + (n * g) + (nk * h), nkℓ). The wreath product M ≀ (Y, N ) is this semidirect product. The monoid M ≀ (Y, N ) acts on X × Y by (x, y) · (f, n) = (x · yf, y · n). The resulting transformation monoid is denoted by (X, M ) ≀ (Y, N ). It is the wreath product of the transformation monoids (X, M ) and (Y, N ). If both (X, M ) and (Y, N ) are faithful, then (X, M )≀(Y, N ) is faithful, too. The wreath product of transformation monoids is associative up to isomorphism. This fact is well-known and stated as Lemma 2.1. The proof follows from a straightforward calculation based on the canonical bijection (M Y ×N ) Z → M Y ×Z ×N Z . Details can be found in the appendix, Section 5.
Remark 2.2. The number (of isomorphism classes) of finite transformation monoids is countable. The wreath product operation turns this countable set into an infinite monoid with ({1} , {1}) as a neutral element. According to a standard convention, we define the wreath product over an empty index set as the trivial transformation monoid ({1} , {1}).

Divisors
The divisor realation yields a partially defined surjection from Y to X where the domain is Y ′ ⊆ Y . However, the Krohn-Rhodes decomposition holds for totally defined surjections from Y to X. Thus, it is enough (and more convenient here) to restrict ourselves to totally defined surjections. For this we introduce the notion of strong division: We say that (X, M ) strongly divides (Y, N ), if there exists a submonoid N ′ of N and a surjective morphism from (Y, N ′ ) onto (X, M ). In this case we also say that (X, M ) is a strong divisor of (Y, N ) and we write (X, M ) ≺ (Y, N ). Every strong divisor is a divisor. This is why our notation (X, M ) ≺ (Y, N ) is "on the safe side". Another way to express (X, M ) ≺ (Y, N ) is that there exists a surjection ϕ : Y → X, a submonoid N ′ of N , and a surjective homomorphism ψ : The notion of divisor is closely related to Eilenberg's notion of a covering [5]. As we use here strong division, we restrict the definition of a covering to totally defined surjections: Let (X, M ) and (Y, N ) be transformation monoids and ϕ : Y → X be any surjective mapping. An element m ∈ N is called a cover of m ∈ M if ϕ(y) · m = ϕ(y · m) for all y ∈ Y . This defines a submonoid S ϕ of M × N as follows: The intuition is that (m, m) ∈ S ϕ says that m can "simulate" m in the sense that, instead of computing ϕ(y) · m in (X, M ) we can do the computation y · m in (Y, N ) and then apply ϕ. Let π i : M × N → M is the projection to the i-th component, i = 1, 2. We say that ϕ is a covering if π 1 (S ϕ ) = M , i.e., every m ∈ M has some cover.
The other way round, let R ϕ ⊆ S ϕ such that π 1 : R ϕ → M is surjective and π 2 : R ϕ → N is injective. Then we obtain a surjective homomorphism ψ from N ′ = π 2 (R ϕ ) onto M . It follows that the pair (ϕ, ψ) is a surjective morphism of (Y, N ′ ) onto (X, M ), and the transformation monoid (Y, N ′ ) embeds into (Y, N ).
The following proposition collects some useful properties and relations between coverings and strong divisors. In particular, for faithful transformation monoids the notions of covering and strong divisor become equivalent. 1. If M is generated by A ⊆ M and every a ∈ A has a cover a ∈ N , then ϕ : Y → X is a covering.
Proof. Assertion "1." is trivial, because a 1 · · · a m is a cover of a 1 · · · a m . To see assertion "2." it suffices to show that Example 2.4. We have the following divisions. • If N is a submonoid of M , then (X, N ) strongly divides (X, M ). N ). Indeed, let ϕ be the identity on X ×Y and let P ⊆ M Y contain all constant functions k m with yk m = m for all y ∈ Y . The subset P × N is a submonoid in the semidirect product M Y ⋊N . We see that Moreover, R ϕ satisfies the conditions that π 1 is surjective and π 2 is injective.
We conclude this section with a few more well-known facts. For proofs see again Section 5.
Remark 2.6. The set (of isomorphism classes) of finite transformation monoids is partially ordered by the divisor relation ≺. This ordering is compatible with the multiplication by the wreath product operation by Lemma 2.5. Hence this set is an infinite ordered monoid. N is a normal subgroup of G, then (G, G) ≺ (N, N ) ≀ (G/N, G/N ).
If G is finite but not simple, then (by induction) there exists a proper normal subgroup N of G such that N is smaller and G/N is non-trivial.
Corollary 2.8. For every finite group G, the transformation monoid (G, G) strongly divides a wreath product of the form Proof. This follows by induction using Proposition 2.7 and the classical formula |N | · |G/N | = |G| for subgroups N in G.

Constants
Let X be a set and let (as above) T (X) be the monoid of all mappings from X to itself. For x ∈ X we denote by x the constant function which maps all y ∈ X to x, i.e., yx = x for all x, y ∈ X. By X we denote the subset {x | x ∈ X} of T (X). This defines the faithful transformation monoid (X, U X ) with U X = X ∪ {1}. In semigroup theory, U n denotes the monoid resulting from adjoining an external identity to the n-element right zero semigroup {1, . . . , n}. In particular, U 1 is the two-element monoid. Note that if |X| = n ≥ 2, then U X ∼ = U n . On the other hand, U 1 , which is a submonoid of U 2 , is not of the form U X for any set X. Again, we conclude with a few more well-known results whose proofs can be found in Section 5. Lemma 2.9. Let (X, G) be a faithful transformation monoid such that G is a group.

Local divisors
Let M be a monoid and c ∈ M . We have the following inclusions of subsemigroups: Proof. We have xc • cm = x · cm for all x ∈ X. Thus, the faithful action of M on X determines cm ∈ M c . Remark 2.12. The assertion of Lemma 2.11 is one the main reasons why the tool of local divisors simplifies the proof of Theorem 4.1. In this proof we apply Lemma 2.11 to a faithful and finite transformation monoid (X, M ) where c ∈ M is not a unit. As a consequence, the action of c is not a permutation. Thus, |Xc| < |X|. The submonoid M c ∪ {1} of M acts on Xc, and it makes sense to say that (Xc, M c ∪ {1}) is smaller than (X, M ), because |Xc| < |X| and |M c ∪ {1}| ≤ |M |. However, (Xc, M c ∪ {1}) is never faithful! Indeed, let t, p ∈ N, p > 0 such that c t+p = c t . Choose t minimal with this property. Then t ≥ 1 since c is not a unit. We obtain xc · c t+p−1 = x · c t = xc · c t−1 .
The interested reader may notice that the surjective mapping ϕ : X → Xc, x → x · c yields (Xc, M c ) ≺ (X, M ). More precisely, the translation x → x · c defines a surjective morphism of (X, cM ∪ {1}) onto (Xc, M c ). This justifies saying that (Xc, M c ) is the local divisor of (X, M ) at c.

A decomposition using local divisors
The following result is the main contribution of this paper. Let A be a generating set for the monoid M and c ∈ A. It gives a decomposition of M into a wreath product of a local divisor M c and the submonoid N = A \ {c} generated by A \ {c}, but this decomposition involves constants. More precisely, if a transformation monoid (X, M ) is faithful, then by Lemma 2.11 the transformation monoid (Xc, M c ) is faithful, too; and so we may assume that the monoids M , M c , and N are submonoids of T (X), T (Xc), and T (X∪ N ), respectively. Here X∪ N denotes the disjoint union of X and N .
For a finite monoid M , by successively choosing A to be minimal and c ∈ A not to be a unit, we will end up at groups with constants, see Corollary 3.2.
We have to verify that this defines a division. For this, we have to show that every element in A ∪ X has a cover. A cover of x ∈ X is (f, x) ∈ W where f is arbitrary. Then for all (p, y) ∈ Xc × X ′ we have In the following, we always assume a ∈ A \ {c}. A cover of a is (k c , a) ∈ W and a cover of c is (f c , 1) ∈ W where yk c = c for all y ∈ X ′ yf c = y · c for y ∈ X nf c = cnc for n ∈ N First, let y ∈ X. Then Let now y = n ∈ N . Then Therefore, every element in A ∪ X has a cover in W which proves the claim.
Here |X i | > 1, every (X i , G i ) is faithful, and every G i is a group dividing M for all 1 ≤ i ≤ n and some n ≥ 0. Moreover, the number n can be chosen such that |G 1 | + · · · + |G n | < 2 |M | .
Proof. Since (X, M ) strongly divides the faithful transformation monoid (X ×M, M ), we may assume that (X, M ) is faithful. Since (X, M ) is faithful, we have (X, M ) ≺ (X, M ).
Thus it suffices to prove that if (X, M ) is a faithful transformation monoid, then where the X i , G i and n are as in the statement of the corollary. We proceed by induction on |M |. If |X| = 1, then M is trivial, too. We allow n = 0 in this case 1 . The assertion is trivial if M is a group. Otherwise, let A be a minimal generating set of M . Since M is not a group, there exists a generator c ∈ A which is not a unit. Let N = A \ {c} . We have |M c | < |M | and |N | < |M |; and we can apply Theorem 3.1. The result follows by induction. given by the Holonomy Theorem [5]. In particular, our decomposition agrees with the Holonomy decomposition in number of factors but our construction blows up the state sets.
On the other hand, the decomposition provided by the first proof of the Krohn-Rhodes theorem in Eilenberg [5] is much worse. The first step gives a decomposition ([n], T n ) ≺ ([n − 1], T n cT n ) ≀ (S n , S n ) and then decomposes ([n − 1], T n cT n ) into a wreath product of several copies of ([n − 1], T n−1 ), one for each of the n left ideals generated by rank n − 1 idempotents of T n . Our approach then seems to beat the previous inductive proofs.

The Krohn-Rhodes decomposition
The Krohn-Rhodes theorem [10] was the first global structure theorem in finite semigroup theory. Finite semigroups are too general to be classified up to isomorphisms. One needs to use a more global viewpoint to study them. Groups embed in a wreath product of their composition factors, which are certain simple group divisors. One might hope that one could embed a finite semigroup into a wreath product of composition factors of maximal subgroups and some relatively small semigroups with only trivial maximal subgroups. But this is impossible since whenever T (X) embeds into a semidirect product, it embeds in one of the factors. Thus one must introduce division and obtain a decomposition only up to division, which is what Krohn and Rhodes did. This philosophy for ever changed finite semigroup theory, leading to the current approach via varieties of finite semigroups. It also established the semidirect product as the key player in the study of semigroup theory. In summary the Krohn-Rhodes theory is the closest thing to a Jordan-Hölder theorem for semigroups. It is also a powerful inductive scheme for proving results about finite semigroups and regular languages, such as Schützenberger's theorem on star-free languages [19] (see for example [2,5,15,18]). For more philosophy on the Krohn-Rhodes theorem, the reader is referred to the book of Rhodes [17].
Proof. By Corollary 3.2, we can assume that (X, M ) = (X, G) for some finite group G and |X| > 1. By Lemma 2.9, this transformation monoid divides (X, U X ) ≀ (G, G). By Lemma 2.10, (X, U X ) divides a direct product of |X| − 1 copies of ({a, b} , U 2 ), which in turn divides a wreath product of |X| − 1 copies of ({a, b} , U 2 ) by Example 2.4. By Corollary 2.8, (G, G) divides a wreath product of simple groups (G 1 , G 1 ) ≀ · · · ≀ (G m , G m ) such that each G i divides G.
Our approach to prove Theorem 4.1 yields a simple way to bound the number of necessary wreath products by a singly exponential function:  (X∪ N, N ). Leaves are of the form (X i , G i ) where G i is a group. The distance of such a leaf to the root is bounded by |M | − |G i |. It also follows that we have: Now, we continue by making each of the (X i , G i ) to be inner nodes. Its left child is (X i , U X i ) its right child becomes (G i , G i ). This is the splitting according to Lemma 2.9. We continue on the group side (G i , G i ) until all leaves are of the form (G i , G i ) where G i is simple. Due to Corollary 2.8 the distance of all nodes to the root in this tree is still at most |M | − 1. Since it is a binary tree we obtain at most 2 |M |−1 leaves. In the worst case all leaves are now of the form (X i , U X i ) for which we need additional wreath products. However as we have |X i | < |X| + |M | 2 , we conclude with Lemma 2.10. Remark 4.3. For a moment let T be the ordered monoid of all (of isomorphism classes) of finite transformation monoids with the wreath product ≀ as multiplication and with strong division ≺ as ordering. Let P be the submonoid generated by the transformation monoids ({a, b} , U 2 ) and (G, G) where G is a non-trivial simple group. Theorem 4.1 can be rephrased by saying that for all (X, M ) ∈ T there is some (Y, K) ∈ P such that (X, M ) ≺ (Y, K). Corollary 4.2 says that we need less than |M | (|M | + |X|)2 |M | generators of P to express (Y, K).
Remark 4.4. The Holonomy Theorem of [5] provides a bound on the length of the decomposition in Corollary 4.2 that is exponential in |X| rather than |M |. It therefore is a tighter result since in practice |X| will be no bigger than |M | as (X, M ) will come from an automaton in which all states are accessible from the initial state. The improved bound is at the price of a more complicated proof.
Remark 4.5. It was proved by Krohn and Rhodes that the prime monoids are exactly the finite simple groups and the submonoids of U 2 , where a monoid M is prime if whenever it divides a semidirect product of two monoids, it divides one of the factors. The situation for transformation monoids is more delicate and can be found in Eilenberg [5]. There the more general definition of division is used and it is not clear whether the prime transformation monoids are the same with respect to strong division.

Appendix: Missing proofs
For convenience of the reader we repeat the statements where the proofs have previously been missing. The proof techniques are well-known and not meant to be original. It should however be noted that our divisor relation is based on totally defined surjective mappings rather than on partially defined functions. Thus, we pay attention to that.
Thus ϕ × ϕ ′ and ψ × ψ ′ : P × N → M Y ⋊ N define a strong division. Proof. Let h 1 , . . . , h n ∈ G be representatives of the cosets of N . By identifying cosets with their representatives, we can assume that G/N acts on {h 1 , . . . , h n }. For each g ∈ G let [g] = h i such that N g = N h i . We define ϕ : N × {h 1 , . . . , h n } → G by ϕ(n, h i ) = nh i . A cover of g ∈ G is (f g , Thus (G, G) strongly divides (N, N ) ≀ (G/N, G/N ). Lemma 2.9: Let (X, G) be a faithful transformation monoid such that G is a group. Then (X, G) ≺ (X, U X ) ≀ (G, G).