Addition chains

[Christian G. Bower]

Technical point:

It appears you are actually referring to the free semigroup of n
generators. Words of length 2 in the free group are:

aa, ab, ab', ba, ba', bb, a'a', a'b, a'b', b'a, b'a', b'b'

------ Original Message ------
From: Colin Mallows <colinm at research.avayalabs.com>
To: seqfan at ext.jussieu.fr
Subject: Addition chains

> 
> Following on the recent interest in addition chains, may I draw
> attention to related problems for a free group on two generators.  
> Namely, given a free group with generators a and b,  how many multiplies 
> are needed to compute all the words of length n?  (See A075099).   For
> computing a single word of length n, what is the worst case word, and how 
> many multiplies does it need?  (Clearly  at least A003313).   
> 
> And free groups with three generators, etc.
> 
>    Colin Mallows (colinm at research.avayalabs.com)
> 
>