The standard factorization of Lyndon words: an average point of view |
| |
Authors: | Frédérique Bassino Cyril Nicaud |
| |
Institution: | Institut Gaspard Monge, Université de Marne-la-Vallée, 5, Boulevard Descartes, 77454 Marne-la-Vallée Cedex 2, France |
| |
Abstract: | A non-empty word w 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 suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4. |
| |
Keywords: | Lyndon word Standard factorization Average-case analysis Analytic combinatorics Success run |
本文献已被 ScienceDirect 等数据库收录! |
|