Asymptotic Properties of the Factors of Words Over a Finite Alphabet

• Autorzy: Tomescu I.
• Języki publikacji: EN

Abstrakty

EN

Let A be an alphabet of cardinality m, k_n be a sequence of positive integers and w e A* (|w| = kk_n). In this paper it is shown that if lim sup _n→∞k_nn <1/lnm, then almost all words of length n over A contain the factor w, but if lim sup _n→∞k_n/ln_n > 1/lnm, then this property is not true. Also, if lim inf...k_n/ln_n > 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,k_n,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.

Słowa kluczowe

EN

word; factor; recurrence relation; characteristic equation; pseudo-Vandermonde determinant; autocorrelation polynomial; generating functions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 463--470
• Opis fizyczny: Bibliogr.11 poz.

Twórcy

autor

Tomescu I.

• Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, 010014 Bucharest, Romania,

Bibliografia

• [1] C. Calude, Information and Randomness: An Algorithmic Perspective. Springer-Verlag, Berlin, 1995.
• [2] C. Calude, I. Chit¸escu, Qualitative properties of P. Martin-L¨of random sequences. Bolletino della Unione Matematica Italiana, 7, 3-B (1989), 229–240.
• [3] C. Choffrut, J. Karhumäki, Combinatorics on words. Rapport LITP 97/12, Institut Blaise Pascal, Paris, 1997, 110 p.
• [4] Ph. Flajolet, P. Kirschenhofer, R.F. Tichy, Deviations from uniformity in random strings. Probability Theory and Related Fields, 80 (1988), 139–150.
• [5] L.J. Guibas, A.M. Odlyzko, String overlaps, pattern matching, and nontransitive games. J. Combinatorial Theory, A30 (1981), 183–208.
• [6] S. Marcus, G. Păun, Infinite (almost periodic) words, formal languages and dynamical systems. Bull. EATCS, 54 (1994), 224–231.
• [7] I. Proskuriakov, Recueil de problèmes d’algèbre linèaire. Mir, Moscou, 1989.
• [8] R.P. Stanley, Enumerative Combinatorics, vol. I. Wadsworth and Brooks, California, 1986.
• [9] I. Tomescu, On words containing all short subwords. Theoret. Comput. Sci., 197 (1998), 235–240.
• [10] I. Tomescu, A threshold property concerning words containing all short factors. Bull. EATCS, 64 (1998), 166–170.
• [11] H.S. Wilf, Generatingfunctionology. Academic Press, San Diego, 1990.