Unpublished conference/Abstract (Scientific congresses and symposiums)
Nyldon words
Charlier, Emilie
2018Workshop on Words and Complexity
 

Files


Full Text
Charlier-expose-Lyon2018.pdf
Publisher postprint (349.52 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Lyndon words; Factorization of the free monoid; Codes; Lazard sets; Hall sets; standard factorization
Abstract :
[en] The theorem of Chen-Fox-Lyndon states that every finite word can be uniquely factorized as a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to define the family of Lyndon words in a recursive way: 1) the letters are Lyndon; 2) a finite word of length greater than one is Lyndon if it cannot be factorized into a nonincreasing sequence of shorter Lyndon words. In a post on Mathoverflow in November 2014, Darij Grinberg defines a variant of Lyndon words, which he calls Nyldon words, by reversing the lexicographic order in the previous recursive definition. The class of words so obtained is not, as one might first think, the class of maximal words in their conjugacy classes. Gringberg asks three questions: 1) How many Nyldon words of length n are there? 2) Is there an equivalent to the Chen-Fox-Lyndon theorem for Nyldon words? 3) Is it true that every primitive words admits exactly one Nyldon word in his conjugacy class? In this talk, I will discuss these questions in the more general context of Lazard factorizations of the free monoid and show that each of Grinberg’s questions has an explicit answer. This is a joint work with Manon Philibert (ENS Lyon) and Manon Stipulanti (ULiège)
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Nyldon words
Publication date :
February 2018
Event name :
Workshop on Words and Complexity
Event place :
Lyon, France
Event date :
19-23 février 2018
By request :
Yes
Audience :
International
Available on ORBi :
since 08 January 2019

Statistics


Number of views
35 (2 by ULiège)
Number of downloads
7 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi