Asymptotic Properties of the Factors of Words Over a Finite Alphabet
Titel:
Asymptotic Properties of the Factors of Words Over a Finite Alphabet
Auteur:
Ioan Tomescu
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 64 (2005) nr. 1-4 pagina's 463-470
Jaar:
2005-06-27
Inhoud:
Let A be an alphabet of cardinality m, kn be a sequence of positive integers and ω∈ A* (|ω|=kn). In this paper it is shown that if lim sup_{n→∞}kn/ln n<1/ln m, then almost all words of length n over A contain the factor ω, but if lim sup_{n→∞}kn/ln n>1/ln m, then this property is not true. Also, if lim inf{n→∞}kn/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-knln m)=α∈ R, then lim sup{n→∞}|W(n,kn,ω,A)| /m^m≤1−exp (−exp(α)) and lim inf{n→∞}|W (n, kn,ω,A)|/m^n≥1−exp (−(1−1/m) exp(α)), where W(n, kn, ω, A) denotes the set of words of length n over A containing the factor ω of length kn.
Tijdschrift beschrijving