Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length) (Q1121024)

A Lyndon word is a word w in a free monoid \(A^*\) over a totally ordered alphabet A such that: \(w=uv\) \((u,v\neq w)\Rightarrow w<vu\) (where \(<\) is the alphabetic order in \(A^*)\). L words are in one-to-one correspondence with circular words without period. The author gives an algorithm which generates all L words of length \(\leq n\), in alphabetic order. One step of this algorithm is to go from a Lyndon word w to the next one; this step requires only the knowledge of w, and not of the previously created L words, and is made in linear time.