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

11 Green's relations
 11.1 Creating Green's classes and representatives
 11.2 Iterators and enumerators of classes and representatives
 11.3 Properties of Green's classes
 11.4 Attributes of Green's classes
 11.5 Visualising the Green's structure

11 Green's relations

In this chapter we describe the functions in Semigroups for computing Green's classes and related properties of semigroups.

11.1 Creating Green's classes and representatives

In this section, we describe the methods in the Semigroups package for creating Green's classes.

11.1-1 XClassOfYClass
‣ DClassOfHClass( class )( method )
‣ DClassOfLClass( class )( method )
‣ DClassOfRClass( class )( method )
‣ LClassOfHClass( class )( method )
‣ RClassOfHClass( class )( method )

Returns: A Green's class.

XClassOfYClass returns the X-class containing the Y-class class where X and Y should be replaced by an appropriate choice of D, H, L, and R.

Note that if it is not known to GAP whether or not the representative of class is an element of the semigroup containing class, then no attempt is made to check this.

The same result can be produced using:

First(GreensXClasses(S), x-> Representative(x) in class);

but this might be substantially slower. Note that XClassOfYClass is also likely to be faster than

GreensXClassOfElement(S, Representative(class));

DClass can also be used as a synonym for DClassOfHClass, DClassOfLClass, and DClassOfRClass; LClass as a synonym for LClassOfHClass; and RClass as a synonym for RClassOfHClass. See also GreensDClassOfElement (Reference: GreensDClassOfElement) and GreensDClassOfElementNC (11.1-3).

gap> S := Semigroup(Transformation( [ 1, 3, 2 ] ), 
> Transformation( [ 2, 1, 3 ] ), Transformation( [ 3, 2, 1 ] ), 
> Transformation( [ 1, 3, 1 ] ) );;
gap> R := GreensRClassOfElement(S, Transformation( [ 3, 2, 1 ] ));
<Green's R-class: Transformation( [ 3, 2, 1 ] )>
gap> DClassOfRClass(R);
<Green's D-class: Transformation( [ 3, 2, 1 ] )>
gap> IsGreensDClass(DClassOfRClass(R));
true
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 ]));
<inverse partial perm semigroup on 10 pts with 2 generators>
gap> x := S.1;
[3,7][8,1,2,6,9][10,5]
gap> H := HClass(S, x);
<Green's H-class: [3,7][8,1,2,6,9][10,5]>
gap> R := RClassOfHClass(H);
<Green's R-class: [3,7][8,1,2,6,9][10,5]>
gap> L := LClass(H);
<Green's L-class: <identity partial perm on [ 1, 2, 5, 6, 7, 9 ]>>
gap> DClass(R) = DClass(L);
true
gap> DClass(H) = DClass(L);
true

11.1-2 GreensXClassOfElement
‣ GreensDClassOfElement( X, f )( operation )
‣ DClass( X, f )( function )
‣ GreensHClassOfElement( X, f )( operation )
‣ GreensHClassOfElement( R, i, j )( operation )
‣ HClass( X, f )( function )
‣ HClass( R, i, j )( function )
‣ GreensLClassOfElement( X, f )( operation )
‣ LClass( X, f )( function )
‣ GreensRClassOfElement( X, f )( operation )
‣ RClass( X, f )( function )

Returns: A Green's class.

These functions produce essentially the same output as the GAP library functions with the same names; see GreensDClassOfElement (Reference: GreensDClassOfElement). The main difference is that these functions can be applied to a wider class of objects:

GreensDClassOfElement and DClass

X must be a semigroup.

GreensHClassOfElement and HClass

X can be a semigroup, \(\mathscr{R}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{D}\)-class.

If R is a IxJ Rees matrix semigroup or a Rees 0-matrix semigroup, and i and j are integers of the corresponding index sets, then GreensHClassOfElement returns the \(\mathscr{H}\)-class in row i and column j.

GreensLClassOfElement and LClass

X can be a semigroup or \(\mathscr{D}\)-class.

GreensRClassOfElement and RClass

X can be a semigroup or \(\mathscr{D}\)-class.

Note that GreensXClassOfElement and XClass are synonyms and have identical output. The shorter command is provided for the sake of convenience.

11.1-3 GreensXClassOfElementNC
‣ GreensDClassOfElementNC( X, f )( operation )
‣ DClassNC( X, f )( function )
‣ GreensHClassOfElementNC( X, f )( operation )
‣ HClassNC( X, f )( function )
‣ GreensLClassOfElementNC( X, f )( operation )
‣ LClassNC( X, f )( function )
‣ GreensRClassOfElementNC( X, f )( operation )
‣ RClassNC( X, f )( function )

Returns: A Green's class.

These functions are essentially the same as GreensDClassOfElement (11.1-2) except that no effort is made to verify if f is an element of X. More precisely, GreensXClassOfElementNC and XClassNC first check if f has already been shown to be an element of X. If it is not known to GAP if f is an element of X, then no further attempt to verify this is made.

Note that GreensXClassOfElementNC and XClassNC are synonyms and have identical output. The shorter command is provided for the sake of convenience.

It can be quicker to compute the class of an element using GreensRClassOfElementNC, say, than using GreensRClassOfElement if it is known a priori that f is an element of X. On the other hand, if f is not an element of X, then the results of this computation are unpredictable.

For example, if

x := Transformation( [ 15, 18, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 ] );

in the semigroup X of order-preserving mappings on 20 points, then

GreensRClassOfElementNC(X, x);

returns an answer relatively quickly, whereas

GreensRClassOfElement(X, x)

can take a signficant amount of time to return a value.

See also GreensRClassOfElement (Reference: GreensRClassOfElement) and RClassOfHClass (11.1-1).

gap> S := RandomTransformationSemigroup(2,1000);;
gap> x := [ 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1 ];;
gap> x := EvaluateWord(Generators(S), x);;                            
gap> R := GreensRClassOfElementNC(S, x);;
gap> Size(R);
1
gap> L := GreensLClassOfElementNC(S, x);;
gap> Size(L);
1
gap> x := PartialPerm([ 1, 2, 3, 4, 7, 8, 9, 10 ],
> [ 2, 3, 4, 5, 6, 8, 10, 11 ]);;
gap> L := LClass(POI(13), x);
<Green's L-class: [1,2,3,4,5,6,8,11][7,10]>
gap> Size(L);
1287

11.1-4 GreensXClasses
‣ GreensDClasses( obj )( method )
‣ DClasses( obj )( method )
‣ GreensHClasses( obj )( method )
‣ HClasses( obj )( method )
‣ GreensJClasses( obj )( method )
‣ JClasses( obj )( method )
‣ GreensLClasses( obj )( method )
‣ LClasses( obj )( method )
‣ GreensRClasses( obj )( method )
‣ RClasses( obj )( method )

Returns: A list of Green's classes.

These functions produce essentially the same output as the GAP library functions with the same names; see GreensDClasses (Reference: GreensDClasses). The main difference is that these functions can be applied to a wider class of objects:

GreensDClasses and DClasses

X should be a semigroup.

GreensHClasses and HClasses

X can be a semigroup, \(\mathscr{R}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{D}\)-class.

GreensLClasses and LClasses

X can be a semigroup or \(\mathscr{D}\)-class.

GreensRClasses and RClasses

X can be a semigroup or \(\mathscr{D}\)-class.

