§ Krohn-Rhodes decomposition

We denote partial functions with XYX \rightharpoonup Y and total functions with XYX \rightarrow Y. A set XX equipped with a binary operator :X×XX\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:XX}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:XX;eX(x)=xe_x: X \rightarrow X; e_X(x) = x
  • A zero function θx:XX;θ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 SPf(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 Qa,bQ \equiv \\{ a, b \\} and the transformation semigroup SfαbS \equiv \\{ f \equiv \alpha \mapsto b \\}. Now the set SS is indeed a monoid with identity element as f:QQf: Q \rightarrow Q. however, f1Qf \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:TPf(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 ].
  • t1t2    xXt_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, t1t2    r(t1)r(t2)t_1 \neq t_2 \implies r(t_1) \neq r(t_2) where we define function equality extensionally: f=gx,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:SPf(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 sS\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 sxSXs_x \in S_X and sySYs_y \in S_Y. Then, if the following diagram commutes:
abxy \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 sxSXs_x \in S_X there exists a tySYt_y \in S_Y such that tt covers ss relative to ϕ\phi, then we say that ϕ:\phi: is a relation of automata .
  • If ϕ:QYQX\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 sxtxs_x \circ t_x is covered by tyqyt_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 tyYt_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 ϕ:YX\phi: Y \rightarrow X, then we define:
Σ{(s,t):tTY covers sSX} \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 XYX \wr Y. We begn with the set WSXQY×SYW \equiv S_X^{Q_Y} \times S_Y, where SXQY{f:QYSX}S_X^{Q_Y} \equiv \{ f : Q_Y \rightarrow S_X \}. The wreath product then becomes:
XY(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:QYSX,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 ryty(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:QYgSXf, g: Q_Yg \rightarrow S_X, and sy,tySYs_y, t_y \in S_Y. The result is going to be:
(f,sy)(g,ty)=(λqy.f(qy)g(qy),tyuy) (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 bab \leq a if either bab \subseteq a or there exists some sSs \in S such that bsab \subseteq sa, where s(a){s(ai):aia}s(a) \equiv \{ s(a_i) : a_i \in a\}. We can define an equivalence relation ab    abbaa \sim b \iff a \leq b \land b \leq a.

§ Note

ba    ba b \leq a \implies |b| \leq |a|, since bab \leq a means that bs(a)b \subseteq s(a). Note that ss is actually a function s:QQs: 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, bsaab \subseteq sa \subseteq a, and thus ba|b| \leq |a|. Similiarly, ab    aba \leq b \implies |a| \leq |b|. Therefore, bab \sim a means that b=a|b| = |a|.

§ Theorem

for all a,bQXa, b \in Q_X such that a ba ~ b such that bs(a)b \subseteq s(a), we show that b=s(a)b = s(a), and there exists a tSXt \in S_X such that a=t(b)a = t(b).

§ Proof

Since bs(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 tSXt \in S_X. To do this, first note that if the order of the permutation ss is nn, then t=sn1t = s^{n-1}, since ts=sn1s=1St \circ s = s^{n-1} \circ s = 1_S. Since the semigroup SS is closed under composition t=sn1t = s^{n-1} is in SS, since it is ss composed with itself (n1)(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 sSXs \in S_X
  • the set QQ
  • the empty set \emptyset
  • all the singleton sets {q}\{ q \} for all qQq \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 sSXs \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 sSXs \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:AZh: A \rightarrow \mathbb Z such that:
  1. h()=1h(\emptyset) = -1.
  2. h({q})=0qQh(\{ q \}) = 0 \forall q \in Q.
  3. ab    h(a)=h(b)a \sim b \implies h(a) = h(b) for all a,bAa, b \in A.
  4. b<a    h(b)<h(a)b < a \implies h(b) < h(a) for all a,bAa, b \in A.
The notation b<a(ba)¬(ab)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 aAa \in A such that a>1|a| > 1, we denote by BaB_a the set of all bAb \in A what are maximal subsets of aa. That is, if bBab \in B_a then bab \subsetneq a, and ∄c,bca\not \exists c, b \subsetneq c \subsetneq a. Equivalently, if there exists a cc such that bcab \subseteq c \subseteq a, then b=cb = c or b=ab = a. Note that we can assert that a=bBaba = \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 aAa \in A

Let us assume that there exists a sSs \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:AiA,Aia}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{sS: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 sSs \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 GaG_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 GaSG_a \prec S since GaG_a is a quotient of the sub-semigroup {ssS,as=a}\{ s | s \in S, as = a \}. (TODO: so what? why does this mean that it's \prec?)

§ Theorem:

If aba \sim b, then HaHbH_a \simeq H_b (similar subsets have isomorphic holonomy transition systems).

§ Proof:

Let us assume that aba \neq b. since aba \sim b, we have elements of the form s,s1Ss, s^{-1} \in S such that b=s(a)b = s(a), a=s1(b)a = s^{-1}(b). Recall that for baBab_a \in B_a is such that for a member gGag \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:
HiHa1Ha2Han 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 pQYp \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ϕHiYX \triangleleft_{\phi} \overline{H_i^\lor} \wr Y is a relational covering of rank i1i - 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:qyQY,h(ϕ(qy))=i}QY_i \equiv \{ q_y : q_y \in Q_Y, h(\phi(q_y)) = i \}
  • QY<{qy:qyQY,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 qyiQYiqy_i \in QY_i, we have that:
  • ϕ(qyi)=aj\phi(qy_i) = a_j for a unique 1jk1 \leq j \leq k.
  • We select elements u,uSu, \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ϕHiYX \triangleleft_{\phi} \wr \overline{H_i^\lor} Y using a relation:
  • ϕ[(Ba1Ba2Bak)×QY]×QX\phi \subseteq [(B_{a_1} \cup B_{a_2} \cup \dots B_{a_k})\times Q_Y ] \times Q_X

§ References