% This file was created automatically from fpsemi.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  fpsemi.msk                GAP documentation                Isabel Araujo
%%
%A  @(#)$Id: fpsemi.msk,v 1.27 2002/08/09 17:49:33 gap Exp $
%%
%Y  (C) 1999 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Finitely Presented Semigroups and Monoids}

A *finitely presented semigroup* (resp. *finitely presented monoid*)
is a quotient of a free semigroup (resp. free monoid) on a finite 
number of generators over a finitely generated congruence on
the free semigroup (resp. free monoid).

Finitely presented semigroups are obtained by factoring a free semigroup 
by a set of relations (a generating set for the congruence), ie, a set of
pairs of words in the free semigroup.

\beginexample
gap> f:=FreeSemigroup("a","b");;
gap> x:=GeneratorsOfSemigroup(f);;
gap> s:=f/[ [x[1]*x[2],x[2]*x[1]] ];
<fp semigroup on the generators [ a, b ]>
gap> GeneratorsOfSemigroup(s);
[ a, b ]
gap> RelationsOfFpSemigroup(s);
[ [ a*b, b*a ] ]
\endexample

Finitely presented monoids are obtained by factoring a free monoid by
a set of relations, i.e. a set of pairs of words in the free monoid. 

\beginexample
gap> f:=FreeMonoid("a","b");;
gap> x:=GeneratorsOfMonoid(f);
[ a, b ]
gap> e:=Identity(f);
<identity ...>
gap> m:=f/[ [x[1]*x[2],e] ];
<fp monoid on the generators [ a, b ]>
gap> RelationsOfFpMonoid(m);
[ [ a*b, <identity ...> ] ]
\endexample

Notice that for {\GAP} a finitely presented monoid is not a finitely 
presented semigroup.

\beginexample
gap> IsFpSemigroup(m);
false
\endexample

However, one can build a finitely presented semigroup isomorphic
to that finitely presented monoid (see "IsomorphismFpSemigroup").

Also note that is not possible to refer to the generators by their names.
These names are not variables, but just display figures.
So, if one wants to access the generators by their names, one first has to 
introduce the respective variables and to assign the generators to them.
 
\beginexample
gap> f:=FreeSemigroup("a","b");;
gap> x:=GeneratorsOfSemigroup(f);;
gap> s:=f/[ [x[1]*x[2],x[2]*x[1]] ];;
gap> a;
Variable: 'a' must have a value

gap> a:=GeneratorsOfSemigroup(s)[1];
a
gap> b:=GeneratorsOfSemigroup(s)[2];
b
gap> a in f;
false
gap> a in s;
true
\endexample

The generators of the free semigroup (resp. free monoid) are different 
from the generators of the finitely presented semigroup (resp. finitely
presented monoid) (even though they are displayed by the same names). 
This means that words in the generators of the free semigroup (resp.
free monoid) are not elements of the finitely presented semigroup (resp. 
finitely presented monoid). Conversely elements of the finitely presented 
semigroup (resp. finitely presented monoid) are not words of the free
semigroup (resp. free monoid).

Calculations comparing elements of an finitely presented semigroup
may run into problems: there are finitely presented semigroups for 
which no algorithm exists (it is known that no such algorithm can exist) 
that will tell for two arbitrary words in the generators whether the 
corresponding elements in the finitely presented semigroup are equal.  
Therefore the methods used by {\GAP} to compute in finitely presented 
semigroups may run into warning errors, run out of memory or run forever. 
If the finitely presented semigroup is (by theory) known to be 
finite the algorithms are guaranteed to terminate (if there is sufficient 
memory available), but the time needed for the calculation cannot be 
bounded a priori. The same can be said for monoids.
(See "Rewriting Systems and the Knuth-Bendix Procedure".)

\beginexample
gap> a*b=a^5;
false
gap> a^5*b^2*a=a^6*b^2;
true
\endexample

Note than elements of a finitely presented semigroup (or monoid) are not 
printed in a unique way:

\beginexample
gap> a^5*b^2*a;
a^5*b^2*a
gap> a^6*b^2;
a^6*b^2
\endexample

\>IsSubsemigroupFpSemigroup( <t> ) A

	true if <t> is a finitely presented semigroup or a 
	subsemigroup of a finitely presented semigroup
	(generally speaking, such a subsemigroup can be constructed
	with `Semigroup(<gens>)', where <gens> is a list of elements
	of a finitely presented semigroup).


\>IsSubmonoidFpMonoid( <t> ) A

	true if <t> is a finitely presented monoid or a 
	submonoid of a finitely presented monoid 
	(generally speaking, such a semigroup can be constructed
	with `Monoid(<gens>)', where <gens> is a list of elements
	of a finitely presented monoid).

	A submonoid of a monoid has the same identity as the monoid.


\>IsFpSemigroup( <s> ) P

is a synonym for `IsSubsemigroupFpSemigroup(<s>)' and 
`IsWholeFamily(<s>)' (this is because a subsemigroup
of a finitely presented semigroup is not necessarily finitely presented).


\>IsFpMonoid( <m> ) P

is a synonym for `IsSubmonoidFpMonoid(<m>)' and 
`IsWholeFamily(<m>)' (this is because a submonoid 
of a finitely presented monoid is not necessarily finitely presented).


\>IsElementOfFpSemigroup( <elm> ) C

	returns true if <elm> is an element of a finitely presented semigroup. 


\>IsElementOfFpMonoid( <elm> ) C

	returns true if <elm> is an element of a finitely presented monoid. 


\>FpGrpMonSmgOfFpGrpMonSmgElement( <elm> ) O

	returns the finitely presented group, monoid or semigroup to which 
	<elm> belongs



\beginexample
gap> f := FreeSemigroup("a","b");;
gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
gap> s := f / [ [ a^2 , a*b ] ];;
gap> IsFpSemigroup( s );
true
gap> t := Semigroup( [ GeneratorsOfSemigroup( s )[ 1 ] ]);
<semigroup with 1 generator>
gap> IsSubsemigroupFpSemigroup( t );
true
gap> IsElementOfFpSemigroup( GeneratorsOfSemigroup( t )[ 1 ] );
true
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creating Finitely Presented Semigroups}

\>`<F>/<rels>'{quotient!of free semigroup}  

creates a finitely presented semigroup given by the presentation
$\langle<gens>\mid<rels>\rangle$ where <gens> are the generators of the free
semigroup <F>, and the relations <rels> are entered as pairs of words in the
generators of  the free semigroup. 

\beginexample
gap> f:=FreeSemigroup(3);;
gap> s:=GeneratorsOfSemigroup(f);;
gap> f/[ [s[1]*s[2]*s[1],s[1]] , [s[2]^4,s[1]] ];
<fp semigroup on the generators [ s1, s2, s3 ]>
\endexample

One may also call the following functions to construct finitely
presented semigroups:
\>FactorFreeSemigroupByRelations( <f>, <rels> ) F

for a free semigroup <f> and <rels> is a list of
pairs of elements of <f>. Returns the finitely presented semigroup 
which is the quotient of <f> by the least congruence on <f> generated by
the pairs in <rels>.



\beginexample
gap> FactorFreeSemigroupByRelations(f,[[s[1]*s[2]*s[1],s[1]],[s[2]^4,s[1]]]);
<fp semigroup on the generators [ s1, s2, s3 ]>
\endexample

Finally, if one has a finitely presented group or a finitely presented 
monoid, to find an isomorphic finitely presented semigroup use
\>IsomorphismFpSemigroup( <s> ) A

for a semigroup <s> returns an isomorphism from <s> to a 
finitely presented semigroup 



\beginexample
gap> f := FreeGroup(2);;
gap> g := f/[f.1^4,f.2^5];
<fp group on the generators [ f1, f2 ]>
gap> phi := IsomorphismFpSemigroup(g);
MappingByFunction( <fp group on the generators 
[ f1, f2 ]>, <fp semigroup on the generators 
[ <identity ...>, f1^-1, f1, f2^-1, f2 
 ]>, function( x ) ... end, function( x ) ... end )
gap> s := Range(phi);
<fp semigroup on the generators [ <identity ...>, f1^-1, f1, f2^-1, f2 ]>
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparison of Elements of Finitely Presented Semigroups}

\>`<a> = <b>'{comparison!fp semigroup elements}
 
Two elements of a finitely presented semigroup are equal if they are equal in
the semigroup. Nevertheless they may be represented as different words in the
generators. Because of the fundamental problems mentioned in the
introduction to this chapter such a test may take a very long time and cannot be
guaranteed to finish (see "Rewriting Systems and the Knuth-Bendix Procedure").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Preimages in the Free Semigroup}

