I need to compute in a Free Nilpotent Lie Algebra $L$ given by a finite list of generators. For example, put the generators $\{A, B\}$. So, the linear generators for the space of $L$ is
$$\{A, B, [A,B], [A, [A,B]],\cdots\}$$
all expressions of depth $\le N$.
But it is needed to construct from this a basis $\{e(1) ... e(m)\}$ of the space of $L$ and to find the table of $[e(i), e(j)]$, with bringing the results to a canonical form.
Probably there are known algorithms for this and also program libraries (for example, for FriCAS (Axiom), Sage, Mathematica, Maple ...).
Please, who can advise?
Finding a basis for a free nilpotent Lie algebra is basically the same problem as finding a basis for a free Lie algebra, since you only need to ignore the bracket expressions above the nilpotency step. For a free Lie algebra, a basis can be found by considering any Hall set, such as the Lyndon words. A good reference for these things is chapter 4 of Reutenauer's book Free Lie Algebras.
For example consider the free nilpotent Lie algebra with 2 generators $A$ and $B$ of nilpotency step 4. The Lyndon words with letters $A$ and $B$ up to length 4 are $$A,B,AB,AAB,ABB,AAAB,AABB,ABBB.$$ To find the corresponding basis elements of the free nilpotent Lie algebra, we look at the standard factorization $w=uv$ of each word $w$, which are \begin{align} AB&=(A)(B),& AAB&=(A)(AB),& ABB&=(AB)(B),\\ AAAB&=(A)(AAB),& AABB&=(A)(ABB),& ABBB&=(ABB)(B) \end{align} From these, we can read off the basis of the free nilpotent Lie algebra, where the Lie bracket corresponding to a word $w=uv$ is the Lie bracket $[u,v]$, with the Lie brackets corresponding to $u,v$ determined recursively. So in this case we obtain the basis \begin{align} A, B, [A,B], [A,[A,B]], [[A,B],B], [A,[A,[A,B]]], [A,[[A,B],B]], [[[A,B],B],B]. \end{align} The computation of Lie brackets is a bit more tricky to describe, but essentially amounts to applying anticommutativity and the Jacobi identity in a systematic fashion using the ordering of Hall words. The precise formalism is in terms of rewriting rules for sequences of Hall words and I would recommend looking at Reutenauer's text for the details.
To give an example in the above setting, consider the Lie bracket $[AAB,B]$ of the basis elements $AAB=[A,AB] = [A,[A,B]]$ and $B$. The element $[AAB,B]$ does not appear in the basis, so it must be a linear combination of some other elements. Applying the Jacobi identity, we obtain $$[AAB,B] = [[A,AB],B] = -[[AB,B],A]-[[B,A],AB].$$ By anticommutativity, we have $$[[B,A],AB]=[-AB,AB] = 0$$ and $$[[AB,B],A] = [ABB,A] = -[A,ABB]=-AABB$$ so we conclude that $[AAB,B] = AABB$. Of course in general the brackets computed in this way can lead to more complicated linear combinations.
Regarding program libraries, free nilpotent Lie algebras have implementations at least in Sage and in GAP.