How many square occurrences must a binary sequence contain

Abstract : Every binary word with at least four letters contains a square. Fraenkel and Simpson FraenkelSimpson95 showed that three distinct squares are necessary and sufficient to construct an infinite binary word. We study the following complementary question: how many square occurrences must a binary word contain? We show that this quantity is, in the limit, a constant fraction of the word length, and we give a good estimation of this constant.
Type de document :
Rapport
[Intern report] A02-R-277 || kucherov02a, 2002, 9 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00101070
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:55:48
Dernière modification le : mardi 6 mars 2018 - 17:40:58

Identifiants

  • HAL Id : inria-00101070, version 1

Collections

Citation

Gregory Kucherov, Pascal Ochem, Michael Rao. How many square occurrences must a binary sequence contain. [Intern report] A02-R-277 || kucherov02a, 2002, 9 p. 〈inria-00101070〉

Partager

Métriques

Consultations de la notice

147