Dear GAP Forum

Cinzia Casagrande wrote:

I have the following problem: I have a semigroup H inside a free group G.
G is of finite rank but clearly infinite. H is given by some generators,
but they could be redundant or have some relations. I would like to know
the relations between these generators in the semigroup H, or at least to
know which generators are necessary to get H. Is this possible in some
way?

This can be done by the Knuth-Bendix procedure, but it is a little
complicated. I give an example here using my KBMAG package. This is
not yet available with GAP4 but will be available with Version 4.3,
which should be released before too long! If you want to send me an
example of yours to try, then I would happily do so.

I chose the sub-semigroup H of the free group <a,b> of rank 2 defined
by H = < a^-1, a*b, b^3, b^-2 >, which has some relations among the
generators.

We need to set the free group up as a semigroup, which means
introducing new semigroup generators A, B and o for a^-1 and b^-1 and
the identity element 1. The generators of H are also introduced as
new generators. This is done in GAP by:

F:=FreeSemigroup(9);
w:=F.1; x:=F.2; y:=F.3; z:=F.4; o:=F.5; a:=F.6; A:=F.7; b:= F.8; B:=F.9;
rels := [[o*a,a], [a*o,a], [o*A,A], [A*o,A],
         [o*b,b], [b*o,b], [o*B,B], [B*o,B],
         [a*A,o], [A*a,o], [b*B,o], [B*b,o],
         [w,A],   [x,a*b], [y,b^3], [z,B^2] ];
S := F/rels;

Now we make this into a rewriting system.

RequirePackage("kbmag");
R:=KBMAGRewritingSystem(S);

We need to choose an ordering on the words in F which ensures that a
reduced word in the rewriting system will always be written in the
generators w,x,y,z of H whenever there is a choice.This will ensure
that a confluent rewriting system will include a confluent rewriting
system for H. This can be done with the wreath product ordering, by
putting the generators of H on a lower level to the other generators.

SetOrderingOfKBMAGRewritingSystem(R,"wreathprod",[1,1,1,1,2,2,2,2,2]);

Now we can run the Knuth-Bendix completion process.

gap> MakeConfluent(R);
true
gap> Rules(R);
[ [ _s5*_s6, _s6 ], [ _s6*_s5, _s6 ], [ _s5^2, _s5 ], [ _s5*_s1, _s1 ], 
  [ _s1*_s5, _s1 ], [ _s7, _s6*_s1 ], [ _s1*_s6, _s6*_s1 ], [ _s5*_s2, _s2 ], 
  [ _s2*_s5, _s2 ], [ _s8, _s6*_s1*_s2 ], [ _s3*_s5, _s3 ], [ _s9, _s6*_s3 ], 
  [ _s3*_s6*_s1*_s2, _s6*_s1 ], [ _s4*_s5, _s4 ], 
  [ _s4*_s6*_s3, _s6*_s1*_s2 ], [ _s2*_s6*_s1*_s2, _s6*_s4 ], 
  [ _s4*_s6*_s1*_s2, _s6*_s1*_s2*_s4 ], [ _s6^2*_s1, _s5 ], [ _s5*_s3, _s3 ], 
  [ _s5*_s4, _s4 ], [ _s2*_s6*_s3, _s6 ], [ _s3*_s4, _s1*_s2 ] ]

The generators of S are printed here as _s1,...,_s9.

To get the relations of H, just pick out those that only involve
_s1 - _s4. These are:

[ _s3*_s1*_s2, _s1*_s2*_s3 ],
[ _s4*_s1*_s2, _s1*_s2*_s4 ],
[ _s1*_s2*_s1*_s2*_s4*_s2, _s2 ],
[ _s1*_s2*_s1*_s2*_s1*_s2, _s3 ],
[ _s2*_s1*_s2*_s1*_s2*_s4, _s2 ],
[ _s4*_s3, _s1*_s2 ],
[ _s1*_s2*_s1*_s2*_s4^2, _s4 ],
[ _s1^2*_s2*_s1*_s2*_s4, _s1 ],
[ _s3*_s4, _s1*_s2 ],
[ _s2*_s1*_s2*_s4*_s1, _s1*_s2*_s1*_s2*_s4 ]

Remember that _s1 = a^-1, _s2 = a*b, _s3 = b^3, _s4 = b^-2.

These relations are highly redundant as a semigroup presentation of H -
they constitute a confluent rewriting system for H.

(Note that _s1*_s2*_s1*_s2*_s4 is actually equal to the identity element
of F, but this was not included as a generator of H. If we include
_s5 (the identity) as a generator of H, we get the slightly simpler set of
relations:

[ _s5^2, _s5 ], [ _s5*_s1, _s1 ], [ _s1*_s5, _s1 ], [ _s5*_s2, _s2 ], 
[ _s2*_s5, _s2 ], [ _s5*_s3, _s3 ], [ _s5*_s4, _s4 ], [ _s3*_s5, _s3 ], 
  [ _s4*_s5, _s4 ], [ _s3*_s4, _s1*_s2 ] ] )

Derek Holt.