On the distribution of characteristic parameters of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 1, pp. 67-96.

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.

DOI : https://doi.org/10.1051/ita:2002006
Classification : 68R15,  68R05
Mots clés : special factor, characteristic parameter, repeated factor
@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},
     pages = {67--96},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {1},
     year = {2002},
     doi = {10.1051/ita:2002006},
     zbl = {1032.68125},
     mrnumber = {1928159},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2002006/}
}
TY  - JOUR
AU  - Carpi, Arturo
AU  - Luca, Aldo de
TI  - On the distribution of characteristic parameters of words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
DA  - 2002///
SP  - 67
EP  - 96
VL  - 36
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2002006/
UR  - https://zbmath.org/?q=an%3A1032.68125
UR  - https://www.ams.org/mathscinet-getitem?mr=1928159
UR  - https://doi.org/10.1051/ita:2002006
DO  - 10.1051/ita:2002006
LA  - en
ID  - ITA_2002__36_1_67_0
ER  - 
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) no. 1, pp. 67-96. doi : 10.1051/ita:2002006. http://www.numdam.org/articles/10.1051/ita:2002006/

[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

Cité par Sources :