Affiliations: Faculty of Mathematics and Computer Science,
University of Bucharest, Str. Academiei 14, 010014 Bucharest, Romania.
[email protected]
Note: [] Address for correspondence: Faculty of Mathematics and Computer
Science, University of Bucharest, Str. Academiei 14, 010014 Bucharest,
Romania
Abstract: Let A be an alphabet of cardinality m, k_n be a
sequence of positive integers and ω∈ A*
(|ω|=k_n). In this paper it is shown that if lim
sup_{n→∞}k_n/ln n<1/ln m,
then almost all words of length n over A contain the factor ω, but if lim
sup_{n→∞}k_n/ln n>1/ln m,
then this property is not true. Also, if lim
inf_{n→∞}k_n/ln n>1/ln m,
then almost all words of length n over A do not contain the factor ω.
Moreover, if lim_{n→∞}(ln
n-k_nln m)=α∈ R, then lim
sup_{n→∞}|W(n,k_n,ω,A)|
/m^m≤1−exp (−exp(α)) and lim
inf_{n→∞}|W (n,
k_n,ω,A)|/m^n≥1−exp
(−(1−1/m) exp(α)), where W(n, k_n,
ω, A) denotes the set of words of length n over A containing the factor
ω of length k_n.
Keywords: Word, factor, recurrence relation, characteristic equation, pseudo-Vandermonde determinant, autocorrelation polynomial, generating function