Note that GreensXClasses and XClasses are synonyms and have identical output. The shorter command is provided for the sake of convenience.

See also DClassReps (11.1-5), IteratorOfDClassReps (11.2-1), IteratorOfDClasses (11.2-2), and NrDClasses (11.1-9).

gap> S := Semigroup(Transformation( [ 3, 4, 4, 4 ] ),
> Transformation( [ 4, 3, 1, 2 ] ));;
gap> GreensDClasses(S);
[ <Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>, 
  <Green's D-class: Transformation( [ 4, 3, 1, 2 ] )>, 
  <Green's D-class: Transformation( [ 4, 4, 4, 4 ] )> ]
gap> GreensRClasses(S);
[ <Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 3, 1, 2 ] )>, 
  <Green's R-class: Transformation( [ 4, 4, 4, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 4, 3, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 3, 4, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 4, 4, 3 ] )> ]
gap> D := GreensDClasses(S)[1];
<Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> GreensLClasses(D);
[ <Green's L-class: Transformation( [ 3, 4, 4, 4 ] )>, 
  <Green's L-class: Transformation( [ 1, 2, 2, 2 ] )> ]
gap> GreensRClasses(D);
[ <Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 4, 3, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 3, 4, 4 ] )>, 
  <Green's R-class: Transformation( [ 4, 4, 4, 3 ] )> ]
gap> R := GreensRClasses(D)[1];
<Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> GreensHClasses(R);
[ <Green's H-class: Transformation( [ 3, 4, 4, 4 ] )>, 
  <Green's H-class: Transformation( [ 1, 2, 2, 2 ] )> ]
gap> S := InverseSemigroup( PartialPerm( [ 1, 2, 3 ], [ 2, 4, 1 ] ),
> PartialPerm( [ 1, 3, 4 ], [ 3, 4, 1 ] ) );;
gap> GreensDClasses(S);
[ <Green's D-class: <identity partial perm on [ 1, 2, 4 ]>>, 
  <Green's D-class: <identity partial perm on [ 1, 3, 4 ]>>, 
  <Green's D-class: <identity partial perm on [ 2, 4 ]>>, 
  <Green's D-class: <identity partial perm on [ 4 ]>>, 
  <Green's D-class: <empty partial perm>> ]
gap> GreensLClasses(S);
[ <Green's L-class: <identity partial perm on [ 1, 2, 4 ]>>, 
  <Green's L-class: [4,2,1,3]>, 
  <Green's L-class: <identity partial perm on [ 1, 3, 4 ]>>, 
  <Green's L-class: <identity partial perm on [ 2, 4 ]>>, 
  <Green's L-class: [2,3][4,1]>, <Green's L-class: [4,2,1]>, 
  <Green's L-class: [4,2,3]>, <Green's L-class: [2,4,3]>, 
  <Green's L-class: [2,1](4)>, 
  <Green's L-class: <identity partial perm on [ 4 ]>>, 
  <Green's L-class: [4,1]>, <Green's L-class: [4,3]>, 
  <Green's L-class: [4,2]>, <Green's L-class: <empty partial perm>> ]
gap> D := GreensDClasses(S)[3];
<Green's D-class: <identity partial perm on [ 2, 4 ]>>
gap> GreensLClasses(D);
[ <Green's L-class: <identity partial perm on [ 2, 4 ]>>, 
  <Green's L-class: [2,3][4,1]>, <Green's L-class: [4,2,1]>, 
  <Green's L-class: [4,2,3]>, <Green's L-class: [2,4,3]>, 
  <Green's L-class: [2,1](4)> ]
gap> GreensRClasses(D);
[ <Green's R-class: <identity partial perm on [ 2, 4 ]>>, 
  <Green's R-class: [1,4][3,2]>, <Green's R-class: [1,2,4]>, 
  <Green's R-class: [3,2,4]>, <Green's R-class: [3,4,2]>, 
  <Green's R-class: [1,2](4)> ]

11.1-5 XClassReps
‣ DClassReps( obj )( attribute )
‣ HClassReps( obj )( attribute )
‣ LClassReps( obj )( attribute )
‣ RClassReps( obj )( attribute )

Returns: A list of representatives.

XClassReps returns a list of the representatives of the Green's classes of obj, which can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-class where appropriate.

The same output can be obtained by calling, for example:

List(GreensXClasses(obj), Representative);

Note that if the Green's classes themselves are not required, then XClassReps will return an answer more quickly than the above, since the Green's class objects are not created.

See also GreensDClasses (11.1-4), IteratorOfDClassReps (11.2-1), IteratorOfDClasses (11.2-2), and NrDClasses (11.1-9).

gap> S := Semigroup(Transformation( [ 3, 4, 4, 4 ] ),
> Transformation( [ 4, 3, 1, 2 ] ));;
gap> DClassReps(S);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 4, 3, 1, 2 ] ), 
  Transformation( [ 4, 4, 4, 4 ] ) ]
gap> LClassReps(S);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ), 
  Transformation( [ 4, 3, 1, 2 ] ), Transformation( [ 4, 4, 4, 4 ] ), 
  Transformation( [ 2, 2, 2, 2 ] ), Transformation( [ 3, 3, 3, 3 ] ), 
  Transformation( [ 1, 1, 1, 1 ] ) ]
gap> D := GreensDClasses(S)[1];
<Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> LClassReps(D);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ) ]
gap> RClassReps(D);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 4, 4, 3, 4 ] ), 
  Transformation( [ 4, 3, 4, 4 ] ), Transformation( [ 4, 4, 4, 3 ] ) ]
gap> R := GreensRClasses(D)[1];;
gap> HClassReps(R);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ) ]
gap> S := SymmetricInverseSemigroup(6);;
gap> e := InverseSemigroup(Idempotents(S));;
gap> M := MunnSemigroup(e);;
gap> DClassReps(M);
[ <identity partial perm on [ 51 ]>, 
  <identity partial perm on [ 27, 51 ]>, 
  <identity partial perm on [ 15, 27, 50, 51 ]>, 
  <identity partial perm on [ 8, 15, 26, 27, 49, 50, 51, 64 ]>, 
  <identity partial perm on 
    [ 4, 8, 14, 15, 25, 26, 27, 48, 49, 50, 51, 60, 61, 62, 63, 64 ]>,
  <identity partial perm on 
    [ 2, 4, 7, 8, 13, 14, 15, 21, 25, 26, 27, 29, 34, 39, 44, 48, 49, \
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 ]>, 
  <identity partial perm on 
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1\
9, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,\
 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 5\
4, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 ]> ]
gap> L := LClassNC(M, PartialPerm( [ 51, 63 ], [ 51, 47 ] ));;
gap> HClassReps(L);
[ <identity partial perm on [ 47, 51 ]>, [27,47](51), [50,47](51), 
  [59,47](51), [63,47](51), [64,47](51) ]

11.1-6 MinimalDClass
‣ MinimalDClass( S )( attribute )

Returns: The minimal \(\mathscr{D}\)-class of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment. MinimalDClass returns the \(\mathscr{D}\)-class corresponding to the minimal ideal of the semigroup S. Equivalently, MinimalDClass returns the minimal \(\mathscr{D}\)-class with respect to the partial order of \(\mathscr{D}\)-classes.

It is significantly easier to find the minimal \(\mathscr{D}\)-class of a semigroup, than to find its \(\mathscr{D}\)-classes.

