Discrete Mathematics & Theoretical Computer Science, Vol 1 (1997)

Font Size:  Small  Medium  Large

Finely homogeneous computations in free Lie algebras

Philippe Andary

Abstract


We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of Lyα(A) for every given multidegree alpha in Nk. We then give an algorithm to compute all the words living in Lyα(A) for any given α in Nk. The best known method for generating Lyndon words is that of Duval [1], which gives a way to go from every Lyndon word of length n to its successor (with respect to lexicographic order by length), in space and worst case time complexity O(n). Finally, we give a simple algorithm which uses Duval's method (the one above) to compute the next standard bracketing of a Lyndon word for lexicographic order by length. We can find an interesting application of this algorithm in control theory, where one wants to compute within the command Lie algebra of a dynamical system (letters are actually vector fields).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page