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( 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
78.2 Degree of a Transformation Monoid
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 ] ] ]
78.7 Set Functions for Transformation Monoids
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
78.8 Monoid Functions for Transformation Monoids
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).
78.9 SchutzenbergerGroup for Transformation Monoids
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.
78.10 H Classes for Transformation Monoids
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:hClass.representative (see SchutzenbergerGroup for
Transformation Monoids).
R:hClass.representative.
L: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.
78.11 R Classes for Transformation Monoids
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:rClass.representative (see SchutzenbergerGroup for
Transformation Monoids).
images:rClass.representative.
rMults: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 x *
rClass.rMults[i] (see PermLeftQuoTrans) is in the resulting group
where 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.
78.12 L Classes for Transformation Monoids
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:lClass.representative (see SchutzenbergerGroup for
Transformation Monoids).
kernels:rClass.representative.
lMults: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 lClass.lMults[i]
* x (see PermLeftQuoTrans) is in the resulting group where i is
the position of the kernel of x in lClass.kernels.
returns the list of H classes contained in the L class lClass.
78.13 D Classes for Transformation Monoids
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:dClass.representative (see SchutzenbergerGroup for
Transformation Monoids).
H:dClass.representative.
L:dClass.representative.
R:dClass.representative.
rCosets: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 dClass.R and the L class 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
dClass.L determined through the multipliers dClass.rCosets and
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 dClass.L determined by the list
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.
78.14 Display a Transformation Monoid
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.bxc.dxe}
is a nonregular D class with a Schützenberger group of size a, consisting of <b> × c L classes (of which c have the same kernel), or <d> × e R classes (of which e have the same image).
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]
78.15 Transformation Monoid Records
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:true.
Moreover, such a record will (after a while) acquire the following components.
orbitClasses:
images:images[ k ] is the list of all
different image sets of size k of the elements of M.
imagePos:orbitClasses and images. The
image set images[k][l] occurs in the orbit of the R class
with index imagePos[k][l] in the list orbitClasses.
rClassReps:rClassReps[l] contains the complete
list of representatives of the R classes with the same image
orbit as the R class orbitClasses[l].
lTrans:lTrans[l][k] is a transformation
α such that lTrans[l][k] * rClassReps[l][k] is
an element of the R class orbitClasses[l].
kernels:kernels[l][k] is the common kernel
of the elements in the R class of rClassReps[l][k].
gap3-jm