See also PartialOrderOfDClasses (11.1-10), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), MinimalIdeal (12.4-1) and RepresentativeOfMinimalIdeal (12.4-2).

gap> D := MinimalDClass(JonesMonoid(8));
<Green's D-class: <bipartition: [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], 
  [ 7, 8 ], [ -1, -2 ], [ -3, -4 ], [ -5, -6 ], [ -7, -8 ]>>
gap> S := InverseSemigroup( 
> PartialPerm( [ 1, 2, 3, 5, 7, 8, 9 ], [ 2, 6, 9, 1, 5, 3, 8 ] ), 
> PartialPerm( [ 1, 3, 4, 5, 7, 8, 9 ], [ 9, 4, 10, 5, 6, 7, 1 ] ) );;
gap> MinimalDClass(S);
<Green's D-class: <empty partial perm>>

11.1-7 MaximalDClasses
‣ MaximalDClasses( S )( attribute )

Returns: The maximal \(\mathscr{D}\)-classes of a semigroup.

MaximalDClasses returns the maximal \(\mathscr{D}\)-classes with respect to the partial order of \(\mathscr{D}\)-classes.

See also PartialOrderOfDClasses (11.1-10), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and MinimalDClass (11.1-6).

gap> MaximalDClasses(BrauerMonoid(8));
[ <Green's D-class: <block bijection: [ 1, -1 ], [ 2, -2 ], 
      [ 3, -3 ], [ 4, -4 ], [ 5, -5 ], [ 6, -6 ], [ 7, -7 ], 
      [ 8, -8 ]>> ]
gap> MaximalDClasses(FullTransformationMonoid(5));
[ <Green's D-class: IdentityTransformation> ]
gap> S := Semigroup( 
> PartialPerm( [ 1, 2, 3, 4, 5, 6, 7 ], [ 3, 8, 1, 4, 5, 6, 7 ] ), 
> PartialPerm( [ 1, 2, 3, 6, 8 ], [ 2, 6, 7, 1, 5 ] ), 
> PartialPerm( [ 1, 2, 3, 4, 6, 8 ], [ 4, 3, 2, 7, 6, 5 ] ), 
> PartialPerm( [ 1, 2, 4, 5, 6, 7, 8 ], [ 7, 1, 4, 2, 5, 6, 3 ] ) );;
gap> MaximalDClasses(S);
[ <Green's D-class: [2,8](1,3)(4)(5)(6)(7)>, 
  <Green's D-class: [8,3](1,7,6,5,2)(4)> ]

11.1-8 NrRegularDClasses
‣ NrRegularDClasses( S )( attribute )
‣ RegularDClasses( S )( attribute )

Returns: A positive integer, or a list.

NrRegularDClasses returns the number of regular \(\mathscr{D}\)-classes of the semigroup S.

RegularDClasses returns a list of the regular \(\mathscr{D}\)-classes of the semigroup S.

See also IsRegularClass (11.3-2) and IsRegularDClass (Reference: IsRegularDClass).

gap> S := Semigroup( [ Transformation( [ 1, 3, 4, 1, 3, 5 ] ), 
> Transformation( [ 5, 1, 6, 1, 6, 3 ] ) ]);;
gap> NrRegularDClasses(S); 
3
gap> NrDClasses(S); 
7
gap> RegularDClasses(S);
[ <Green's D-class: Transformation( [ 1, 4, 1, 1, 4, 3 ] )>, 
  <Green's D-class: Transformation( [ 1, 1, 1, 1, 1, 4 ] )>, 
  <Green's D-class: Transformation( [ 1, 1, 1, 1, 1, 1 ] )> ]

11.1-9 NrXClasses
‣ NrDClasses( obj )( attribute )
‣ NrHClasses( obj )( attribute )
‣ NrLClasses( obj )( attribute )
‣ NrRClasses( obj )( attribute )

Returns: A positive integer.

NrXClasses returns the number of Green's classes in obj where obj can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-class where appropriate. If the actual Green's classes are not required, then it is more efficient to use

NrHClasses(obj)

than

Length(HClasses(obj))

since the Green's classes themselves are not created when NrXClasses is called.

See also GreensRClasses (11.1-4), GreensRClasses (Reference: GreensRClasses), IteratorOfRClasses (11.2-2), and IteratorOfRClassReps (11.2-1).

gap> gens := [ Transformation( [ 1, 2, 5, 4, 3, 8, 7, 6 ] ),
>   Transformation( [ 1, 6, 3, 4, 7, 2, 5, 8 ] ),
>   Transformation( [ 2, 1, 6, 7, 8, 3, 4, 5 ] ),
>   Transformation( [ 3, 2, 3, 6, 1, 6, 1, 2 ] ),
>   Transformation( [ 5, 2, 3, 6, 3, 4, 7, 4 ] ) ];;
gap> S := Semigroup(gens);;
gap> x := Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] );;
gap> R := RClass(S, x);
<Green's R-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(R);
12
gap> D := DClass(R);
<Green's D-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(D);
72
gap> L := LClass(S, x);
<Green's L-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(L);
6
gap> NrHClasses(S);
1555
gap> gens := [ Transformation( [ 4, 6, 5, 2, 1, 3 ] ),
>   Transformation( [ 6, 3, 2, 5, 4, 1 ] ),
>   Transformation( [ 1, 2, 4, 3, 5, 6 ] ),
>   Transformation( [ 3, 5, 6, 1, 2, 3 ] ),
>   Transformation( [ 5, 3, 6, 6, 6, 2 ] ),
>   Transformation( [ 2, 3, 2, 6, 4, 6 ] ),
>   Transformation( [ 2, 1, 2, 2, 2, 4 ] ),
>   Transformation( [ 4, 4, 1, 2, 1, 2 ] ) ];;
gap> S := Semigroup(gens);;
gap> NrRClasses(S);
150
gap> Size(S);
6342
gap> x := Transformation( [ 1, 3, 3, 1, 3, 5 ] );;
gap> D := DClass(S, x);
<Green's D-class: Transformation( [ 2, 4, 2, 2, 2, 1 ] )>
gap> NrRClasses(D);
87
gap> S := SymmetricInverseSemigroup(10);;
gap> NrDClasses(S); NrRClasses(S); NrHClasses(S); NrLClasses(S);
11
1024
184756
1024
gap> S := POPI(10);;
gap> NrDClasses(S);
11
gap> NrRClasses(S);
1024

11.1-10 PartialOrderOfDClasses
‣ PartialOrderOfDClasses( S )( attribute )

Returns: The partial order of the \(\mathscr{D}\)-classes of S.

Returns a list list where list[i] contains every j such that GreensDClasses(S)[j] is immediately less than GreensDClasses(S)[i] in the partial order of \(\mathscr{D}\)- classes of S. There might be other indices in list, and it may or may not include i. The reflexive transitive closure of the relation defined by list is the partial order of \(\mathscr{D}\)-classes of S.

The partial order on the \(\mathscr{D}\)-classes is defined by x≤ y if and only if S^1xS^1 is a subset of S^1yS^1.

See also GreensDClasses (11.1-4), GreensDClasses (Reference: GreensDClasses), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and \< (11.3-1).

gap> S := Semigroup( Transformation( [ 2, 4, 1, 2 ] ), 
> Transformation( [ 3, 3, 4, 1 ] ) );;
gap> PartialOrderOfDClasses(S);
[ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ]
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[1], GreensDClasses(S)[2]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[2], GreensDClasses(S)[1]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[3], GreensDClasses(S)[1]);
true
gap> S := InverseSemigroup( PartialPerm( [ 1, 2, 3 ], [ 1, 3, 4 ] ),
> PartialPerm( [ 1, 3, 5 ], [ 5, 1, 3 ] ) );;
gap> Size(S);
58
gap> PartialOrderOfDClasses(S);              
[ [ 1, 3 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5 ] ]
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[1], GreensDClasses(S)[2]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[5], GreensDClasses(S)[2]);
true
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[3], GreensDClasses(S)[4]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[4], GreensDClasses(S)[3]);
true

11.1-11 IsGreensDLeq
‣ IsGreensDLeq( S )( attribute )

Returns: A function.

IsGreensDLeq(S) returns a function func such that for any two elements x and y of S, func(x, y) return true if the \(\mathscr{D}\)-class of x in S is greater than or equal to the \(\mathscr{D}\)-class of y in S under the usual ordering of Green's \(\mathscr{D}\)-classes of a semigroup.

gap> S := Semigroup( [ Transformation( [ 1, 3, 4, 1, 3 ] ), 
>  Transformation( [ 2, 4, 1, 5, 5 ] ), 
>  Transformation( [ 2, 5, 3, 5, 3 ] ), 
>  Transformation( [ 5, 5, 1, 1, 3 ] ) ] );;
gap> reps := ShallowCopy(DClassReps(S));
[ Transformation( [ 1, 3, 4, 1, 3 ] ), 
  Transformation( [ 2, 4, 1, 5, 5 ] ), 
  Transformation( [ 1, 4, 1, 1, 4 ] ), 
  Transformation( [ 1, 1, 1, 1, 1 ] ) ]
gap> Sort(reps, IsGreensDLeq(S));
gap> reps;
[ Transformation( [ 2, 4, 1, 5, 5 ] ), 
  Transformation( [ 1, 3, 4, 1, 3 ] ), 
  Transformation( [ 1, 4, 1, 1, 4 ] ), 
  Transformation( [ 1, 1, 1, 1, 1 ] ) ]
gap> IsGreensLessThanOrEqual(DClass(S, reps[2]), DClass(S, reps[1]));
true
gap> S := DualSymmetricInverseMonoid(4);;
gap> IsGreensDLeq(S)(S.1, S.3);                      
true
gap> IsGreensDLeq(S)(S.3, S.1);
false
gap> IsGreensLessThanOrEqual(DClass(S, S.3), DClass(S, S.1));
true
gap> IsGreensLessThanOrEqual(DClass(S, S.1), DClass(S, S.3));
false

11.2 Iterators and enumerators of classes and representatives

In this section, we describe the methods in the Semigroups package for incrementally determining Green's classes or their representatives.

11.2-1 IteratorOfXClassReps
‣ IteratorOfDClassReps( S )( function )
‣ IteratorOfHClassReps( S )( function )
‣ IteratorOfLClassReps( S )( function )
‣ IteratorOfRClassReps( S )( function )

Returns: An iterator.

Returns an iterator of the representatives of the Green's classes contained in the semigroup S. See Reference: Iterators for more information on iterators.

See also GreensRClasses (Reference: GreensRClasses), GreensRClasses (11.1-4), and IteratorOfRClasses (11.2-2).

gap> gens := [ Transformation( [ 3, 2, 1, 5, 4 ] ), 
> Transformation( [ 5, 4, 3, 2, 1 ] ), 
> Transformation( [ 5, 4, 3, 2, 1 ] ), Transformation( [ 5, 5, 4, 5, 1 ] ), 
> Transformation( [ 4, 5, 4, 3, 3 ] ) ];;
gap> S := Semigroup(gens);;
gap> iter := IteratorOfRClassReps(S);
<iterator of R-class reps>
gap> NextIterator(iter);
Transformation( [ 3, 2, 1, 5, 4 ] )
gap> NextIterator(iter);
Transformation( [ 5, 5, 4, 5, 1 ] )
gap> iter;
<iterator of R-class reps>
gap> file := Concatenation(SemigroupsDir(), "/tst/test.gz");;
gap> S := InverseSemigroup(ReadGenerators(file, 1377));
<inverse partial perm semigroup on 983 pts with 2 generators>
gap> NrMovedPoints(S);
983
gap> iter := IteratorOfLClassReps(S);
<iterator of L-class reps>
gap> NextIterator(iter);
<partial perm on 634 pts with degree 1000, codegree 1000>

11.2-2 IteratorOfXClasses
‣ IteratorOfDClasses( S )( function )
‣ IteratorOfHClasses( S )( function )
‣ IteratorOfLClasses( S )( function )
‣ IteratorOfRClasses( S )( function )

Returns: An iterator.

Returns an iterator of the Green's classes in the semigroup S. See Reference: Iterators for more information on iterators.

This function is useful if you are, for example, looking for an \(\mathscr{R}\)-class of a semigroup with a particular property but do not necessarily want to compute all of the \(\mathscr{R}\)-classes.

See also GreensRClasses (11.1-4), GreensRClasses (Reference: GreensRClasses), NrRClasses (11.1-9), and IteratorOfRClassReps (11.2-1).

The transformation semigroup in the example below has 25147892 elements but it only takes a fraction of a second to find a non-trivial \(\mathscr{R}\)-class. The inverse semigroup of partial permutations in the example below has size 158122047816 but it only takes a fraction of a second to find an \(\mathscr{R}\)-class with more than 1000 elements.

gap> gens := [ Transformation( [ 2, 4, 1, 5, 4, 4, 7, 3, 8, 1 ] ),
>   Transformation( [ 3, 2, 8, 8, 4, 4, 8, 6, 5, 7 ] ),
>   Transformation( [ 4, 10, 6, 6, 1, 2, 4, 10, 9, 7 ] ),
>   Transformation( [ 6, 2, 2, 4, 9, 9, 5, 10, 1, 8 ] ),
>   Transformation( [ 6, 4, 1, 6, 6, 8, 9, 6, 2, 2 ] ),
>   Transformation( [ 6, 8, 1, 10, 6, 4, 9, 1, 9, 4 ] ),
>   Transformation( [ 8, 6, 2, 3, 3, 4, 8, 6, 2, 9 ] ),
>   Transformation( [ 9, 1, 2, 8, 1, 5, 9, 9, 9, 5 ] ),
>   Transformation( [ 9, 3, 1, 5, 10, 3, 4, 6, 10, 2 ] ),
>   Transformation( [ 10, 7, 3, 7, 1, 9, 8, 8, 4, 10 ] ) ];;
gap> S := Semigroup(gens);;
gap> iter := IteratorOfRClasses(S);
<iterator of R-classes>
gap> for R in iter do
> if Size(R)>1 then break; fi;
> od;
gap> R;
<Green's R-class: Transformation( [ 6, 4, 1, 6, 6, 8, 9, 6, 2, 2 ] )>
gap> Size(R);
21600
gap> S := InverseSemigroup(
> [ PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 10, 11, 19, 20 ], 
> [ 19, 4, 11, 15, 3, 20, 1, 14, 8, 13, 17 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 17 ], 
> [ 15, 14, 20, 19, 4, 5, 1, 13, 11, 10, 3 ] ),
>  PartialPerm( [ 1, 2, 4, 6, 7, 8, 9, 10, 14, 15, 18 ], 
> [ 7, 2, 17, 10, 1, 19, 9, 3, 11, 16, 18 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16 ], 
> [ 8, 3, 18, 1, 4, 13, 12, 7, 19, 20, 2, 11 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 9, 11, 15, 16, 17, 20 ], 
> [ 7, 17, 13, 4, 6, 9, 18, 10, 11, 19, 5, 2, 8 ] ),
>  PartialPerm( [ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 18 ], 
> [ 10, 20, 11, 7, 13, 8, 4, 9, 2, 18, 17, 6, 15 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 17, 18 ], 
> [ 10, 20, 18, 1, 14, 16, 9, 5, 15, 4, 8, 12, 19, 11 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 15, 16, 19, 20 ], 
> [ 13, 6, 1, 2, 11, 7, 16, 18, 9, 10, 4, 14, 15, 5, 17 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 20 ], 
> [ 5, 3, 12, 9, 20, 15, 8, 16, 13, 1, 17, 11, 14, 10, 2 ] ),
>  PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 17, 18, 19, 20 ], 
> [ 8, 3, 9, 20, 2, 12, 14, 15, 4, 18, 13, 1, 17, 19, 5 ] ) ]);;
gap> iter := IteratorOfRClasses(S);
<iterator of R-classes>
gap> repeat r := NextIterator(iter); until Size(r)>1000;
gap> r;
<Green's R-class: [8,3][11,5][13,1][15,2][17,6][19,7]>
gap> Size(r);
10020240

