no. 1
On the distribution of characteristic parameters of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 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: 10.1051/ita:2002006
Classification: 68R15, 68R05
Keywords: 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},
     mrnumber = {1928159},
     zbl = {1032.68125},
     language = {en},
     url = {https://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
SP  - 67
EP  - 96
VL  - 36
IS  - 1
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2002006/
DO  - 10.1051/ita:2002006
LA  - en
ID  - ITA_2002__36_1_67_0
ER  - 
%0 Journal Article
%A Carpi, Arturo
%A Luca, Aldo de
%T On the distribution of characteristic parameters of words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 67-96
%V 36
%N 1
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita:2002006/
%R 10.1051/ita:2002006
%G en
%F 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, Volume 36 (2002) no. 1, pp. 67-96. doi: 10.1051/ita:2002006

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

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

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

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

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

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

[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. | Zbl | MR

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

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

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

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

[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. | Zbl | MR

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

Cited by Sources: