> < ^ From:

^ Subject:

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'.)

> < [top]