6
Creating semigroups and monoids

In this chapter we describe the various ways that semigroups and monoids can be created in **Semigroups**, and the options that are available at the time of creation.

Computing the Green's structure of a semigroup is fundamental to almost every other algorithm for semigroups. There are two fundamental algorithms in the **Semigroups** package for computing the Green's structure of a semigroup, which are described in the next two subsections.

The first type of fundamental algorithms are those described in [EENMP19], which when applied to a semigroup with relatively large subgroups are the most efficient methods in the **Semigroups** package. For example, the complexity of computing, say, the size of a transformation semigroup that happens to be a group, is the same as the complexity of the Schreier-Sims Algorithm (polynomial in the number of points acted on by the transformations) for a permutation group.

In theory, these algorithms can be applied to compute any subsemigroup of a regular semigroup; but so far in the **Semigroups** package they are only implemented for semigroups of: transformations (see Reference: Transformations), partial permutations (see Reference: Partial permutations), bipartitions (see Chapter 3), subsemigroups of regular Rees 0-matrix semigroups over permutation groups (see Chapter Reference: Rees Matrix Semigroups), and matrices over a finite field (see Section 5.4).

We refer to semigroups to which the algorithms in [EENMP19] can be applied as *acting semigroups*, and such semigroups belong to the category `IsActingSemigroup`

(6.1-3).

If you know *a priori* that the semigroup you want to compute is large and \(\mathscr{J}\)-trivial, then you can disable the special methods for acting semigroups when you create the semigroups; see Section 6.3 for more details.

It is harder for the acting semigroup algorithms to compute Green's \(\mathscr{L}\)- and \(\mathscr{H}\)-classes of a transformation semigroup and the methods used to compute with Green's \(\mathscr{R}\)- and \(\mathscr{D}\)-classes are the most efficient in **Semigroups**. Thus, if you are computing with a transformation semigroup, wherever possible, it is advisable to use the commands relating to Green's \(\mathscr{R}\)- or \(\mathscr{D}\)-classes rather than those relating to Green's \(\mathscr{L}\)- or \(\mathscr{H}\)-classes. No such difficulties are present when computing with the other types of acting semigroups in **Semigroups**.

There are methods in **Semigroups** for computing individual Green's classes of an acting semigroup without computing the entire data structure of the underlying semigroup; see `GreensRClassOfElementNC`

(13.1-3). It is also possible to compute the \(\mathscr{R}\)-classes, the number of elements and test membership in a semigroup without computing all the elements; see, for example, `GreensRClasses`

(13.1-4), `RClassReps`

(13.1-5), `IteratorOfRClassReps`

(13.2-1), `IteratorOfRClasses`

(13.2-2), or `NrRClasses`

(13.1-9). This may be useful if you want to study a very large semigroup where computing all the elements of the semigroup is not feasible.

The second fundamental algorithm is the Froidure-Pin Algorithm [FP97]. The **Semigroups** package contains two implementations of the Froidure-Pin Algorithm: one in the libsemigroups C++ library and the other within the **Semigroups** package kernel module.

Both implementations outperform the algorithms for acting semigroups when applied to semigroups with small (trivial) subgroups. This method is also used to determine the structure of a semigroup when the algorithms described in [EENMP19] do not apply. It is possible to specify which methods should be applied to a given semigroup; see Section 6.3.

We refer to semigroups to which the Froidure-Pin Algorithm can be applied in **GAP** as *enumerable semigroups*, and such semigroups should belong to the representation `IsEnumerableSemigroupRep`

(6.1-4). Every acting semigroup in **Semigroups** is an enumerable semigroup since the acting semigroup data structure does not readily admit computation of certain properties or attributes.

Currently, the libsemigroups implementation of the Froidure-Pin Algorithm can be applied to semigroups consisting of the following types of elements: transformations (see Reference: Transformations), partial permutations (see Reference: Partial permutations), bipartitions (see Chapter 3), partitioned binary relations (see Chapter 4) as defined in [MM13]; and matrices over the following semirings:

the

*Boolean semiring*\(\{0, 1\}\) where \(0 + 0 = 0\), \(0 + 1 = 1 + 1 = 1 + 0 = 1\), and \(1\cdot 0 = 0 \cdot 0 = 0 \cdot 1 = 0\)finite fields;

the

*max-plus semiring*of natural numbers and negative infinity \(\mathbb{N}\cup \{-\infty\}\) with operations max and plus;the

*min-plus semiring*of natural numbers and infinity \(\mathbb{N}\cup \{\infty\}\) with operations min and plus;the

*tropical max-plus semiring*\(\{-\infty, 0, 1, \ldots, t\}\) for some threshold \(t\) with operations max and plus;the

*tropical min-plus semiring*\(\{0, 1, \ldots, t, \infty\}\) for some threshold \(t\) with operations min and plus;the semiring \(\mathbb{N}_{t, p} = \{0, 1, \ldots, t, t + 1, \ldots, t + p - 1\}\) for some threshold \(t\) and period \(p\) under addition and multiplication modulo the congruence \(t = t + p\).

(see Chapter 5).

The version of the Froidure-Pin Algorithm [FP97] written in C within the **Semigroups** package kernel module can be used to compute any other semigroup in **GAP** with representation `IsEnumerableSemigroupRep`

(6.1-4). In theory, any finite semigroup can be computed using this algorithm. However, the condition that the semigroup has representation `IsEnumerableSemigroupRep`

(6.1-4) is imposed to avoid this method being used when it is inappropriate (such as for finitely presented semigroups which happen to be finite). If implementing a new type of semigroup in **GAP**, then simply do

InstallTrueMethod(IsGeneratorsOfEnumerableSemigroup, MyNewSemigroupType);

to make your new semigroup type `MyNewSemigroupType`

use this version of the Froidure-Pin Algorithm.

Mostly due to the way that **GAP** handles memory, this implementation is approximately 4 times slower than the implementation in libsemigroups. This version of the Froidure-Pin Algorithm is included because it applies to a wider class of semigroups than those currently implemented in libsemigroups and it is more straightforward to extend the classes of semigroup to which it applies. From a usage perspective there is no difference between those enumerable semigroups that are representable in libsemigroups and those that are not, except that the latter has superior performance.

`‣ IsActingSemigroup` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

Every acting semigroup, as defined in Section 6.1-1, belongs to this category.

gap> S := Semigroup(Transformation([1, 3, 2]));; gap> IsActingSemigroup(S); true gap> IsEnumerableSemigroupRep(S); true gap> S := FreeSemigroup(3);; gap> IsActingSemigroup(S); false

`‣ IsEnumerableSemigroupRep` ( obj ) | ( representation ) |

Returns: `true`

or `false`

.

Every semigroup with this representation can have the Froidure-Pin algorithm applied to it; see Section 6.1-2 for more details.

Basic operations for enumerable semigroups are `AsListCanonical`

(14.1-1), `EnumeratorCanonical`

(14.1-1), `IteratorCanonical`

(14.1-1), `PositionCanonical`

(14.1-2), `Enumerate`

(14.1-3), and `IsFullyEnumerated`

(14.1-4).

gap> S := Semigroup(Transformation([1, 3, 2]));; gap> IsEnumerableSemigroupRep(S); true gap> S := FreeSemigroup(3);; gap> IsEnumerableSemigroupRep(S); false

`‣ InverseMonoidByGenerators` ( coll[, opts] ) | ( operation ) |

`‣ InverseSemigroupByGenerators` ( coll[, opts] ) | ( operation ) |

Returns: An inverse monoid or semigroup.

If `coll` is a collection satisfying `IsGeneratorsOfInverseSemigroup`

, then `InverseMonoidByGenerators`

and `InverseSemigroupByGenerators`

return the inverse monoid and semigroup generated by `coll`, respectively.

If present, the optional second argument `opts` should be a record containing the values of the options for the semigroup being created, as described in Section 6.3.

When using any of the functions:

`InverseSemigroup`

(Reference: InverseSemigroup),`InverseMonoid`

(Reference: InverseMonoid),`Semigroup`

(Reference: Semigroup),`Monoid`

(Reference: Monoid),`SemigroupByGenerators`

(Reference: SemigroupByGenerators),`MonoidByGenerators`

(Reference: MonoidByGenerators),`ClosureSemigroup`

(6.4-1),`ClosureMonoid`

(6.4-1),`ClosureInverseSemigroup`

(6.4-1),`ClosureInverseMonoid`

(6.4-1),`SemigroupIdeal`

(7.1-1)

a record can be given as an optional final argument. The components of this record specify the values of certain options for the semigroup being created. A list of these options and their default values is given below.

Assume that `S` is the semigroup created by one of the functions given above and that either: `S` is generated by a collection `gens`; or `S` is an ideal of such a semigroup.

`acting`

this component should be

`true`

or`false`

. Roughly speaking, there are two types of methods in the**Semigroups**package: those for semigroups which have to be fully enumerated, and those for semigroups that do not; see Section 1.1. In order for a semigroup to use the latter methods in**Semigroups**it must satisfy`IsActingSemigroup`

(6.1-3). By default any semigroup or monoid of transformations, partial permutations, Rees 0-matrix elements, or bipartitions satisfies`IsActingSemigroup`

.There are cases (such as when it is known

*a priori*that the semigroup is \(\mathscr{D}\)-trivial), when it might be preferable to use the methods that involve fully enumerating a semigroup. In other words, it might be desirable to disable the more sophisticated methods for acting semigroups. If this is the case, then the value of this component can be set`false`

when the semigroup is created. Following this none of the special methods for acting semigroup will be used to compute anything about the semigroup.`regular`

this component should be

`true`

or`false`

. If it is known*a priori*that the semigroup`S`

being created is a regular semigroup, then this component can be set to`true`

. In this case,`S`

knows it is a regular semigroup and can take advantage of the methods for regular semigroups in**Semigroups**. It is usually much more efficient to compute with a regular semigroup that to compute with a non-regular semigroup.If this option is set to

`true`

when the semigroup being defined is**not**regular, then the results might be unpredictable.The default value for this option is

`false`

.`hashlen`

this component should be a positive integer, which roughly specifies the lengths of the hash tables used internally by

**Semigroups**.**Semigroups**uses hash tables in several fundamental methods. The lengths of these tables are a compromise between performance and memory usage; larger tables provide better performance for large computations but use more memory. Note that it is unlikely that you will need to specify this option unless you find that**GAP**runs out of memory unexpectedly or that the performance of**Semigroups**is poorer than expected. If you find that**GAP**runs out of memory unexpectedly, or you plan to do a large number of computations with relatively small semigroups (say with tens of thousands of elements), then you might consider setting`hashlen`

to be less than the default value of`12517`

for each of these semigroups. If you find that the performance of**Semigroups**is unexpectedly poor, or you plan to do a computation with a very large semigroup (say, more than 10 million elements), then you might consider setting`hashlen`

to be greater than the default value of`12517`

.You might find it useful to set the info level of the info class

`InfoOrb`

to 2 or higher since this will indicate when hash tables used by**Semigroups**are being grown; see`SetInfoLevel`

(Reference: InfoLevel).`small`

if this component is set to

`true`

, then**Semigroups**will compute a small subset of`gens`that generates`S`at the time that`S`is created. This will increase the amount of time required to create`S`substantially, but may decrease the amount of time required for subsequent calculations with`S`. If this component is set to`false`

, then**Semigroups**will return the semigroup generated by`gens`without modifying`gens`. The default value for this component is`false`

.This option is ignored when passed to

`ClosureSemigroup`

(6.4-1) or`ClosureInverseSemigroup`

(6.4-1).`cong_by_ker_trace_threshold`

this should be a positive integer, which specifies a semigroup size. If

`S`is a semigroup with inverse op, and`S`has a size greater than or equal to this threshold, then any congruence defined on it may use the "kernel and trace" method to perform calculations. If its size is less than the threshold, then other methods will be used instead. The "kernel and trace" method has better complexity than the generic method, but has large overheads which make it a poor choice for small semigroups. The default value for this component is`10 ^ 5`

. See Section 17.7 for more information about the "kernel and trace" method.`report`

this component should be either

`true`

or`false`

. If this component is set to`true`

, then some additional information will be provided during computations performed by the libsemigroups C++ library.`batch_size`

this component should be a positive integer. If

`S`is a semigroup with representation`IsEnumerableSemigroupRep`

(6.1-4), then when certain computations are performed with`S`using the libsemigroups C++ library, then the computations will be executed in batches of size at least`batch_size`

. This value of this component changes the performance of the libsemigroups C++ library — you may wish to tweak this parameter if you experience sub-optimal performance.`nr_threads`

this component should be a positive integer. This number sets the maximum number of threads that can be used by computations in the libsemigroups C++ library.

gap> S := Semigroup(Transformation([1, 2, 3, 3]), > rec(hashlen := 100003, small := false)); <commutative transformation semigroup of degree 4 with 1 generator>

The default values of the options described above are stored in a global variable named `SEMIGROUPS.DefaultOptionsRec`

(6.3-1). If you want to change the default values of these options for a single **GAP** session, then you can simply redefine the value in **GAP**. For example, to change the option `small`

from the default value of `false` use:

gap> SEMIGROUPS.DefaultOptionsRec.small := true; true

If you want to change the default values of the options stored in `SEMIGROUPS.DefaultOptionsRec`

(6.3-1) for all **GAP** sessions, then you can edit these values in the file `semigroups/gap/options.g`

.

`‣ SEMIGROUPS.DefaultOptionsRec` | ( global variable ) |

This global variable is a record whose components contain the default values of certain options for semigroups. A description of these options is given above in Section 6.3.

The value of `SEMIGROUPS.DefaultOptionsRec`

is defined in the file `semigroups/gap/options.g`

.

`‣ ClosureSemigroup` ( S, coll[, opts] ) | ( operation ) |

`‣ ClosureMonoid` ( S, coll[, opts] ) | ( operation ) |

`‣ ClosureInverseSemigroup` ( S, coll[, opts] ) | ( operation ) |

`‣ ClosureInverseMonoid` ( S, coll[, opts] ) | ( operation ) |

Returns: A semigroup, monoid, inverse semigroup, or inverse monoid.

These operations return the semigroup, monoid, inverse semigroup or inverse monoid generated by the argument `S` and the collection of elements `coll` after removing duplicates and elements from `coll` that are already in `S`. In most cases, the new semigroup knows at least as much information about its structure as was already known about that of `S`.

When `X`

is any of `Semigroup`

(Reference: Semigroup), `Monoid`

(Reference: Monoid), `InverseSemigroup`

(Reference: InverseSemigroup), or `InverseMonoid`

(Reference: InverseMonoid), the argument `S` of the operation `ClosureX`

must belong to the category `IsX`

, and `ClosureX(`

returns an object in the category `S`, `coll`)`IsX`

such that

ClosureX(S, coll) = X(S, coll);

but may have fewer generators, if for example, `coll` contains a duplicates or elements already known to belong to `S`.

For example, the argument `S` of `ClosureInverseSemigroup`

must be an inverse semigroup in the category `IsInverseSemigroup`

(Reference: IsInverseSemigroup). `ClosureInverseSemigroup(`

returns an inverse semigroup which is equal to `S`, `coll`)`InverseSemigroup(`

.`S`, `coll`)

If present, the optional third argument `opts` should be a record containing the values of the options for the semigroup being created as described in Section 6.3.

gap> gens := [Transformation([2, 6, 7, 2, 6, 1, 1, 5]), > Transformation([3, 8, 1, 4, 5, 6, 7, 1]), > Transformation([4, 3, 2, 7, 7, 6, 6, 5]), > Transformation([7, 1, 7, 4, 2, 5, 6, 3])];; gap> S := Monoid(gens[1]);; gap> for x in gens do > S := ClosureSemigroup(S, x); > od; gap> S; <transformation monoid of degree 8 with 4 generators> gap> Size(S); 233606 gap> S := Monoid(PartialPerm([1])); <trivial partial perm group of rank 1 with 1 generator> gap> T := ClosureMonoid(S, [PartialPerm([2 .. 5])]); <partial perm monoid of rank 5 with 2 generators> gap> One(T); <identity partial perm on [ 1, 2, 3, 4, 5 ]> gap> T := ClosureSemigroup(S, [PartialPerm([2 .. 5])]); <partial perm semigroup of rank 4 with 2 generators> gap> One(T); fail gap> ClosureInverseMonoid(DualSymmetricInverseMonoid(3), > DClass(DualSymmetricInverseMonoid(3), > IdentityBipartition(3))); <inverse block bijection monoid of degree 3 with 3 generators> gap> S := InverseSemigroup(Bipartition([[1, -1, -3], [2, 3, -2]]), > Bipartition([[1, -3], [2, -2], [3, -1]]));; gap> T := ClosureInverseSemigroup(S, DClass(PartitionMonoid(3), > IdentityBipartition(3))); <inverse block bijection semigroup of degree 3 with 3 generators> gap> T := ClosureInverseSemigroup(T, [T.1, T.1, T.1]); <inverse block bijection semigroup of degree 3 with 3 generators> gap> S := InverseMonoid([ > PartialPerm([5, 9, 10, 0, 6, 3, 8, 4, 0]), > PartialPerm([10, 7, 0, 8, 0, 0, 5, 9, 1])]);; gap> x := PartialPerm([ > 5, 1, 7, 3, 10, 0, 2, 12, 0, 14, 11, 0, 16, 0, 0, 0, 0, 6, 9, 15]); [4,3,7,2,1,5,10,14][8,12][13,16][18,6][19,9][20,15](11) gap> S := ClosureInverseSemigroup(S, x); <inverse partial perm semigroup of rank 19 with 4 generators> gap> Size(S); 9744 gap> T := Idempotents(SymmetricInverseSemigroup(10));; gap> S := ClosureInverseSemigroup(S, T); <inverse partial perm semigroup of rank 19 with 14 generators>

`‣ SubsemigroupByProperty` ( S, func ) | ( operation ) |

`‣ SubsemigroupByProperty` ( S, func, limit ) | ( operation ) |

Returns: A semigroup.

`SubsemigroupByProperty`

returns the subsemigroup of the semigroup `S` generated by those elements of `S` fulfilling `func` (which should be a function returning `true`

or `false`

).

If no elements of `S` fulfil `func`, then `fail`

is returned.

If the optional third argument `limit` is present and a positive integer, then once the subsemigroup has at least `limit` elements the computation stops.

gap> func := function(x) > local n; > n := DegreeOfTransformation(x); > return 1 ^ x <> 1 and ForAll([1 .. n], y -> y = 1 or y ^ x = y); > end; function( x ) ... end gap> T := SubsemigroupByProperty(FullTransformationSemigroup(3), func); <transformation semigroup of size 2, degree 3 with 2 generators> gap> T := SubsemigroupByProperty(FullTransformationSemigroup(4), func); <transformation semigroup of size 3, degree 4 with 3 generators> gap> T := SubsemigroupByProperty(FullTransformationSemigroup(5), func); <transformation semigroup of size 4, degree 5 with 4 generators>

`‣ InverseSubsemigroupByProperty` ( S, func ) | ( operation ) |

Returns: An inverse semigroup.

`InverseSubsemigroupByProperty`

returns the inverse subsemigroup of the inverse semigroup `S` generated by those elements of `S` fulfilling `func` (which should be a function returning `true`

or `false`

).

If no elements of `S` fulfil `func`, then `fail`

is returned.

If the optional third argument `limit` is present and a positive integer, then once the subsemigroup has at least `limit` elements the computation stops.

gap> IsIsometry := function(f) > local n, i, j, k, l; > n := RankOfPartialPerm(f); > for i in [1 .. n - 1] do > k := DomainOfPartialPerm(f)[i]; > for j in [i + 1 .. n] do > l := DomainOfPartialPerm(f)[j]; > if not AbsInt(k ^ f - l ^ f) = AbsInt(k - l) then > return false; > fi; > od; > od; > return true; > end;; gap> S := InverseSubsemigroupByProperty(SymmetricInverseSemigroup(5), > IsIsometry);; gap> Size(S); 142

`‣ DirectProduct` ( S[, T, ...] ) | ( function ) |

`‣ DirectProductOp` ( list, S ) | ( operation ) |

Returns: A transformation semigroup.

The function `DirectProduct`

takes an arbitrary positive number of finite semigroups, and returns a semigroup that is isomorphic to their direct product.

If these finite semigroups are all partial perm semigroups, all bipartition semigroups, or all PBR semigroups, then `DirectProduct`

returns a semigroup of the same type. Otherwise, `DirectProduct`

returns a transformation semigroup.

The operation `DirectProductOp`

is included for consistency with the **GAP** library (see `DirectProductOp`

(Reference: DirectProductOp)). It takes exactly two arguments, namely a non-empty list `list` of semigroups and one of these semigroups, `S`, and returns the same result as `CallFuncList(DirectProduct, `

.`list`)

If `D`