11.3 Properties of Green's classes

In this section, we describe the properties and operators of Green's classes that are available in the Semigroups package

11.3-1 Less than for Green's classes
‣ \<( left-expr, right-expr )( method )

Returns: true or false.

The Green's class left-expr is less than or equal to right-expr if they belong to the same semigroup and the representative of left-expr is less than the representative of right-expr under <; see also Representative (Reference: Representative).

Please note that this is not the usual order on the Green's classes of a semigroup as defined in Reference: Green's Relations. See also IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual).

gap> S := FullTransformationSemigroup(4);;
gap> A := GreensRClassOfElement(S, Transformation( [ 2, 1, 3, 1 ] ));
<Green's R-class: Transformation( [ 2, 1, 3, 1 ] )>
gap> B := GreensRClassOfElement(S, Transformation( [ 1, 2, 3, 4 ] ));
<Green's R-class: IdentityTransformation>
gap> A < B;
false
gap> B < A;
true
gap> IsGreensLessThanOrEqual(A,B);
true
gap> IsGreensLessThanOrEqual(B,A);
false
gap> S := SymmetricInverseSemigroup(4);;
gap> A := GreensJClassOfElement(S, PartialPerm([ 1 .. 3 ], [ 1, 3, 4 ]) );
<Green's D-class: <identity partial perm on [ 1, 2, 3 ]>>
gap> B := GreensJClassOfElement(S, PartialPerm([ 1, 2 ], [ 3, 1 ]) );
<Green's D-class: <identity partial perm on [ 1, 2 ]>>
gap> A < B;
false
gap> B < A;
true
gap> IsGreensLessThanOrEqual(A, B);
false
gap> IsGreensLessThanOrEqual(B, A);
true

11.3-2 IsRegularClass
‣ IsRegularClass( class )( property )

Returns: true or false.

This function returns true if class is a regular Green's class and false if it is not. See also IsRegularDClass (Reference: IsRegularDClass), IsGroupHClass (Reference: IsGroupHClass), GroupHClassOfGreensDClass (Reference: GroupHClassOfGreensDClass), GroupHClass (11.4-1), NrIdempotents (12.6-2), Idempotents (12.6-1), and IsRegularSemigroupElement (Reference: IsRegularSemigroupElement).

The function IsRegularDClass produces the same output as the GAP library functions with the same name; see IsRegularDClass (Reference: IsRegularDClass).

gap> S := Monoid(Transformation( [ 10, 8, 7, 4, 1, 4, 10, 10, 7, 2 ] ),
> Transformation( [ 5, 2, 5, 5, 9, 10, 8, 3, 8, 10 ] ));;
gap> f := Transformation( [ 1, 1, 10, 8, 8, 8, 1, 1, 10, 8 ] );;
gap> R := RClass(S, f);;
gap> IsRegularClass(R);
true
gap> S := Monoid(Transformation([2,3,4,5,1,8,7,6,2,7]), 
> Transformation( [ 3, 8, 7, 4, 1, 4, 3, 3, 7, 2 ] ));;
gap> f := Transformation( [ 3, 8, 7, 4, 1, 4, 3, 3, 7, 2 ] );;
gap> R := RClass(S, f);;
gap> IsRegularClass(R);
false
gap> NrIdempotents(R);
0
gap> S := Semigroup(Transformation( [ 2, 1, 3, 1 ] ), 
> Transformation( [ 3, 1, 2, 1 ] ), Transformation( [ 4, 2, 3, 3 ] ));;
gap> f := Transformation( [ 4, 2, 3, 3 ] );;
gap> L := GreensLClassOfElement(S, f);;
gap> IsRegularClass(L);
false
gap> R := GreensRClassOfElement(S, f);;
gap> IsRegularClass(R);
false
gap> g := Transformation( [ 4, 4, 4, 4 ] );;
gap> IsRegularSemigroupElement(S, g);
true
gap> IsRegularClass(LClass(S, g));
true
gap> IsRegularClass(RClass(S, g));
true
gap> IsRegularDClass(DClass(S, g));
true
gap> DClass(S, g)=RClass(S, g);
true

11.3-3 IsGreensClassNC
‣ IsGreensClassNC( class )( property )

Returns: true or false.

A Green's class class of a semigroup S satisfies IsGreensClassNC if it was not known to GAP that the representative of class was an element of S at the point that class was created.

11.3-4 IsTransformationSemigroupGreensClass
‣ IsTransformationSemigroupGreensClass( class )( property )

Returns: true or false.

A Green's class class of a semigroup S satisfies the property IsTransformationSemigroupGreensClass if and only if S is a semigroup of transformations.

11.3-5 IsBipartitionSemigroupGreensClass
‣ IsBipartitionSemigroupGreensClass( class )( property )

Returns: true or false.

A Green's class class of a semigroup S satisfies the property IsBipartitionSemigroupGreensClass if and only if S is a semigroup of bipartitions.

11.3-6 IsPartialPermSemigroupGreensClass
‣ IsPartialPermSemigroupGreensClass( class )( property )

Returns: true or false.

A Green's class class of a semigroup S satisfies the property IsPartialPermSemigroupGreensClass if and only if S is a semigroup of partial perms.

11.4 Attributes of Green's classes

In this section, we describe the attributes of Green's classes that are available in the Semigroups package

11.4-1 GroupHClass
‣ GroupHClass( class )( attribute )

Returns: A group \(\mathscr{H}\)-class of the \(\mathscr{D}\)-class class if it is regular and fail if it is not.

GroupHClass is a synonym for GroupHClassOfGreensDClass (Reference: GroupHClassOfGreensDClass).

See also IsGroupHClass (Reference: IsGroupHClass), IsRegularDClass (Reference: IsRegularDClass), IsRegularClass (11.3-2), and IsRegularSemigroup (14.1-14).

