The Krohn-Rhodes Decomposition Theorem (KRDT) is a central result in automata and semigroup theories: it states that any (deterministic) finite-state automaton can be disassembled into a collection of automata of two simple types, that can be arranged into a combination - cascade - that simulates the original automaton. The elementary building blocks of the decomposition are either resets or permutations. The full-fledged theorem features two orthogonal dimensions of complexity: the type and the number of building blocks appearing in the cascade, and a deep step in the proof is the characterization of the permutations appearing in the decomposition. This characterization implies, in the case of counter-free automata, that the resulting cascade contains no permutations. In this paper we start analysing KRDT for two compression-oriented classes of automata: (i) pathcoherent: state-ordered automata mapping state-intervals to state-intervals; (ii) Wheeler: a subclass of path-coherent automata whose order is the one induced by the co-lexicographic order of words. These classes were recently defined and studied and they turn out to be eficiently encodable and indexable. We prove that each automata in these classes can be decomposed as a cascade with a number of components which is linear in the number of states of the original automaton and, for the Wheeler class, we prove that only two-state resets are needed. Our line of reasoning avoids the necessity of using full KRDT and proves our results directly by a simple inductive argument.
One of the most fruitful, pervasive, and basic idea in mathematics is primal decomposition, where a complex mathematical structure is decomposed in a more or less structured collection of simpler components. Examples are the factorization of a number into prime numbers, the many matrix decomposition used in linear algebra, the Fourier decomposition of a periodic function, or the Jordan-Holder Decomposition Theorem for finite groups.
The Krohn-Rhodes Decomposition Theorem (KRDT), in general terms, falls into this category:
it is a method for decomposing a deterministic finite automaton into “simple” finite automata [
Finite deterministic automata (DFA) correspond, via their transition semigroups, to finite
semigroups and a cascade of DFAs correspond to a wreath product of semigroups. As a
consequence KRDT is also an unexpected major result in the theory of semigroups, an analogue of
the Jordan–Holder Theorem for finite groups (see [
The permutations appearing in the KRDT cascade of an automaton are (homomorphic images of) subgroups of the transition semigroup of the original automaton. This is in fact the part of the KRDT that is most dificult to prove, requiring a careful analysis for the permutations’ components. This is exploited for proving that the cascade decomposition of counter-free automata (that is automata without non-primitive cycles) is permutation-free, i.e. it contains only two-state resets. However, to the best of our knowledge, no proof of the decomposition in the counter-free case guarantees the linearity of the number of the two-state reset blocks 1.
In this paper we consider the KRDT for two classes of automata: path-coherent and Wheeler
automata. The first class comprises automata that are state-ordered in such a way that the
image of an interval of states, by any transition, is still an interval of states. The Wheeler class
(see [
We prove that for both path-coherent and Wheeler classes it is always possible to find a decomposition into a cascade made of a linear number of components. Moreover, the cascade whose existence we prove in the case of Wheeler automata is permutation-free and, contrary to the counter-free case, the proof is a simple induction, not requiring particular care for handling permutations.
The paper is organized as follows. Section 2 deals with notation and basic definitions. Section 3 introduces the path-coherent and Wheeler classes and prove some basic dependencies/independencies of the properties involved in their definitions. In section 4 we prove our main results on the existence of a cascade with a linear number of component for the aforementioned classes. Finally, section 5 is dedicated to conclusions and further works. The proofs that are not present in the body of the paper can be found in the Appendix.
The KRDT is a theorem on deterministic finite automata (DFAs), but initial and final states play
no role in its statement. Hence we start defining semiautomata, which are DFAs where initial
and final states are not specified. Moreover, the general KRDT theorem is stated for complete
deterministic automata, where transitions from any states are always defined for every letter.
1In [
A partial semiautomaton is a tuple = (, Σ, ) where: (i) is a finite set of states; (ii) Σ is the alphabet; (iii) : × Σ → is a partial function. In this paper, by a semiautomaton we always mean a partial semiautomaton. For any ∈ Σ, we denote by (− , ) the (possibly partial) function from to that maps in (, ), for each ∈ . Moreover, for any subset of states ⊆ and any symbol ∈ Σ, we denote by (, ) the set {′ ∈ | ′ = (, ) ∧ ∈ }. Since we will also introduce semiautomata = (, Σ, ) and = ( , Σ , ) where Σ = Σ and states in are subsets of – that is, ⊆ () –, we avoid ambiguity by always explicitly indicating the automaton, as in (, ) and (, ), so that it is clear whether is a state of or a subset of -states.
Finally, if (, ) does not belong to the domain of we write (, ) = ⊥, where ⊥ ̸∈ . More in general, for a partial function : → and an element ∈ we write () = ⊥ to denote that ∈/ dom( ). Clearly, a function can be defined only if all of its arguments are defined, thus we consider every function that has ⊥ as one of its arguments as undefined – e.g. (⊥) = ⊥ and (⊥, ) = (, ⊥) = ⊥ for all . Moreover, given two functions , : → , when we write ∀ ∈ () = () we always imply that () = ⊥ if and only if () = ⊥, that is, and have the same domain.
Definition 1. A transition ∈ Σ in a semiautomaton = (, Σ, ) is: 1) a reset if either a) there exists a state ∈ such that (, ) ̸= ⊥ implies (, ) = , for all ∈ ; or b) (, ) ̸= ⊥ implies (, ) = , for all ∈ — that is, (− , ) is the identity over its domain. 2) A permutation if it is not a reset and the function (− , ) is a permutation over its domain i.e. it is injective and maps its domain onto itself. A semiautomaton is a permutation-reset semiautomaton if all its transitions are permutations or resets. We say that is a reset semiautomaton if all its transitions are resets. We say that is a permutation automaton if all its transitions are permutations.
1 2 3 1 2 3 (a) The transition is a reset.
(b) The transition is a permutation.
Definition 2 (Homomorphic image). Let , be two semiautomata over the same alphabet Σ. We say that is an homomorphic image of if there is a surjective (total) function : → such that, for all ∈ and ∈ Σ,
( (, )) = ((), ).
A semiautomaton can be transformed into a language acceptor by fixing an initial state and a set of final states and setting, as usual, ℒ() = { ∈ (Σ)* | (, ) ∈ }. We say that a semiautomaton is as least as expressive as the semiautomaton if any language accepted by is also accepted by . The next lemma proves that if is a homomorphic image of then is at least as expressive as .
Lemma 1. If the semiautomaton is a homomorphic image of the semiautomaton and the language is accepted by , then is also accepted by .
We now introduce the operation we shall use in our decomposition results. Definition 3 (Cascade product). Let = ( , Σ, ) be a semiautomaton and = ( , × Σ, ) be a semiautomaton whose alphabet is the cartesian product of and Σ. The cascade product ∘ = (∘ , Σ, ∘ ) is the semiautomaton with set of states ∘ := × and transition function defined by
∘ ((, ), ) = ( (, ), (, (, ))).
Note that both and might be partial functions, thus we are implicitly requiring that ∘ ((, ), ) ̸= ⊥ if and only if (, ) ̸= ⊥ ∧ (, (, )) ̸= ⊥. (a) The automata and . The two links from Σ to and from (b) The cascade product ∘ beto indicate that, at each step, the automaton reads both the input tween and .
letter from Σ and the current state of the automaton .
Next, we state some basic results about cascades and homomorphic images. Since these results are normally stated and proved for complete semiautomata, we add the proofs for the more general partial case in the Appendix.
Proposition 2. 1) The cascade product is associative (see [
3 1 2 4 5 1 , 2 , 3
In this section we introduce the two classes we shall analyze in terms of KRDT. We first consider a related property.
Definition 4 (Input Consistency). A semiautomaton = (, Σ, ) is input consistent if (, ) = (, ) = implies = , whenever , , ∈ and ∈ Σ.
Path-coherence is a condition on graphs equipped with a total order over their nodes, that
requires intervals of states to be mapped by transitions into intervals of states. It was originally
introduced in the context of Wheeler graphs [
Definition 5 (Path Coherence). Let < be a total order over the set of states of a semiautomaton = (, Σ, ). Then (, <) is path-coherent if, for all ∈ Σ, the function (− , ) maps intervals in intervals. Equivalently, (, <) is path-coherent if, for all < ′ ∈ , ∈ Σ, and , , ∈ it holds that:
< < ∧ , ∈ ([, ′], ) → ∈ ([, ′], ).
Figure 3 shows an example of a path-coherent automaton on the alphabet Σ = {}.
Wheeler automata where first introduced in [
Definition 6 (Wheeler Axioms). Let = (, Σ, ) be a semiautomaton and let ≺ , < be
a total order over the alphabet Σ and a total order over the set of states , respectively.
Wheeler Axioms 1 (W1) and 2 (W2)2 are stated as follows (see [
A semiautomaton satisfying W1 and W2 is called a Wheeler semiautomaton. A Wheeler DFA (WDFA) is a DFA based on a Wheeler semiautomaton. Moreover, it is required that the initial 2The W2 axiom was introduced in [9] in the context of complete DFA to define the class of ordered DFAs. 1 2 3 4 state has no ingoing transitions and it is the minimum in the order <.
A Wheeler language is a language recognized by a WDFA 3.
If not specified otherwise we always assume that the set of states of a semiautomaton satisfying W1, W2, or path-coherence is = {1, ..., }, ordered as 1 < · · · < .
In general, a path-coherent semiautomaton may not satisfy W1, for any order of the alphabet. Consider for example the semiautomaton in Figure 4. Moreover, path-coherence and W1 do not imply W2. Consider for example the semiautomaton in Figure 5.
However, we do have the following dependencies.
Proposition 3. 1) If a semiautomaton satisfies both path-coherence and input consistency then there is an order ≺ over the alphabet Σ for which satisfies W1. In particular, a path-coherent, input consistent semiautomaton satisfying W2 is a Wheeler semiautomaton. 2) Any semiautomaton satisfying both W1 and W2 and such that any state has at least an incoming transition is path-coherent. 4. Krohn-Rhodes Decomposition for Path Coherent Graphs and
Wheeler Graphs The general KRDT states that each semiautomaton is a homomorphic image of a subsemiautomaton of a cascade product of two-state resets and permutation automata. Moreover, the cascade can be choosen in such a way that, for each permutation automaton in the cascade, the semigroup generated by the transitions of the automaton is a simple group which is an homomorphic image of subgroups of the semigroup generated by the -transitions. This implies that any counter-free automaton is a homomorphic image of a (sub-)semiautomaton4 of a cascade product of two-state resets. In this section we give a simpler proof of the decomposition for the path-coherent and Wheeler class. In the Wheeler case we also prove that the numbers of the blocks –two-state resets– is linear in the number of states of the original automaton.
We start by defining the first element of the cascade using the notion of admissible
decomposition (see [
Definition 7. A set of subsets of the set of states of a semiautomaton = (, Σ, ) is
said to be an admissible decomposition if:
3In [
1. ∪ = ; 2. for any ∈ Σ the image of an element of under (− , ) is contained in at least one element of :
∀ ∈ Σ, ∈ ∃′ ∈ (, ) ⊆ ′
Given an admissible decomposition of a semiautomata we can build a factor semiautomaton / over the same alphabet with / = and /(, ) = ′ where ′ ∈ is such that (, ) ⊆ ′ (if there is more than one, then choose one arbitrarily).5
Given a semiautomaton , the first element of a cascade decomposition for can be choosen
to be a factor of (see Zimmermann [10], Ginzburg [
In the following lemma and theorem we prove that, in case of path-coherent semiautomata, a particular choice for the decomposition of allows to use a simple induction for obtaining the full decomposition. Moreover, when applied to the Wheeler case, we shall see that this decomposition avoid altogether the use of permutations in the cascade.
Lemma 4. Let = (, Σ, , <) be a path-coherent semiautomaton with = || > 2. Then, there are a permutation-reset semiautomaton with || = 2 and a path-coherent semiautomaton with | | = − 1, such that is a homomorphic image of ∘ .
Proof. Consider the decomposition = {0, 1} of where
0 = {1, . . . , − 1}, 1 = {2, . . . , }.
We have either (, ) ⊆ 0 or (, ) ⊆ 1 (possibly both) for = 0, 1: it cannot be the case that both 1 and are in (, ) or, by path-coherence, we would have (, ) = {1, . . . , } which is not possible, being deterministic. In other words, the decomposition is admissible. Let = / = (, Σ, ) be the -factor of , defined as follows. The set of states is = {0, 1} and we define ( , ) = ⊥ if and only if ( , ) = ∅. If instead ( , ) ̸= ∅, then we define ( , ) = 0 if ( , ) ⊆ 0 (or, equivalently, if ̸∈ ( , )), whereas we define ( , ) = 1 if ( , ) ̸⊆ 0 (or, equivalently, ∈ ( , )) and hence ( , ) ⊆ 1. More succinctly, when ( , ) ̸= ⊥ we have ( , ) = (,), where (, ) is defined as (, ) = {︃0 if ∈/ ( , )
1 if ∈ ( , ) for all ∈ {0, 1} and ∈ Σ. Note that has only two states. Hence, a transition in can only be a (eventually partial) reset, the identity, or the permutation (0, ) = 1, (1, ) = 0. Therefore, is a permutation-reset automaton. 5For a complete semiautomaton , where the transition functions are total, a factor of is always a homomorphic image of . This is not always the case for partial automata.
Let = ( , × Σ, ) be the semiautomaton with set of states = {1, . . . , − 1} with = {(, 0), ( + 1, 1)} for 1 ≤ ≤ − 1 and transition function defined as follows, for = 1, . . . , − 1 and = 0, 1: Note that (︁ , ( , )︁) is well defined because it always hold (︁ , ( , ) ︁)
= (+,)− (,). 0 < ( + , ) − (, ) < . (1) function. 1, . . . , − 1:
can be proved in a similar manner.
Assuming, for contradiction, that ( + , ) − (, ) = , we must have both ( + , ) = and (, ) = 0. Note that + ∈ , for all = 1, . . . , − ( + , ) = it follows that ∈ ( , ). By definition of , this means that (, ) = 1: a contradiction. Therefore ( + , ) − (, ) ̸= . The fact that ( + , ) − (, ) ̸= 0 1 and = 0, 1, thus, from We prove that is a homomorphic image of the cascade ∘ . Consider the function : ∘ → defined by ( , ) = + .
The codomain of is because if = 1, . . . , − 1 and = 0, 1 then + ∈ {1, . . . , } = . Moreover, is surjective. Notice that, as opposed to the Krohn-Rhodes general case, is a total We prove that is a homomorphism from ∘ to , that is, for all = 0, 1 and = ( ∘ (( , ), )) = (( , ), ).
( ∘ (( , ), )) = ( ( , ), (, ( , )) = ( (,), (+,)− (,)) = ( + , ) − (, ) + (, ) = (( , ), ). follows that, for all ∈ {0, 1} and for all ∈ Σ,
To conclude the proof of the lemma we prove that the order 1 < · · · < − 1 makes path-coherent. Let [, ] be any interval, with 1 ≤ ≤ ≤ − 1. From equation (1) it (︁ [, ], ( , ) = {ℎ : ℎ + (, ) ∈ ([ + , + ], )}.
︁) hence also the set (︁
[, ], ( , )︁) is an interval.
By the hypothesis that is path-coherent it follows that ([ + , + ], ) is an interval, Theorem 5. Each path-coherent semiautomaton with ≥ 2 states is an homomorphic image of a cascade product of − 1 permutation-reset semiautomata, each one having exactly 2 states. Σ 0 ,
B2
Lemma 6. Let = (, Σ, , <) be a path-coherent semiautomaton satisfying Wheeler axiom 2 (W2). Then the construction of Lemma 4 provides a reset semiautomaton with || = 2 and a path-coherent semiautomaton with | | = − 1 still satisfying W2 such that is an homomorphic image of ∘ .
Theorem 7. Each path-coherent semiautomaton satisfying W2 with ≥ 2 states is the homomorphic image of a cascade product of − 1 reset semiautomata, each one having exactly 2 states.
Proof. The proof is the same as the one of Theorem 5, but we apply Lemma 6 instead of Lemma 4 everywhere.
Since Wheeler automata are path-coherent and satisfy W2, we get Corollary 7.1. Wheeler semiautomaton with ≥ 2 states is the homomorphic image of a cascade product of − 1 reset semiautomata, each one having exactly 2 states.
In this paper, we proved that path-coherent automata admit a linear-sized cascade decomposition into permutation-reset automata. Moreover we showed that, for the case of Wheeler automata, the cascade is permutation-free.
Some further natural questions arise. For example: • Can we find a linear-sized permutation-free decomposition for counter-free, path-coherent automata? • Is there a condition on the blocks of a cascade of resets in order for it to be a Wheeler automaton? • The Krohn-Rhodes complexity (KR-complexity) of a finite semigroup was introduced in [ 11] as a way of measuring the complexity of a cascade based on the least number of simple groups in it. Can the KR-complexity of path-coherent automata be efectively computed? If yes, what is the computational complexity of establishing their KR-complexity? • Are there eficient algorithms implementing Theorems 5 and 7? In addition to the above, more theoretical, issues one might wonder, on a more practical side, if the cascade decomposition can be used in the index production/optimization for a Wheeler automaton. [9] H.-J. Shyr, G. Thierrin, Ordered automata and associated languages, Tamkang J. Math 5 (1974) 9–20. [10] K. Zimmermann, On krohn-rhodes theory for semiautomata, CoRR abs/2010.16235 (2020).
URL: https://arxiv.org/abs/2010.16235. arXiv:2010.16235. [11] K. Krohn, J. Rhodes, Complexity of finite semigroups, Annals of Mathematics 88 (1968) 128–160. URL: http://www.jstor.org/stable/1970558.