Originally, in 1953, Anatoly Shirshov introduces the notion of regular words. In 1954, Roger Lyndon investigates them as standard lexicographic sequences, now known as Lyndon words. But the story really begins in 1958, when Chen, Fox and Lyndon state that any word can be factorized into a unique non-increasing product of standard sequences. It took a quarter of century to find an algorithm computing this factorization. This elegant and efficient algorithm was published by Jean-Pierre Duval in 1983.

Since this paper, one can observe an increasing interest for Lyndon words. They are studied for themselves but they are also used for solving problems, proving theorems. During the last decades, new data structures have been defined such as Lyndon arrays or Lyndon trees. They appear in a multitude of theoretical and practical domains: string algorithmics, data compression, bioinformatics...

In summary, Lyndon words are of great interest for everyone interested in algorithmics. That is the main reason why this project is born 70 years after Shirshov's paper and 40 years after Duval's paper.

The Lyndex project aims to concentrate as many knowledge as possible on Lyndon words, derived algorithms and data structures.

If you are interested in Lyndon words and want to follow us, please contact us at Lyndexmail