In this chapter we describe the various ways that semigroups and monoids defined by generating sets can be created in Semigroups; where the generators are, for example, those elements described in earlier chapters of this manual.
Computing the Green's structure of a semigroup or monoid is a fundamental step in almost every algorithm for semigroups. There are two fundamental algorithms in the Semigroups package for computing the Green's structure of a semigroup defined by a set of generators. In the next two subsections we briefly describe these two algorithms.
The first of the fundamental algorithms for computing a semigroup defined by a generating set is described in [EENMP19]. When applied to a semigroup or monoid with relatively large subgroups, or \(\mathscr{D}\)-classes, these 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), matrices over a finite field (see Section 5.4); subsemigroups of regular Rees 0-matrix semigroups over permutation groups (see Chapter Reference: Rees Matrix Semigroups), and subsemigroups of McAlister triples (see Section 8.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-2).
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 (10.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 (10.1-4), RClassReps (10.1-5), IteratorOfRClasses (10.2-2), or NrRClasses (10.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.
‣ 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> CanUseFroidurePin(S); true gap> S := FreeSemigroup(3);; gap> IsActingSemigroup(S); false
The second fundamental algorithm for computing finite semigroups 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.
A semigroup to which the Froidure-Pin Algorithm can be applied in Semigroups satisfy CanUseFroidurePin (6.1-4). Every acting semigroup in Semigroups satisfies CanUseFroidurePin (6.1-4) and the Froidure-Pin Algorithm is used to compute 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 which satisfies CanUseGapFroidurePin (6.1-4). In theory, any finite semigroup can be computed using this algorithm. However, the condition that the semigroup has satisfies CanUseGapFroidurePin (6.1-4) is imposed to avoid this method being used when it is inappropriate. If implementing a new type of semigroup in GAP, then simply do
InstallTrueMethod(CanUseGapFroidurePin,
MyNewSemigroupType);to make your new semigroup type MyNewSemigroupType use this version of the Froidure-Pin Algorithm. To make this work efficiently it is necessary that a hash function is implemented for the elements of MyNewSemigroupType; more details will be included in a future edition of this manual.
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.
‣ CanUseFroidurePin( obj ) | ( property ) |
‣ CanUseGapFroidurePin( obj ) | ( property ) |
‣ CanUseLibsemigroupsFroidurePin( obj ) | ( property ) |
Returns: true or false.
Every semigroup satisfying CanUseFroidurePin is a valid input for the Froidure-Pin algorithm; see Section 6.1-3 for more details.
Basic operations for semigroups satisfying CanUseFroidurePin are: AsListCanonical (11.1-1), EnumeratorCanonical (11.1-1), IteratorCanonical (11.1-1), PositionCanonical (11.1-2), Enumerate (11.1-3), and IsEnumerated (11.1-4).
gap> S := Semigroup(Transformation([1, 3, 2]));; gap> CanUseFroidurePin(S); true gap> S := FreeSemigroup(3);; gap> CanUseFroidurePin(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 (9.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.
actingthis 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-2). 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.
regularthis 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.
hashlenthis 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).
smallif 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_thresholdthis 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 13.7 for more information about the "kernel and trace" method.
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-5.3.7/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(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>
‣ 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
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:
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.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).
‣ 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); <bipartition semigroup of size 11, degree 6 with 2 generators> -> <transformation semigroup of size 11, degree 12 with 2 generators> gap> IsomorphismSemigroup(IsBooleanMatSemigroup, S); <bipartition semigroup of size 11, degree 6 with 2 generators> -> <semigroup of size 11, 12x12 boolean matrices with 2 generators> gap> IsomorphismSemigroup(IsFpSemigroup, S); <bipartition semigroup of size 11, degree 6 with 2 generators> -> <fp semigroup with 2 generators and 5 relations of length 27> 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); <inverse partial perm semigroup of rank 10 with 2 generators> -> <inverse bipartition semigroup of degree 10 with 2 generators> gap> S := SymmetricInverseMonoid(4); <symmetric inverse monoid of degree 4> gap> IsomorphismSemigroup(IsBlockBijectionSemigroup, S); <symmetric inverse monoid of degree 4> -> <inverse block bijection monoid of degree 5 with 3 generators> gap> Size(Range(last)); 209 gap> S := Semigroup([ > PartialPerm([3, 1]), PartialPerm([1, 3, 4])]);; gap> IsomorphismSemigroup(IsBlockBijectionSemigroup, S); <partial perm semigroup of rank 3 with 2 generators> -> <block bijection semigroup of degree 5 with 2 generators>
‣ 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 (12.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 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); <transformation semigroup of degree 10 with 2 generators> -> <transformation monoid of degree 8 with 2 generators> gap> IsomorphismMonoid(IsBooleanMatMonoid, S); <transformation semigroup of degree 10 with 2 generators> -> <monoid of 8x8 boolean matrices with 2 generators> gap> IsomorphismMonoid(IsFpMonoid, S); <transformation semigroup of degree 10 with 2 generators> -> <fp monoid with 2 generators and 17 relations of length 278>
‣ 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
‣ 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 (12.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 (12.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 (11.13-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 (12.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); <Rees 0-matrix semigroup 3x3 over Group(())> -> <Rees 0-matrix semigroup 3x3 over Group(())> 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 (12.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); <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> -> <Rees matrix semigroup 3x3 over Sym( [ 1 .. 4 ] )> 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) ] ]
‣ IsomorphismReesMatrixSemigroup( S ) | ( attribute ) |
‣ IsomorphismReesZeroMatrixSemigroup( S ) | ( attribute ) |
‣ IsomorphismReesMatrixSemigroupOverPermGroup( S ) | ( attribute ) |
‣ IsomorphismReesZeroMatrixSemigroupOverPermGroup( S ) | ( attribute ) |
Returns: An isomorphism.
If the semigroup S is finite and simple, then IsomorphismReesMatrixSemigroup returns an isomorphism to a Rees matrix semigroup over some group (usually a permutation group), and IsomorphismReesMatrixSemigroupOverPermGroup returns an isomorphism to a Rees matrix semigroup over a permutation group.
If S is finite and 0-simple, then IsomorphismReesZeroMatrixSemigroup returns an isomorphism to a Rees 0-matrix semigroup over some group (usually a permutation group), and IsomorphismReesZeroMatrixSemigroupOverPermGroup returns an isomorphism to a Rees 0-matrix semigroup over a permutation group.
See also InjectionPrincipalFactor (10.4-7).
gap> S := Semigroup(PartialPerm([1])); <trivial partial perm group of rank 1 with 1 generator> gap> iso := IsomorphismReesMatrixSemigroup(S);; gap> Source(iso) = S; true gap> Range(iso); <Rees matrix semigroup 1x1 over Group(())> gap> S := Semigroup(PartialPerm([1]), PartialPerm([])); <partial perm monoid of rank 1 with 2 generators> gap> Range(IsomorphismReesZeroMatrixSemigroup(S)); <Rees 0-matrix semigroup 1x1 over Group(())>
‣ AntiIsomorphismDualFpSemigroup( S ) | ( attribute ) |
‣ AntiIsomorphismDualFpMonoid( S ) | ( attribute ) |
Returns: A finitely presented semigroup or monoid.
AntiIsomorphismDualFpSemigroup returns an anti-isomorphism (MappingByFunction (Reference: MappingByFunction)) from the finitely presented semigroup S to another finitely presented semigroup. The range finitely presented semigroup is obtained from S by reversing the relations of S.
AntiIsomorphismDualFpMonoid works analogously when S is a finitely presented monoid, and the range of the returned anti-isomorphism is a finitely presented monoid.
gap> F := FreeSemigroup("a", "b"); <free semigroup on the generators [ a, b ]> gap> AssignGeneratorVariables(F); gap> R := [[a ^ 3, a], [b ^ 2, b], [(a * b) ^ 2, a]]; [ [ a^3, a ], [ b^2, b ], [ (a*b)^2, a ] ] gap> S := F / R; <fp semigroup with 2 generators and 3 relations of length 14> gap> map := AntiIsomorphismDualFpSemigroup(S); MappingByFunction( <fp semigroup with 2 generators and 3 relations of length 14>, <fp semigroup with 2 generators and 3 relations of length 14> , function( x ) ... end, function( x ) ... end ) gap> RelationsOfFpSemigroup(Range(map)); [ [ a^3, a ], [ b^2, b ], [ (b*a)^2, a ] ]
‣ EmbeddingFpMonoid( S ) | ( attribute ) |
Returns: A finitely presented monoid.
EmbeddingFpMonoid returns an embedding (SemigroupHomomorphismByImages (14.1-1)) from the finitely presented semigroup S into a finitely presented monoid. If S satisfies IsMonoidAsSemigroup (12.1-13), then the mapping returned by this function is an isomorphism (the same isomorphism as IsomorphismFpMonoid (Reference: IsomorphismFpMonoid)). If S is not a monoid, then the range is isomorphic to S with an identity adjoined (a new element not previously in S). The embedded copy of S in the range can be recovered using Image (Reference: Image).
gap> F := FreeSemigroup("a", "b"); <free semigroup on the generators [ a, b ]> gap> AssignGeneratorVariables(F); gap> R := [[a ^ 3, a], [b ^ 2, b], [(a * b) ^ 2, a]]; [ [ a^3, a ], [ b^2, b ], [ (a*b)^2, a ] ] gap> S := F / R; <fp semigroup with 2 generators and 3 relations of length 14> gap> Size(S); 3 gap> IsMonoidAsSemigroup(S); false gap> map := EmbeddingFpMonoid(S); <fp semigroup with 2 generators and 3 relations of length 14> -> <fp monoid with 2 generators and 3 relations of length 14> gap> Size(Range(map)); 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):
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:
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!):
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 generator>> 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>
generated by GAPDoc2HTML