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

6 Special Classes of Semigroup
 6.1 Some Classes of Semigroup
  6.1-1 SingularSemigroup

  6.1-2 OrderPreservingSemigroup

  6.1-3 KiselmanSemigroup
 6.2 Zero Groups and Zero Semigroups
  6.2-1 ZeroSemigroup

  6.2-2 ZeroSemigroupElt

  6.2-3 ZeroGroup

  6.2-4 ZeroGroupElt

  6.2-5 UnderlyingGroupOfZG

  6.2-6 UnderlyingGroupEltOfZGElt
 6.3 Random Semigroups
  6.3-1 RandomMonoid

  6.3-2 RandomSemigroup

  6.3-3 RandomReesMatrixSemigroup

  6.3-4 RandomReesZeroMatrixSemigroup

6 Special Classes of Semigroup

In this chapter functions for creating certain semigroups are given.

6.1 Some Classes of Semigroup

6.1-1 SingularSemigroup
> SingularSemigroup( n )( function )

creates the semigroup of singular transformations of degree n. That is, the semigroup of all transformations of the n-element set {1,2,...,n} that are non-invertible.

This semigroup is known to be regular, idempotent generated (satisfies IsSemiBand (5.2-10)), and has size n^n-n!.

The generators used here are the idempotents of rank n-1, so there are n(n-1) generators in total.

  gap> S:=SingularSemigroup(6);
  <semigroup with 30 generators>
  gap> Size(S);
  45936
  gap> IsRegularSemigroup(S);
  true
  gap> IsSemiBand(S);
  true

6.1-2 OrderPreservingSemigroup
> OrderPreservingSemigroup( n )( operation )

returns the semigroup of order preserving transformations of the n- element set {1,2,...,n}. That is, the mappings f such that i is at most j implies f(i) is at most f(j) for all i,j in {1,2,...,n}.

This semigroup is known to be regular, idempotent generated (satisfies IsSemiBand (5.2-10)), and has size Binomial(2*n-1, n-1). The generators and relations used here are those specified by Aizenstat as given in [AR00] and [GH92]. That is, OrderPreservingSemigroup(n) has the 2n-2 idempotent generators

u_2:=Transformation([2,2,3,..,n]), u_3:=Transformation([1,3,3,..,n]), ...
v_n-2:=Transformation([1,2,2,...,n]), v_n-3:=Transformation
([1,2,3,3,...,n]), ...

and the presentation obtained using IsomorphismFpMonoid (7.7-4) has relations

  v_n−i u_i = u_i v_n−i+1 (i=2,..., n−1)
  u_n−i v_i = v_i u_n−i+1 (i=2,...,n−1),
  v_n−i u_i = u_i (i=1,...,n−1),
  u_n−i v_i = v_i (i=1,...,n−1),
  u_i v_j = v_j u_i (i,j=1,...,n−1; not j=n-i, n-i+1),
  u_1 u_2 u_1 = u_1 u_2,
  v_1 v_2 v_1 = v_1 v_2. 
  


  gap> S:=OrderPreservingSemigroup(5);
  <monoid with 8 generators>
  gap> IsSemiBand(S);
  true
  gap> IsRegularSemigroup(S);
  true
  gap> Size(S)=Binomial(2*5-1, 5-1);
  true

6.1-3 KiselmanSemigroup
> KiselmanSemigroup( n )( operation )

returns the Kiselman semigroup with n generators. That is, the semigroup defined in [KM05] with the presentation

<a_1, a_2, ... , a_n | a_i^2=a_i (i=1,...n) a_ia_ja_i=a_ja_ia_j=a_ja_i (1<=i< j<=n)>.

  gap> S:=KiselmanSemigroup(3);
  <fp monoid on the generators [ m1, m2, m3 ]>
  gap> Elements(S);
  [ <identity ...>, m1, m2, m3, m1*m2, m1*m3, m2*m1, m2*m3, m3*m1, m3*m2, 
    m1*m2*m3, m1*m3*m2, m2*m1*m3, m2*m3*m1, m3*m1*m2, m3*m2*m1, m2*m1*m3*m2, 
    m2*m3*m1*m2 ]
  gap> Idempotents(S);
  [ 1, m1, m2*m1, m3*m2*m1, m3*m1, m2, m3*m2, m3 ]
  gap> SetInfoLevel(InfoAutos, 0);
  gap> AutomorphismGroup(Range(IsomorphismTransformationSemigroup(S)));
  <group of size 1 with 1 generators>
  

6.2 Zero Groups and Zero Semigroups

6.2-1 ZeroSemigroup
> ZeroSemigroup( n )( operation )

returns the zero semigroup S of order n. That is, the unique semigroup up to isomorphism of order n such that there exists an element 0 in S such that xy=0 for all x,y in S.

A zero semigroup is generated by its nonzero elements, has trivial Green's relations, and is not regular.

  gap> S:=ZeroSemigroup(10);
  <zero semigroup with 10 elements>
  gap> Size(S);
  10
  gap> GeneratorsOfSemigroup(S);
  [ z1, z2, z3, z4, z5, z6, z7, z8, z9 ]
  gap> Idempotents(S);
  [ 0 ]
  gap> IsZeroSemigroup(S);
  true
  gap> GreensRClasses(S);
  [ {0}, {z1}, {z2}, {z3}, {z4}, {z5}, {z6}, {z7}, {z8}, {z9} ]

6.2-2 ZeroSemigroupElt
> ZeroSemigroupElt( n )( operation )

returns the zero semigroup element zn where n is a positive integer and z0 is the multiplicative zero.

The zero semigroup element zn belongs to every zero semigroup with degree at least n.

  gap> ZeroSemigroupElt(0);
  0
  gap> ZeroSemigroupElt(4);
  z4

6.2-3 ZeroGroup
> ZeroGroup( G )( operation )

returns the monoid obtained by adjoining a zero element to G. That is, the monoid S obtained by adjoining a zero element 0 to G with g0=0g=0 for all g in S.

  gap> S:=ZeroGroup(CyclicGroup(10));
  <zero group with 3 generators>
  gap> IsRegularSemigroup(S);
  true
  gap> Elements(S);
  [ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4, 
    f1*f2^4 ]
  gap> GreensRClasses(S);
  [ {<adjoined zero>}, {ZeroGroup(<identity> of ...)} ]

6.2-4 ZeroGroupElt
> ZeroGroupElt( g )( operation )

returns the zero group element corresponding to the group element g. The function ZeroGroupElt is only used to create an object in the correct category during the creation of a zero group using ZeroGroup (6.2-3).

  gap> ZeroGroupElt(Random(DihedralGroup(10)));;
  gap> IsZeroGroupElt(last);
  true

6.2-5 UnderlyingGroupOfZG
> UnderlyingGroupOfZG( ZG )( attribute )

returns the group from which the zero group ZG was constructed.

  gap> G:=DihedralGroup(10);;
  gap> S:=ZeroGroup(G);;
  gap> UnderlyingGroupOfZG(S)=G;
  true

6.2-6 UnderlyingGroupEltOfZGElt
> UnderlyingGroupEltOfZGElt( g )( attribute )

returns the group element from which the zero group element g was constructed.

  gap> G:=DihedralGroup(10);;
  gap> S:=ZeroGroup(G);;
  gap> Elements(S);
  [ 0, <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2, f2^3, f1*f2^3, f2^4, 
    f1*f2^4 ]
  gap> x:=last[5];
  f1*f2
  gap> UnderlyingGroupEltOfZGElt(x);
  f1*f2

6.3 Random Semigroups

6.3-1 RandomMonoid
> RandomMonoid( m, n )( function )

returns a random transformation monoid of degree n with m generators.

  gap> S:=RandomMonoid(5,5);
  <semigroup with 5 generators>

6.3-2 RandomSemigroup
> RandomSemigroup( m, n )( function )

returns a random transformation semigroup of degree n with m generators.

  gap> S:=RandomSemigroup(5,5);
  <semigroup with 5 generators>

6.3-3 RandomReesMatrixSemigroup
> RandomReesMatrixSemigroup( i, j, deg )( function )

returns a random Rees matrix semigroup with an i by j sandwich matrix over a permutation group with maximum degree deg.

  gap> S:=RandomReesMatrixSemigroup(4,5,5);
  Rees Matrix Semigroup over Group([ (1,5,3,4), (1,3,4,2,5) ])
  [ [ (), (), (), (), () ], 
  [ (), (1,3,5)(2,4), (1,3,5)(2,4), (1,5,3), (1,5,3) ], 
  [ (), (1,3,5), (1,5,3)(2,4), (), (1,5,3) ], 
  [ (), (), (1,3,5)(2,4), (2,4), (2,4) ] ]

6.3-4 RandomReesZeroMatrixSemigroup
> RandomReesZeroMatrixSemigroup( i, j, deg )( function )

returns a random Rees 0-matrix semigroup with an i by j sandwich matrix over a permutation group with maximum degree deg.

  gap> S:=RandomReesZeroMatrixSemigroup(2,3,2);
  Rees Zero Matrix Semigroup over <zero group with 2 generators>
  gap> SandwichMatrixOfReesZeroMatrixSemigroup(S);
  [ [ 0, (), 0 ], [ 0, 0, 0 ] ]
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML