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

3 Monoid Actions and Orbits
 3.1 Introduction
 3.2 Actions
  3.2-1 OnTuplesOfSetsAntiAction

  3.2-2 OnKernelsAntiAction
 3.3 General Orbits
  3.3-1 MonoidOrbit

  3.3-2 MonoidOrbits

  3.3-3 StrongOrbit

  3.3-4 StrongOrbits

  3.3-5 GradedOrbit

  3.3-6 ShortOrbit

  3.3-7 GradedStrongOrbit

  3.3-8 ShortStrongOrbit
 3.4 Some Specific Orbits
  3.4-1 ImagesOfTransSemigroup

  3.4-2 GradedImagesOfTransSemigroup

  3.4-3 KernelsOfTransSemigroup

  3.4-4 GradedKernelsOfTransSemigroup

  3.4-5 StrongOrbitOfImage

  3.4-6 StrongOrbitsOfImages

3 Monoid Actions and Orbits

3.1 Introduction

The functions described in this section relate to how a transformation semigroup acts on its underlying set.

Let S be a transformation semigroup of degree n. Then the orbit of i in {1,...,n} is the set of elements j in {1,...,n} such that there exists f in S where (i)f=j. Note that the essential difference between monoid orbits and group orbits is that monoid orbits do not describe an equivalence relation on S. In particular, the relation described by monoid orbits is not symmetric.

The strong orbit of i in {1,...,n} is the set of elements j in {1,...,n} such that there exists f, g in S where (i)f=j and (j)g=i.

Recall that a grading is a function f from a transformation semigroup S of degree n to the natural numbers such that if s in S and X is a subset of {1,...,n}, then (Xs)f is at most (X)f.

3.2 Actions

In addition to the actions define in the reference manual Reference: Basic Actions the following two actions are available in MONOID.

3.2-1 OnTuplesOfSetsAntiAction
> OnTuplesOfSetsAntiAction( tup, f )( function )

returns the preimages of each of the sets in the tuple of sets tup under the transformation f. The tuple of sets tup can have any number of elements.

gap> f:=Transformation( [ 8, 7, 5, 3, 1, 3, 8, 8 ] );;
gap> OnTuplesOfSetsAntiAction([ [ 1, 2 ], [ 3 ], [ 4 ], [ 5 ] ], f);
[ [ 5 ], [ 4, 6 ], [ 3 ] ]

3.2-2 OnKernelsAntiAction
> OnKernelsAntiAction( ker, f )( function )

returns the kernel of the product f*g of the transformation f with a transformation g having kernel ker.

gap> f:=Transformation( [ 8, 7, 5, 3, 1, 3, 8, 8 ] );;
gap> OnKernelsAntiAction([ [ 1, 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6, 7, 8 ] ], f);
[ [ 1, 2, 7, 8 ], [ 3 ], [ 4, 6 ], [ 5 ] ]

3.3 General Orbits

The following functions allow the calculation of arbitrary orbits in transformation semigroups. Several more specific orbits that are often useful are given in Section 3.4.

3.3-1 MonoidOrbit
> MonoidOrbit( S, obj[, act] )( operation )

returns the orbit of obj under the action act of the transformation semigroup S. Usually, obj would be a point, list of points, or list of lists, and act would be OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), OnTuples (Reference: OnTuples), or another action defined in Reference: Basic Actions. The argument act can be any function.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> MonoidOrbit(S, 1);
  [ 1, 3, 4, 2, 6 ]
  gap> MonoidOrbit(S, [1,2], OnSets);
  [ [ 1, 2 ], [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ]
  gap> MonoidOrbit(S, [1,2], OnTuples);
  [ [ 1, 2 ], [ 3, 3 ], [ 4, 4 ], [ 2, 2 ], [ 6, 6 ], [ 1, 1 ] ]
  gap> MonoidOrbit(S, 2, OnPoints);
  [ 2, 3, 4, 6, 1 ]

3.3-2 MonoidOrbits
> MonoidOrbits( S, list[, act] )( operation )

returns a list of the orbits of the elements of list under the action act of the transformation semigroup S using the MonoidOrbit (3.3-1) function.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> MonoidOrbits(S, [1,2]);
  [ [ 1, 3, 4, 2, 6 ], [ 2, 3, 4, 6, 1 ] ]
  gap> MonoidOrbits(S, [[1,2], [2,3]], OnSets);
  [ [ [ 1, 2 ], [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ], 
    [ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ] ]

3.3-3 StrongOrbit
> StrongOrbit( S, obj[, act] )( operation )

returns the strong orbit of obj under the action act of the transformation semigroup S. Usually, obj would be a point, list of points, or list of lists, and act would be OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), OnTuples (Reference: OnTuples), or another action defined in Reference: Basic Actions. The argument act can be any function.

If the optional third argument act is not given and obj is a point, then OnPoints (Reference: OnPoints) is the default action.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> StrongOrbit(S, 4, OnPoints);
  [ 1, 3, 2, 4, 6 ]
  gap> StrongOrbit(S, 4); 
  [ 1, 3, 2, 4, 6 ]
  gap> StrongOrbit(S, [2,3], OnSets);
  [ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ] 
  gap> StrongOrbit(S, [2,3], OnTuples);
  [ [ 2, 3 ], [ 3, 2 ], [ 4, 6 ], [ 6, 4 ], [ 1, 3 ], [ 3, 1 ] ]

3.3-4 StrongOrbits
> StrongOrbits( S, obj[, act] )( operation )

returns a list of the strong orbits of the elements of list under the action act of the transformation semigroup S using the StrongOrbit (3.3-3) function.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> StrongOrbits(S, [1..6]);
  [ [ 1, 3, 2, 4, 6 ], [ 5 ] ]
  gap> StrongOrbits(S, [[1,2],[2,3]], OnSets);
  [ [ [ 1, 2 ] ], [ [ 2, 3 ], [ 4, 6 ], [ 1, 3 ] ] ]
  gap> StrongOrbits(S, [[1,2],[2,3]], OnTuples);
  [ [ [ 1, 2 ] ], [ [ 2, 3 ], [ 3, 2 ], [ 4, 6 ], [ 6, 4 ], 
    [ 1, 3 ], [ 3, 1 ] ] ]

3.3-5 GradedOrbit
> GradedOrbit( S, obj[, act], grad )( operation )

returns the orbit of obj under the action act of the transformation semigroup S partitioned by the grading grad. That is, two elements lie in the same class if they have the same value under grad.

(Recall that a grading is a function f from a transformation semigroup S of degree n to the natural numbers such that if s in S and X is a subset of {1,...,n}, then (Xs)f is at most (X)f. )

Note that this function will not check if grad actually defines a grading or not.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> GradedOrbit(S, [1,2], OnSets, Size);
  [ [ [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ], [ [ 1, 2 ] ] ]
  gap> GradedOrbit(S, [1,2], Size);
  [ [ [ 3 ], [ 4 ], [ 2 ], [ 6 ], [ 1 ] ], [ [ 1, 2 ] ] ]
  gap> GradedOrbit(S, [1,3,4], OnTuples, function(x)
  > if 1 in x then return 2;
  > else return 1;
  > fi;
  > end); 
  [ [ [ 3, 2, 6 ], [ 2, 3, 4 ], [ 6, 4, 3 ], [ 4, 6, 2 ] ], 
    [ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ] ]

3.3-6 ShortOrbit
> ShortOrbit( S, obj[, act], grad )( operation )

returns the elements of the orbit of obj under the action act of the transformation semigroup S with the same value as obj under the grading grad.

(Recall that a grading is a function f from a transformation semigroup S of degree n to the natural numbers such that if s in S and X is a subset of {1,...,n}, then (Xs)f is at most (X)f. )

Note that this function will not check if grad actually defines a grading or not.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> ShortOrbit(S, [1,2], Size);
  [ [ 1, 2 ] ]
  gap> ShortOrbit(S, [2,4], Size);
  [ [ 2, 4 ], [ 3, 6 ], [ 1, 4 ] ]
  gap> ShortOrbit(S, [1,2], OnTuples, Size);
  [ [ 1, 2 ], [ 3, 3 ], [ 4, 4 ], [ 2, 2 ], [ 6, 6 ], [ 1, 1 ] ]

3.3-7 GradedStrongOrbit
> GradedStrongOrbit( S, obj[, act], grad )( operation )

returns the strong orbit of obj under the action act of the transformation semigroup S partitioned by the grading grad. That is, two elements lie in the same class if they have the same value under grad.

(Recall that a grading is a function f from a transformation semigroup S of degree n to the natural numbers such that if s in S and X is a subset of {1,...,n}, then (Xs)f is at most (X)f. )

Note that this function will not check if grad actually defines a grading or not.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap> GradedStrongOrbit(S, [1,3,4], OnTuples, function(x)
  > if 1 in x then return 2; else return 1; fi; end);
  [ [ [ 3, 2, 6 ], [ 2, 3, 4 ], [ 6, 4, 3 ], [ 4, 6, 2 ] ], 
    [ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ] ]
  gap> GradedStrongOrbit(S, [1,3,4], OnTuples, Size);
  [ [ [ 1, 3, 4 ], [ 3, 2, 6 ], [ 4, 6, 1 ], [ 2, 3, 4 ], [ 6, 4, 3 ], 
    [ 4, 6, 2 ], [ 3, 1, 6 ] ] ]

3.3-8 ShortStrongOrbit
> ShortStrongOrbit( S, obj[, act], grad )( operation )

returns the elements of the orbit of obj under the action act of the transformation semigroup S with the same value as obj under the grading grad.

(Recall that a grading is a function f from a transformation semigroup S of degree n to the natural numbers such that if s in S and X is a subset of {1,...,n}, then (Xs)f is at most (X)f. )

Note that this function will not check if grad actually defines a grading or not.

If the optional third argument act is not given, then OnPoints (Reference: OnPoints), OnSets (Reference: OnSets), or OnSetsSets (Reference: OnSetsSets) is used as the default action depending on what obj is.

Further details can be found in Algorithm A and B of [LPRR02].

  gap> g1:=Transformation([3,3,2,6,2,4,4,6,3,4,6]);;
  gap> g2:=Transformation([4,4,6,1,3,3,3,3,11,11,11]);;
  gap> g3:=Transformation([2,2,3,4,4,6,6,6,6,6,11]);;
  gap> S:=Monoid(g1,g2,g3);;
  gap>ShortStrongOrbit(S, [1,3,4], OnTuples, function(x) 
  >  if 1 in x then return 2; else return 1; fi; end);
  [ [ 1, 3, 4 ], [ 4, 6, 1 ], [ 3, 1, 6 ] ]

3.4 Some Specific Orbits

The following specific orbits are used in the computation of Green's relations and to test if an arbitrary transformation semigroup has a particular property; see Chapter 4 and Chapter 5.

3.4-1 ImagesOfTransSemigroup
> ImagesOfTransSemigroup( S[, n] )( attribute )

returns the set of all the image sets that elements of S admit. That is, the union of the orbits of the image sets of the generators of S under the action OnSets (Reference: OnSets).

If the optional second argument n (a positive integer) is present, then the list of image sets of size n is returned. If you are only interested in the images of a given size, then the second version of the function will likely be faster.

gap>  S:=Semigroup([ Transformation( [ 6, 4, 4, 4, 6, 1 ] ), 
> Transformation( [ 6, 5, 1, 6, 2, 2 ] ) ];;
gap> ImagesOfTransSemigroup(S, 6);
[  ]
gap> ImagesOfTransSemigroup(S, 5);
[  ]
gap> ImagesOfTransSemigroup(S, 4);
[ [ 1, 2, 5, 6 ] ]
gap> ImagesOfTransSemigroup(S, 3);
[ [ 1, 4, 6 ], [ 2, 5, 6 ] ]
gap> ImagesOfTransSemigroup(S, 2);
[ [ 1, 4 ], [ 2, 5 ], [ 2, 6 ], [ 4, 6 ] ]
gap> ImagesOfTransSemigroup(S, 1);
[ [ 1 ], [ 2 ], [ 4 ], [ 5 ], [ 6 ] ]
gap> ImagesOfTransSemigroup(S);
[ [ 1 ], [ 1, 2, 5, 6 ], [ 1, 4 ], [ 1, 4, 6 ], [ 2 ], [ 2, 5 ], [ 2, 5, 6 ], 
  [ 2, 6 ], [ 4 ], [ 4, 6 ], [ 5 ], [ 6 ] ]
  

3.4-2 GradedImagesOfTransSemigroup
> GradedImagesOfTransSemigroup( S )( attribute )

returns the set of all the image sets that elements of S admit in a list where the ith entry contains all the images with size i (including the empty list when there are no image sets with size i).

This is just the union of the orbits of the images of the generators of S under the action OnSets (Reference: OnSets) graded according to size.

gap> gens:=[ Transformation( [ 1, 5, 1, 1, 1 ] ), 
> Transformation( [ 4, 4, 5, 2, 2 ] ) ];;
gap> S:=Semigroup(gens);;
gap> GradedImagesOfTransSemigroup(S);
[ [ [ 1 ], [ 4 ], [ 2 ], [ 5 ] ], [ [ 1, 5 ], [ 2, 4 ] ], [ [ 2, 4, 5 ] ], 
  [  ], [ [ 1 .. 5 ] ] ]

3.4-3 KernelsOfTransSemigroup
> KernelsOfTransSemigroup( S[, n] )( attribute )

returns the set of all the kernels that elements of S admit. This is just the union of the orbits of the kernels of the generators of S under the action OnKernelsAntiAction (3.2-2).

If the optional second argument n (a positive integer) is present, then the list of image sets of size n is returned. If you are only interested in the images of a given size, then the second version of the function will likely be faster.

gap>  S:=Semigroup([ Transformation( [ 2, 4, 1, 2 ] ),
> Transformation( [ 3, 3, 4, 1 ] ) ]);
gap>  KernelsOfTransSemigroup(S);   
[ [ [ 1, 2 ], [ 3 ], [ 4 ] ], [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2, 3 ], 
[ 4 ] ], 
  [ [ 1, 2, 3, 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ], [ [ 1, 3, 4 ], [ 2 ] ], 
  [ [ 1, 4 ], [ 2 ], [ 3 ] ], [ [ 1, 4 ], [ 2, 3 ] ] ]
gap>  KernelsOfTransSemigroup(S,1);
[ [ [ 1, 2, 3, 4 ] ] ]
gap>  KernelsOfTransSemigroup(S,2);
[ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 2, 3 ], [ 4 ] ], [ [ 1, 2, 4 ], [ 3 ] ], 
  [ [ 1, 3, 4 ], [ 2 ] ], [ [ 1, 4 ], [ 2, 3 ] ] ]
gap>  KernelsOfTransSemigroup(S,3);
[ [ [ 1, 2 ], [ 3 ], [ 4 ] ], [ [ 1, 4 ], [ 2 ], [ 3 ] ] ]
gap>  KernelsOfTransSemigroup(S,4);
[  ]

3.4-4 GradedKernelsOfTransSemigroup
> GradedKernelsOfTransSemigroup( S )( attribute )

returns the set of all the kernels that elements of S admit in a list where the ith entry contains all the kernels with i classes (including the empty list when there are no kernels with i classes).

This is just the union of the orbits of the kernels of the generators of S under the action OnKernelsAntiAction (3.2-2) graded according to size.

gap> gens:=[ Transformation( [ 1, 1, 2, 1, 4 ] ), 
> Transformation( [ 2, 5, 3, 2, 3 ] ) ];;
gap> S:=Semigroup(gens);;
gap> GradedKernelsOfTransSemigroup(S);
[ [ [ [ 1, 2, 3, 4, 5 ] ] ], 
  [ [ [ 1, 2, 4, 5 ], [ 3 ] ], [ [ 1, 4 ], [ 2, 3, 5 ] ], 
      [ [ 1, 2, 4 ], [ 3, 5 ] ] ], 
  [ [ [ 1, 2, 4 ], [ 3 ], [ 5 ] ], [ [ 1, 4 ], [ 2 ], [ 3, 5 ] ] ], [  ], 
  [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] ] ]

3.4-5 StrongOrbitOfImage
> StrongOrbitOfImage( S, f )( operation )

returns a triple where

gap> gens:=[ Transformation( [ 3, 5, 2, 5, 1 ] ), 
> Transformation( [ 4, 3, 2, 1, 5 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 2, 1, 1, 1, 5 ] );;
gap> StrongOrbitOfImage(S, f);        
[ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ], 
      [ 2, 4, 5 ], [ 3, 4, 5 ] ], 
  [ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2), 
      (1,3,2,4) ], Group([ (), (2,5), (1,5) ]) ]

3.4-6 StrongOrbitsOfImages
> StrongOrbitsOfImages( S )( attribute )

this is a mutable attribute that stores the result of StrongOrbitOfImage (3.4-5) every time it is used. If StrongOrbitOfImage (3.4-5) has not been invoked for S, then an error is returned.

gap> gens:=[ Transformation( [ 3, 5, 2, 5, 1 ] ), 
> Transformation( [ 4, 3, 2, 1, 5 ] ) ];;
gap> S:=Semigroup(gens);;
gap> f:=Transformation( [ 2, 1, 1, 1, 5 ] );;
gap> StrongOrbitOfImage(S, f);;
gap> StrongOrbitsOfImages(S);
[ [ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ], 
          [ 2, 4, 5 ], [ 3, 4, 5 ] ] ], 
  [ [ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2), 
          (1,3,2,4) ] ], [ Group([ (), (2,5), (1,5) ]) ] ]
gap> f:=Transformation( [ 5, 5, 5, 5, 2 ] );
gap> StrongOrbitOfImage(S, f);;
gap> StrongOrbitsOfImages(S); 
[ [ [ [ 1, 2, 5 ], [ 1, 3, 5 ], [ 1, 2, 3 ], [ 2, 3, 5 ], [ 2, 3, 4 ], 
          [ 2, 4, 5 ], [ 3, 4, 5 ] ], 
      [ [ 2, 5 ], [ 1, 5 ], [ 1, 3 ], [ 2, 3 ], [ 2, 4 ], [ 4, 5 ], [ 3, 5 ], 
          [ 1, 2 ], [ 3, 4 ] ] ], 
  [ [ (), (1,5,2,3), (1,2)(3,5,4), (1,3,2,5), (1,3)(2,5,4), (1,3,4,5,2), 
          (1,3,2,4) ], 
      [ (), (1,5,2), (1,2)(3,5,4), (2,5,4,3), (2,5,4), (2,3,4,5), (2,3), 
          (1,5,4,3), (2,3)(4,5) ] ], 
  [ Group([ (), (2,5), (1,5) ]), Group([ (), (2,5) ]) ] ]
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML