A transformation monoid is a monoid of transformations of *n* points (see
chapter Transformations). These monoids occur for example in the
theory of finite state automata and as the results of enumerations of
finitely presented monoids. In the theory of semigroups and monoids they
ply to some extend the role that is taken by permutation groups in group
theory. In fact, there are close relations between permutation groups
and transformation monoids. One of these relations is manifested by the
Schützenberger group of an element of a transformation monoid,
which is represented as a permutation group rather than a group of
transformations. Another relation which is used by most functions that
deal with transformation monoids is the fact that a transformation monoid
can be efficiently described in terms of several permutation groups (for
details see LPRR1 and LPRR2).

This chapter describes the functions that deal with transformation monoids.

The chapter starts with the description of the function that tests whether or not a given object is a transformation monoid (see IsTransMonoid). Then there is the function that determines the degree of a transformation monoid (see Degree of a Transformation Monoid).

There are a function to construct the full transformation monoid of
degree *n* (see FullTransMonoid) and a function to construct the monoid
of all partial transformations of degree *n* (see PartialTransMonoid).

Then there are a function that determines all images of a transformation monoid (see ImagesTransMonoid) and a function that determines all kernels of a transformation monoid (see KernelsTransMonoid).

Because each transformation monoid is a domain all set theoretic functions can be applied to it (see chapter "Domains" and Set Functions for Transformation Monoids). Also because a transformation monoid is after all a monoid all monoid functions can be applied to it (see chapter Monoids and Semigroups and Monoid Functions for Transformation Monoids).

Next the functions that determine Green classes in transformation monoids are described (see H Classes for Transformation Monoids, R Classes for Transformation Monoids, L Classes for Transformation Monoids, and D Classes for Transformation Monoids).

Finally, there is a section about how a transformation monoid is
displayed (see Display a Transformation Monoid). The last section in
this chapter describes how transformation monoids are represented as
records in **GAP3** (see Transformation Monoid Records).

The functions described here are in the file `"monotran.g"`

.

- IsTransMonoid
- Degree of a Transformation Monoid
- FullTransMonoid
- PartialTransMonoid
- ImagesTransMonoid
- KernelsTransMonoid
- Set Functions for Transformation Monoids
- Monoid Functions for Transformation Monoids
- SchutzenbergerGroup for Transformation Monoids
- H Classes for Transformation Monoids
- R Classes for Transformation Monoids
- L Classes for Transformation Monoids
- D Classes for Transformation Monoids
- Display a Transformation Monoid
- Transformation Monoid Records

`IsTransMonoid( `

`obj` )

`IsTransMonoid`

returns `true`

if the object `obj`, which may be an
object of an arbitrary type, is a transformation monoid, and `false`

otherwise. It will signal an error if `obj` is an unbound variable.

gap> IsTransMonoid( Monoid( [ Transformation( [ 1, 2, 1 ] ) ] ) ); true gap> IsTransMonoid( Group( (1,2), (1,2,3,4) ) ); false gap> IsTransMonoid( [ 1, 2, 1 ] ); false

`Degree( `

`M` )

`Degree`

returns the degree of a transformation monoid `M`, which is the
common degree of all the generators of `M`.

gap> Degree( Monoid( Transformation( [ 1, 2, 1 ] ) ) ); 3

The **degree** of a transformation monoid is the number of points it acts
upon.

`FullTransMonoid( `

`n` )

`FullTransMonoid`

returns the full transformation monoid of degree `n`.

gap> M:= FullTransMonoid( 8 ); Monoid( [ Transformation( [ 2, 1, 3, 4, 5, 6, 7, 8 ] ), Transformation( [ 8, 1, 2, 3, 4, 5, 6, 7 ] ), Transformation( [ 2, 2, 3, 4, 5, 6, 7, 8 ] ) ] ) gap> Size( M ); 16777216

The **full transformation monoid** of degree *n* is the monoid of all
transformations of degree *n*.

`PartialTransMonoid( `

`n` )

`PartialTransMonoid`

returns the monoid of partial transformations of
degree `n`.

gap> M:= PartialTransMonoid( 8 ); Monoid( [ Transformation( [ 2, 1, 3, 4, 5, 6, 7, 8, 9 ] ), Transformation( [ 8, 1, 2, 3, 4, 5, 6, 7, 9 ] ), Transformation( [ 9, 2, 3, 4, 5, 6, 7, 8, 9 ] ), Transformation( [ 2, 2, 3, 4, 5, 6, 7, 8, 9 ] ) ] ) gap> Size( M ); 1000000000

