On the distribution of characteristic parameters of words

Carpi, Arturo; Luca, Aldo de

doi:10.1051/ita:2002006

Carpi, Arturo ; Luca, Aldo de

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 1, pp. 67-96.

Résumé

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.

MR Zbl

DOI : 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},
     mrnumber = {1928159},
     zbl = {1032.68125},
     language = {en},
     url = {http://archive.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  - http://archive.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 http://archive.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, Tome 36 (2002) no. 1, pp. 67-96. doi : 10.1051/ita:2002006. http://archive.numdam.org/articles/10.1051/ita:2002006/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :