[GAP Forum] free bands

[James Mitchell]

Dear Joao, dear forum,

You can produce the elements of the free band with n generators using
the code at the end of this email: FreeBand(4), for example will
return the free band on 4 as lists of positive integers, i.e. the set
of all square free finite words over the alphabet "1", "2", "3", "4".

It takes about 2.5 seconds on my laptop to produce the elements of the
free band on 4 points. Since there are 2, 751,884,514, 765, elements
of the free band on 5 generators, it seems unlikely that these could
be produced in any reasonable amount of time.

The function U(set) below creates the list of all elements of the free
band containing the letters in set (where set is a list of positive
integers).

To represent any such list as word in "a", "b", "c", and "d" do:

gap> s:=FreeSemigroup("a", "b", "c", "d");
<free semigroup on the generators [ a, b, c, d ]>
gap> a:=s.1;; b:=s.2;; c:=s.3;; d:=s.4;;

gap> fb:=FreeBand(3);;
gap> EvaluateWord([a,b,c,d], Random(fb));
a*b*c*b*a*c


The code....

U:=function(P)
  local out,u0, u1, w0, w1;

  if Length(P)=1 then
    return List(P, x-> [x]);
  fi;
  out:=[];
  for u0 in P do
    for w0 in U(Difference(P, [u0])) do
      for u1 in P do
        for w1 in U(Difference(P, [u1])) do
          Add(out, Collapse(w0,u0,u1,w1));
        od;
      od;
    od;
  od;
  return out;
end;

Collapse:=function(v0, u0, u1, v1)
  local i, j;
  w0:=Concatenation(v0, [u0]);
  w1:=Concatenation([u1], v1);

  i:=Length(w0);

  while w0[i]<>u1 and i>1 do
    i:=i-1;
  od;

  j:=0;

  while j<=Length(w0)-i do
    j:=j+1;
    if w1[j]<>w0[i+j-1] then
      return Concatenation(w0, w1);
    fi;
  od;

  return Concatenation(w0, w1{[j+1..Length(w1)]});
end;

FreeBand:=function(n)
  local out, enum, i;
  out:=[];
  enum:=EnumeratorOfCombinations([1..n]);
  for i in [2..2^n] do
    Append(out, U(enum[i]));
  od;
  return out;
end;

if not IsBound(EvaluateWord) then
  EvaluateWord:=function ( gens, w )
    local  i, res;
    if Length( w ) = 0  then
        return gens[1] ^ 0;
    fi;
    res := gens[w[1]];
    for i  in [ 2 .. Length( w ) ]  do
        res := res * gens[w[i]];
    od;
    return res;
  end;
fi;



>> From: Joao Araujo <mjoao at classic.univ-ab.pt>
>> Subject: [GAP Forum] free bands
>> Date: 13 July 2009 11:56:13 GMT+01:00
>> To: forum at gap-system.org
>>
>>
>> Dear all,
>>
>> I would be grateful if someone could tell me how I can use GAP to get all the elements of the free band on 3 (or 4) generators.
>>
>> I thank in advance,
>> Joao
>>
>> _______________________________________________
>> Forum mailing list
>> Forum at mail.gap-system.org
>> http://mail.gap-system.org/mailman/listinfo/forum
>
>
> --
> Dr. Alexander Konovalov               School of Computer Science
> & Centre for Interdisciplinary Research in Computational Algebra
> University of St Andrews                 Tel +44/0 (1334) 461633
> http://www.cs.st-andrews.ac.uk/~alexk    Fax +44/0 (1334) 463278
> The University of St Andrews is a charity registered in Scotland:No.SC013532
>
>
>
>
>
>
>



-- 
James Mitchell
tinyurl.com/jdmitchell

The University of St Andrews is a charity registered in Scotland : No SC013532