\>FreeSemigroupOfFpSemigroup( <s> ) A

	returns the underlying free semigroup for the finitely presented 
	semigroup <s>, ie, the free semigroup over which <s> is defined 
	as a quotient
	(this is the free semigroup generated by the free generators provided 
	by `FreeGeneratorsOfFpSemigroup(<s>)').


\>FreeGeneratorsOfFpSemigroup( <s> ) A

returns the underlying free generators corresponding to the 
	generators of the finitely presented semigroup <s>.  


\>RelationsOfFpSemigroup( <s> ) A

returns the relations of the finitely presented semigroup <s> as
pairs of words in the free generators provided by
`FreeGeneratorsOfFpSemigroup(<s>)'.




\beginexample
gap> f := FreeSemigroup( "a" , "b" );;
gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
gap> s := f / [ [ a^3 , a ] , [ b^3 , b ] , [ a*b , b*a ] ];
<fp semigroup on the generators [ a, b ]>
gap> Size( s );
8
gap> fs := FreeSemigroupOfFpSemigroup( s );;
gap> f = fs;
true
gap> FreeGeneratorsOfFpSemigroup( s );
[ a, b ]
gap> RelationsOfFpSemigroup( s );
[ [ a^3, a ], [ b^3, b ], [ a*b, b*a ] ]
\endexample

Elements of a finitely presented semigroup are not words, but are represented
using a word from the free semigroup as representative. 

\>UnderlyingElement( <elm> )!{fp semigroup elements} O 

for an element <elm> of a finitely presented semigroup, it 
returns the word from the free semigroup that is used as a
representative for <elm>.

\beginexample
gap> w := GeneratorsOfSemigroup(s)[1] * GeneratorsOfSemigroup(s)[2];
a*b
gap> IsWord (w );
false
gap> ue := UnderlyingElement( w );
a*b
gap> IsWord( ue );
true
\endexample

\>ElementOfFpSemigroup( <fam>, <w> ) O

for a family <fam> of elements of a finitely presented semigroup and 
a word <w> in the free generators underlying this finitely presented
semigroup, this operation creates the element of the finitely 
presented semigroup with the representative <w> in the free semigroup.


\beginexample
gap> fam := FamilyObj( GeneratorsOfSemigroup(s)[1] );;
gap> ge := ElementOfFpSemigroup( fam, a*b );
a*b
gap> ge in f;
false
gap> ge in s;
true
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finitely presented monoids}

\>`<F>/<rels>'{quotient!of free monoid} 

creates a finitely presented monoid given by the monoid presentation 
$\langle<gens>\mid<rels>\rangle$ where <gens> are the generators of 
the free monoid <F>, and the relations <rel> are entered as pairs of 
words in both the identity and the generators of the free monoid.

\beginexample
gap> f := FreeMonoid( 3 );
<free monoid on the generators [ m1, m2, m3 ]>
gap> x := GeneratorsOfMonoid( f );
[ m1, m2, m3 ]
gap> e:= Identity ( f );
<identity ...>
gap> m := f/[ [x[1]^3,e] , [x[1]*x[2],x[2] ]];
<fp monoid on the generators [ m1, m2, m3 ]>
\endexample

The functionality available for finitely presented monoids is essentially
the same as that available for finitely presented semigroups,
and thus the previous sections apply (with the obvious changes)
to finitely presented monoids.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Rewriting Systems and the Knuth-Bendix Procedure}

If a finitely presented semigroup has a confluent rewriting system then 
it has a solvable word problem, that is, there is an algorithm to decide 
when two words in the free underlying semigroup represent the same element 
of the finitely presented semigroup. 
Indeed, once we have a confluent rewriting system, it is possible to 
successfully test that two words represent the same element in the 
semigroup, by reducing both words using the rewriting system rules. 
This is, at the moment, the method that {\GAP} uses to check equality
in finitely presented semigroups and monoids.

\>ReducedConfluentRewritingSystem( <S> ) A
\>ReducedConfluentRewritingSystem( <S> , <ordering> ) A

in the first form returns a reduced confluent rewriting system 
of the finitely presented semigroup or monoid <S> with respect 
to the length plus lexicographic ordering on words (also
called the shortlex ordering; for the definition see for example
Sims \cite{Sims94}).

In the second form it returns a reduced confluent rewriting system of
the finitely presented semigroup or monoid <S> with respect to the 
reduction ordering <ordering> (see "Orderings"). 

Notice that this might not terminate. In particular, if the semigroup or 
monoid <S> does not have a solvable word problem then it this will
certainly never end.
Also, in this case, the object returned is an immutable 
rewriting system, because once we have a confluent
rewriting system for a finitely presented semigroup or monoid we do 
not want to allow it to change (as it was most probably very time 
consuming to get it in the first place). Furthermore, this is also
an attribute storing object (see "Representation").



\beginexample
gap> f := FreeSemigroup( "a" , "b" );;
gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
gap> g := f /  [ [ a^2 , a*b ] , [ a^4 , b] ];;
gap> rws := ReducedConfluentRewritingSystem(g);
Rewriting System for Semigroup( [ a, b ] ) with rules 
[ [ a*b, a^2 ], [ a^4, b ], [ b*a, a^2 ], [ b^2, a^2 ] ]
\endexample

The creation of a reduced confluent rewriting system for a semigroup
or for a monoid, in {\GAP}, uses the Knuth-Bendix procedure for strings, 
which manipulates a rewriting system of the semigroup or monoid and attempts 
to make it confluent (See "Rewriting Systems". See also Sims \cite{Sims94}). 
(Since the word problem for semigroups/monoids is not solvable in general, 
Knuth-Bendix procedure cannot always terminate). 

In order to apply this procedure we will build a rewriting system
for the semigroup or monoid, which we will call a  *Knuth-Bendix Rewriting 
System* (we need to define this because we need the rewriting system
to store some information needed for the implementation of the
Knuth-Bendix procedure). 

Actually, Knuth-Bendix Rewriting Systems do not only serve this purpose.
Indeed these  are objects which are mutable and which can be manipulated 
(see "rewriting systems").

Note that the implemented version of the Knuth-Bendix procedure, in {\GAP}
returns, if it terminates, a confluent rewriting system which is reduced.
Also, a reduction ordering has to be specified when building a rewriting
system. If none is specified, the shortlex ordering is assumed
(note that the procedure may terminate with a certain ordering and
not with another one).

On Unix systems it is possible to replace the built-in Knuth-Bendix by other
routines, for example the package `kbmag' offers such a possibility.

