Skip to Main content Skip to Navigation
Journal articles

Fewest repetitions in infinite binary words

Abstract : A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold.
Document type :
Journal articles
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00742086
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 2:23:02 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:29 AM

File

Fewest_repetitions_in_infinite...
Files produced by the author(s)

Identifiers

Citation

Golnaz Badkobeh, Maxime Crochemore. Fewest repetitions in infinite binary words. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2012, 46 (1), pp.17-31. ⟨10.1051/ita/2011109⟩. ⟨hal-00742086⟩

Share

Metrics

Record views

338

Files downloads

389