This chapter contains instructions on how to use the functions for computing Green's relations and related notions for transformation semigroups and monoids that are implemented in MONOID.
The theory behind these algorithms is developed in [LPRR98] and the algorithms themselves are described in [LPRR02]. Another reference is [LM90].
Green's relations can be calculated when MONOID is loaded using the same commands that you would used when MONOID is not loaded; see Reference: Semigroups. For example, in GAP with the MONOID package loaded:
gap> a:=Transformation([2,1,1,2,1]);; gap> b:=Transformation([3,4,3,4,4]);; gap> c:=Transformation([3,4,3,4,3]);; gap> d:=Transformation([4,3,3,4,4]);; gap> S:=Semigroup(a,b,c,d); <semigroup with 4 generators> gap> GreensRClasses(S); [ {Transformation( [ 2, 1, 1, 2, 1 ] )}, {Transformation( [ 1, 2, 1, 2, 2 ] )} , {Transformation( [ 1, 2, 1, 2, 1 ] )}, {Transformation( [ 2, 1, 1, 2, 2 ] )} ] |
Without the MONOID package loaded:
gap> a:=Transformation([2,1,1,2,1]);; gap> b:=Transformation([3,4,3,4,4]);; gap> c:=Transformation([3,4,3,4,3]);; gap> d:=Transformation([4,3,3,4,4]);; gap> S:=Semigroup(a,b,c,d); <semigroup with 4 generators> gap> GreensRClasses(S); [ {Transformation( [ 1, 2, 1, 2, 1 ] )}, {Transformation( [ 1, 2, 1, 2, 2 ] )} , {Transformation( [ 1, 2, 2, 1, 1 ] )}, {Transformation( [ 1, 2, 2, 1, 2 ] )} ] |
The only noticable differences are the representatives of the classes and the order the classes appear in the list. These differences are caused by the differences in the methods for GreensRClasses
in MONOID and the GAP library.
Most of the commands in this section relate to how Green's relations are calculated in MONOID. Although some of the commands might be used for other purposes, if all that is required is to calculate Green's classes, relations and so on, then this is done in the exactly the same way as described in the GAP manual; see Reference: Green's Relations.
Due to inherent difficulties with computing Green's L- and D-classes, the methods used to compute with Green's R-classes are the most efficient in MONOID. Thus wherever possible it is advisable to use the commands relating to Green's R-classes rather than those relating to Green's L-classes, D-classes, or H-classes.
For small examples of semigroups, say with fewer than 40 elements, it may be more efficient to use the methods from the library than those in MONOID. This stems from the fact that there are higher overheads in the methods used in MONOID. In either case, with such small examples computing Green's relations does not take much time.
The methods in MONOID allow the computation of individual Green's classes without the need to compute all the elements of the underlying semigroup. It is also possible to compute all the R-classes, the number of elements and test membership in a transformation semigroup without computing all the elements. This may be useful if you want to study a very large semigroup where computing all the elements of the semigroup is infeasible.
> GreensData ( C ) | ( operation ) |
if C
satisfies IsGreensRClass
(Reference: IsGreensRClass), then GreensData
returns the value of GreensRClassData
(4.2-2) with argument C
.
if C
satisfies IsGreensLClass
(Reference: IsGreensLClass), then GreensData
returns the value of GreensLClassData
(4.2-3) with argument C
.
if C
satisfies IsGreensHClass
(Reference: IsGreensHClass), then GreensData
returns the value of GreensHClassData
(4.2-4) with argument C
.
if C
satisfies IsGreensDClass
(Reference: IsGreensDClass), then GreensData
returns the value of GreensDClassData
(4.2-5) with argument C
.
> GreensRClassData ( C ) | ( attribute ) |
if C
satisfies IsGreensRClass
(Reference: IsGreensRClass), then GreensRClassData
returns an object in the category IsGreensRClassData
(4.2-6) with representation IsGreensRClassDataRep
(4.2-8) and the following four components:
rep
the representative of the R-class.
strongorb
the strong orbit of the image of rep
under the action of the semigroup on sets.
perms
a list of permutations that map the image of rep
to the corresponding image in strongorb
, that is, OnSets(strongorb[i], perms[i])=strongorb[1]
.
schutz
the group of permutations arising from elements of the semigroup that stabilise the image of rep
(called the (generalized) right Schutzenberger group).
The components strongorb
, perms
, and schutz
are obtained using the function StrongOrbitOfImage
(3.4-5). Further details can be found in Algorithm C, D, E, F, and U of [LPRR02].
gap> a:=Transformation( [ 2, 1, 4, 5, 6, 3 ] );; gap> b:=Transformation( [ 2, 3, 1, 5, 4, 1 ] );; gap> M:=Semigroup(a,b);; gap> rc:=GreensRClassOfElement(M, a*b*a); {Transformation( [ 4, 1, 6, 5, 2, 2 ] )} gap> GreensRClassData(rc); GreensRClassData( Transformation( [ 4, 1, 6, 5, 2, 2 ] ), [ [ 1, 2, 4, 5, 6 ], [ 1, 2, 3, 5, 6 ], [ 1, 2, 3, 4, 6 ], [ 1, 2, 3, 4, 5 ] ], [ (), (1,2) (3,6,5,4), (3,5)(4,6), (1,6,3,2)(4,5) ], Group( [ (), (2,4,6), (2,6,4), (1,2,6)(4,5) ] ) ) |
> GreensLClassData ( S, f ) | ( attribute ) |
if C
satisfies IsGreensLClass
(Reference: IsGreensLClass), then GreensLClassData
returns an object in the category IsGreensLClassData
(4.2-6) with representation IsGreensLClassDataRep
(4.2-8) and the following five components:
rep
the representative of the L-class.
strongorb
the strong orbit of the kernel of rep
under the action of the semigroup by OnTuplesOfSetsAntiAction
(3.2-1).
relts
a list of relations such that
KernelOfTransformation(relts[i]*x)=strongorb[1]
whenever x
has
KernelOfTransformation(x)=strongorb[i].
invrelts
the inverses of the relations relts
, so that
KernelOfTransformation(invrelts[i]*rep)=strongorb[i].
schutz
the (generalised) left Schutzenberger group.
Further details can be found in Algorithm G, H, I, and J of [LPRR02].
gap> gens:=[ Transformation( [ 4, 1, 4, 5, 3 ] ), > Transformation( [ 5, 3, 5, 4, 3 ] ) ];; gap> S:=Semigroup(gens);; gap> C:=GreensLClassOfElement(S, gens[1]*gens[2]*gens[1]); {Transformation( [ 5, 3, 5, 4, 3 ] )} gap> GreensLClassData(C); GreensLClassData( Transformation( [ 5, 3, 5, 4, 3 ] ), [ [ [ 1, 3 ], [ 2, 5 ], [ 4 ] ] ], [ Binary Relation on 5 points ], [ Binary Relation on 5 points ], Group( [ (), (3,5,4), (3,5) ] ) ) |
> GreensHClassData ( S, f ) | ( attribute ) |
if C
satisfies IsGreensHClass
(Reference: IsGreensHClass), then GreensLClassData
returns an object in the category IsGreensHClassData
(4.2-6) with representation IsGreensHClassDataRep
(4.2-8) and the following two components:
rep
the representative of the H-class.
schutz
the intersection of the left Schutzenberger group and right Schutzenberger group of the L-class and R-class containing the representative rep
(that is, the intersection of the schutz
component of GreensRClassData
(4.2-2) and the schutz
component of GreensLClassData
(4.2-3)).
Further details can be found in Algorithm K, L, M, and N of [LPRR02].
gap> gens:=[ Transformation( [ 2, 2, 5, 2, 3 ] ), > Transformation( [ 2, 5, 3, 5, 3 ] ) ];; gap> S:=Semigroup(gens);; gap> f:=Transformation( [ 5, 5, 3, 5, 3 ] );; gap> GreensHClassData(GreensHClassOfElement(S, f)); GreensHClassData( Transformation( [ 5, 5, 3, 5, 3 ] ), Group( () ) ) |
> GreensDClassData ( S, f ) | ( attribute ) |
if C
satisfies IsGreensDClass
(Reference: IsGreensDClass), then GreensDClassData
returns an object in the category IsGreensDClassData
(4.2-6) with representation IsGreensDClassDataRep
(4.2-8) and the following five components:
rep
the representative of the D-class.
R
the result of GreensRClassData
(4.2-2) with argument rep
.
L
the result of GreensLClassData
(4.2-3) with argument rep
.
H
the result of GreensHClassData
(4.2-4) with argument rep
.
cosets
a transversal of right cosets of the Schutzenberger group of H
in the Schutzenberger group of R
.
Note that only the first three components are displayed. Further details can be found in Algorithm O, P, Q, R, S, and T of [LPRR02].
gap> gens:=[ Transformation( [ 4, 1, 5, 2, 4 ] ), > Transformation( [ 4, 4, 1, 5, 3 ] ) ];; gap> S:=Semigroup(gens);; gap> f:=Transformation( [ 5, 5, 3, 3, 3 ] );; gap> GreensDClassData(GreensDClassOfElement(S, f)); GreensDClassData( Transformation( [ 5, 5, 3, 3, 3 ] ), GreensRClassData( Transformation( [ 5, 5, 3, 3, 3 ] ) ), GreensLClassData( Transformation( [ 5, 5, 3, 3, 3 ] ) ) ) |
> IsGreensData ( obj ) | ( category ) |
> IsGreensRClassData ( obj ) | ( category ) |
> IsGreensLClassData ( obj ) | ( category ) |
> IsGreensHClassData ( obj ) | ( category ) |
> IsGreensDClassData ( obj ) | ( category ) |
returns true
if obj
lies in the category IsGreensData
, IsGreensRClassData
, IsGreensLClassData
, IsGreensHClassData
, IsGreensDClassData
, respectively. The objects created using the functions RClassData
(4.2-7), LClassData
(4.2-7), HClassData
(4.2-7), and DClassData
(4.2-7) lie in the categories IsGreensRClassData
, IsGreensLClassData
, IsGreensHClassData
, IsGreensDClassData
, respectively, and all these categories are contained in the category IsGreensData
.
> RClassData ( rec ) | ( function ) |
> LClassData ( rec ) | ( function ) |
> HClassData ( rec ) | ( function ) |
> DClassData ( rec ) | ( function ) |
These function construct objects in the categories IsGreensRClassData
(4.2-6), IsGreensLClassData
(4.2-6), IsGreensHClassData
(4.2-6), and IsGreensDClassData
(4.2-6) subcategories of IsGreensData
(4.2-6) using the output from GreensRClassData
(4.2-2), GreensLClassData
(4.2-3), GreensHClassData
(4.2-4), GreensDClassData
(4.2-5).
> IsGreensRClassDataRep ( obj ) | ( representation ) |
> IsGreensLClassDataRep ( obj ) | ( representation ) |
> IsGreensHClassDataRep ( obj ) | ( representation ) |
> IsGreensDClassDataRep ( obj ) | ( representation ) |
returns true
if obj
has IsGreensRClassDataRep
, IsGreensLClassDataRep
, IsGreensHClassDataRep
, or IsGreensDClassDataRep
, respectively as a representation.
These representations each have several components detailed in GreensRClassData
(4.2-2), GreensLClassData
(4.2-3), GreensHClassData
(4.2-4), GreensDClassData
(4.2-5), respectively.
> IsAssociatedSemigpTransSemigp ( C ) | ( property ) |
returns true
if C
is a Green's class of a transformation semigroup and returns false
otherwise.
This attribute is required so that a Green's class knowns that it belongs to a transformation semigroup, so that the methods defined in the MONOID are used in preference to those in the library.
gap> a:=Transformation( [ 2, 1, 4, 5, 6, 3 ] );; gap> b:=Transformation( [ 2, 3, 1, 5, 4, 1 ] );; gap> M:=Semigroup(a,b);; gap> GreensLClassOfElement(M,a); {Transformation( [ 2, 1, 4, 5, 6, 3 ] )} gap> IsAssociatedSemigpTransSemigp(last); true gap> f:=FreeSemigroup(3);; gap> a:=f.1;; b:=f.2;; c:=f.3;; gap> s:=f/[[a^2, a], [b^2,b], [c^2,c], [a*b,a], [b*a,b], [a*c,a], > [c*a,c], [b*c,b],[c*b,c]]; <fp semigroup on the generators [ s1, s2, s3 ]> gap> Size(s); 3 gap> GreensLClassOfElement(s,a); {s1} gap> IsAssociatedSemigpTransSemigp(last); false |
> SchutzenbergerGroup ( D ) | ( attribute ) |
if D
satisfies IsGreensRClassData
(4.2-6), IsGreensLClassData
(4.2-6), IsGreensHClassData
(4.2-6), or IsGreensDClassData
(4.2-6), then SchutzenbergerGroup
returns the schutz
component of D
.
If D
satisfies IsGreensRClass
(Reference: IsGreensRClass), IsGreensLClass
(Reference: IsGreensLClass), IsGreensHClass
(Reference: IsGreensHClass), IsGreensDClass
(Reference: IsGreensDClass), then SchutzenbergerGroup
returns the schutz
component of GreensData
with argument D
.
gap> gens:=[ Transformation( [ 4, 4, 3, 5, 3 ] ), > Transformation( [ 5, 1, 1, 4, 1 ] ), > Transformation( [ 5, 5, 4, 4, 5 ] ) ];; gap> f:=Transformation( [ 4, 5, 5, 5, 5 ] );; gap> SchutzenbergerGroup(GreensDClassOfElement(S, f)); Group([ (), (4,5) ]) gap> SchutzenbergerGroup(GreensRClassOfElement(S, f)); Group([ (), (4,5) ]) gap> SchutzenbergerGroup(GreensLClassOfElement(S, f)); Group([ (), (4,5) ]) gap> SchutzenbergerGroup(GreensHClassOfElement(S, f)); Group([ (), (4,5) ]) |
> Idempotents ( X[, n] ) | ( function ) |
returns a list of the idempotents in the transformation semigroup or Green's class X
.
If the optional second argument n
is present, then a list of the idempotents in S
of rank n
is returned. If you are only interested in the idempotents of a given rank, then the second version of the function will likely be faster.
gap> S:=Semigroup([ Transformation( [ 2, 3, 4, 1 ] ), > Transformation( [ 3, 3, 1, 1 ] ) ]);; gap> Idempotents(S, 1); [ ] gap> Idempotents(S, 2); [ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ] gap> Idempotents(S, 3); [ ] gap> Idempotents(S, 4); [ Transformation( [ 1, 2, 3, 4 ] ) ] gap> Idempotents(S); [ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 2, 3, 4 ] ), Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ] |
> PartialOrderOfDClasses ( S ) | ( attribute ) |
returns the partial order of the D
-classes of S
as a directed graph in GRAPE, if it is installed, using the command
Graph(Group(()), [1..Length(GreensDClasses(S))], OnPoints, function(x,y) return y in poset[x]; end, true); ; |
where y
in poset[x]
if and only if S^1yS^1
is a subset of S^1 xS^1
.
If GRAPE is not loaded, then the list poset
is returned instead.
generated by GAPDoc2HTML