On the distribution of characteristic parameters of words
Carpi, Arturo ; Luca, Aldo de
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002), p. 67-96 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

For any finite word w on a finite alphabet, we consider the basic parameters R w and K w of w defined as follows: R w is the minimal natural number for which w has no right special factor of length R w and K w is the minimal natural number for which w has no repeated suffix of length K w . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

Publié le : 2002-01-01
DOI : https://doi.org/10.1051/ita:2002006
Classification:  68R15,  68R05 
@article{ITA_2002__36_1_67_0,
     author = {Carpi, Arturo and Luca, Aldo de},
     title = {On the distribution of characteristic parameters of words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {36},
     year = {2002},
     pages = {67-96},
     doi = {10.1051/ita:2002006},
     mrnumber = {1928159},
     zbl = {1032.68125},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2002__36_1_67_0}
}

Carpi, Arturo; Luca, Aldo de. On the distribution of characteristic parameters of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) pp. 67-96. doi : 10.1051/ita:2002006. http://gdmltest.u-ga.fr/item/ITA_2002__36_1_67_0/

[1] A. Carpi and A. De Luca, Words and special factors. Theoret. Comput. Sci. 259 (2001) 145-182. | MR 1832789 | Zbl 0973.68191

[2] A. Carpi and A. De Luca, Semiperiodic words and root-conjugacy. Theoret. Comput. Sci. (to appear). | MR 1964629 | Zbl 1063.68081

[3] A. Carpi and A. De Luca, Periodic-like words, periodicity, and boxes. Acta Informatica 37 (2001) 597-618. | MR 1830469 | Zbl 0973.68192

[4] A. Carpi and A. De Luca, On the distribution of characteristic parameters of words II. RAIRO: Theoret. Informatics Appl. 36 (2002) 97-127. | Numdam | MR 1928160 | Zbl 1052.68106

[5] A. Carpi, A. De Luca and S. Varricchio, Words, univalent factors, and boxes. Acta Informatica 38 (2002) 409-436. | MR 1897479 | Zbl 1025.68052

[6] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997) 67-88. | MR 1440670 | Zbl 0921.68065

[7] A. Colosimo and A. De Luca, Special factors in biological strings. J. Theor. Biol. 204 (2000) 29-46.

[8] A. De Luca, On the combinatorics of finite words. Theoret. Comput. Sci. 218 (1999) 13-39. | MR 1687752 | Zbl 0916.68119

[9] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24 (1982) 195-221. | MR 652466 | Zbl 0482.68033

[10] L.J. Guibas and A. M. Odlyzko, Periods in strings. J. Comb. Theory (A) 30 (1981) 19-42. | MR 607037 | Zbl 0464.68070

[11] M. Lothaire, Combinatorics on Words, 2nd Edition. Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997). | MR 1475463 | Zbl 0874.20040

[12] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, UK (2002). | MR 1905123 | Zbl 1001.68093

[13] R.C. Lyndon and M.P. Schützenberger, The equation a M =b N c P in a free group. Mich. Math. J. 9 (1962) 289-298. | MR 162838 | Zbl 0106.02204

[14] E. Rivals and S. Rahmann, Combinatorics of periods in strings. Springer, Berlin, Lecture Notes in Comput. Sci. 2076 (2001) 615-626. | MR 2066538 | Zbl 0986.68101