> < ^ From:

> < ^ Subject:

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.

> < [top]