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:
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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
  
  --    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.
  
  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:
  
  --    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].
  
  ---------------------------  Example  ----------------------------
    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:
  
  --    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].
  
  ---------------------------  Example  ----------------------------
    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:
  
  --    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].
  
  ---------------------------  Example  ----------------------------
    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:
  
  --    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].
  
  ---------------------------  Example  ----------------------------
    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.
  
  ---------------------------  Example  ----------------------------
    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.
  
  ---------------------------  Example  ----------------------------
    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.
  
  ---------------------------  Example  ----------------------------
    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
  
  ---------------------------  Example  ----------------------------
    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.