§ Krohn-Rhodes decomposition

We denote partial functions with X⇀YX \rightharpoonup Y and total functions with X→YX \rightarrow Y. A set XX equipped with a binary operator ⋆:X×X→X\star: X \times X \rightarrow X which is closed and associative is a semigroup.

§ Partial function semigroup

For a ground set XX, the set of partial functions Pf(X)≡{f:X⇀X}Pf(X) \equiv \{ f: X \rightharpoonup X \} along with function composition forms a semigroup. This is in fact stronger than a semigroup. There exists:
  • An identify function ex:X→X;eX(x)=xe_x: X \rightarrow X; e_X(x) = x
  • A zero function θx:X⇀X;θx(x)=undef\theta_x: X \rightharpoonup X; \theta_x(x) = \texttt{undef}, where by undef\texttt{undef} we mean that it is undefined .

§ Transformation semigroup(TS)

Let QQ be a set. Let S⊆Pf(Q)S \subseteq Pf(Q) be a sub-semigroup of Pf(Q)Pf(Q). Then the semigroup X≡(Q,S)X \equiv (Q, S) is called as the transformation semigroup (X) of states QQ.
  • The elements of QQ are called states of XX
  • while the elements of SS are called actions of XX.
  • The set QQ itself is called as the underlying set of XX.
  • For a fixed transformation semigroup XX, we will write QXQ_X and SXS_Xto refer to its states and actions.
We call X≡(Q,S)X \equiv (Q, S) as a transformation monoid if SS contains 1Q(q)=q1_Q(q) = q.

§ Subtlety of being a transformation monoid.

There is some subttlety here. Just because SS is a monoid does not mean that it that is a transformation monoid . It must have the identity element of Pf(Q)Pf(Q) to be called a transformation monoid. For example, consider the set Q≡a,bQ \equiv \\{ a, b \\} and the transformation semigroup S≡f≡α↦bS \equiv \\{ f \equiv \alpha \mapsto b \\}. Now the set SS is indeed a monoid with identity element as f:Q→Qf: Q \rightarrow Q. however, f≠1Qf \neq 1_Q , andh ence, SS is a not a transformation monoid .

§ Examples of transformation semigroups

  1. (X,{θ(x)=undef})(X, \{ \theta(x) = \texttt{undef} \}). The semigroup with the empty transformation.
  2. (X,∅)(X, \emptyset), the semigroup with no transformations.

§ Semigroup action

We sometimes wish to represent a semigroup using an action/transformation semigroup on a ground set XX. So, given some semigroup (T,×)(T, \times) that needs to be represented, if we can find a morphism r:T→Pf(X)r: T \rightarrow Pf(X) ( rr for representation) such that:
  • r(t1+t2)=r(t1)∘r(t2) r(t_1 + t_2) = r(t_1) \circ r(t_2). [ rr is a semigroup morphism ].
  • t1≠t2  ⟹  ∃x∈Xt_1 \neq t_2 \implies \exists x \in X such that r(t1)(x)≠r(t2)(x)r(t_1)(x) \neq r(t_2)(x). [Faithfulness ].
Put more simply, t1≠t2  ⟹  r(t1)≠r(t2)t_1 \neq t_2 \implies r(t_1) \neq r(t_2) where we define function equality extensionally: f=g≡∀x,f(x)=g(x)f = g \equiv \forall x, f(x) = g(x).

§ Embedding actions into the transformation semigroup

We often wish to represent some semigroup SS as the transformation semigroup of some set of states QQ. We can achieve this by proving a morphism:
  • r:S→Pf(Q)r: S \rightarrow Pf(Q) that is faithful.
Then, we can treat elements of SS as elements of Pf(Q)Pf(Q).

§ Completion of a transformation semigroup

Given a transformation semigroup X≡(Q,S)X \equiv (Q, S) we can complete it by adding a new sink state ⊥\bot, and then converting all partial functions in SS to total functions that transition to ⊥\bot. We have that ⊥⋅s=s⋅⊥ ∀s∈S\bot \cdot s = s \cdot \bot ~ \forall s \in S. We denote the completion as Xc≡(Qc,Sc)X^c \equiv (Q^c, S^c).

§ Coverings