A **partial transformation** of degree *n* is a mapping from *{1, ...,
n}* to itself where every point *i ∈ {1, ..., n}* has at most one
image. Here the undefined point is represented by *n+1*.

`ImagesTransMonoid( `

`M` )

`ImagesTransMonoid`

returns the set of images of all elements of the
transformation monoid `M` (see Image of a Transformation).

gap> M:= Monoid( Transformation( [ 1, 4, 4, 2 ] ), > Transformation( [ 2, 4, 4, 4 ] ) );; gap> ImagesTransMonoid(M); [ [ 1, 2, 3, 4 ], [ 1, 2, 4 ], [ 2 ], [ 2, 4 ], [ 4 ] ]

`KernelsTransMonoid( `

`M` )

`KernelsTransMonoid`

returns the set of kernels of all elements of the
transformation monoid `M` (see Kernel of a Transformation).

gap> M:= Monoid( [ Transformation( [ 1, 4, 4, 2 ] ), > Transformation( [ 2, 4, 4, 4 ] ) ] );; gap> KernelsTransMonoid(M); [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 1 ], [ 2, 3 ], [ 4 ] ], [ [ 1 ], [ 2, 3, 4 ] ], [ [ 1, 2, 3, 4 ] ] ]

All set theoretic functions described in chapter "Domains" are also applicable to transformation monoids. This section describes which functions are implemented specially for transformation monoids. Functions not mentioned here are handled by the default methods described in the respective sections of chapter "Domains".

`Size`

calls `RClasses`

(see RClasses), if necessary, and returns the
sum of the sizes of all *R* classes of `M`.

gap> Size( Monoid( Transformation( [ 1, 2, 1 ] ) ) ); 2

`Elements`

calls `RClasses`

(see RClasses) if necessary, and returns
the union of the elements of all *R* classes of `M`.

gap> Elements( Monoid( Transformation( [ 1, 2, 1 ] ) ) ); [ Transformation( [ 1, 2, 1 ] ), Transformation( [ 1 .. 3 ] ) ]

The membership test of elements of transformation monoids first checks
whether `obj` is a transformation in the first place (see
IsTransformation) and if so whether the degree of `obj` (see Degree of
a Transformation) coincides with the degree of `M` (see Degree of a
Transformation Monoid). Then the image and the kernel of `obj` is used
to locate the possible *R* class of `obj` in `M` and the membership test
is delegated to that *R* class (see Set Functions for Green Classes).

gap> M:= Monoid( Transformation( [ 1, 2, 1 ] ) );; gap> (1,2,3) in M; false gap> Transformation( [1, 2, 1 ] ) in M; true gap> Transformation( [ 1, 2, 1, 4 ] ) in M; false

All functions described in chapter Monoids and Semigroups can be applied to transformation monoids.

Green classes are special subsets of a transformation monoid. In
particular, they are domains so all set theoretic functions for domains
(see chapter "Domains") can be applied to Green classes. This is
described in Set Functions for Green Classes. Single Green classes of
a transformation monoid are constructed by the functions `RClass`

(see
RClass and R Classes for Transformation Monoids), `LClass`

(see
LClass and L Classes for Transformation Monoids), `DClass`

(see
DClass and D Classes for Transformation Monoids), and `HClass`

(see
HClass and H Classes for Transformation Monoids). The list of all
Green classes of a given type in a transformation monoid is constructed
by the functions `RClasses`

(see RClasses), `LClasses`

(see
LClasses), `DClasses`

(see DClasses), and `HClasses`

(see
HClasses).

`SchutzenbergerGroup( `

`M`, `s` )

`SchutzenbergerGroup( `

`class` )

`SchutzenbergerGroup`

returns the Schützenberger group of the
element `s` in the transformation monoid `M` as a permutation group on
the image of `s`.

In the second form `SchutzenbergerGroup`

returns the
Schützenberger group of the Green class `class` of a
transformation monoid, where `class` is either an H class, an R class or
a D class. The Schützenberger group of an H class `class` is
the same as the Schützenberger group of `class`. The
Schützenberger group of an R class `class` is the generalised
right Schützenberger group of the representative of `class` and
the Schützenberger group of an L class `class` is the
generalised left Schützenberger group of the representative of
`class`. Note that the Schützenberger of an R class is only
unique up to conjugation.

