Nyldon words (Q2318478): Difference between revisions

Consider a totally ordered alphabet. A Lyndon word is a non-empty word that is less than all its conjugates (i.e., cyclic shifts). They are of significant importance in algebra, combinatorics and computer science. In particular, the so-called Chen-Fox-Lyndon theorem states that every finite word can be uniquely factorized as a lexicographically non-increasing sequence of Lyndon words. This theorem can be used to recursively define the family of Lyndon words. In a Mathoverflow post, Darij Grinberg defined Nyldon words by reversing the lexicographic order: letters are Nyldon; a finite word of length greater than one is Nyldon if and only if it cannot be factorized into a non-decreasing sequence of shorter Nyldon words. Nyldon words of length up to \(4\) are: \(0\), \(1\), \(10\), \(100\), \(101\), \(1000\), \(1001\), \(1011\). In this paper, the authors study in detail these words, their prefixes and suffixes. They show that the uniqueness of the Nyldon factorization implies that there are equally many Nyldon and Lyndon words of each length. Nyldon words are greater than all their Nyldon proper suffixes. This implies that Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. They also provide algorithms for computing the Nyldon factorization of a word and for generating the Nyldon words up to any given length. Nyldon words are primitive, and each primitive conjugacy class contains exactly one Nyldon word. The paper ends with a discussion of the connections between Nyldon and Lyndon words. The interested reader will also find several problems that are left open.