Geodesic
Lyndon Words, Free Algebras and Shuffles
Canadian journal of mathematics, Tome 41 (1989) no. 4, pp. 577-591

Voir la notice de l'article provenant de la source Cambridge University Press

A Lyndon word is a primitive word which is minimum in its conjugation class, for the lexicographical ordering. These words have been introduced by Lyndon in order to find bases of the quotients of the lower central series of a free group or, equivalently, bases of the free Lie algebra [2], [7]. They have also many combinatorial properties, with applications to semigroups, pi-rings and pattern-matching, see [1], [10].We study here the Poincaré-Birkhoff-Witt basis constructed on the Lyndon basis (PBWL basis). We give an algorithm to write each word in this basis: it reads the word from right to left, and the first encountered inversion is either bracketted, or straightened, and this process is iterated: the point is to show that each bracketting is a standard one: this we show by introducing a loop invariant (property (S)) of the algorithm. This algorithm has some analogy with the collecting process of P. Hall [5], but was never described for the Lyndon basis, as far we know. 
Melançon, Guy; Reutenauer, Christophe. Lyndon Words, Free Algebras and Shuffles. Canadian journal of mathematics, Tome 41 (1989) no. 4, pp. 577-591. doi: 10.4153/CJM-1989-025-2
@article{10_4153_CJM_1989_025_2,
     author = {Melan\c{c}on, Guy and Reutenauer, Christophe},
     title = {Lyndon {Words,} {Free} {Algebras} and {Shuffles}},
     journal = {Canadian journal of mathematics},
     pages = {577--591},
     year = {1989},
     volume = {41},
     number = {4},
     doi = {10.4153/CJM-1989-025-2},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1989-025-2/}
}
TY  - JOUR
AU  - Melançon, Guy
AU  - Reutenauer, Christophe
TI  - Lyndon Words, Free Algebras and Shuffles
JO  - Canadian journal of mathematics
PY  - 1989
SP  - 577
EP  - 591
VL  - 41
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1989-025-2/
DO  - 10.4153/CJM-1989-025-2
ID  - 10_4153_CJM_1989_025_2
ER  - 
%0 Journal Article
%A Melançon, Guy
%A Reutenauer, Christophe
%T Lyndon Words, Free Algebras and Shuffles
%J Canadian journal of mathematics
%D 1989
%P 577-591
%V 41
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1989-025-2/
%R 10.4153/CJM-1989-025-2
%F 10_4153_CJM_1989_025_2

[1] 1. Duval, J. P., Factorizing words over an ordered alphabet, J. Algorithms 4 (1983), 363–381. Google Scholar

[2] 2. Chen, K. T., Fox, R. H. and Lyndon, R. C., Free differential calculus IV. - The quotient groups of the lower central series, Ann. Math. 68 (1958), 81–95. Google Scholar

[3] 3. Foata, D., La série génératrice exponentielle dans les problèmes d'énumération (Presses Univ. Montréal, 1974). Google Scholar

[4] 4. Hall, M. Jr, The theory of groups (Macmillan, New York, 1964). Google Scholar

[5] 5. Hall, P., A contribution to theory of groups of prime-power order, Proc. London Math. Soc. 36 (1933), 29–95. Google Scholar

[6] 6. Lothaire, M., Combinatorics on words (Reading, Massachusetts, 1983). Google Scholar

[7] 7. Lyndon, R. C., On Burnside problem I, Trans. Amer. Math. Soc. 77 (1954), 202–215. Google Scholar

[8] 8. Perrin, D.and Viennot, G., A note on shuffle algebras, unpublished manuscript (1981). Google Scholar

[9] 9. Radford, D. E., A natural ring basis for the shuffle algebra and an application to group schemes, Journal of Algebra 58 (1979), 432–453. Google Scholar

[10] 10. Reutenauer, C., Mots de Lyndon et un théorème de Shirshov, Ann. Sci. Maths. Québec 10 (1986), 237–245. Google Scholar

[11] 11. Schützenberger, M. P., Sur une propriété combinatoire des algèbres de Lie libres pouvant être utilisée dans un problème de mathématiques appliquées (Algèbre et Théorie des Nombres) Paris (1958/59). Google Scholar

[12] 12. Ree, R., Lie elements and an algebra associated with shuffles, Ann. Math 68 (1958), 210–220. Google Scholar

[13] 13. Sweedler, M. E., Hopf algebras (Benjamin, 1969). Google Scholar

Cité par Sources :