Finely homogeneous computations in free Lie algebras

Abstract : 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).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 1997, 1, pp.101-114
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00955693
Contributeur : Alain Monteil <>
Soumis le : mercredi 5 mars 2014 - 09:31:34
Dernière modification le : mardi 5 juin 2018 - 10:14:24
Document(s) archivé(s) le : jeudi 5 juin 2014 - 10:52:46

Fichier

dm010107.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00955693, version 1

Citation

Philippe Andary. Finely homogeneous computations in free Lie algebras. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1997, 1, pp.101-114. 〈hal-00955693〉

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

252