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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00101070
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:55:48 PM
Last modification on : Friday, January 25, 2019 - 3:42:09 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

160