Let X≡(QX,SX)X \equiv (Q_X, S_X) and Y≡(QY,SY)Y \equiv (Q_Y, S_Y) be transformation semigroups. Let ϕ⊆QY×QX\phi \subseteq Q_Y \times Q_X be a relation. Let sx∈SXs_x \in S_X and sy∈SYs_y \in S_Y. Then, if the following diagram commutes:
a→b↓↓x→y \begin{array}{ccc} a & \rightarrow & b \\ \downarrow & & \downarrow \\ x & \rightarrow & y \\ \end{array}
If sx(ϕ(qy))=ϕ(ty(qy))s_x(\phi(q_y)) = \phi(t_y(q_y)) then we say that tyt_y covers sxs_x relative to ϕ\phi. We imagine the tyt_y lying above sxs_x, being projected down by ϕ\phi. If a fixed ϕ\phi, for all sx∈SXs_x \in S_X there exists a ty∈SYt_y \in S_Y such that tt covers ss relative to ϕ\phi, then we say that ϕ:\phi: is a relation of automata .
  • If ϕ:QY→QX\phi: Q_Y \rightarrow Q_X is surjective, then we say that ϕ\phi is a relational covering and write: X◃ϕYX \triangleleft_{\phi} Y.
  • If ϕ⊆QY×QX\phi \subseteq Q_Y \times Q_X is both surjective and partial, then we say that ϕ\phi is a covering and write: X≺ϕYX \prec_\phi Y
  • If X≺ϕYX \prec_\phi Y, we say that YY dominates XX, or YY covers XX, or XX divides YY.

§ Checking coverings and generating subsets

We note that for a given covering ϕ\phi, if sxs_x is covered by tyt_y and pxp_x is covered by qyq_y, then sx∘txs_x \circ t_x is covered by ty∘qyt_y \circ q_y. Thus, to check if XX is covered by YY, we simply need to check if some generating subset of XX is covered by YY.

§ Checking coverings of representations

Let us assume we have a representation of a transformation semigroup given with a semigroup Σ\Sigma, a transformation semigroup X≡(QX,SX)X \equiv (Q_X, S_X), and a representation r:Σ→SXr: \Sigma \rightarrow S_X that is faithful. Now, to check that XX is covered by another YY, it suffices to check that there exists a ty∈Yt_y \in Y for each σ∈X\sigma \in X such that r(σ)r(\sigma) is covered by this tyt_y.

§ Companion relation

Given a relation ϕ:Y→X\phi: Y \rightarrow X, then we define:
Σ≡{(s,t):t∈TY covers s∈SX} \Sigma \equiv \{ (s, t) : t \in T_Y \text{ covers } s \in S_X \}
Recall compositions of elements are covered by a composition of their coverings. Hence, if (s,t),(s′,t′)∈Σ(s, t), (s', t') \in \Sigma, then (ss′,tt′)∈Σ(ss', tt') \in \Sigma. thus, Σ\Sigma is a subsemigroup of SX×SYS_X \times S_Y. We can regard Σ\Sigma as the graph of a relation ϕ′⊆QY×QX\phi' \subseteq Q_Y \times Q_X. This will be called as companion relation of ϕ\phi.

§ Wreath products

Let X≡(QX,SX)X \equiv (Q_X, S_X) and Y≡(QY,SY)Y \equiv (Q_Y, S_Y). We're going to define a large product X≀YX \wr Y. We begn with the set W≡SXQY×SYW \equiv S_X^{Q_Y} \times S_Y, where SXQY≡{f:QY→SX}S_X^{Q_Y} \equiv \{ f : Q_Y \rightarrow S_X \}. The wreath product then becomes:
X≀Y≡(QX×QY,W) X \wr Y \equiv (Q_X \times Q_Y, W)
with the action of WW on an element of QX×QYQ_X \times Q_Y being defined as:
(f:QY→SX,sy:SY)(qx:QX,qY:QY)≡(f(qy)(qx),sy(qy)) (f : Q_Y \rightarrow S_X, s_y : S_Y) (q_x : Q_X, q_Y : Q_Y) \equiv ( f(q_y)(q_x) , s_y (q_y))
it's a "follow the types" sort of definition, where we edit the right component as ry↦ty(ry)r_y \mapsto t_y(r_y) since that's all we can do. In the case of the left component, we have a qxq_x, and we need to produce another element in QXQ_X, so we "must use ff". The only way to use ff is to feed it a tyt_y. This forces us into the above definition.

§ Composition of wreath products

To show that its closed under composition, let's consider (f,sy),(g,ty)∈W(f, s_y), (g, t_y) \in W with f,g:QYg→SXf, g: Q_Yg \rightarrow S_X, and sy,ty∈SYs_y, t_y \in S_Y. The result is going to be:
(f,sy)(g,ty)=(λqy.f(qy)∘g(qy),ty∘uy) (f, s_y) (g, t_y) = (\lambda q_y. f(q_y) \circ g(q_y), t_y \circ u_y)

§ Equivalences of subsets of states

Let X=(Q,S)X = (Q, S) be a transition system. Given subsets (a,b,⊆Q)(a, b, \subseteq Q), we shall write b≤ab \leq a if either b⊆ab \subseteq a or there exists some s∈Ss \in S such that b⊆sab \subseteq sa, where s(a)≡{s(ai):ai∈a}s(a) \equiv \{ s(a_i) : a_i \in a\}. We can define an equivalence relation a∼b  ⟺  a≤b∧b≤aa \sim b \iff a \leq b \land b \leq a.