In addition to the usual components of an H class record, the record
representing the H class `hClass` of `s` in a transformation monoid can
have the following components. They are created by the function
`SchutzenbergerGroup`

(see SchutzenbergerGroup) which is called
whenever the size, the list of elements of `hClass`, or a membership test
in `hClass` is asked for.

`schutzenbergerGroup`

:

set to the Schützenberger group of`hClass`as a permutation group on the set of images of

(see SchutzenbergerGroup for Transformation Monoids).`hClass`.representative

`R`

:

the R class of`hClass`.representative.

`L`

:

the L class of`hClass`.representative.

The following functions have a special implementation in terms of these components.

returns the size of the H class `hClass`. This function calls
`SchutzenbergerGroup`

and determines the size of `hClass` as the size of
the resulting group.

returns the set of elements of the H class `hClass`. This function calls
`SchutzenbergerGroup`

and determines the set of elements of `hClass` as
the set of elements of the resulting group multiplied by the
representative of `hClass`.

returns `true`

if `x` is an element of the H class `hClass` and `false`

otherwise. This function calls `SchutzenbergerGroup`

and tests whether
the quotient of the representative of `hClass` and `x` (see
PermLeftQuoTrans) is in the resulting group.

In addition to the usual components of an R class record, the record
representing the R class `rClass` of `s` in a transformation monoid can
have the following components. They are created by the function
`SchutzenbergerGroup`

(see SchutzenbergerGroup) which is called
whenever the size, the list of elements of `rClass`, or a membership test
in `rClass` is asked for.

`schutzenbergerGroup`

:

set to the Schützenberger group of`rClass`as a permutation group on the set of images of

(see SchutzenbergerGroup for Transformation Monoids).`rClass`.representative

`images`

:

is the list of different image sets occurring in the R class`rClass`. The first entry in this list is the image set of

.`rClass`.representative

`rMults`

:

is a list of permutations such that the product of the representative of`rClass`and the inverse of the*i*th entry in the list yields an element of`rClass`whose image set is the*i*th entry in the list

.`rClass`.images

The following functions have a special implementation in terms of these components.

returns the size of the R class `rClass`. This function calls
`SchutzenbergerGroup`

and determines the size of `rClass` as the size of
the resulting group times the length of the list

.
`rClass`.images

returns the set of elements of the R class `rClass`. This function calls
`SchutzenbergerGroup`

and determines the set of elements of `rClass` as
the set of elements of the resulting group multiplied by the
representative of `rClass` and each single permutation in the list

.
`rClass`.rMults

returns `true`

if `x` is an element of the R class `rClass` and `false`

otherwise. This function calls `SchutzenbergerGroup`

and tests whether
the quotient of the representative of `rClass` and

(see PermLeftQuoTrans) is in the resulting group
where `x` *
`rClass`.rMults[`i`]`i` is the position of the image set of `x` in

.
`rClass`.images

returns the list of H classes contained in the R class `rClass`.

In addition to the usual components of an L class record, the record
representing the L class `lClass` of `s` in a transformation monoid can
have the following components. They are created by the function
`SchutzenbergerGroup`

(see SchutzenbergerGroup) which is called
whenever the size, the list of elements of `lClass`, or a membership test
in `lClass` is asked for.

`schutzenbergerGroup`

:

set to the Schützenberger group of`lClass`as a permutation group on the set of images of

(see SchutzenbergerGroup for Transformation Monoids).`lClass`.representative

`kernels`

:

is the list of different kernels occurring in the L class`lClass`. The first entry in this list is the kernel of

.`rClass`.representative

`lMults`

:

is a list of binary relations such that the product of the inverse of the*i*th entry in the list and the representative of`rClass`yields an element of`rClass`whose kernel is the*i*th entry in the list

.`rClass`.kernels

The following functions have a special implementation in terms of these components.

returns the size of the L class `lClass`. This function calls
`SchutzenbergerGroup`

and determines the size of `lClass` as the size of
the resulting group times the length of the list

.
`lClass`.kernels

returns the set of elements of the L class `lClass`. This function calls
`SchutzenbergerGroup`

and determines the set of elements of `lClass` as
the set of elements of the resulting group premultiplied by the
representative of `lClass` and each single binary relation in the list

.
`lClass`.lMults

returns `true`

if `x` is an element of the L class `lClass` and `false`

otherwise. This function calls `SchutzenbergerGroup`

and tests whether
the quotient of the representative of `lClass` and

