On the distribution of characteristic parameters of words

Arturo Carpi; Aldo de Luca

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

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

Abstract

top
For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

How to cite

top

Carpi, 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. [1] A. Carpi and A. de Luca, Words and special factors. Theoret. Comput. Sci. 259 (2001) 145-182. Zbl0973.68191MR1832789
  2. [2] A. Carpi and A. de Luca, Semiperiodic words and root-conjugacy. Theoret. Comput. Sci. (to appear). Zbl1063.68081MR1964629
  3. [3] A. Carpi and A. de Luca, Periodic-like words, periodicity, and boxes. Acta Informatica 37 (2001) 597-618. Zbl0973.68192MR1830469
  4. [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. [5] A. Carpi, A. de Luca and S. Varricchio, Words, univalent factors, and boxes. Acta Informatica 38 (2002) 409-436. Zbl1025.68052MR1897479
  6. [6] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997) 67-88. Zbl0921.68065MR1440670
  7. [7] A. Colosimo and A. de Luca, Special factors in biological strings. J. Theor. Biol. 204 (2000) 29-46. 
  8. [8] A. de Luca, On the combinatorics of finite words. Theoret. Comput. Sci. 218 (1999) 13-39. Zbl0916.68119MR1687752
  9. [9] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Rev. 24 (1982) 195-221. Zbl0482.68033MR652466
  10. [10] L.J. Guibas and A. M. Odlyzko, Periods in strings. J. Comb. Theory (A) 30 (1981) 19-42. Zbl0464.68070MR607037
  11. [11] M. Lothaire, Combinatorics on Words, 2nd Edition. Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997). Zbl0874.20040MR1475463
  12. [12] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, UK (2002). Zbl1001.68093MR1905123
  13. [13] R.C. Lyndon and M.P. Schützenberger, The equation in a free group. Mich. Math. J. 9 (1962) 289-298. Zbl0106.02204MR162838
  14. [14] E. Rivals and S. Rahmann, Combinatorics of periods in strings. Springer, Berlin, Lecture Notes in Comput. Sci. 2076 (2001) 615-626. Zbl0986.68101MR2066538

NotesEmbed ?

top

You must be logged in to post comments.