§ Note

b≤a  ⟹  ∣b∣≤∣a∣ b \leq a \implies |b| \leq |a|, since b≤ab \leq a means that b⊆s(a)b \subseteq s(a). Note that ss is actually a function s:Q→Qs: Q \rightarrow Q, and a function mapped over a set can only ever decrease the number of elements in a set, since a function can only xglomp elements together; it can never break an element apart into two. Hence, b⊆sa⊆ab \subseteq sa \subseteq a, and thus ∣b∣≤∣a∣|b| \leq |a|. Similiarly, a≤b  ⟹  ∣a∣≤∣b∣a \leq b \implies |a| \leq |b|. Therefore, b∼ab \sim a means that ∣b∣=∣a∣|b| = |a|.

§ Theorem

for all a,b∈QXa, b \in Q_X such that a ba ~ b such that b⊆s(a)b \subseteq s(a), we show that b=s(a)b = s(a), and there exists a t∈SXt \in S_X such that a=t(b)a = t(b).

§ Proof

Since b⊆s(a)⊆ab \subseteq s(a) \subseteq a and ∣b∣=∣a∣|b| = |a|, b=s(a)b = s(a). Therefore ss is a permutation. Hence, ss is invertible and there exists an inverse permutation tt such that a=t(b)a = t(b). We now need to show that t∈SXt \in S_X. To do this, first note that if the order of the permutation ss is nn, then t=sn−1t = s^{n-1}, since t∘s=sn−1∘s=1St \circ s = s^{n-1} \circ s = 1_S. Since the semigroup SS is closed under composition t=sn−1t = s^{n-1} is in SS, since it is ss composed with itself (n−1)(n-1) times.

§ Subset families of interest

We will be interest in a family of subsets of QXQ_X called AA, of the form:
  • all sets of the form s(Q)s(Q) for all s∈SXs \in S_X
  • the set QQ
  • the empty set ∅\emptyset
  • all the singleton sets {q}\{ q \} for all q∈Qq \in Q.
In the above set, we have ≤\leq and ∼\sim as defined above. We note that the set AA is closed under the action of all s∈SXs \in S_X. For example, the empty set is taken to the empty set. All singleton sets are taken to other singleton sets. For the full set QQ, we add the sets s(Q)s(Q) for all s∈SXs \in S_X.

§ Height function

A height function for a transition system X≡(QX,SX)X \equiv (Q_X, S_X) is a function h:A→Zh: A \rightarrow \mathbb Z such that:
  1. h(∅)=−1h(\emptyset) = -1.
  2. h({q})=0∀q∈Qh(\{ q \}) = 0 \forall q \in Q.
  3. a∼b  ⟹  h(a)=h(b)a \sim b \implies h(a) = h(b) for all a,b∈Aa, b \in A.
  4. b<a  ⟹  h(b)<h(a)b < a \implies h(b) < h(a) for all a,b∈Aa, b \in A.
The notation b<a≡(b≤a)∧¬(a≤b)b < a \equiv (b \leq a) \land \lnot (a \leq b). (3) + (4) imply that two elements of the same height are either equivalent or incomparable.

§ Pavings and bricks

for a∈Aa \in A such that ∣a∣>1|a| > 1, we denote by BaB_a the set of all b∈Ab \in A what are maximal subsets of aa. That is, if b∈Bab \in B_a then b⊊ab \subsetneq a, and ∄c,b⊊c⊊a\not \exists c, b \subsetneq c \subsetneq a. Equivalently, if there exists a cc such that b⊆c⊆ab \subseteq c \subseteq a, then b=cb = c or b=ab = a. Note that we can assert that a=∪b∈Baba = \cup_{b \in B_a} b. This is because BaB_a contains all the singletons of QXQ_X. so we can begin by writing aa as a union of singletons, and then merging elements of BaB_a into larger elements of BB, terminating when we cannot merge any more elements of BaB_a.
  • The set BaB_a is called as the paving of aa.
  • The elements of BaB_a are called as the bricks of aa.

§ Group of permutations for a∈Aa \in A

