Displaying similar documents to “Fewest repetitions in infinite binary words”

Fewest repetitions in infinite binary words

Golnaz Badkobeh, Maxime Crochemore (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance 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,...

Fewest repetitions in infinite binary words

Golnaz Badkobeh, Maxime Crochemore (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

A square is the concatenation of a nonempty word with itself. A word has period if its letters at distance 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,...

On the number of squares in partial words

Vesa Halava, Tero Harju, Tomi Kärki (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word  of length  can contain is less than . This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is , where is the size of the alphabet. Moreover, we prove that the number of distinct squares in...