Philippe Andary - Finely homogeneous computations in free Lie algebras

dmtcs:236 - Discrete Mathematics & Theoretical Computer Science, January 1, 1997, Vol. 1 -
Finely homogeneous computations in free Lie algebrasArticle

Authors: Philippe Andary 1

  • 1 Laboratoire d'informatique fondamentale et appliquée de Rouen

We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of \textitLy_α (A) for every given multidegree alpha in \textbfN^k. We then give an algorithm to compute all the words living in \textitLy_α (A) for any given α in \textbfN^k. 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).

Volume: Vol. 1
Published on: January 1, 1997
Imported on: March 26, 2015
Keywords: finely homogeneous computations,Lie algebras,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

2 Documents citing this article

Consultation statistics

This page has been seen 287 times.
This article's PDF has been downloaded 245 times.