(see PermLeftQuoTrans) is in the resulting group where `lClass`.lMults[`i`]
* `x``i` is
the position of the kernel of `x` in

.
`lClass`.kernels

returns the list of H classes contained in the L class `lClass`.

In addition to the usual components of a D class record, the record
representing the D class `dClass` of `s` in a transformation monoid can
have the following components. They are created by the function
`SchutzenbergerGroup`

(see SchutzenbergerGroup) which is called
whenever the size, the list of elements of `dClass`, or a membership test
in `dClass` is asked for.

`schutzenbergerGroup`

:

set to the Schützenberger group of`dClass`as a permutation group on the set of images of

(see SchutzenbergerGroup for Transformation Monoids).`dClass`.representative

`H`

:

set to the H class of

.`dClass`.representative

`L`

:

set to the L class of

.`dClass`.representative

`R`

:

set to the R class of

.`dClass`.representative

`rCosets`

:

contains a list of (right) coset representatives of the Schützenberger group of`dClass`in the Schützenberger group of the R class

.`dClass`.R

The following functions have a special implementation in terms of these components.

returns the size of the D class `dClass`. This function calls
`SchutzenbergerGroup`

and determines the size of `dClass` in terms of the
sizes of the resulting group and the Schützenberger groups of
the R class

and the L class `dClass`.R

.
`dClass`.L

returns the set of elements of the D class `dClass`. This function calls
`SchutzenbergerGroup`

and determines the set of elements of `dClass` as
the union of cosets of the Schützenberger group of the L class

determined through the multipliers `dClass`.L

and
`dClass`.rCosets

.
`dClass`.R.rMults

returns `true`

if `x` is an element of the D class `dClass` and `false`

otherwise. This function calls `SchutzenbergerGroup`

and tests whether
the quotient of the representative of `dClass` and a suitable translate
of `x` can be found in one of the cosets of the Schützenberger
group of the L class

determined by the list
`dClass`.L

.
`dClass`.rCosets

returns the list of H classes contained in the D class `dClass`.

returns the list of L classes contained in the D class `dClass`.

returns the list of R classes contained in the D class `dClass`.

`Display( `

`M` )

`Display`

displays the Green class structure of the transformation monoid
`M`. Each D class is displayed as a single item on a line according to
its rank. A D class displayed as

`[`

`a`.`b`.`d`]

is a regular D class with a Schützenberger group of size `a`,
consisting of `b` L classes, or `d` R classes. A D class displayed as

`{`

`a`.`b`x`c`.`d`x`e`}

is a nonregular D class with a Schützenberger group of size
`a`, consisting of *<b> × c* L classes (of which

gap> M:= Monoid( Transformation( [ 7, 7, 1, 1, 5, 6, 5, 5 ] ), > Transformation( [ 3, 8, 3, 7, 4, 6, 4, 5 ] ) );; gap> Size( M ); 27 gap> Display( M ); Rank 8: [1.1.1] Rank 6: {1.1x1.1x1} Rank 5: {1.1x1.1x1} Rank 4: {1.1x1.1x1} [2.1.1] Rank 3: {1.1x1.4x1} [1.3.4] Rank 2: [1.5.1]

In addition to the usual components of a monoid record (see Monoid
Records and Semigroup Records) the record representing a transformation
monoid `M` has a component

`isTransMonoid`

:

which is always set to`true`

.

Moreover, such a record will (after a while) acquire the following components.

`orbitClasses`

:

a list of R classes of`M`such that every orbit of image sets is represented exactly once.

`images`

:

the list of lists where`images[`

is the list of all different image sets of size`k`]`k`of the elements of`M`.

`imagePos`

:

stores the relation between`orbitClasses`

and`images`

. The image set`images[`

occurs in the orbit of the R class with index`k`][`l`]`imagePos[`

in the list`k`][`l`]`orbitClasses`

.

`rClassReps`

:

a list of lists, where`rClassReps[`

contains the complete list of representatives of the R classes with the same image orbit as the R class`l`]`orbitClasses[`

.`l`]

`lTrans`

:

a list of lists, where`lTrans[`

is a transformation`l`][`k`]*α*such that`lTrans[`

is an element of the R class`l`][`k`] * rClassReps[`l`][`k`]`orbitClasses[`

.`l`]

`kernels`

:

a list of lists, where`kernels[`

is the common kernel of the elements in the R class of`l`][`k`]`rClassReps[`

.`l`][`k`]

gap3-jm

24 Apr 2021