Lyndon words; Nyldon words; complete factorization of the free monoid; Lazard factorization; Hall set; comma-free code
Abstract :
[en] 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. In a Mathoverflow post dating from November 2014, Darij Grinberg defines a variant of Lyndon words, which he calls Nyldon words, by reversing the lexicographic order. In a recent collaboration with Emilie Charlier (University of Liège) and Manon Philibert (Aix-Marseille University), 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. In our paper, we investigate this new family of words by presenting some of their properties.
Disciplines :
Mathematics
Author, co-author :
Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Nyldon words
Publication date :
15 January 2020
Number of pages :
22
Event name :
Joint Mathematics Meetings (JMM2020)
Event organizer :
The American Mathematical Society (AMS) and the Mathematical Association of America (MAA)
Event place :
Denver, Colorado, United States
Event date :
du 15 au 18 janvier 2020
By request :
Yes
Audience :
International
Funders :
BAEF - Belgian American Educational Foundation FRIA - Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture
Commentary :
Work in collaboration with Émilie Charlier (ULiège) and Manon Philibert (Université Aix-Marseille). // Travail en collaboration avec Émilie Charlier (ULiège) et Manon Philibert (Université Aix-Marseille).
