# On the distribution of characteristic parameters of words

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

- Volume: 36, Issue: 1, page 67-96
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCarpi, Arturo, and Luca, Aldo de. "On the distribution of characteristic parameters of words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.1 (2002): 67-96. <http://eudml.org/doc/245842>.

@article{Carpi2002,

abstract = {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.},

author = {Carpi, Arturo, Luca, Aldo de},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {special factor; characteristic parameter; repeated factor; finite word; finite alphabet},

language = {eng},

number = {1},

pages = {67-96},

publisher = {EDP-Sciences},

title = {On the distribution of characteristic parameters of words},

url = {http://eudml.org/doc/245842},

volume = {36},

year = {2002},

}

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

PB - EDP-Sciences

VL - 36

IS - 1

SP - 67

EP - 96

AB - 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.

LA - eng

KW - special factor; characteristic parameter; repeated factor; finite word; finite alphabet

UR - http://eudml.org/doc/245842

ER -

## References

top- [1] A. Carpi and A. de Luca, Words and special factors. Theoret. Comput. Sci. 259 (2001) 145-182. Zbl0973.68191MR1832789
- [2] A. Carpi and A. de Luca, Semiperiodic words and root-conjugacy. Theoret. Comput. Sci. (to appear). Zbl1063.68081MR1964629
- [3] A. Carpi and A. de Luca, Periodic-like words, periodicity, and boxes. Acta Informatica 37 (2001) 597-618. Zbl0973.68192MR1830469
- [4] A. Carpi and A. de Luca, On the distribution of characteristic parameters of words II. RAIRO: Theoret. Informatics Appl. 36 (2002) 97-127. Zbl1052.68106MR1928160
- [5] A. Carpi, A. de Luca and S. Varricchio, Words, univalent factors, and boxes. Acta Informatica 38 (2002) 409-436. Zbl1025.68052MR1897479
- [6] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997) 67-88. Zbl0921.68065MR1440670
- [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. Zbl0916.68119MR1687752
- [9] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24 (1982) 195-221. Zbl0482.68033MR652466
- [10] L.J. Guibas and A. M. Odlyzko, Periods in strings. J. Comb. Theory (A) 30 (1981) 19-42. Zbl0464.68070MR607037
- [11] M. Lothaire, Combinatorics on Words, 2nd Edition. Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997). Zbl0874.20040MR1475463
- [12] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, UK (2002). Zbl1001.68093MR1905123
- [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. Zbl0106.02204MR162838
- [14] E. Rivals and S. Rahmann, Combinatorics of periods in strings. Springer, Berlin, Lecture Notes in Comput. Sci. 2076 (2001) 615-626. Zbl0986.68101MR2066538

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.