Semigroups package in GAP

In [ ]:
LoadPackage("Semigroups");;

The Semigroups package for GAP contains an external library called libsemigroups.

This library is called automatically from GAP whenever the appropriate questions are asked. Let's see the library in action.

We start by creating the Motzkin Monoid of degree 4. This is a bipartition semigroup, which has recently been of interest to researchers.

In [ ]:
M := MotzkinMonoid(4);
Size(M);

The Semigroups manual (http://gap-packages.github.io/Semigroups/doc/chap6.html) tells us that the Froidure--Pin algorithm can be used with semigroups that are enumerable. Furthermore, it tells us that libsemigroups is used if the semigroup in question is a semigroups of bipartitions. We first check that this is true:

In [ ]:
IsEnumerableSemigroupRep(M);
IsBipartitionSemigroup(M);

So, if we ask the appropriate questions, libsemigroups itself will be called. For example, it will be used when we ask for the semigroup's $\mathcal{D}$-classes:

In [ ]:
d := GreensDClasses(M);

We can see how these $\mathcal{D}$-classes fit together by displaying the semigroup's eggbox diagram:

In [ ]:
JupyterSplashDot(DotString(M));

We know that the Motzkin monoid has one $\mathcal{D}$-class for each rank, 0 to 4.

In [ ]:
List(d, class -> RankOfBipartition(Representative(class)));

Let's take elements of rank 1 and 2, and use them to generate a congruence.

In [ ]:
x := Random(d[5]);
y := Random(d[2]);
In [ ]:
cong := SemigroupCongruence(M, [x, y]);;

Calculating features of the congruence will also use the libsemigroups library, even taking advantage of parallelism to try different algorithms at the same time!

In [ ]:
NrCongruenceClasses(cong);
In [ ]:
IsReesCongruence(cong);

All these features are faster for using the library, and this has even made it possible to calculate entire congruence lattices in a reasonable amount of time.

In [ ]:
latt := LatticeOfCongruences(M);
In [ ]:
time;

We can even display this lattice:

In [ ]:
JupyterSplashDot(DotString(latt));

The lattice has an interesting structure, but it is not immediately obvious why it has the shape it does. This investigation led to a classification of the congruences of a variety of related monoids in the following research paper:

J. East, J. D. Mitchell, N. Ruškuc, and M. Torpey, Congruence lattices of finite diagram monoids, Advances in Mathematics, 333:931–1003, 2018, https://doi.org/10.1016/j.aim.2018.05.016.