Displaying similar documents to “A note on the number of squares in a partial word with one hole”

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...

Infinite words containing squares at every position

James Currie, Narad Rampersad (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Richomme asked the following question: what is the infimum of the real numbers > 2 such that there exists an infinite word that avoids -powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is = 7/3.

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

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,...