Factors of Words
Factors of Words
复制标题
词的因素
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
J. Pin
中科院分区：
文献类型：
--
作者：
D. Beauquier;J. Pin
设A是基数为m的字母表，nk是正整数序列，（）nwAwk ∈ = .本文证明了：如果lim supn→ ∞ kn/ ln n < 1/ lnm，则A上几乎所有长度为n的字都含有因子w，但如果lim supn→ ∞ kn/ln n> 1/ lnm，则这一性质不成立.此外，如果lim infn→ ∞ kn/ lnn >1/ lnm，则A上几乎所有长度为n的字都不包含因子w。此外，如果lim（ln ln）n n n k m α → ∞ − = ∈…然后limsup（，/ 1 exp（exp（））n n n W n k w A m α → ∞ ≤ − − and liminf（，/ 1 exp（（1 1/）exp（））n n n W n k w A m α → ∞ ≥ − −，其中W（n，kn，w，A）表示A上长度为n的字的集合，包含长度为n k的因子w。
Let A be an alphabet of cardinality m, n k be a sequence of positive integers and ( ) n w A w k ∈ = . In this paper it is shown that if lim supn→ ∞ kn/ ln n < 1/ lnm then almost all words of length n over A contain the factor w, but if lim supn→ ∞ kn/ln n> 1/ lnm then this property is not true. Also, if lim infn→ ∞ kn/ lnn >1/ lnm then almost all words of length n over A do not contain the factor w. Moreover, if lim (ln ln ) n n n k m α → ∞ − = ∈ ¡ then limsup ( , , , / 1 exp( exp( )) n n n W n k w A m α → ∞ ≤ − − and liminf ( , , , / 1 exp( (1 1/ ) exp( )) n n n W n k w A m m α → ∞ ≥ − − − , where W(n, kn,w,A) denotes the set of words of length n over A containing the factor w of length n k .