The standard factorization of Lyndon words: an average point of view
The standard factorization of Lyndon words: an average point of view
复制标题
Lyndon 词的标准分解：平均观点
DOI：
10.1016/j.disc.2004.11.002
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
C. Nicaud
中科院分区：
文献类型：
--
作者：
Frédérique Bassino;J. Clément;C. Nicaud
非空单词w是Lyndon单词，当且仅当它在字典顺序上严格小于它的任何适当后缀。这样的单词w要么是一个字母，要么允许进行标准的因式分解，其中v是其最小的适当后缀。对于任意林登词v，我们证明了以v作为标准分解的右因子的林登词集合是正则的，并显式地计算了相关的生成函数。接下来，考虑两个字母字母表中长度为n的Lyndon单词，我们建立了，对于均匀分布，标准分解的右因子v的平均长度渐近为3n/4。
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.