Dear Gap Forum,

we are pleased to announce a new package MONOID (Version 2.0).

This is a package of GAP functions for transformation monoids and
related objects. Below we attach a short description of the package
from the README file of the distribution.

We hope that the functions are useful and welcome any comments on the
package.

Steve Linton, Goetz Pfeiffer, Nik Ruskuc, Edmund Robertson.

##  1. The Package.  ########################################################

MONOID is a package of GAP functions for transformation monoids and related
objects. It contains functions that deal with

(finite) transformations,
transformation monoids,
finite binary relations, and
actions of monoids on various sorts of sets.

A *transformation* of degree $n$ is a map from the set $\{1, \dots, n\}$ to
itself. In MONOID a transformation is represented by its image list.

gap> a:= Transformation( [ 8, 6, 9, 6, 5, 4, 3, 1, 8, 3, 9, 11 ] );
Transformation( [ 8, 6, 9, 6, 5, 4, 3, 1, 8, 3, 9, 11 ] )
gap> 1^a;
8
gap> Image(a);
[ 1, 3, 4, 5, 6, 8, 9, 11 ]
gap> Rank(a);
8
gap> Degree(a);
12
gap> a^0;
Transformation( [ 1 .. 12 ] )

Transformations act from the right on $\{1, \dots, n\}$, their multiplication
is defined accordingly.

gap> b:= Transformation( [ 2, 1, 12, 5, 9, 9, 9, 2, 3, 10, 11, 7 ] );;
gap> a * b;
Transformation( [ 2, 9, 3, 9, 9, 5, 12, 2, 2, 12, 3, 11 ] )

A *transformation monoid* of degree $n$ is a monoid generated by
transformations of degree $n$.

gap> M:= Monoid(a, b); 
Monoid( [ Transformation( [ 8, 6, 9, 6, 5, 4, 3, 1, 8, 3, 9, 11 ] ), 
  Transformation( [ 2, 1, 12, 5, 9, 9, 9, 2, 3, 10, 11, 7 ] ) ] )
gap> Size(M);
84253

MONOID provides functions that determine the size of a transformation monoid
$M$, can list the elements of $M$ or decide membership of any transformation
of degree $n$ in $M$. Moreover, the Green class structure of $M$ can be
determined.

gap> Length(DClasses(M));
267

A *finite binary relation* of degree $n$ is a graph with vertex set $\{1,
\dots, n\}$. In MONOID such a relation is represented by its list of
successors.

gap> d:= Relation( [ [ ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] );
Relation( [ [  ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] )

Relations can be multiplied, checked for properties like reflexive,
symmetric, transitive, and closures can be formed. Relations of degree $n$
can be used to generate a monoid.

The *action* of a transformation monoid on $\{1, \dots, n\}$ induces actions
on tuples, subsets, ... which can be used to build new transformation
monoids from given ones.

gap> orb:= StrongOrbit(M, [1,2,3], Size, OnSets);
[ [ 1, 2, 3 ], [ 1, 2, 12 ], [ 1, 2, 7 ], [ 1, 2, 9 ] ]
gap> act:= ActionWithZero(M, orb, OnSets);
Monoid( [ Transformation( [ 5, 5, 5, 5, 5 ] ), 
  Transformation( [ 2, 3, 4, 1, 5 ] ) ] )
gap> Size(act);
5

(For the precise meaning of the commands in the above example we refer to the
MONOID manual.) The concept of monoid actions can be used to turn a monoid
of binary relations into a transformation monoid.

##  3. Where to get it.  ####################################################

The MONOID package is distributed under the terms and conditions of the GAP
copyright. It is available as 'gzip'ed 'tar' file (size 80k) via anonymous
'ftp' from the 'incoming' directory of GAPs 'ftp' servers, in particular at

'ftp-gap.dcs.st-and.ac.uk' (University of St Andrews, Scotland):
get /pub/gap/incoming/monoid-2.0.tgz

and at

'schmidt.ucg.ie' (University College Galway, Ireland):
get /pub/goetz/gap/monoid-2.0.tgz

(for mirror sites see GAPs home page 'http://www-gap.dcs.st-and.ac.uk/~gap'.)