Discrete Mathematics & Theoretical Computer Science
Volume 1 n° 1 (1997), pp. 101-114
| author: | Philippe Andary |
|---|---|
| title: | Finely homogeneous computations in free Lie algebras |
| keywords: | Lie algebras, finely homogeneous computations |
| abstract: | We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of Ly-alpha(A) for every given multidegree alpha in Nk. We then give an algorithm to compute all the words living in Ly-alpha(A) for any given alpha 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). |
| reference: | Philippe Andary (1997), Finely homogeneous computations in free Lie algebras, Discrete Mathematics and Theoretical Computer Science 1, pp. 101-114 |
| ps.gz-source: | dm010107.ps.gz |
| ps-source: | dm010107.ps ( 139 K ) |
| pdf-source: | dm010107.pdf ( 1742 K ) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Tue Jan 19 17:49:00 MET 1999 by gustedt