Displaying similar documents to “An algorithm for deciding if a polyomino tiles the plane”

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