Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

6 Creating semigroups and monoids
 6.1 Underlying algorithms and related representations
 6.2 Semigroups represented by generators
 6.3 Options when creating semigroups
 6.4 New semigroups from old
 6.5 Changing the representation of a semigroup
 6.6 Random semigroups
 6.7 Endomorphism monoid of a digraph

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.

6.1 Underlying algorithms and related representations

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.

6.1-1 Acting semigroups

The first type of fundamental algorithms are those described in [EENMP15], 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 [EENMP15] 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 (12.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 (12.1-4), RClassReps (12.1-5), IteratorOfRClassReps (12.2-1), IteratorOfRClasses (12.2-2), or NrRClasses (12.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.

6.1-2 Enumerable semigroups

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 [EENMP15] 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 [MM11]; and matrices over the following semirings:

(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.

6.1-3 IsActingSemigroup
‣ 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

6.1-4 IsEnumerableSemigroupRep
‣ 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 (13.1-1), EnumeratorCanonical (13.1-1), IteratorCanonical (13.1-1), PositionCanonical (13.1-2), Enumerate (13.1-3), and IsFullyEnumerated (13.1-4).

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

6.2 Semigroups represented by generators

6.2-1 InverseMonoidByGenerators
‣ 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.

6.3 Options when creating semigroups

When using any of the functions:

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 16.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.

6.3-1 SEMIGROUPS.DefaultOptionsRec
‣ 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.

6.4 New semigroups from old

6.4-1 ClosureSemigroup
‣ 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(S, coll) returns an object in the category 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(S, coll) returns an inverse semigroup which is equal to 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>

6.4-2 SubsemigroupByProperty
‣ 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>

6.4-3 InverseSubsemigroupByProperty
‣ 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

6.4-4 DirectProduct
‣ DirectProduct( S[, T, ...] )( function )
‣ DirectProductOp( list, S )( operation )

Returns: A transformation semigroup.

The function DirectProduct takes an arbitrary positive number of transformation semigroups and returns another transformation semigroup isomorphic to their direct product. 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 transformation semigroups and one of these semigroups, S.

gap> S := Semigroup(Transformation([2, 1]));;
gap> T := Semigroup(Transformation([1, 2, 3, 3, 3]));;
gap> DP := DirectProduct(S, T);
<commutative transformation semigroup of degree 7 with 2 generators>
gap> Elements(DP);
[ Transformation( [ 1, 2, 3, 4, 5, 5, 5 ] ), 
  Transformation( [ 2, 1, 3, 4, 5, 5, 5 ] ) ]
gap> S := Monoid([Transformation([2, 4, 3, 4]),
>                 Transformation([3, 3, 2, 3, 3])]);;
gap> T := Semigroup([Transformation([3, 5, 4, 2, 6, 3])]);;
gap> DP := DirectProduct(S, T);
<transformation semigroup of degree 11 with 4 generators>
gap> Size(DP);
35

6.5 Changing the representation of a semigroup

The Semigroups package provides two convenient constructors IsomorphismSemigroup (6.5-1) and IsomorphismMonoid (6.5-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.5-1) nor IsomorphismMonoid (6.5-2) can be used to determine whether two given semigroups, or monoids, are isomorphic.

Some methods for IsomorphismSemigroup (6.5-1) and IsomorphismMonoid (6.5-2) are based on methods for the GAP library operations:

The operation IsomorphismMonoid (6.5-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.5-2). Either IsomorphismSemigroup (6.5-1) or IsomorphismMonoid (6.5-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.5-7) and RZMSNormalization (6.5-6).

6.5-1 IsomorphismSemigroup
‣ 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.5-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 filt(T) will return 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 )

6.5-2 IsomorphismMonoid
‣ 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.5-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 (14.1-12).

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 filt(T) will return 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 )

6.5-3 AsSemigroup
‣ AsSemigroup( filt, S )( operation )

Returns: A semigroup.

AsSemigroup(filt, S) is just shorthand for Range(IsomorphismSemigroup(filt, S)), when S is a semigroup; see IsomorphismSemigroup (6.5-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

6.5-4 AsMonoid
‣ AsMonoid( [filt, ]S )( operation )

Returns: A monoid or fail.

AsMonoid(filt, S) is just shorthand for Range(IsomorphismMonoid(filt, S)), when S is a semigroup or monoid; see IsomorphismMonoid (6.5-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 (14.1-12), 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>

6.5-5 IsomorphismPermGroup
‣ IsomorphismPermGroup( S )( attribute )

Returns: An isomorphism.

If the semigroup S is mathematically a group, so that it satisfies IsGroupAsSemigroup (14.1-6), 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> Range(IsomorphismPermGroup(S));
Group([ (5,6,8), (2,3,8,4) ])
gap> StructureDescription(Range(IsomorphismPermGroup(S)));
"S6"
gap> S := Range(IsomorphismPartialPermSemigroup(SymmetricGroup(4)));
<partial perm group of size 24, rank 4 with 2 generators>
gap> IsomorphismPermGroup(S);
MappingByFunction( <partial perm group of size 24, rank 4 with
  2 generators>, Group([ (1,2,3,4), (1,
2) ]), <Attribute "AsPermutation">, function( x ) ... end )
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

6.5-6 RZMSNormalization
‣ RZMSNormalization( R )( attribute )

Returns: An isomorphism.

If R is a Rees 0-matrix semigroup M^0[I, T, Λ; P] then RZMSNormalization returns an isomorphism from R to a normalized Rees 0-matrix semigroup S = M^0[I, T, Λ; Q]. The structure matrix Q is obtained by normalizing the matrix P (see Matrix (Reference: Matrix)) and has the following properties:

Furthermore, if T is a group (i.e. a semigroup for which IsGroupAsSemigroup (14.1-6) returns true), then the non-zero entries of the structure matrix Q are chosen such that the following hold:

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, () ] 
 ]

6.5-7 RMSNormalization
‣ RMSNormalization( R )( attribute )

Returns: An isomorphism.

If R is a Rees matrix semigroup over a group G (i.e. a semigroup for which IsGroupAsSemigroup (14.1-6) 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) ] ]

6.6 Random semigroups

6.6-1 RandomSemigroup
‣ 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>

6.7 Endomorphism monoid of a digraph

6.7-1 EndomorphismMonoid
‣ 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:

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> EndomorphismMonoid(gr, [1, 2, 2]);
<transformation group of degree 3 with 1 generator>
gap> EndomorphismMonoid(gr, [[1], [2, 3]]);
<transformation group of degree 3 with 1 generator>
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind

generated by GAPDoc2HTML