§ Krohn-Rhodes decomposition
We denote partial functions with and total functions
A set equipped with a binary operator
which is closed and associative
is a semigroup.
§ Partial function semigroup
For a ground set , the set of partial functions
along with function composition forms a semigroup. This is in fact stronger
than a semigroup. There exists:
- An identify function
- A zero function , where by we mean that it is undefined .
§ Transformation semigroup(TS)
Let be a set. Let be a sub-semigroup of .
Then the semigroup is called as the
transformation semigroup (X) of states .
We call as a transformation monoid if contains .
- The elements of are called states of
- while the elements of are called actions of .
- The set itself is called as the underlying set of .
- For a fixed transformation semigroup , we will write and to refer to its states and actions.
§ Subtlety of being a transformation monoid.
There is some subttlety here. Just because is a monoid does not mean that
it that is a transformation monoid . It must have the identity element of
to be called a transformation monoid. For example, consider the
set and the transformation semigroup .
Now the set is indeed a monoid with identity element as .
however, , andh ence, is a not a transformation monoid .
§ Examples of transformation semigroups
- . The semigroup with the empty transformation.
- , the semigroup with no transformations.
§ Semigroup action
We sometimes wish to represent a semigroup using an action/transformation semigroup
on a ground set . So, given some semigroup that needs to be represented,
if we can find a morphism ( for representation)
Put more simply, where we define
function equality extensionally: .
- . [ is a semigroup morphism ].
- such that . [Faithfulness ].
§ Embedding actions into the transformation semigroup
We often wish to represent some semigroup as the transformation semigroup
of some set of states . We can achieve this by proving a morphism:
Then, we can treat elements of as elements of .
- that is faithful.
§ Completion of a transformation semigroup
Given a transformation semigroup we can complete it
by adding a new sink state , and then converting all partial
functions in to total functions that transition to . We have that
We denote the completion as .
Let and be transformation
semigroups. Let be a relation. Let
and . Then, if the following diagram commutes:
If then we say that covers relative to .
We imagine the lying above , being projected down by .
If a fixed , for all there exists a such that
covers relative to , then we say that is a
relation of automata .
- If is surjective, then we say that is a relational covering and write: .
- If is both surjective and partial, then we say that is a covering and write:
- If , we say that dominates , or covers , or divides .
§ Checking coverings and generating subsets
We note that for a given covering , if is covered by
and is covered by , then is covered by .
Thus, to check if is covered by , we simply need to check if
some generating subset of is covered by .
§ Checking coverings of representations
Let us assume we have a representation of a transformation semigroup
given with a semigroup , a transformation semigroup
, and a representation that is
Now, to check that is covered by another , it suffices to check that
there exists a for each such that is
covered by this .
§ Companion relation
Given a relation , then we define:
Recall compositions of elements are covered by a composition
of their coverings. Hence, if , then
. thus, is a subsemigroup of .
We can regard as the graph of a relation .
This will be called as companion relation of .
§ Wreath products
Let and . We're going to define a large
We begn with the set , where
The wreath product then becomes:
with the action of on an element of being defined as:
it's a "follow the types" sort of definition, where we edit the right component
as since that's all we can do. In the case of
the left component, we have a , and we need to produce another element
in , so we "must use ". The only way to use is to feed it
a . This forces us into the above definition.
§ Composition of wreath products
To show that its closed under composition, let's consider
with , and . The result is
going to be:
§ Equivalences of subsets of states
Let be a transition system. Given subsets ,
we shall write if either or there exists some
such that , where . We can
define an equivalence relation .
means that . Note that is actually a
function , 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, , and thus .
Similiarly, . Therefore, means
for all such that
such that , we show that , and there exists
a such that .
Since and , .
Therefore is a permutation. Hence, is invertible and there exists
an inverse permutation such that . We now need to show that
. To do this, first note that if the order of the permutation
is , then , since .
Since the semigroup is closed under composition is in ,
since it is composed with itself times.
§ Subset families of interest
We will be interest in a family of subsets of called , of the form:
In the above set, we have and as defined above.
We note that the set is closed under the action of all .
For example, the empty set is taken to the empty set. All singleton
sets are taken to other singleton sets. For the full set , we add
the sets for all .
- all sets of the form for all
- the set
- the empty set
- all the singleton sets for all .
§ Height function
A height function for a transition system is a function
The notation .
(3) + (4) imply that two elements of the same height are either equivalent
- for all .
- for all .
§ Pavings and bricks
for such that , we denote by the set of all
what are maximal subsets of . That is, if then ,
and . Equivalently, if there
exists a such that , then or .
Note that we can assert that . This is because
contains all the singletons of . so we can begin by writing as
a union of singletons, and then merging elements of into larger elements
of , terminating when we cannot merge any more elements of .
- The set is called as the paving of .
- The elements of are called as the bricks of .
§ Group of permutations for
Let us assume that there exists a such that . Let
be the set of all elements in contained in :
Recall that the set was closed under the action of all , and hence,
since is a permutation of , this naturally extends into a
permutation of : . Now note that this induces a permutation
of the set . This creates a transition system:
We have already shown how if defines a permutation of some set
by its action, then its inverse also exists in . So, this means that
is in fact a transition group that acts on .
It might turn out that . However, if ,
then as stated above, is a group.
We will call such a transition group a generalized transition group , since
either or is a group.
Now, the generalized transition group is called as the
holonomy transition system of , and the group is called as
the holonomy group of .
We have that since is a quotient of the sub-semigroup
. (TODO: so what? why does this mean that it's ?)
If , then (similar subsets have isomorphic holonomy transition systems).
Let us assume that . since , we have elements
of the form such that , .
Recall that for is such that for a member ,
. must have the element [TODO! ]
§ Holonomy decomposition
Let be a transition system and let be a height
function for , such that . For a fixed ,
let be the representatives of equivalence classes of
elements of of height equal to . We define:
§ Inductive hypothesis for coverings
We will say a relational covering is of rank
with respect to a given height function if relates states in
to subsets of states in that are members of and have rank at most i.
Formally, for each , we have that and .
We prove that if is a relational covering of rank ,
then is a relational covering
of rank .
The proof is a proof by induction.
§ Base case:
Start with the relational covering with ,
and the cover . Clearly, this has rank since the height
of is , and is inded a covering, since the only transition
that can make (stay at the same state) is simulated by any transition
in [TODO: is this really the argument? ]
For induction, assume is a relational covering of rank
with respect to some height function . and
. We define
We know that contains elements of height exactly . Let
be representatives of sets of of height in . Thus, for each ,
we have that:
We will show how to establish a relational covering:
- for a unique .
- We select elements such that and .
- using a relation: