[GAP Forum] free bands

[James Mitchell]

Dear Joao, dear Forum,

One correction to my previous mail: the comment `i.e. the set of all
square free finite words over the ...' is nonsense since there are
infinitely many square free words over any alphabet with at least 3
letters. So, please ignore this comment.

Regards,

James

On 2 July 2012 11:24, James Mitchell <jdm3 at st-and.ac.uk> wrote:
> 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



-- 
James Mitchell
tinyurl.com/jdmitchell

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