Let us assume that there exists a s∈Ss \in S such that s(a)=as(a) = a. Let AaA_a be the set of all elements in AA contained in aa: Aa={Ai:Ai∈A,Ai⊆a}A_a = \{ A_i : A_i \in A, A_i \subseteq a \}. Recall that the set AA was closed under the action of all ss, and hence, since ss is a permutation of aa, this naturally extends into a permutation of AaA_a: sAa=Aas A_a = A_a. Now note that this induces a permutation of the set BaB_a. This creates a transition system:
Ga≡{s∈S:sa=a}Ha≡(Ba,Ga) \begin{aligned} &G_a \equiv \{ s \in S : s a = a \} \\ &H_a \equiv (B_a, G_a) \\ \end{aligned}
We have already shown how if s∈Ss \in S defines a permutation of some set XX by its action, then its inverse also exists in SS. So, this means that GaG_a is in fact a transition group that acts on BaB_a. It might turn out that Ga=∅G_a = \emptyset. However, if Ga≠∅G_a \neq \emptyset, then as stated above, GaG_a is a group. We will call such a transition group a generalized transition group , since either Ga=∅G_a = \emptyset or GaG_a is a group. Now, the generalized transition group HaH_a is called as the holonomy transition system of aa, and the group GaG_a is called as the holonomy group of aa. We have that Ga≺SG_a \prec S since GaG_a is a quotient of the sub-semigroup {s∣s∈S,as=a}\{ s | s \in S, as = a \}. (TODO: so what? why does this mean that it's ≺\prec?)

§ Theorem:

If a∼ba \sim b, then Ha≃HbH_a \simeq H_b (similar subsets have isomorphic holonomy transition systems).

§ Proof:

Let us assume that a≠ba \neq b. since a∼ba \sim b, we have elements of the form s,s−1∈Ss, s^{-1} \in S such that b=s(a)b = s(a), a=s−1(b)a = s^{-1}(b). Recall that for ba∈Bab_a \in B_a is such that for a member g∈Gag \in G_a, g(ba)=bag(b_a) = b_a. BbB_b must have the element s(ba)s(b_a) [TODO! ]

§ Holonomy decomposition

Let X≡(Q,S)X \equiv (Q, S) be a transition system and let hh be a height function for XX, such that h(Q)>0h(Q) > 0. For a fixed ii, let a1,a2,…aka_1, a_2, \dots a_k be the representatives of equivalence classes of elements of AA of height equal to ii. We define:
Hi∨≡Ha1∨Ha2⋯∨Han H_i^\lor \equiv H_{a_1} \lor H_{a_2} \dots \lor H_{a_n}

§ Inductive hypothesis for coverings

We will say a relational covering X◃ϕYX \triangleleft_{\phi} Y is of rank ii with respect to a given height function hh if ϕ\phi relates states in YY to subsets of states in xx that are members of AA and have rank at most i. Formally, for each p∈QYp \in Q_Y, we have that ϕ(p)∈A\phi(p) \in A and h(ϕ(p))≤ih(\phi(p)) \leq i. We prove that if X◃ϕYX \triangleleft_{\phi} Y is a relational covering of rank ii, then X◃ϕHi∨‾≀YX \triangleleft_{\phi} \overline{H_i^\lor} \wr Y is a relational covering of rank i−1i - 1. The proof is a proof by induction.

§ Base case:

Start with the relational covering with QY={0},SY={id}Q_Y = \{ 0 \}, S_Y = \{ id \}, and the cover ϕ(0)=QX\phi(0) = Q_X. Clearly, this has rank nn since the height of QXQ_X is nn, and ϕ\phi is inded a covering, since the only transition that YY can make (stay at the same state) is simulated by any transition in SXS_X [TODO: is this really the argument? ] For induction, assume X◃ϕYX \triangleleft_{\phi} Y is a relational covering of rank ii with respect to some height function hh. X≡(QX,SX)X\equiv (Q_X, S_X) and Y≡(QY,SY)Y \equiv (Q_Y, S_Y). We define
  • QYi≡{qy:qy∈QY,h(ϕ(qy))=i}QY_i \equiv \{ q_y : q_y \in Q_Y, h(\phi(q_y)) = i \}
  • QY<≡{qy:qy∈QY,h(ϕ(qy))<i}QY_< \equiv \{ q_y : q_y \in Q_Y, h(\phi(q_y)) < i \}
We know that AA contains elements of height exactly ii. Let a1,a2,…aka_1, a_2, \dots a_k be representatives of sets of of height ii in AA. Thus, for each qyi∈QYiqy_i \in QY_i, we have that:
  • ϕ(qyi)=aj\phi(qy_i) = a_j for a unique 1≤j≤k1 \leq j \leq k.
  • We select elements u,u‾∈Su, \overline{u} \in S such that u(ϕ(qyi))=aju(\phi(qy_i)) = a_jand u‾(aj)=ϕ(qyi)\overline{u}(a_j) = \phi(qy_i).
We will show how to establish a relational covering:
  • X◃ϕ≀Hi∨‾YX \triangleleft_{\phi} \wr \overline{H_i^\lor} Y using a relation:
  • ϕ⊆[(Ba1∪Ba2∪…Bak)×QY]×QX\phi \subseteq [(B_{a_1} \cup B_{a_2} \cup \dots B_{a_k})\times Q_Y ] \times Q_X

§ References