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
.
In addition to the actions define in the reference manual Reference: Basic Actions the following two actions are available in MONOID.
> 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 ] ] |
> 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 ] ] |
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.
> 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 ] |
> 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 ] ] ] |
> 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 ] ] |
> 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 ] ] ] |
> 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 ] ] ] |
> 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 ] ] |
> 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 ] ] ] |
> 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 ] ] |
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.
> 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 ] ] |
> GradedImagesOfTransSemigroup ( S ) | ( attribute ) |
returns the set of all the image sets that elements of S
admit in a list where the i
th 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 ] ] ] |
> 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); [ ] |
> GradedKernelsOfTransSemigroup ( S ) | ( attribute ) |
returns the set of all the kernels that elements of S
admit in a list where the i
th 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 ] ] ] ] |
> StrongOrbitOfImage ( S, f ) | ( operation ) |
returns a triple where
the first entry imgs
is the strong orbit of the image set A
of f
under the action of S
. That is, the set of image sets B
of elements of S
such that there exist g,h
in S
with OnSets(A, g)=B
and OnSet(B, h)=A
. If the strong orbit of the image of f
has already been calculated, then the image of f
might not be the first entry in the list imgs
.
the second entry is a list of permutations mults
such that OnSets(imgs[i], mults[i])=imgs[1]
.
the third entry is the Right Schutzenberger group associated to the first entry in the list imgs
(that is, the group of permutations arising from elements of the semigroup that stabilise the set imgs[1]
).
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) ]) ] |
> 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) ]) ] ] |
generated by GAPDoc2HTML