gap> S := Semigroup( Transformation( [ 2, 6, 7, 2, 6, 1, 1, 5 ] ), 
> Transformation( [ 3, 8, 1, 4, 5, 6, 7, 1 ] ) );;
gap> IsRegularSemigroup(S);
false
gap> iter := IteratorOfDClasses(S);;
gap> repeat D := NextIterator(iter); until IsRegularDClass(D);   
gap> D;
<Green's D-class: Transformation( [ 6, 1, 1, 6, 1, 2, 2, 6 ] )>
gap> NrIdempotents(D);
12
gap> NrRClasses(D);
8
gap> NrLClasses(D);
4
gap> GroupHClass(D);
<Green's H-class: Transformation( [ 1, 2, 2, 1, 2, 6, 6, 1 ] )>
gap> GroupHClassOfGreensDClass(D);
<Green's H-class: Transformation( [ 1, 2, 2, 1, 2, 6, 6, 1 ] )>
gap> StructureDescription(GroupHClass(D));
"S3"
gap> repeat D := NextIterator(iter); until not IsRegularDClass(D);
gap> D;
<Green's D-class: Transformation( [ 7, 5, 2, 2, 6, 1, 1, 2 ] )>
gap> IsRegularDClass(D);
false
gap> GroupHClass(D);
fail
gap> S := InverseSemigroup( [ PartialPerm( [ 1, 2, 3, 5 ], [ 2, 1, 6, 3 ] ),
> PartialPerm( [ 1, 2, 3, 6 ], [ 3, 5, 2, 6 ] ) ]);;
gap> x := PartialPerm([ 1 .. 3 ], [ 6, 3, 1 ]);;
gap> First(DClasses(S), x-> not IsTrivial(GroupHClass(x)));
<Green's D-class: <identity partial perm on [ 1, 2 ]>>
gap> StructureDescription(GroupHClass(last));
"C2"

11.4-2 SchutzenbergerGroup
‣ SchutzenbergerGroup( class )( attribute )

Returns: A permutation group.

SchutzenbergerGroup returns the generalized Schutzenberger group (defined below) of the \(\mathscr{R}\)-, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{H}\)-class class.

If f is an element of a semigroup of transformations or partial permutations and im(f) denotes the image of f, then the generalized Schutzenberger group of im(f) is the permutation group

\{\:g|_{\textrm{im}(f)}\::\:\textrm{im}(f*g)=\textrm{im}(f)\:\}.

The generalized Schutzenberger group of the kernel ker(f) of a transformation f or the domain dom(f) of a partial permutation f is defined analogously.

The generalized Schutzenberger group of a Green's class is then defined as follows.

\(\mathscr{R}\)-class

The generalized Schutzenberger group of the image or range of the representative of the \(\mathscr{R}\)-class.

\(\mathscr{L}\)-class

The generalized Schutzenberger group of the kernel or domain of the representative of the \(\mathscr{L}\)-class.

\(\mathscr{H}\)-class

The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the \(\mathscr{H}\)-class.

\(\mathscr{D}\)-class

The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the representative of the \(\mathscr{D}\)-class.

gap> S := Semigroup( Transformation( [ 4, 4, 3, 5, 3 ] ), 
> Transformation( [ 5, 1, 1, 4, 1 ] ), 
> Transformation( [ 5, 5, 4, 4, 5 ] ) );;
gap> f := Transformation( [ 5, 5, 4, 4, 5 ] );;
gap> SchutzenbergerGroup(RClass(S, f));
Group([ (4,5) ])
gap> S := InverseSemigroup(
> [ PartialPerm([ 1, 2, 3, 7 ], [ 9, 2, 4, 8 ]),
> PartialPerm([ 1, 2, 6, 7, 8, 9, 10 ], [ 6, 8, 4, 5, 9, 1, 3 ]),
> PartialPerm([ 1, 2, 3, 5, 6, 7, 8, 9 ], [ 7, 4, 1, 6, 9, 5, 2, 3 ]) ] );;
gap> List(DClasses(S), SchutzenbergerGroup);
[ Group(()), Group(()), Group(()), Group(()), Group([ (1,9,8), (8,
   9) ]), Group([ (4,9) ]), Group(()), Group(()), Group(()), 
  Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), 
  Group(()), Group([ (2,5)(3,7) ]), Group([ (1,7,5,6,9,3) ]), 
  Group(()), Group(()), Group(()), Group(()), Group(()) ]

11.4-3 StructureDescriptionSchutzenbergerGroups
‣ StructureDescriptionSchutzenbergerGroups( S )( attribute )

Returns: Distinct structure descriptions of the Schutzenberger groups of a semigroup.

StructureDescriptionSchutzenbergerGroups returns the distinct values of StructureDescription (Reference: StructureDescription) when it is applied to the Schutzenberger groups of the \(\mathscr{R}\)-classes of the semigroup S.

gap> S:=Semigroup( PartialPerm( [ 1, 2, 3 ], [ 2, 5, 4 ] ), 
>  PartialPerm( [ 1, 2, 3 ], [ 4, 1, 2 ] ), 
>  PartialPerm( [ 1, 2, 3 ], [ 5, 2, 3 ] ), 
>  PartialPerm( [ 1, 2, 4, 5 ], [ 2, 1, 4, 3 ] ), 
>  PartialPerm( [ 1, 2, 5 ], [ 2, 3, 5 ] ), 
>  PartialPerm( [ 1, 2, 3, 5 ], [ 2, 3, 5, 4 ] ), 
>  PartialPerm( [ 1, 2, 3, 5 ], [ 4, 2, 5, 1 ] ), 
>  PartialPerm( [ 1, 2, 3, 5 ], [ 5, 2, 4, 3 ] ), 
>  PartialPerm( [ 1, 2, 5 ], [ 5, 4, 3 ] ) );;
gap> StructureDescriptionSchutzenbergerGroups(S);            
[ "1", "C2", "S3" ]
gap> S:=Monoid( 
> Bipartition([[ 1, 2, 5, -1, -2 ], [ 3, 4, -3, -5 ], [ -4 ]]), 
> Bipartition([[ 1, 2, -2 ], [ 3, -1 ], [ 4 ], [ 5 ], [ -3, -4 ], [ -5 ]]),
> Bipartition([[ 1 ], [ 2, 3, -5 ], [ 4, -3 ], [ 5, -2 ], [ -1, -4 ]]));
<bipartition monoid on 5 pts with 3 generators>
gap> StructureDescriptionSchutzenbergerGroups(S);
[ "1", "C2" ]

11.4-4 StructureDescriptionMaximalSubgroups
‣ StructureDescriptionMaximalSubgroups( S )( attribute )

Returns: Distinct structure descriptions of the maximal subgroups of a semigroup.

StructureDescriptionMaximalSubgroups returns the distinct values of StructureDescription (Reference: StructureDescription) when it is applied to the maximal subgroups of the semigroup S.

gap> S := DualSymmetricInverseSemigroup(6);
<inverse bipartition monoid on 6 pts with 3 generators>
gap> StructureDescriptionMaximalSubgroups(S);
[ "1", "C2", "S3", "S4", "S5", "S6" ]
gap> S := Semigroup( PartialPerm( [ 1, 3, 4, 5, 8 ], [ 8, 3, 9, 4, 5 ] ), 
>  PartialPerm( [ 1, 2, 3, 4, 8 ], [ 10, 4, 1, 9, 6 ] ), 
>  PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 10 ], [ 4, 1, 6, 7, 5, 3, 2, 10 ] ), 
>  PartialPerm( [ 1, 2, 3, 4, 6, 8, 10 ], [ 4, 9, 10, 3, 1, 5, 2 ] ) );;
gap> StructureDescriptionMaximalSubgroups(S);
[ "1", "C2", "C3", "C4" ]