\>`KB_REW' V
\>`GAPKB_REW' V

KB_REW is a global record variable whose components contain functions
used for Knuth-Bendix. By default `KB_REW' is assigned to
`GAPKB_REW', which contains the KB functions provided by
the GAP library.


\>KnuthBendixRewritingSystem(<s>,<wordord>)
\>KnuthBendixRewritingSystem(<m>,<wordord>)

in the first form, for a semigroup $s$ and a reduction ordering
for the underlying free semigroup, it returns the Knuth-Bendix 
rewriting system of the finitely presented semigroup <s> using the 
reduction ordering <wordord>.
In the second form, for a monoid $m$ and a reduction ordering
for the underlying free semigroup, it returns the Knuth-Bendix 
rewriting system of the finitely presented semigroup <s> using the 
reduction ordering <wordord>.


\>SemigroupOfRewritingSystem( <rws> ) A

returns the semigroup over which <rws> is
a rewriting system


\>MonoidOfRewritingSystem( <rws> ) A

returns the monoid over which <rws> is a rewriting system


\>FreeSemigroupOfRewritingSystem( <rws> ) A

returns the free semigroup over which <rws> is
a rewriting system


\>FreeMonoidOfRewritingSystem( <rws> ) A

returns the free monoid over which <rws> is
a rewriting system



\beginexample
gap> f1 := FreeSemigroupOfRewritingSystem(rws);
<free semigroup on the generators [ a, b ]>
gap> f1=f;
true
gap> g1 := SemigroupOfRewritingSystem(rws);
<fp semigroup on the generators [ a, b ]>
gap> g1=g;
true
\endexample

As mentioned before, having a confluent rewriting system, one can decide
whether two words represent the same element of a finitely 
presented semigroup (or finitely presented monoid). 

\beginexample
gap> a := GeneratorsOfSemigroup( g )[ 1 ];
a
gap> b := GeneratorsOfSemigroup( g )[ 2 ];
b
gap> a*b*a=a^3;
true
gap> ReducedForm(rws,UnderlyingElement(a*b*a));
a^3
gap> ReducedForm(rws,UnderlyingElement(a^3));
a^3
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Todd-Coxeter Procedure}

This procedure gives a standard way of finding a transformation
representation of a finitely presented semigroup. Usually
one does not explicitly call this procedure but uses
IsomorphismTransformationSemigroup 
or HomomorphismTransformationSemigroup 
(see "IsomorphismTransformationSemigroup").

\>CosetTableOfFpSemigroup( <r> ) A

<r> is a right congruence of an fp-semigroup <S>.
This attribute is the coset table of FP semigroup 
<S> on a right congruence <r>.
Given a right congruence <r> we represent <S> as a set of 
transformations of the congruence classes of <r>.


The images   of the cosets under the   generators are compiled in  a list
<table> such that  <table[i][s]> contains  the image  of  coset <s> under
generator <i>.   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%
%E