is the direct product of a collection of semigroups, then an embedding of the `i`

th factor into `D`

can be accessed with the command `Embedding(D, i)`

, and a projection of `D`

onto its `i`

th factor can be accessed with the command `Projection(D, i)`

; see `Embedding`

(Reference: Embedding) and `Projection`

(Reference: Projection) for more information.

gap> S := InverseMonoid([PartialPerm([2, 1])]);; gap> T := InverseMonoid([PartialPerm([1, 2, 3])]);; gap> D := DirectProduct(S, T); <commutative inverse partial perm monoid of rank 5 with 1 generator> gap> Elements(D); [ <identity partial perm on [ 1, 2, 3, 4, 5 ]>, (1,2)(3)(4)(5) ] gap> S := PartitionMonoid(2);; gap> D := DirectProduct(S, S, S);; IsRegularSemigroup(D);; D; <regular bipartition monoid of size 3375, degree 6 with 9 generators> gap> S := Semigroup([PartialPerm([2, 5, 0, 1, 3]), > PartialPerm([5, 2, 4, 3])]);; gap> T := Semigroup([Bipartition([[1, -2], [2], [3, -1, -3]])]);; gap> D := DirectProduct(S, T); <transformation semigroup of size 122, degree 9 with 63 generators> gap> Size(D) = Size(S) * Size(T); true

`‣ WreathProduct` ( M, S ) | ( operation ) |

Returns: A transformation semigroup.

If `M` is a transformation monoid (or a permutation group) of degree `m`

, and `S` is a transformation semigroup (or permutation group) of degree `s`

, the operation `WreathProduct(`

returns the wreath product of `M`, `S`)`M` and `S`, in terms of an embedding in the full transformation monoid of degree `m * s`

.

gap> T := FullTransformationMonoid(3);; gap> C := Group((1, 3));; gap> W := WreathProduct(T, C);; gap> Size(W); 39366 gap> WW := WreathProduct(C, T);; gap> Size(WW); 216

The *dual semigroup* of a semigroup `S`

is the semigroup with the same underlying set of elements but with reversed multiplication; this is anti-isomorphic to `S`

. In **Semigroups** a semigroup and its dual are represented with disjoint sets of elements.

`‣ DualSemigroup` ( S ) | ( attribute ) |

Returns: The dual semigroup of the given semigroup.

The dual semigroup of a semigroup `S` is the semigroup with the same underlying set as `S`, but with multiplication reversed; this is anti-isomorphic to `S`. This attribute returns a semigroup isomorphic to the dual semigroup of `S`.

gap> S := Semigroup([Transformation([1, 4, 3, 2, 2]), > Transformation([5, 4, 4, 1, 2])]);; gap> D := DualSemigroup(S); <dual semigroup of <transformation semigroup of degree 5 with 2 generators>> gap> Size(S) = Size(D); true gap> NrDClasses(S) = NrDClasses(D); true

`‣ IsDualSemigroupRep` ( sgrp ) | ( category ) |

Returns: Returns `true`

if `sgrp` is represented as a dual semigroup.

Semigroups created using `DualSemigroup`

(6.5-1) normally have this representation. The exception is semigroups which are the dual of semigroups already lying in this category. That is, a semigroup has the representation `IsDualSemigroupRep`

if and only if the corresponding dual semigroup does not.

gap> S := Semigroup([Transformation([3, 5, 1, 1, 2]), > Transformation([1, 2, 4, 4, 3])]); <transformation semigroup of degree 5 with 2 generators> gap> D := DualSemigroup(S); <dual semigroup of <transformation semigroup of degree 5 with 2 generators>> gap> IsDualSemigroupRep(D); true gap> R := DualSemigroup(D); <transformation semigroup of degree 5 with 2 generators> gap> IsDualSemigroupRep(R); false gap> R = S; true gap> T := Range(IsomorphismTransformationSemigroup(D)); <transformation semigroup of size 16, degree 17 with 2 generators> gap> IsDualSemigroupRep(T); false gap> x := Representative(D); <Transformation( [ 3, 5, 1, 1, 2 ] ) in the dual semigroup> gap> V := Semigroup(x); <dual semigroup of <commutative transformation semigroup of degree 5 with 1 generator>> gap> IsDualSemigroupRep(V); true

`‣ IsDualSemigroupElement` ( elt ) | ( category ) |

Returns: Returns `true`

if `elt` has the representation of a dual semigroup element.

Elements of a dual semigroup obtained using `AntiIsomorphismDualSemigroup`

(6.5-4) normally lie in this category. The exception is elements obtained by applying the map `AntiIsomorphismDualSemigroup`

(6.5-4) to elements already in this category. That is, the elements of a semigroup lie in the category `IsDualSemigroupElement`

if and only if the elements of the corresponding dual semigroup do not.

gap> S := SingularPartitionMonoid(4);; gap> D := DualSemigroup(S);; gap> s := GeneratorsOfSemigroup(S)[1];; gap> map := AntiIsomorphismDualSemigroup(S);; gap> t := s ^ map; <<block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ], [ 4, -4 ]> in the dual semigroup> gap> IsDualSemigroupElement(t); true gap> inv := InverseGeneralMapping(map);; gap> x := t ^ inv; <block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ], [ 4, -4 ]> gap> IsDualSemigroupElement(x); false

`‣ AntiIsomorphismDualSemigroup` ( S ) | ( attribute ) |

Returns: An anti-isomorphism from `S` to the corresponding dual semigroup.

The dual semigroup of `S` mathematically has the same underlying set as `S`, but is represented with a different set of elements in **Semigroups**. This function returns a mapping which is an anti-isomorphism from `S` to its dual.

gap> S := PartitionMonoid(3); <regular bipartition *-monoid of size 203, degree 3 with 4 generators> gap> map := AntiIsomorphismDualSemigroup(S); MappingByFunction( <regular bipartition *-monoid of size 203, degree 3 with 4 generators>, <dual semigroup of <regular bipartition *-monoid of size 203, degree 3 with 4 generators> >, function( x ) ... end, function( x ) ... end ) gap> inv := InverseGeneralMapping(map);; gap> x := Bipartition([[1, -2], [2, -3], [3, -1]]); <block bijection: [ 1, -2 ], [ 2, -3 ], [ 3, -1 ]> gap> y := Bipartition([[1], [2, -2], [3, -3], [-1]]); <bipartition: [ 1 ], [ 2, -2 ], [ 3, -3 ], [ -1 ]> gap> (x ^ map) * (y ^ map) = (y * x) ^ map; true gap> x ^ map; <<block bijection: [ 1, -2 ], [ 2, -3 ], [ 3, -1 ]> in the dual semigroup>

The **Semigroups** package provides two convenient constructors `IsomorphismSemigroup`

(6.6-1) and `IsomorphismMonoid`

(6.6-2) for changing the representation of a given semigroup or monoid. These methods can be used to find an isomorphism from any semigroup to a semigroup of any other type, provided such an isomorphism exists.

Note that at present neither `IsomorphismSemigroup`

(6.6-1) nor `IsomorphismMonoid`

(6.6-2) can be used to determine whether two given semigroups, or monoids, are isomorphic.

