In this section we give the theoretical results and the corresponding GAP functions that can be used to determine whether a set of transformations generates a semigroup of a given type. Let S be a semigroup. Then
S is a left zero semigroup if xy=x for all x,y in S.
S is a right zero semigroup if xy=y for all x,y in S.
S is commutative if xy=yx for all x,y in S.
S is simple if it has no proper two-sided ideals.
S is regular if for all x in S there exists y in S such that xyx=x.
S is completely regular if every element of S lies in a subgroup.
S is an inverse semigroup if for all elements x in S there exists a unique semigroup inverse, that is, a unique element y such that xyx=x and yxy=y.
S is a Clifford semigroup if it is a regular semigroup whose idempotents are central, that is, for all e in S with e^2=e and x in S we have that ex=xe.
S is a band if every element is an idempotent, that is, x^2=x for all x in S.
S is a rectangular band if for all x,y,z in S we have that x^2=x and xyz=xz.
S is a semiband if it is generated by its idempotent elements, that is, elements satisfying x^2=x.
S is an orthodox semigroup if its idempotents (elements satisfying x^2=x) form a subsemigroup.
S is a zero semigroup if there exists an element 0 in S such that xy=0 for all x,y in S.
S is a zero group if there exists an element 0 in S such that S without 0 is a group and for all x in S we have that x0=0x=0.
The following results provide efficient methods to determine if an arbitrary transformation semigroup is a left zero, right zero, simple, completely regular, inverse or Clifford semigroup. Proofs of these results can be found in [GM05].
Let S be a semigroup generated by a set of transformations U on a finite set. Then the following hold:
S is a left zero semigroup if and only if for all f, g in U the image of f equals the image of g and f^2=f.
S is a right zero semigroup if and only if for all f, g in U the kernel of f equals the kernel of g and f^2=f.
S is simple if and only if for all f, g in U every class of the kernel of f contains exactly 1 element of the image of g.
S is completely regular if and only if for all f in U and g in S, every class of the kernel of f contains at most 1 element of the set found by applying g to the image of f.
S is inverse if and only if it is regular and there is a bijection \phi from the set of kernels of elements of S to the set of images of elements of S such that every class of a kernel K contains exactly 1 element in (K)\phi.
S is a Clifford semigroup if and only if for all f, g in U
f permutes its image
f commutes with the power of g that acts as the identity on its image.
It is straightforward to verify that a transformation semigroup S generated by U is a group if and only if for all f, g in U
the kernel of f equals the kernel of g.
the image of f equals the image of g.
f permutes its image.
At first glance it might not be obvious why these conditions are an improvement over the original definitions. The main point is that it can be easily determined whether a semigroup S generated by a set U of mappings satisfies these conditions by considering the generators U and their action on the underlying set only.
> IsCompletelyRegularSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is completely regular and false otherwise.
A semigroup is completely regular if every element is contained in a subgroup.
gap> gens:=[ Transformation( [ 1, 2, 4, 3, 6, 5, 4 ] ), > Transformation( [ 1, 2, 5, 6, 3, 4, 5 ] ), > Transformation( [ 2, 1, 2, 2, 2, 2, 2 ] ) ];; gap> S:=Semigroup(gens);; gap> IsCompletelyRegularSemigroup(S); true gap> S:=RandomSemigroup(5,5);; gap> IsSimpleSemigroup(S); false |
> IsSimpleSemigroup( S ) | ( property ) |
> IsCompletelySimpleSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is simple and false otherwise.
A semigroup is simple if it has no proper 2-sided ideals. A semigroup is completely simple if it is simple and possesses minimal left and right ideals. A finite semigroup is simple if and only if it is completely simple.
gap> gens:=[ Transformation( [ 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2 ] ), > Transformation( [ 1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3 ] ), > Transformation( [ 1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5 ] ), > Transformation( [ 7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7 ] ) ];; gap> S:=Semigroup(gens);; gap> IsSimpleSemigroup(S); true gap> IsCompletelySimpleSemigroup(S); true gap> S:=RandomSemigroup(5,5);; gap> IsSimpleSemigroup(S); false |
> IsGroupAsSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a group and false otherwise.
gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), > Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];; gap> S:=Semigroup(gens);; gap> IsGroupAsSemigroup(S); true |
> IsCommutativeSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is commutative and false otherwise. The function IsCommutative (Reference: IsCommutative) can also be used to test if a semigroup is commutative.
A semigroup S is commutative if xy=yx for all x,y in S.
gap> gens:=[ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), > Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];; gap> S:=Semigroup(gens);; gap> IsCommutativeSemigroup(S); true gap> IsCommutative(S); true |
> IsRegularSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a regular semigroup and false otherwise. The algorithm used here is essentially the same algorithm as that used for GreensRClasses (Reference: GreensRClasses) in MONOID. If S is regular, then S will have the attribute GreensRClasses after IsRegularSemigroup is invoked.
A semigroup S is regular if for all x in S there exists y in S such that xyx=x.
gap> IsRegularSemigroup(FullTransformationSemigroup(5)); true |
> IsInverseSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is an inverse semigroup and false otherwise.
A semigroup S is an inverse semigroup if every element x in S has a unique semigroup inverse, that is, a unique element y such that xyx=x and yxy=y.
gap> gens:=[Transformation([1,2,4,5,6,3,7,8]), > Transformation([3,3,4,5,6,2,7,8]), >Transformation([1,2,5,3,6,8,4,4])];; gap> S:=Semigroup(gens);; gap> IsInverseSemigroup(S); true |
> IsCliffordSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a Clifford semigroup and false otherwise.
A semigroup S is a Clifford semigroup if it is a regular semigroup whose idempotents are central, that is, for all e in S with e^2=e and x in S we have that ex=xe.
gap> gens:=[Transformation([1,2,4,5,6,3,7,8]), > Transformation([3,3,4,5,6,2,7,8]), >Transformation([1,2,5,3,6,8,4,4])];; gap> S:=Semigroup(gens);; gap> IsCliffordSemigroup(S); true |
> IsBand( S ) | ( property ) |
returns true if the transformation semigroup S is a band and false otherwise.
A semigroup S is a band if every element is an idempotent, that is, x^2=x for all x in S.
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];; gap> S:=Semigroup(gens);; gap> IsBand(S); true |
> IsRectangularBand( S ) | ( property ) |
returns true if the transformation semigroup S is a rectangular band and false otherwise.
A semigroup S is a rectangular band if for all x,y,z in S we have that x^2=x and xyz=xz.
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];; gap> S:=Semigroup(gens);; gap> IsRectangularBand(S); true |
> IsSemiBand( S ) | ( property ) |
returns true if the transformation semigroup S is a semiband and false otherwise.
A semigroup S is a semiband if it is generated by its idempotent elements, that is, elements satisfying x^2=x.
gap> S:=FullTransformationSemigroup(4);; gap> x:=Transformation( [ 1, 2, 3, 1 ] );; gap> D:=GreensDClassOfElement(S, x);; gap> T:=Semigroup(Elements(D));; gap> IsSemiBand(T); true |
> IsOrthodoxSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is orthodox and false otherwise.
A semigroup is an orthodox semigroup if its idempotent elements form a subsemigroup.
gap> gens:=[ Transformation( [ 1, 1, 1, 4, 5, 4 ] ), > Transformation( [ 1, 2, 3, 1, 1, 2 ] ), > Transformation( [ 1, 2, 3, 1, 1, 3 ] ), > Transformation( [ 5, 5, 5, 5, 5, 5 ] ) ];; gap> S:=Semigroup(gens);; gap> IsOrthodoxSemigroup(S); true |
> IsRightZeroSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a right zero semigroup and false otherwise.
A semigroup S is a right zero semigroup if xy=y for all x,y in S.
gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ), > Transformation( [ 3, 2, 3, 1, 1 ] ) ];; gap> S:=Semigroup(gens);; gap> IsRightZeroSemigroup(S); false gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ), > Transformation( [ 1, 2, 4, 4, 1 ] )];; gap> S:=Semigroup(gens);; gap> IsRightZeroSemigroup(S); true |
> IsLeftZeroSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a left zero semigroup and false otherwise.
A semigroup S is a left zero semigroup if xy=x for all x,y in S.
gap> gens:=[ Transformation( [ 2, 1, 4, 3, 5 ] ), > Transformation( [ 3, 2, 3, 1, 1 ] ) ];; gap> S:=Semigroup(gens);; gap> IsRightZeroSemigroup(S); false gap> gens:=[Transformation( [ 1, 2, 3, 3, 1 ] ), > Transformation( [ 1, 2, 3, 3, 3 ] ) ];; gap> S:=Semigroup(gens);; gap> IsLeftZeroSemigroup(S); true |
> IsZeroSemigroup( S ) | ( property ) |
returns true if the transformation semigroup S is a zero semigroup or if S was created using the ZeroSemigroup (6.2-1) command. Otherwise false is returned.
A semigroup S is a zero semigroup if there exists an element 0 in S such that xy=0 for all x,y in S.
gap> gens:=[ Transformation( [ 4, 7, 6, 3, 1, 5, 3, 6, 5, 9 ] ), > Transformation( [ 5, 3, 5, 1, 9, 3, 8, 7, 4, 3 ] ), > Transformation( [ 5, 10, 10, 1, 7, 6, 6, 8, 7, 7 ] ), > Transformation( [ 7, 4, 3, 3, 2, 2, 3, 2, 9, 3 ] ), > Transformation( [ 8, 1, 3, 4, 9, 6, 3, 7, 1, 6 ] ) ];; gap> S:=Semigroup(gens);; gap> IsZeroSemigroup(S); false |
> IsZeroGroup( S ) | ( property ) |
returns true if the transformation semigroup S is a zero group or if S was created using the ZeroGroup (6.2-3) command. Otherwise false is returned.
A semigroup S S is a zero group if there exists an element 0 in S such that S without 0 is a group and for all x in S we have that x0=0x=0.
gap> S:=ZeroGroup(DihedralGroup(10));; gap> iso:=IsomorphismTransformationSemigroup(S);; gap> T:=Range(iso);; gap> IsZeroGroup(T); true |
> MultiplicativeZero( S ) | ( property ) |
returns the multiplicative zero of the transformation semigroup S if it has one and returns fail otherwise.
gap> gens:=[ Transformation( [ 1, 4, 2, 6, 6, 5, 2 ] ), > Transformation( [ 1, 6, 3, 6, 2, 1, 6 ] ) ];; gap> S:=Semigroup(gens);; gap> MultiplicativeZero(S); Transformation( [ 1, 1, 1, 1, 1, 1, 1 ] ) |
generated by GAPDoc2HTML