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
topHow 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.
- A. Carpi and A. de Luca, Semiperiodic words and root-conjugacy. Theoret. Comput. Sci. (to appear).
- A. Carpi and A. de Luca, Periodic-like words, periodicity, and boxes. Acta Informatica37 (2001) 597-618.
- A. Carpi and A. de Luca, On the distribution of characteristic parameters of words II. RAIRO: Theoret. Informatics Appl.36 (2002) 97-127.
- A. Carpi, A. de Luca and S. Varricchio, Words, univalent factors, and boxes. Acta Informatica38 (2002) 409-436.
- 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.
- H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Rev.24 (1982) 195-221.
- L.J. Guibas and A. M. Odlyzko, Periods in strings. J. Comb. Theory (A)30 (1981) 19-42.
- M. Lothaire, Combinatorics on Words, 2nd Edition. Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997).
- M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, UK (2002).
- R.C. Lyndon and M.P. Schützenberger, The equation aM=bNcP in a free group. Mich. Math. J.9 (1962) 289-298.
- E. Rivals and S. Rahmann, Combinatorics of periods in strings. Springer, Berlin, Lecture Notes in Comput. Sci. 2076 (2001) 615-626.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.