%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  basics.tex           GAP documentation               Manuel Delgado
%%
%H  $Id: basics.tex,v 0.1 mdelgado Exp $
%%
%Y  Copyright (C)CMUP, University of Porto
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Some basic functions}

%\Section{Basics}
\> IsFpSgpAndMonoid(S) 

Tests whether a finitely presented semigroup <S> has an
identity and thus is a monoid. 
Note that while {\sf IsFpSemigroup} is part of \GAP, there is no built-in
function to test whether some object is a finitely presented monoid. 
The following examples involve the *Brandt
semigroup* $B_2$ and the *Brandt monoid*
$B_2^1$.\index{Brandt!semigroup}\index{Brandt!monoid}\index{b21} 

\beginexample
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 semigroup on the generators [ <identity ...>, a, b ]>
gap> IsFpSgpAndMonoid(b21);
true
\endexample
\beginexample
gap> f := FreeSemigroup("a","b");
<free semigroup on the generators [ a, b ]>
gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
gap> b := GeneratorsOfSemigroup( 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> b2:= f/r; 
<fp semigroup on the generators [ a, b ]>
gap> IsFpSgpAndMonoid(b2); 
false
\endexample

%\> IsIdempotent(m)  Tests if an element of a magma is idempotent.

%\> Idempotents(M)  Produces the list of idempotents of a finite magma.

\> HasCommutingIdempotents(M)  

Tests whether the idempotents of the semigroup <M> commute.

\> IsInverseSemigroup(S)  

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 {\sf IsRegularSemigroup} is part of \GAP.

\> DClassDistribution( M, K )  

Computes the number of elements of the subset K of the semigroup M in each
D-class.  
\beginexample
gap> K := Idempotents(b21);
[ <identity ...>, a^2, a*b, b*a ]
gap> DClassDistribution(b21,K);
The D-class of <identity ...> has 1 element which is in K
The D-class of a has 4 elements 2 of which are in K
The D-class of a^2 has 1 element which is in K
gap> 
\endexample

\> SOne(TS)  

Adds an identity to a transfomation semigroup, if the given semigroup is
 not a monoid. (Note that it only works for transfomation semigroups.)


%\Section{CayleyGraphs}

\> RightCayleyGraph(M)   

Computes the right Cayley graph of the monoid <M>. (It is returned as an
automaton without initial and final states.) 

\beginexample
gap> rcg := RightCayleyGraph(b21);
      |  1  2  3  4  5  6 
   -  -  -  -  -  -  -  - 
   a  |  2  4  6  4  2  4 
   b  |  3  5  4  4  4  3 
Initial state: [  ]
Accepting states: [  ]
\endexample

\>  AutCayley(rcg,x)  

<rcg> is the Cayley graph of a finite monoid and
 <x> is an element of the monoid (more precisely, the position of
 that element in the list of the elements of the monoid). It produces
 an automaton whose initial state is the identity the final state is <x>.
\beginexample
gap> AutCayley(rcg,3);
      |  1  2  3  4  5  6 
   -  -  -  -  -  -  -  - 
   a  |  2  4  6  4  2  4 
   b  |  3  5  4  4  4  3 
Initial state: [ 1 ]
Accepting state: [ 3 ]
\endexample

We give here examples of monoids of injective partial transformations that
will be used later. \index{poi4}\index{popi4} 
\beginexample
gap> g0:=Transformation([5,1,2,3,5]);
Transformation( [ 5, 1, 2, 3, 5 ] )
gap> g1:=Transformation([1,2,4,5,5]);
Transformation( [ 1, 2, 4, 5, 5 ] )
gap> g2:=Transformation([1,3,5,4,5]);
Transformation( [ 1, 3, 5, 4, 5 ] )
gap> g3:=Transformation([2,5,3,4,5]);
Transformation( [ 2, 5, 3, 4, 5 ] )
gap> g:=Transformation([2,3,4,1,5]);
Transformation( [ 2, 3, 4, 1, 5 ] )
gap> poi4:= Monoid(g0,g1,g2,g3);;
gap> popi4:= Monoid(g,g0,g1,g2,g3);
gap> Size(poi4);Size(popi4);
70
141
\endexample