Some methods for `IsomorphismSemigroup`

(6.6-1) and `IsomorphismMonoid`

(6.6-2) are based on methods for the **GAP** library operations:

`IsomorphismReesMatrixSemigroup`

(Reference: IsomorphismReesMatrixSemigroup),`AntiIsomorphismTransformationSemigroup`

(Reference: AntiIsomorphismTransformationSemigroup),`IsomorphismTransformationSemigroup`

(Reference: IsomorphismTransformationSemigroup) and`IsomorphismTransformationMonoid`

(Reference: IsomorphismTransformationMonoid),`IsomorphismPartialPermSemigroup`

(Reference: IsomorphismPartialPermSemigroup) and`IsomorphismPartialPermMonoid`

(Reference: IsomorphismPartialPermMonoid),`IsomorphismFpSemigroup`

(Reference: IsomorphismFpSemigroup) and`IsomorphismFpMonoid`

.

The operation `IsomorphismMonoid`

(6.6-2) can be used to return an isomorphism from a semigroup which is mathematically a monoid (but does not below to the category of monoids in **GAP** `IsMonoid`

(Reference: IsMonoid)) into a monoid. This is the primary purpose of the operation `IsomorphismMonoid`

(6.6-2). Either `IsomorphismSemigroup`

(6.6-1) or `IsomorphismMonoid`

(6.6-2) can be used to change the representation of a monoid, but only the latter is guaranteed to return an object in the category of monoids.

gap> S := Monoid(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]), > Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));; gap> AsSemigroup(IsBooleanMatSemigroup, S); <monoid of 10x10 boolean matrices with 2 generators> gap> AsMonoid(IsBooleanMatMonoid, S); <monoid of 10x10 boolean matrices with 2 generators> gap> S := Semigroup(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]), > Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));; gap> AsSemigroup(IsBooleanMatSemigroup, S); <semigroup of 10x10 boolean matrices with 2 generators> gap> AsMonoid(IsBooleanMatMonoid, S); <monoid of 8x8 boolean matrices with 2 generators> gap> M := Monoid([ > Bipartition([[1, -3], [2, 3, 6], [4, 7, -6], [5, -8], [8, -4, -5], > [-1], [-2], [-7]]), > Bipartition([[1, 3, -6], [2, -8], [4, 8, -1], [5], [6, -3, -4], > [7], [-2], [-5], [-7]]), > Bipartition([[1, 2, 4, -3, -7, -8], [3, 5, 6, 8, -4, -6], > [7, -1, -2, -5]])]);; gap> AsMonoid(IsPBRMonoid, M); <pbr monoid of size 163, degree 163 with 3 generators> gap> AsSemigroup(IsPBRSemigroup, M); <pbr semigroup of size 163, degree 8 with 4 generators>

There are some further methods in **Semigroups** for obtaining an isomorphism from a Rees matrix, or 0-matrix, semigroup to another such semigroup with particular properties; `RMSNormalization`

(6.6-7) and `RZMSNormalization`

(6.6-6).

`‣ IsomorphismSemigroup` ( filt, S ) | ( operation ) |

Returns: An isomorphism of semigroups.

`IsomorphismSemigroup`

can be used to find an isomorphism from a given semigroup to a semigroup of another type, provided such an isomorphism exists.

The first argument `filt` must be of the form `IsXSemigroup`

, for example, `IsTransformationSemigroup`

(Reference: IsTransformationSemigroup), `IsFpSemigroup`

(Reference: IsFpSemigroup), and `IsPBRSemigroup`

(4.6-1) are some possible values for `filt`. Note that `filt` should not be of the form `IsXMonoid`

; see `IsomorphismMonoid`

(6.6-2). The second argument `S` should be a semigroup.

`IsomorphismSemigroup`

returns an isomorphism from `S` to a semigroup `T` of the type described by `filt`, if such an isomorphism exists. More precisely, if `T`

is the range of the returned isomorphism, then

will return `filt`(T)`true`

. For example, if `filt` is `IsTransformationSemigroup`

, then the range of the returned isomorphism will be a transformation semigroup.

An error is returned if there is no isomorphism from `S` to a semigroup satisfying `filt`. For example, there is no method for `IsomorphismSemigroup`

when `filt` is, say, `IsReesMatrixSemigroup`

(Reference: IsReesMatrixSemigroup) and when `S` is a non-simple semigroup. Similarly, there is no method when `filt` is `IsPartialPermSemigroup`

(Reference: IsPartialPermSemigroup) and when `S` is a non-inverse semigroup.

In some cases, if no better method is installed, `IsomorphismSemigroup`

returns an isomorphism found by composing an isomorphism from `S` to a transformation semigroup `T`

, and an isomorphism from `T`

to a semigroup of type `filt`.

Note that if the argument `S` belongs to the category of monoids `IsMonoid`

(Reference: IsMonoid), then `IsomorphismSemigroup`

will often, but not always, return a monoid isomorphism.

gap> S := Semigroup([ > Bipartition([ > [1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]), > Bipartition([ > [1, -4], [2, 3, 4, 5], [6], [-1, -6], [-2, -3], [-5]])]); <bipartition semigroup of degree 6 with 2 generators> gap> IsomorphismSemigroup(IsTransformationSemigroup, S); MappingByFunction( <bipartition semigroup of size 11, degree 6 with 2 generators>, <transformation semigroup of size 11, degree 12 with 2 generators>, function( x ) ... end, function( x ) ... end ) gap> IsomorphismSemigroup(IsBooleanMatSemigroup, S); MappingByFunction( <bipartition semigroup of size 11, degree 6 with 2 generators>, <semigroup of size 11, 12x12 boolean matrices with 2 generators>, function( x ) ... end, function( x ) ... end ) gap> IsomorphismSemigroup(IsFpSemigroup, S); MappingByFunction( <bipartition semigroup of size 11, degree 6 with 2 generators>, <fp semigroup on the generators [ s1, s2 ]>, function( x ) ... end, function( x ) ... end ) gap> S := InverseSemigroup([ > PartialPerm([1, 2, 3, 6, 8, 10], > [2, 6, 7, 9, 1, 5]), > PartialPerm([1, 2, 3, 4, 6, 7, 8, 10], > [3, 8, 1, 9, 4, 10, 5, 6])]);; gap> IsomorphismSemigroup(IsBipartitionSemigroup, S); MappingByFunction( <inverse partial perm semigroup of rank 10 with 2 generators>, <inverse bipartition semigroup of degree 10 with 2 generators>, function( x ) ... end, <Operation "AsPartialPerm"> ) gap> S := SymmetricInverseMonoid(4); <symmetric inverse monoid of degree 4> gap> IsomorphismSemigroup(IsBlockBijectionSemigroup, S); MappingByFunction( <symmetric inverse monoid of degree 4>, <inverse block bijection monoid of degree 5 with 3 generators> , function( x ) ... end, function( x ) ... end ) gap> Size(Range(last)); 209 gap> S := Semigroup([ > PartialPerm([3, 1]), PartialPerm([1, 3, 4])]);; gap> IsomorphismSemigroup(IsBlockBijectionSemigroup, S); MappingByFunction( <partial perm semigroup of rank 3 with 2 generators>, <block bijection semigroup of degree 5 with 2 generators>, function( x ) ... end, function( x ) ... end )

`‣ IsomorphismMonoid` ( filt, S ) | ( operation ) |

Returns: An isomorphism of monoids.

`IsomorphismMonoid`

can be used to find an isomorphism from a given semigroup which is mathematically a monoid (but might not belong to the category of monoids in **GAP**) to a monoid, provided such an isomorphism exists.

The first argument `filt` must be of the form `IsXMonoid`

, for example, `IsTransformationMonoid`

(Reference: IsTransformationMonoid), `IsFpMonoid`

(Reference: IsFpMonoid), and `IsBipartitionMonoid`

(3.8-1) are some possible values for `filt`. Note that `filt` should not be of the form `IsXSemigroup`

; see `IsomorphismSemigroup`

(6.6-1). The second argument `S` should be a semigroup which is mathematically a monoid but which may or may not belong to the category `IsMonoid`

(Reference: IsMonoid) of monoids in **GAP**, i.e. `S` must satisfy `IsMonoidAsSemigroup`

(15.1-13).

`IsomorphismMonoid`

returns a monoid isomorphism from `S` to a semigroup `T` of the type described by `filt`, if such an isomorphism exists. In this context, a *monoid isomorphism* is a semigroup isomorphism that maps the `MultiplicativeNeutralElement`

(Reference: MultiplicativeNeutralElement) of `S` to the `One`

(Reference: One) of `T`. If `T`

is the range of the returned isomorphism, then

will return `filt`(T)`true`

. For example, if `filt` is `IsTransformationMonoid`

, then the range of the returned isomorphism will be a transformation monoid.

An error is returned if there is no isomorphism from `S` to a monoid satisfying `filt`. For example, there is no method for `IsomorphismMonoid`

when `filt` is, say, `IsReesZeroMatrixSemigroup`

(Reference: IsReesZeroMatrixSemigroup) and when `S` is a not 0-simple. Similarly, there is no method when `filt` is `IsPartialPermMonoid`

(Reference: IsPartialPermMonoid) and when `S` is a non-inverse monoid.

In some cases, if no better method is installed, `IsomorphismMonoid`

returns an isomorphism found by composing an isomorphism from `S` to a transformation monoid `T`

, and an isomorphism from `T`

to a monoid of type `filt`.

gap> S := Semigroup(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]), > Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9])); <transformation semigroup of degree 10 with 2 generators> gap> IsomorphismMonoid(IsTransformationMonoid, S); MappingByFunction( <transformation semigroup of degree 10 with 2 generators>, <transformation monoid of degree 8 with 2 generators> , function( x ) ... end, function( x ) ... end ) gap> IsomorphismMonoid(IsBooleanMatMonoid, S); MappingByFunction( <transformation semigroup of degree 10 with 2 generators>, <monoid of 8x8 boolean matrices with 2 generators> , function( x ) ... end, function( x ) ... end ) gap> IsomorphismMonoid(IsFpMonoid, S); MappingByFunction( <transformation semigroup of degree 10 with 2 generators>, <fp monoid on the generators [ m1, m2 ]>, function( x ) ... end, function( x ) ... end )

`‣ AsSemigroup` ( filt, S ) | ( operation ) |

Returns: A semigroup.

`AsSemigroup(`

is just shorthand for `filt`, `S`)`Range(IsomorphismSemigroup(`

, when `filt`, `S`))`S` is a semigroup; see `IsomorphismSemigroup`

(6.6-1) for more details.

Note that if the argument `S` belongs to the category of monoids `IsMonoid`

(Reference: IsMonoid), then `AsSemigroup`

will often, but not always, return a monoid. A monoid is not returned if there is not a good monoid isomorphism from `S` to a monoid of the required type, but there is a good semigroup isomorphism.

If it is not possible to convert the semigroup `S` to a semigroup of type `filt`, then an error is given.

gap> S := Semigroup([ > Bipartition([ > [1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]), > Bipartition([ > [1, -4], [2, 3, 4, 5], [6], [-1, -6], [-2, -3], [-5]])]); <bipartition semigroup of degree 6 with 2 generators> gap> AsSemigroup(IsTransformationSemigroup, S); <transformation semigroup of size 11, degree 12 with 2 generators> gap> S := Semigroup([ > Bipartition([ > [1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]), > Bipartition([ > [1, -4], [2, 3, 4, 5], [6], [-1, -6], [-2, -3], [-5]])]); <bipartition semigroup of degree 6 with 2 generators> gap> AsSemigroup(IsTransformationSemigroup, S); <transformation semigroup of size 11, degree 12 with 2 generators> gap> T := Semigroup(Transformation([2, 2, 3]), > Transformation([3, 1, 3])); <transformation semigroup of degree 3 with 2 generators> gap> S := AsSemigroup(IsMatrixOverFiniteFieldSemigroup, GF(5), T); <semigroup of 3x3 matrices over GF(5) with 2 generators> gap> Size(S); 5

`‣ AsMonoid` ( [filt, ]S ) | ( operation ) |

Returns: A monoid or `fail`

.

`AsMonoid(`

is just shorthand for `filt`, `S`)`Range(IsomorphismMonoid(`

, when `filt`, `S`))`S` is a semigroup or monoid; see `IsomorphismMonoid`

(6.6-2) for more details.

If the first argument `filt` is omitted and the semigroup `S` is mathematically a monoid which does not belong to the category of monoids in **GAP**, then `AsMonoid`

returns a monoid (in the category of monoids) isomorphic to `S` and of the same type as `S`. If `S` is already in the category of monoids and the first argument `filt` is omitted, then `S` is returned.

If the first argument `filt` is omitted and the semigroup `S` is not a monoid, i.e. it does not satisfy `IsMonoidAsSemigroup`

(15.1-13), then `fail`

is returned.

gap> S := Semigroup(Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]), > Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9]));; gap> AsMonoid(S); <transformation monoid of degree 8 with 2 generators> gap> AsSemigroup(IsBooleanMatSemigroup, S); <semigroup of 10x10 boolean matrices with 2 generators> gap> AsMonoid(IsBooleanMatMonoid, S); <monoid of 8x8 boolean matrices with 2 generators> gap> S := Monoid(Bipartition([[1, -1, -3], [2, 3], [-2]]), > Bipartition([[1, -1], [2, 3, -3], [-2]])); <bipartition monoid of degree 3 with 2 generators> gap> AsMonoid(IsTransformationMonoid, S); <transformation monoid of size 3, degree 3 with 2 generators> gap> AsMonoid(S); <bipartition monoid of size 3, degree 3 with 2 generators>

`‣ IsomorphismPermGroup` ( S ) | ( attribute ) |

Returns: An isomorphism.

If the semigroup `S` is mathematically a group, so that it satisfies `IsGroupAsSemigroup`

(15.1-7), then `IsomorphismPermGroup`

returns an isomorphism to a permutation group.

If `S` is not a group then an error is given.

See also `IsomorphismPermGroup`

(Reference: IsomorphismPermGroup).

gap> S := Semigroup(Transformation([2, 2, 3, 4, 6, 8, 5, 5]), > Transformation([3, 3, 8, 2, 5, 6, 4, 4]));; gap> IsGroupAsSemigroup(S); true gap> iso := IsomorphismPermGroup(S);; gap> Source(iso) = S and Range(iso) = Group([(5, 6, 8), (2, 3, 8, 4)]); true gap> StructureDescription(Range(IsomorphismPermGroup(S))); "S6" gap> S := Range(IsomorphismPartialPermSemigroup(SymmetricGroup(4))); <partial perm group of size 24, rank 4 with 2 generators> gap> Range(IsomorphismPermGroup(S)); Group([ (1,2,3,4), (1,2) ]) gap> G := GroupOfUnits(PartitionMonoid(4)); <block bijection group of degree 4 with 2 generators> gap> StructureDescription(G); "S4" gap> iso := IsomorphismPermGroup(G);; gap> RespectsMultiplication(iso); true gap> inv := InverseGeneralMapping(iso);; gap> ForAll(G, x -> (x ^ iso) ^ inv = x); true gap> ForAll(G, x -> ForAll(G, y -> (x * y) ^ iso = x ^ iso * y ^ iso)); true

`‣ RZMSNormalization` ( R ) | ( attribute ) |

Returns: An isomorphism.

If `R` is a Rees 0-matrix semigroup \(M^{0}[I, T, \Lambda; P]\) then `RZMSNormalization`

returns an isomorphism from `R` to a *normalized* Rees 0-matrix semigroup \(S = M^{0}[I, T, \Lambda; Q]\). The structure matrix \(Q\) is obtained by *normalizing* the matrix \(P\) (see `Matrix`

(Reference: Matrix)) and has the following properties:

The matrix \(Q\) is in block diagonal form, and the blocks are ordered by decreasing size along the leading diagonal (the size of a block is defined to be the number of rows it contains multiplied by the number of columns it contains).

If the index sets \(I\) and \(\Lambda\) are partitioned into \(k\) parts according to the

`RZMSConnectedComponents`

(14.14-2) of \(S\), giving a disjoint union \(I=I_1\cup\ldots\cup I_k\) and \(\Lambda=\Lambda_1\cup\ldots\cup\Lambda_k\), then the \(r\)th block corresponds to the sub-matrix \(Q_{r}\) of \(Q\) defined by \(I_{r}\) and \(\Lambda_{r}\).The first non-zero entry in a row occurs no sooner than the first non-zero entry in any previous row.

The first non-zero entry in a column occurs no sooner than the first non-zero entry in any previous column.

The previous two items imply that if the matrix \(P\) has any rows/columns consisting entirely of zeroes, then these will become the final rows/columns of \(Q\).

Furthermore, if \(T\) is a group (i.e. a semigroup for which `IsGroupAsSemigroup`

(15.1-7) returns `true`

), then the non-zero entries of the structure matrix \(Q\) are chosen such that the following hold:

The first non-zero entry of every row and every column is equal to the identity of \(T\).

For each \(r\), let \(Q_{r}\) be the sub-matrix of \(Q\) defined by \(I_r\) and \(\Lambda_r\) (as above), and let \(T_r\) be the subsemigroup of \(T\) generated by the non-zero entries of \(Q_{r}\). Then the idempotent generated subsemigroup of \(S\) is equal to:

\(\bigcup_{r=1}^{k} M^{0}[I_r, T_r, \Lambda_r, Q_r]\), where the zeroes of these Rees 0-matrix semigroups are all identified with the zero of \(S\).

The normalization given by `RZMSNormalization`

is based on Theorem 2 of [Gra68] and is sometimes called *Graham normal form*. Note that isomorphic Rees 0-matrix semigroups can have normalizations which are not equal.

gap> R := ReesZeroMatrixSemigroup(Group(()), > [[0, (), 0], > [(), 0, 0], > [0, 0, ()]]); <Rees 0-matrix semigroup 3x3 over Group(())> gap> iso := RZMSNormalization(R); MappingByFunction( <Rees 0-matrix semigroup 3x3 over Group(())>, <Rees 0-matrix semigroup 3x3 over Group(())> , function( x ) ... end, function( x ) ... end ) gap> S := Range(iso); <Rees 0-matrix semigroup 3x3 over Group(())> gap> Matrix(S); [ [ (), 0, 0 ], [ 0, (), 0 ], [ 0, 0, () ] ] gap> R := ReesZeroMatrixSemigroup(SymmetricGroup(4), > [[0, 0, 0, (1, 3, 2)], > [(2, 3), 0, 0, 0], > [0, 0, (1, 3), (1, 2)], > [0, (4, 1, 2, 3), 0, 0]]); <Rees 0-matrix semigroup 4x4 over Sym( [ 1 .. 4 ] )> gap> S := Range(RZMSNormalization(R)); <Rees 0-matrix semigroup 4x4 over Sym( [ 1 .. 4 ] )> gap> Matrix(S); [ [ (), (), 0, 0 ], [ 0, (), 0, 0 ], [ 0, 0, (), 0 ], [ 0, 0, 0, () ] ]

`‣ RMSNormalization` ( R ) | ( attribute ) |

Returns: An isomorphism.

If `R` is a Rees matrix semigroup over a group `G`

(i.e. a semigroup for which `IsGroupAsSemigroup`

(15.1-7) returns `true`

), then `RMSNormalization`

returns an isomorphism from `R` to a *normalized* Rees matrix semigroup `S`

over `G`

.

The semigroup `S`

is normalized in the sense that the first entry of each row and column of the `Matrix`

(Reference: Matrix) of `S`

is the identity element of `G`

.

gap> R := ReesMatrixSemigroup(SymmetricGroup(4), > [[(1, 2), (2, 4, 3), (2, 1, 4)], > [(1, 3, 2), (1, 2)(3, 4), ()], > [(2, 3), (1, 3, 2, 4), (2, 3)]]); <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> gap> iso := RMSNormalization(R); MappingByFunction( <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> , <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> , function( x ) ... end, function( x ) ... end ) gap> S := Range(iso); <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> gap> Matrix(S); [ [ (), (), () ], [ (), (1,2), (1,4,2,3) ], [ (), (1,4,2,3), (2,4) ] ]

`‣ RandomSemigroup` ( arg... ) | ( function ) |

`‣ RandomMonoid` ( arg... ) | ( function ) |

`‣ RandomInverseSemigroup` ( arg... ) | ( function ) |

`‣ RandomInverseMonoid` ( arg... ) | ( function ) |

Returns: A semigroup.

The operations described in this section can be used to generate semigroups, in some sense, at random. There is no guarantee given about the distribution of these semigroups, and this is only intended as a means of generating semigroups for testing and other similar purposes.

Roughly speaking, the arguments of `RandomSemigroup`

are a filter specifying the type of the semigroup to be returned, together with some further parameters that describe some attributes of the semigroup to be returned. For instance, we may want to specify the number of generators, and, say, the degree, or dimension, of the elements, where appropriate. The arguments of `RandomMonoid`

, `RandomInverseSemigroup`

, and `RandomInverseMonoid`

are analogous.

If no arguments are specified, then they are all chosen at random, for a truly random experience.

The first argument, if present, should be a filter `filter`. For `RandomSemigroup`

and `RandomInverseSemigroup`

the filter `filter` must be of the form `IsXSemigroup`

. For example, `IsTransformationSemigroup`

(Reference: IsTransformationSemigroup), `IsFpSemigroup`

(Reference: IsFpSemigroup), and `IsPBRSemigroup`

(4.6-1) are some possible values for `filter`. For `RandomMonoid`

and `RandomInverseMonoid`

the argument `filter` must be of the form `IsXMonoid`

; such as `IsBipartitionMonoid`

(3.8-1) or `IsBooleanMatMonoid`

(5.7-2).

Suppose that the first argument `filter` is `IsFpSemigroup`

(Reference: IsFpSemigroup). Then the only other arguments that can be specified is (and this argument is also optional):

**number of generators**The second argument, if present, should be a positive integer

`m`indicating the number of generators that the semigroup should have. If the second argument`m`is not specified, then a number is selected at random.

If `filter` is a filter such as `IsTransformationSemigroup`

(Reference: IsTransformationSemigroup) or `IsIntegerMatrixSemigroup`

(5.7-1), then a further argument can be specified:

**degree / dimension**The third argument, if present, should be a positive integer

`n`, which specifies the degree or dimension of the generators. For example, if the first argument`filter`is`IsTransformationSemigroup`

, then the value of this argument is the degree of the transformations in the returned semigroup; or if`filter`is`IsMatrixOverFiniteFieldSemigroup`

, then this argument is the dimension of the matrices in the returned semigroup.

If `filter` is `IsTropicalMaxPlusMatrixSemigroup`

(5.7-1), for example, then a fourth argument can be given (or not!):

**threshold**The fourth argument, if present, should be a positive integer

`t`, which specifies the threshold of the semiring over which the matrices in the returned semigroup are defined.

You get the idea, the error messages are self-explanatory, and `RandomSemigroup`

works for most of the type of semigroups defined in **GAP**.

`RandomMonoid`

is similar to `RandomSemigroup`

except it returns a monoid. Likewise, `RandomInverseSemigroup`

and `RandomInverseMonoid`

return inverse semigroups and monoids, respectively.

gap> RandomSemigroup(); <semigroup of 10x10 max-plus matrices with 12 generators> gap> RandomMonoid(IsTransformationMonoid); <transformation monoid of degree 9 with 7 generators> gap> RandomMonoid(IsPartialPermMonoid, 2); <partial perm monoid of rank 17 with 2 generators> gap> RandomMonoid(IsPartialPermMonoid, 2, 3); <partial perm monoid of rank 3 with 2 generators> gap> RandomInverseSemigroup(IsTropicalMinPlusMatrixSemigroup); <semigroup of 6x6 tropical min-plus matrices with 14 generators> gap> RandomInverseSemigroup(IsTropicalMinPlusMatrixSemigroup, 1); <semigroup of 6x6 tropical min-plus matrices with 14 generators> gap> RandomSemigroup(IsTropicalMinPlusMatrixSemigroup, 2); <semigroup of 11x11 tropical min-plus matrices with 2 generators> gap> RandomSemigroup(IsTropicalMinPlusMatrixSemigroup, 2, 1); <semigroup of 1x1 tropical min-plus matrices with 2 generators> gap> RandomSemigroup(IsTropicalMinPlusMatrixSemigroup, 2, 1, 3); gap> last.1; Matrix(IsTropicalMinPlusMatrix, [[infinity]], 3) gap> RandomSemigroup(IsNTPMatrixSemigroup, 2, 1, 3, 4); <semigroup of 1x1 ntp matrices with 2 generators> gap> last.1; Matrix(IsNTPMatrix, [[2]], 3, 4) gap> RandomSemigroup(IsReesMatrixSemigroup, 2, 2); <Rees matrix semigroup 2x2 over <permutation group of size 659 with 1 generators>> gap> RandomSemigroup(IsReesZeroMatrixSemigroup, 2, 2, Group((1, 2), (3, 4))); <Rees 0-matrix semigroup 2x2 over Group([ (1,2), (3,4) ])> gap> RandomInverseMonoid(IsMatrixOverFiniteFieldMonoid, 2, 2); <monoid of 3x3 matrices over GF(421^4) with 3 generators> gap> RandomInverseMonoid(IsMatrixOverFiniteFieldMonoid, 2, 2, GF(7)); <monoid of 3x3 matrices over GF(7) with 2 generators> gap> RandomSemigroup(IsBipartitionSemigroup, 5, 5); <bipartition semigroup of degree 5 with 5 generators> gap> RandomMonoid(IsBipartitionMonoid, 5, 5); <bipartition monoid of degree 5 with 5 generators> gap> RandomSemigroup(IsBooleanMatSemigroup); <semigroup of 3x3 boolean matrices with 18 generators> gap> RandomMonoid(IsBooleanMatMonoid); <monoid of 11x11 boolean matrices with 19 generators>

`‣ EndomorphismMonoid` ( digraph ) | ( attribute ) |

`‣ EndomorphismMonoid` ( digraph, colors ) | ( operation ) |

Returns: A monoid.

An endomorphism of `digraph` is a homomorphism `DigraphHomomorphism`

(Digraphs: DigraphHomomorphism) from `digraph` back to itself.

`EndomorphismMonoid`

, called with a single argument, returns the monoid of all endomorphisms of `digraph`.

If the `colors` argument is specified, then it will return the monoid of endomorphisms which respect the given colouring. The colouring `colors` can be in one of two forms:

A list of positive integers of size the number of vertices of

`digraph`, where`colors``[i]`

is the colour of vertex`i`

.A list of lists, such that

`colors``[i]`

is a list of all vertices with colour`i`

.

See also `GeneratorsOfEndomorphismMonoid`

(Digraphs: GeneratorsOfEndomorphismMonoid). Note that the performance of `EndomorphismMonoid`

may differ from that of `GeneratorsOfEndomorphismMonoid`

(Digraphs: GeneratorsOfEndomorphismMonoid) since the former incrementally adds newly discovered endomorphisms to the monoid using `ClosureMonoid`

(6.4-1).

gap> gr := Digraph(List([1 .. 3], x -> [1 .. 3]));; gap> EndomorphismMonoid(gr); <transformation monoid of degree 3 with 3 generators> gap> gr := CompleteDigraph(3);; gap> EndomorphismMonoid(gr); <transformation group of size 6, degree 3 with 2 generators> gap> S := EndomorphismMonoid(gr, [1, 2, 2]);; gap> IsGroupAsSemigroup(S); true gap> Size(S); 2 gap> S := EndomorphismMonoid(gr, [[1], [2, 3]]);; gap> S := EndomorphismMonoid(gr, [1, 2, 2]);; gap> IsGroupAsSemigroup(S); true

generated by GAPDoc2HTML