11.4-5 MultiplicativeNeutralElement
‣ MultiplicativeNeutralElement( H )( method )

Returns: A semigroup element or fail.

If the \(\mathscr{H}\)-class H of a semigroup S is a subgroup of S, then MultiplicativeNeutralElement returns the identity of H. If H is not a subgroup of S, then fail is returned.

gap> S := Semigroup( 
>  PartialPerm( [ 1, 2, 3 ], [ 1, 5, 2 ] ), 
>  PartialPerm( [ 1, 3 ], [ 2, 4 ] ), 
>  PartialPerm( [ 1, 2, 3 ], [ 4, 1, 5 ] ), 
>  PartialPerm( [ 1, 3, 5 ], [ 1, 3, 4 ] ), 
>  PartialPerm( [ 1, 2, 4, 5 ], [ 1, 2, 3, 5 ] ), 
>  PartialPerm( [ 1, 2, 3, 5 ], [ 1, 3, 2, 5 ] ), 
>  PartialPerm( [ 1, 4, 5 ], [ 5, 4, 3 ] ) );;
gap> H := HClass(S, PartialPerm( [ 1, 2 ], [ 1, 2 ] ));;
gap> MultiplicativeNeutralElement(H);
<identity partial perm on [ 1, 2 ]>
gap> H := HClass(S, PartialPerm( [ 1, 2 ], [ 1, 4 ] ));;
gap> MultiplicativeNeutralElement(H);
fail

11.4-6 StructureDescription
‣ StructureDescription( class )( attribute )

Returns: A string or fail.

StructureDescription returns the value of StructureDescription (Reference: StructureDescription) when it is applied to a group isomorphic to the group \(\mathscr{H}\)-class class. If class is not a group \(\mathscr{H}\)-class, then fail is returned.

gap> S := Semigroup( 
> PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 9 ], [ 1, 9, 4, 3, 5, 2, 10, 7 ] ), 
> PartialPerm( [ 1, 2, 4, 7, 8, 9 ], [ 6, 2, 4, 9, 1, 3 ] ) );;
gap> H := HClass(S, 
> PartialPerm( [ 1, 2, 3, 4, 7, 9 ], [ 1, 7, 3, 4, 9, 2 ] ));;
gap> StructureDescription(H);
"C6"

11.4-7 InjectionPrincipalFactor
‣ InjectionPrincipalFactor( D )( attribute )
‣ IsomorphismReesMatrixSemigroup( D )( attribute )

Returns: A injective mapping.

If the \(\mathscr{D}\)-class D is a subsemigroup of a semigroup S, then the principal factor of D is just D itself. If D is not a subsemigroup of S, then the principal factor of D is the semigroup with elements D and a new element 0 with multiplication of x,y∈ D defined by:

