# On the distribution of characteristic parameters of words

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topCarpi, Arturo, and de Luca, Aldo. "On the distribution of characteristic parameters of words." RAIRO - Theoretical Informatics and Applications 36.1 (2010): 67-96. <http://eudml.org/doc/92692>.

@article{Carpi2010,

abstract = {
For any finite word w on a finite alphabet, we consider the
basic parameters Rw and Kw of w defined as follows:
Rw is the minimal natural number for which w has no right
special factor of length Rw and Kw is the minimal
natural number for which w has no repeated suffix of length
Kw. 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, de Luca, Aldo},

journal = {RAIRO - Theoretical Informatics and Applications},

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

language = {eng},

month = {3},

number = {1},

pages = {67-96},

publisher = {EDP Sciences},

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

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

volume = {36},

year = {2010},

}

TY - JOUR

AU - Carpi, Arturo

AU - de Luca, Aldo

TI - On the distribution of characteristic parameters of words

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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 Rw and Kw of w defined as follows:
Rw is the minimal natural number for which w has no right
special factor of length Rw and Kw is the minimal
natural number for which w has no repeated suffix of length
Kw. 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/92692

ER -

## References

top- A. Carpi and A. de Luca, Words and special factors. Theoret. Comput. Sci.259 (2001) 145-182. Zbl0973.68191
- A. Carpi and A. de Luca, Semiperiodic words and root-conjugacy. Theoret. Comput. Sci. (to appear). Zbl1063.68081
- A. Carpi and A. de Luca, Periodic-like words, periodicity, and boxes. Acta Informatica37 (2001) 597-618. Zbl0973.68192
- A. Carpi and A. de Luca, On the distribution of characteristic parameters of words II. RAIRO: Theoret. Informatics Appl.36 (2002) 97-127. Zbl1052.68106
- A. Carpi, A. de Luca and S. Varricchio, Words, univalent factors, and boxes. Acta Informatica38 (2002) 409-436. Zbl1025.68052
- J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc.4 (1997) 67-88.
- A. Colosimo and A. de Luca, Special factors in biological strings. J. Theor. Biol.204 (2000) 29-46.
- A. de Luca, On the combinatorics of finite words. Theoret. Comput. Sci.218 (1999) 13-39. Zbl0916.68119
- H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Rev.24 (1982) 195-221. Zbl0482.68033
- L.J. Guibas and A. M. Odlyzko, Periods in strings. J. Comb. Theory (A)30 (1981) 19-42. Zbl0464.68070
- M. Lothaire, Combinatorics on Words, 2nd Edition. Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997). Zbl0874.20040
- M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, UK (2002). Zbl1001.68093
- R.C. Lyndon and M.P. Schützenberger, The equation aM=bNcP in a free group. Mich. Math. J.9 (1962) 289-298. Zbl0106.02204
- E. Rivals and S. Rahmann, Combinatorics of periods in strings. Springer, Berlin, Lecture Notes in Comput. Sci. 2076 (2001) 615-626. Zbl0986.68101

## NotesEmbed ?

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