Asymptotic Properties of the Factors of Words Over a Finite Alphabet

Let A be an alphabet of cardinality m, kn be a sequence of positive integers and w e A* (|w| = kkn). In this paper it is shown that if lim sup n→∞knn <1/lnm, then almost all words of length n over A contain the factor w, but if lim sup n→∞kn/lnn > 1/lnm, then this property is not true. Also, if lim inf...kn/lnn > 1/lnm , then almost all words of length n over A do not contain the factor w. Moreover, if lim...(ln n - knln m) = a e IR, then lim sup...|W(n,kn,w,A)|/m^n < 1-exp(-exp(a)) and liminf n→∞|W(n,kn,w,A)|/m^n >1-exp(-(1-1/m)exp(a)), where W(n,kn,w,A) denotes the set of words of length n over A containing the factor w of length kn.