{"docId":236,"paperId":236,"url":"https:\/\/dmtcs.episciences.org\/236","doi":"10.46298\/dmtcs.236","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":68,"name":"Vol. 1"}],"section":[],"repositoryName":"Hal","repositoryIdentifier":"hal-00955693","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00955693v1","dateSubmitted":"2015-03-26 16:16:59","dateAccepted":"2015-06-09 14:44:54","datePublished":"1997-01-01 08:00:00","titles":{"en":"Finely homogeneous computations in free Lie algebras"},"authors":["Andary, Philippe"],"abstracts":{"en":"We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of \\textitLy_\u03b1 (A) for every given multidegree alpha in \\textbfN^k. We then give an algorithm to compute all the words living in \\textitLy_\u03b1 (A) for any given \u03b1 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)."},"keywords":[["finely homogeneous computations"],["Lie algebras"],"[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}