Not so many runs in strings

Mathieu Giraud 1, 2, *
* Auteur correspondant
2 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Since the work of Kolpakov and Kucherov in 1998, it is known that \rho(n), the maximal number of runs in a string, is linear in the length n of the string. A lower bound of 3/(1 + \sqrt{5}) n = 0.927 n has been given by Franek and al., and upper bounds have been recently provided by Rytter, Puglisi and al., and Crochemore and Ilie (1.6n). However, very few properties are known for the \rho(n)/n function. We show here by a simple argument that this function converges and that its limit is never reached. We further study the asymptotic behavior of the number of runs with short periods. We provide a new bound for some microruns : we show that there is no more than 0.971n runs of period at most 9 in binary strings. Finally, this technique improves the previous best known upper bound, showing that the total number of runs in a binary string of length n is below 1.52n.
Type de document :
Communication dans un congrès
2nd International Conference on Language and Automata Theory and Applications (LATA 2008), Mar 2008, Tarragona, Spain. 2008, LNCS
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00271630
Contributeur : Mathieu Giraud <>
Soumis le : mercredi 9 avril 2008 - 17:32:22
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 12:27:10

Fichier

giraud-lata-08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00271630, version 1

Collections

Citation

Mathieu Giraud. Not so many runs in strings. 2nd International Conference on Language and Automata Theory and Applications (LATA 2008), Mar 2008, Tarragona, Spain. 2008, LNCS. 〈inria-00271630〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

87