chap2.txt

  
  2 Basics
  
  We  give some examples of semigroups to be used later. We also describe some
  basic functions that are not directly available from GAP, but are useful for
  the purposes of this package.
  
  
  2.1 Examples
  
  These are some examples of semigroups that will be used through this manual
  
    Example  
    gap> f := FreeMonoid("a","b");
    <free monoid on the generators [ a, b ]>
    gap> a := GeneratorsOfMonoid( f )[ 1 ];;
    gap> b := GeneratorsOfMonoid( f )[ 2 ];;
    gap> r:=[[a^3,a^2],
    > [a^2*b,a^2],
    > [b*a^2,a^2],
    > [b^2,a^2],
    > [a*b*a,a],
    > [b*a*b,b] ];
    [ [ a^3, a^2 ], [ a^2*b, a^2 ], [ b*a^2, a^2 ], [ b^2, a^2 ], [ a*b*a, a ], 
      [ b*a*b, b ] ]
    gap> b21:= f/r;
    <fp monoid on the generators [ a, b ]>
          
  
  
    Example  
    gap> g0:=Transformation([4,1,2,4]);;
    gap> g1:=Transformation([1,3,4,4]);;
    gap> g2:=Transformation([2,4,3,4]);;
    gap> poi3:= Monoid(g0,g1,g2);
    <monoid with 3 generators>
         
  
  
  
  2.2 Some attributes
  
  These functions are semigroup attributes that get stored once computed.
  
  2.2-1 HasCommutingIdempotents
  
  HasCommutingIdempotents( M )  attribute
  
  Tests whether the idempotents of the semigroup M commute.
  
  2.2-2 IsInverseSemigroup
  
  IsInverseSemigroup( S )  attribute
  
  Tests  whether  a  finite  semigroup  S is inverse. It is well-known that it
  suffices  to test whether the idempotents of S commute and S is regular. The
  function IsRegularSemigroup is part of GAP.
  
  
  2.3 Some basic functions
  
  2.3-1 PartialTransformation
  
  PartialTransformation( L )  function
  
  A  partial  transformation is a partial function of a set of integers of the
  form  {1,dots,  n}.  It  is  given by means of the list of images L. When an
  element  has  no  image,  we write 0. Returns a full transformation on a set
  with one more element that acts like a zero.
  
    Example  
    gap> PartialTransformation([2,0,4,0]);
    Transformation( [ 2, 5, 4, 5, 5 ] )
          
  
  
  2.3-2 ReduceNumberOfGenerators
  
  ReduceNumberOfGenerators( L )  function
  
  Given  a  subset  L  of  the  generators  of  a semigroup, returns a list of
  generators of the same semigroup but possibly with less elements than L.
  
  2.3-3 SemigroupFactorization
  
  SemigroupFactorization( S, L )  function
  
  L  is an element (or list of elements) of the semigroup S. Returns a minimal
  factorization  on the generators of S of the element(s) of L. Works only for
  transformation semigroups.
  
    Example  
    gap> el1 := Transformation( [ 2, 3, 4, 4 ] );;
    gap> el2 := Transformation( [ 2, 4, 3, 4 ] );;
    gap> f1 := SemigroupFactorization(poi3,el1);
    [ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ] ]
    gap> f1[1][1] * f1[1][2] = el1;
    true
    gap> SemigroupFactorization(poi3,[el1,el2]);
    [ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ],
      [ Transformation( [ 2, 4, 3, 4 ] ) ] ]
  
  
  2.3-4 GrahamBlocks
  
  GrahamBlocks( mat )  function
  
  mat  is  a  matrix  as  displayed  by DisplayEggBoxOfDClass(D); of a regular
  D-class  D.  This  function  outputs a list [gmat, phi] where gmat is mat in
  Graham's  blocks  form  and  phi maps H-classes of gmat to the corresponding
  ones  of  mat,  i.e., phi[i][j] = [i',j'] where mat[i'][j'] = gmat[i][j]. If
  the  argument  to  this  function is not a matrix corresponding to a regular
  D-class, the function may abort in error.
  
    Example  
    gap> p1 := PartialTransformation([6,2,0,0,2,6,0,0,10,10,0,0]);;
    gap> p2 := PartialTransformation([0,0,1,5,0,0,5,9,0,0,9,1]);;
    gap> p3 := PartialTransformation([0,0,3,3,0,0,7,7,0,0,11,11]);;
    gap> p4 := PartialTransformation([4,4,0,0,8,8,0,0,12,12,0,0]);;
    gap> css3:=Semigroup(p1,p2,p3,p4);
    <transformation semigroup of degree 13 with 4 generators>
    gap> el := Elements(css3)[8];;
    gap> D := GreensDClassOfElement(css3, el);;
    gap> IsRegularDClass(D);
    true
    gap> DisplayEggBoxOfDClass(D);
    [ [  1,  1,  0,  0 ],
      [  1,  1,  0,  0 ],
      [  0,  0,  1,  1 ],
      [  0,  0,  1,  1 ] ]
    gap> mat := [ [  1,  0,  1,  0 ],
    >   [  0,  1,  0,  1 ],
    >   [  0,  1,  0,  1 ],
    >   [  1,  0,  1,  0 ] ];;
    gap> res := GrahamBlocks(mat);;
    gap> PrintArray(res[1]);
    [ [  1,  1,  0,  0 ],
      [  1,  1,  0,  0 ],
      [  0,  0,  1,  1 ],
      [  0,  0,  1,  1 ] ]
    gap> PrintArray(res[2]);
    [ [  [ 1, 1 ],  [ 1, 3 ],  [ 1, 2 ],  [ 1, 4 ] ],
      [  [ 4, 1 ],  [ 4, 3 ],  [ 4, 2 ],  [ 4, 4 ] ],
      [  [ 2, 1 ],  [ 2, 3 ],  [ 2, 2 ],  [ 2, 4 ] ],
      [  [ 3, 1 ],  [ 3, 3 ],  [ 3, 2 ],  [ 3, 4 ] ] ]
  
  
  
  2.4 Cayley graphs
  
  2.4-1 RightCayleyGraphAsAutomaton
  
  RightCayleyGraphAsAutomaton( S )  function
  
  Computes  the  right Cayley graph of a finite monoid or semigroup S. It uses
  the  GAP  buit-in  function CayleyGraphSemigroup to compute the Cayley Graph
  and  returns  it  as an automaton without initial nor final states. (In this
  automaton  state  i  represents  the  element  Elements(S)[i].) The Automata
  package is used to this effect.
  
    Example  
    gap> rcg := RightCayleyGraphAsAutomaton(b21);
    < deterministic automaton on 2 letters with 6 states >
    gap> Display(rcg);
       |  1  2  3  4  5  6
    -----------------------
     a |  2  4  6  4  2  4
     b |  3  5  4  4  4  3
    Initial state:   [ ]
    Accepting state: [ ]
          
  
  
  2.4-2 RightCayleyGraphMonoidAsAutomaton
  
  RightCayleyGraphMonoidAsAutomaton( S )  function
  
  This function is a synonym of RightCayleyGraphAsAutomaton (2.4-1).