Displaying similar documents to “On the number of squares in partial words”

A note on the number of squares in a partial word with one hole

Francine Blanchet-Sadri, Robert Mercaş (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length is bounded by since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole, or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form where is with , and consequently, such square is compatible...

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