Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

4 Green's Relations
 4.1 Introduction
 4.2 Data Structures
  4.2-1 GreensData

  4.2-2 GreensRClassData

  4.2-3 GreensLClassData

  4.2-4 GreensHClassData

  4.2-5 GreensDClassData

  4.2-6 IsGreensData

  4.2-7 XClassData

  4.2-8 IsGreensXClassDataRep

  4.2-9 IsAssociatedSemigpTransSemigp

  4.2-10 SchutzenbergerGroup

  4.2-11 Idempotents

  4.2-12 PartialOrderOfDClasses

4 Green's Relations

4.1 Introduction

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.

4.2 Data Structures

4.2-1 GreensData
> GreensData( C )( operation )

4.2-2 GreensRClassData
> 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:

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

4.2-3 GreensLClassData
> 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:

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

4.2-4 GreensHClassData
> 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:

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

4.2-5 GreensDClassData
> 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:

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

4.2-6 IsGreensData
> 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.

4.2-7 XClassData
> 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).

4.2-8 IsGreensXClassDataRep
> 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.

4.2-9 IsAssociatedSemigpTransSemigp
> 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

4.2-10 SchutzenbergerGroup
> 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) ])

4.2-11 Idempotents
> 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 ] ) ]

4.2-12 PartialOrderOfDClasses
> 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.

 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML