Prague Stringology Conference 2010
Golnaz Badkobeh and Maxime Crochemore
Bounded Number of Squares in Infinite Repetition-Constrained 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 sketch of the new 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |