The code SetReducedMultiplication for semigroups

Question

Let $S$ be a finite semigroup like this:

gap> f:=FreeSemigroup("a","b");;  
     a:=f.1;;  b:=f.2;;  
     s:=f/[[a^5,a],[b^5,a^2*b],[b^3*a,a*b^5]];;
     el:=Elements(s);

and assume you want to find the useful set $eSe$ where e is indeed el[31] an idempotent of $S$. So you do:

gap> l:=DuplicateFreeList(el[31]*el*el[31]);;

to find l as smaller as it can be:

[ a^3*b*a*b*a^4*b*a*b, a^3*b*a*b^2*a^3*b*a*b, a^3*b*a*b*a^5*b*a*b, 
      a^3*b*a*b*a*b*a^3*b*a*b, a^3*b*a*b^2*a^4*b*a*b, a^3*b*a*b^3*a^3*b*a*b, a^3*b*a*b*a^6*b*a*b, a*b*a*b*a^2*b*a^3*b*a*b,   a^3*b*a*b*a*b*a^4*b*a*b, a^3*b*a*b*a*b^2*a^3*b*a*b, a^3*b*a*b^3*a^4*b*a*b,  a^3*b*a*b*a^7*b*a*b, a^3*b*a*b*a^3*b*a^3*b*a*b, a^3*b*a*b*a^2*b*a^4*b*a*b, 
     a^3*b*a*b*a^2*b^2*a^3*b*a*b, a^3*b*a*b*a^3*b*a^4*b*a*b ]

It seems annoying finding something likea^3*b*a*b*a*b*a^4*b*a*b. Unfortunately the code SetReducedMultiplication didn’t work here and I just applied another code Position:

gap> List([1..16], i->Position(el,l[i]));
 [ 12, 25, 19, 4, 23, 20, 28, 8, 9, 10, 27, 31, 16, 17, 18, 26 ]

Is there an alternative code like SetReducedMultiplication for semigroups to reduce the lentgh of words or you suggest to use for example Position? Thanks for any hints.

Answer 1

If you use the KBMAG package:

gap> rws := KBMAGRewritingSystem(s);;
gap> MakeConfluent(rws);
true
gap> l := DuplicateFreeList(el[31] * el * el[31]);;
gap> List(l, x -> ReducedForm(rws, UnderlyingElement(x)));
[ b*a*b, a^4*b, (a*b)^2, a*b, b^2*a*b, a*b^2*a, a*(a*b)^2, a^2*b, a*b*a,
  a*b^2, a^3*b^2, a^2*(a*b)^2, a^3*b, a^2*b*a, a^2*b^2, a^3*b*a ]

SetReducedMultiplication does not work for finitely presented semigroups or monoids in GAP, and many of the methods in the GAP library for computing with finitely presented semigroups and monoids depend on a terrible implementation of the Knuth-Bendix algorithm in the GAP library. There are plans to improve this!

If you had a transformation representation of your semigroup:

gap> T := Range(IsomorphismTransformationSemigroup(s));

Then you can avoid these problems, although there is currently no method for calculating the local submonoid $eSe$ that you are interested in. If you file an issue here requesting this feature, we can add it in the next release of the Semigroups package.