Displaying similar documents to “Van der Waerden's theorem and avoidability in words.”

On the D0L Repetition Threshold

Ilya Goldstein (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed...

Non-repetitive tilings.

Currie, James D., Simpson, Jamie (2002)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Squares and overlaps in the Thue-Morse sequence and some variants

Shandy Brown, Narad Rampersad, Jeffrey Shallit, Troy Vasiga (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are -regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of ) contains an overlap.

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.

The theorem of Fine and Wilf for relational periods

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

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

Similarity:

We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.