 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
The average lengths of the factors of the standard factorization of Lyndon words
Abstract : A non-empty word w of {a; b}* is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suÆx. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is rational and compute explicitly the associated generating function. Next we establish that, for the uniform distribution over the Lyndon words of length n, the average length of the right factor v of the standard factorization is asymptotically 3n/4. Finally we present algorithms on Lyndon words derived from our work together with experimental results.
https://hal-upec-upem.archives-ouvertes.fr/hal-00619865
Contributor : Cyril Nicaud <>
Submitted on : Thursday, October 6, 2011 - 1:24:49 PM
Last modification on : Monday, September 14, 2020 - 10:24:01 AM
Long-term archiving on: : Saturday, January 7, 2012 - 2:21:52 AM
Contributor : Cyril Nicaud <>
Submitted on : Thursday, October 6, 2011 - 1:24:49 PM
Last modification on : Monday, September 14, 2020 - 10:24:01 AM
Long-term archiving on: : Saturday, January 7, 2012 - 2:21:52 AM
Files
hal.pdf
Files produced by the author(s)