xy=\left\{\begin{array}{ll} x*y\ (\textrm{in }S)&\textrm{if }x*y\in D\\ 0&\textrm{if }xy\not\in D. \end{array}\right.

InjectionPrincipalFactor returns an injective function from the \(\mathscr{D}\)-class D to a Rees (0-)matrix semigroup, which contains the principal factor of D as a subsemigroup.

If D is a subsemigroup of its parent semigroup, then the function returned by InjectionPrincipalFactor or IsomorphismReesMatrixSemigroup is an isomorphism from D to a Rees matrix semigroup; see ReesMatrixSemigroup (Reference: ReesMatrixSemigroup).

If D is not a semigroup, then the function returned by InjectionPrincipalFactor is an injective function from D to a Rees 0-matrix semigroup isomorphic to the principal factor of D; see ReesZeroMatrixSemigroup (Reference: ReesZeroMatrixSemigroup). In this case, IsomorphismReesMatrixSemigroup and IsomorphismReesZeroMatrixSemigroup returns an error.

See also PrincipalFactor (11.4-8).

    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> x := PartialPerm([ 1, 2, 5, 6, 7, 9 ], [ 1, 2, 5, 6, 7, 9 ]);;
    gap> d := GreensDClassOfElement(S, x);
    <Green's D-class: <identity partial perm on [ 1, 2, 5, 6, 7, 9 ]>>
    gap> InjectionPrincipalFactor(d);;
    gap> rms := Range(last);
    <Rees 0-matrix semigroup 3x3 over Group(())>
    gap> MatrixOfReesZeroMatrixSemigroup(rms);
    [ [ (), 0, 0 ], [ 0, (), 0 ], [ 0, 0, () ] ]
    gap> Size(rms);
    10
    gap> Size(d);
    9
    gap> S := Semigroup(
    > Bipartition( [ [ 1, 2, 3, -3, -5 ], [ 4 ], [ 5, -2 ], [ -1, -4 ] ] ), 
    > Bipartition( [ [ 1, 3, 5 ], [ 2, 4, -3 ], [ -1, -2, -4, -5 ] ] ), 
    > Bipartition( [ [ 1, 5, -2, -4 ], [ 2, 3, 4, -1, -5 ], [ -3 ] ] ), 
    > Bipartition( [ [ 1, 5, -1, -2, -3 ], [ 2, 4, -4 ], [ 3, -5 ] ] ) );;
    gap> D := DClasses(S)[3];
    <Green's D-class: <bipartition: [ 1, 5, -2, -4 ], [ 2, 3, 4, -1, -5 ]
       , [ -3 ]>>
    gap> inj := InjectionPrincipalFactor(D);
    MappingByFunction( <Green's D-class: <bipartition: [ 1, 5, -2, -4 ], 
      [ 2, 3, 4, -1, -5 ], [ -3 ]>>, <Rees matrix semigroup 1x1 over 
      Group([ (1,2) ])>, function( f ) ... end, function( x ) ... end )

11.4-8 PrincipalFactor
‣ PrincipalFactor( D )( attribute )

Returns: A Rees matrix semigroup.

PrincipalFactor(D) is just shorthand for Range(InjectionPrincipalFactor(D)), where D is a \(\mathscr{D}\)-class of semigroup; see InjectionPrincipalFactor (11.4-7) for more details.

gap> S := Semigroup([ PartialPerm( [ 1, 2, 3 ], [ 1, 3, 4 ] ), 
>  PartialPerm( [ 1, 2, 3 ], [ 2, 5, 3 ] ), 
>  PartialPerm( [ 1, 2, 3, 4 ], [ 2, 4, 1, 5 ] ), 
>  PartialPerm( [ 1, 3, 5 ], [ 5, 1, 3 ] ) ] );;
gap> PrincipalFactor(MinimalDClass(S));
<Rees matrix semigroup 1x1 over Group(())>
gap> MultiplicativeZero(S);
<empty partial perm>
gap> S := Semigroup(
> Bipartition( [ [ 1, 2, 3, 4, 5, -1, -3 ], [ -2, -5 ], [ -4 ] ] ), 
> Bipartition( [ [ 1, -5 ], [ 2, 3, 4, 5, -1, -3 ], [ -2, -4 ] ] ), 
> Bipartition( [ [ 1, 5, -4 ], [ 2, 4, -1, -5 ], [ 3, -2, -3 ] ] ) );;
gap> D := MinimalDClass(S);    
<Green's D-class: <bipartition: [ 1, 2, 3, 4, 5, -1, -3 ], 
  [ -2, -5 ], [ -4 ]>>
gap> PrincipalFactor(D);
<Rees matrix semigroup 1x5 over Group(())>

11.5 Visualising the Green's structure

In this section, we describe some functions for creating pictures of various structural properties of a semigroup.

Several of the functions described in this section return a string, which can be written to a file using the function FileString (GAPDoc: FileString) or viewed using Splash (11.5-1).

11.5-1 Splash
‣ Splash( str[, opts] )( function )

Returns: Nothing.

This function attempts to convert the string str into a pdf document and open this document, i.e. to splash it all over your monitor.

The string str must correspond to a valid dot or LaTeX text file and you must have have GraphViz and pdflatex installed on your computer. For details about these file formats, see http://www.latex-project.org and http://www.graphviz.org.

This function is provided to allow convenient, immediate viewing of the pictures produced by the functions: TikzBlocks (3.8-2), TikzBipartition (3.8-1), DotSemilatticeOfIdempotents (11.5-3), and DotDClasses (11.5-2).

The optional second argument opts should be a record with components corresponding to various options, given below.

path

this should be a string representing the path to the directory where you want Splash to do its work. The default value of this option is "~/".

directory

this should be a string representing the name of the directory in path where you want Splash to do its work. This function will create this directory if does not already exist.

The default value of this option is "tmp.viz" if the option path is present, and the result of DirectoryTemporary (Reference: DirectoryTemporary) is used otherwise.

filename

this should be a string representing the name of the file where str will be written. The default value of this option is "vizpicture".

viewer

this should be a string representing the name of the program which should open the files produced by GraphViz or pdflatex.

type

this option can be used to specify that the string str contains a LaTeX or dot document. You can specify this option in str directly by making the first line "%latex" or "//dot". There is no default value for this option, this option must be specified in str or in opt.type.

filetype

this should be a string representing the type of file which Splash should produce. For LaTeX files, this option is ignored and the default value "pdf" is used.

This function was written by Attila Egri-Nagy and Manuel Delgado with some minor changes by J. D. Mitchell.

        gap> Splash(DotDClasses(FullTransformationMonoid(4)));

11.5-2 DotDClasses
‣ DotDClasses( S )( attribute )
‣ DotDClasses( S, record )( operation )

Returns: A string.

This function produces a graphical representation of the partial order of the \(\mathscr{D}\)-classes of the semigroup S together with the eggbox diagram of each \(\mathscr{D}\)-class. The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see http://www.graphviz.org.

The string returned by DotDClasses can be written to a file using the command FileString (GAPDoc: FileString).

The \(\mathscr{D}\)-classes are shown as eggbox diagrams with \(\mathscr{L}\)-classes as rows and \(\mathscr{R}\)-classes as columns; group \(\mathscr{H}\)-classes are shaded gray and contain an asterisk. The \(\mathscr{D}\)-classes are numbered according to their index in GreensDClasses(S), so that an i appears next to the eggbox diagram of GreensDClasses(S)[i]. A red line from one \(\mathscr{D}\)-class to another indicates that the higher \(\mathscr{D}\)-class is greater than the lower one in the \(\mathscr{D}\)-order on S.

If the optional second argument record is present, it can be used to specify some options for output.

number

if record.number is false, then the \(\mathscr{D}\)-classes in the diagram are not numbered according to their index in the list of \(\mathscr{D}\)-classes of S. The default value for this option is true.

maximal

if record.maximal is true, then the structure description of the group \(\mathscr{H}\)-classes is displayed; see StructureDescription (Reference: StructureDescription). Setting this attribute to true can adversely affect the performance of DotDClasses. The default value for this option is false.

gap> S:=FullTransformationSemigroup(3);
<full transformation semigroup on 3 pts>
gap> DotDClasses(S);        
"digraph  DClasses {\nnode [shape=plaintext]\nedge [color=red,arrowhe\
ad=none]\n1 [shape=box style=dotted label=<\n<TABLE BORDER=\"0\" CELL\
BORDER=\"1\" CELLPADDING=\"10\" CELLSPACING=\"0\" PORT=\"1\">\n<TR BO\
RDER=\"0\"><TD COLSPAN=\"1\" BORDER=\"0\" >1</TD></TR><TR><TD BGCOLOR\
=\"grey\">*</TD></TR>\n</TABLE>>];\n2 [shape=box style=dotted label=<\
\n<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLPADDING=\"10\" CELLSPACING\
=\"0\" PORT=\"2\">\n<TR BORDER=\"0\"><TD COLSPAN=\"3\" BORDER=\"0\" >\
2</TD></TR><TR><TD BGCOLOR=\"grey\">*</TD><TD BGCOLOR=\"grey\">*</TD>\
<TD></TD></TR>\n<TR><TD BGCOLOR=\"grey\">*</TD><TD></TD><TD BGCOLOR=\
\"grey\">*</TD></TR>\n<TR><TD></TD><TD BGCOLOR=\"grey\">*</TD><TD BGC\
OLOR=\"grey\">*</TD></TR>\n</TABLE>>];\n3 [shape=box style=dotted lab\
el=<\n<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLPADDING=\"10\" CELLSPA\
CING=\"0\" PORT=\"3\">\n<TR BORDER=\"0\"><TD COLSPAN=\"1\" BORDER=\"0\
\" >3</TD></TR><TR><TD BGCOLOR=\"grey\">*</TD></TR>\n<TR><TD BGCOLOR=\
\"grey\">*</TD></TR>\n<TR><TD BGCOLOR=\"grey\">*</TD></TR>\n</TABLE>>\
];\n1 -> 2\n2 -> 3\n }"
gap> FileString(DotDClasses(S), "t3.dot");
fail
gap> FileString("t3.dot", DotDClasses(S));
966

11.5-3 DotSemilatticeOfIdempotents
‣ DotSemilatticeOfIdempotents( S )( attribute )

Returns: A string.

This function produces a graphical representation of the semilattice of the idempotents of an inverse semigroup S where the elements of S have a unique semigroup inverse accessible via Inverse (Reference: Inverse). The idempotents are grouped by the \(\mathscr{D}\)-class they belong to.

The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see http://www.graphviz.org.

gap> S:=DualSymmetricInverseMonoid(4);
<inverse bipartition monoid on 4 pts with 3 generators>
gap> DotSemilatticeOfIdempotents(S);
"graph graphname {\n  node [shape=point]\nranksep=2;\nsubgraph cluste\
r_1{\n15 \n}\nsubgraph cluster_2{\n5 11 14 8 12 13 \n}\nsubgraph clus\
ter_3{\n2 3 10 4 6 9 7 \n}\nsubgraph cluster_4{\n1 \n}\n2 -- 1\n3 -- \
1\n4 -- 1\n5 -- 2\n5 -- 3\n5 -- 4\n6 -- 1\n7 -- 1\n8 -- 2\n8 -- 6\n8 \
-- 7\n9 -- 1\n10 -- 1\n11 -- 2\n11 -- 9\n11 -- 10\n12 -- 3\n12 -- 6\n\
12 -- 9\n13 -- 3\n13 -- 7\n13 -- 10\n14 -- 4\n14 -- 6\n14 -- 10\n15 -\
- 5\n15 -- 8\n15 -- 11\n15 -- 12\n15 -- 13\n15 -- 14\n }"
 [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 Bib Ind

generated by GAPDoc2HTML