2018/04/25 by Émilie Charlier, Charlier, Émilie, Manon Philibert +3 · 1 citation
Computer Science · Mathematics · #68R15 #94A45 #Advanced Algebra and Logic #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1804.09735
openalex publication_date 2018/04/25 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define the family of Lyndon words in a recursive way. If the lexicographic order is reversed in this definition, we obtain a new family of words, which are called the Nyldon words. In this paper, we show that every finite word can be uniquely factorized into a lexicographically nondecreasing sequence of Nyldon words. Otherwise stated, Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. Then we investigate this new family of words. In particular, we show that Nyldon words form a right Lazard set.