Avoiding large squares in partial words

作者：Blanchet Sadri F^*; Choi Ilkyoo; Mercas Robert

来源：Theoretical Computer Science, 2011, 412(29): 3752-3758.

DOI：10.1016/j.tcs.2011.04.009

• Combinatorics on words
• Partial words
• Squares
• Cubes

Well-known results on the avoidance of large squares in (full) words include the following: (1) Fraenkel and Simpson showed that we can construct an infinite binary word containing at most three distinct squares; (2) Entringer, Jackson and Schatz showed that there exists an infinite binary word avoiding all squares of the form xx such that |x| >= 3, and that the bound 3 is optimal; (3) Dekking showed that there exists an infinite cube-free binary word that avoids all squares xx with |x| >= 4, and that the bound of 4 is best possible. In this paper, we investigate these avoidance results in the context of partial words, or sequences that may have some undefined symbols called holes. Here, a square has the form uu with u and v compatible, and consequently, such a square is compatible with a number of full words that are squares over the given alphabet. We show that (1) holds for partial words with at most two holes. We prove that (2) extends to partial words having infinitely many holes. Regarding (3), we show that there exist binary partial words with infinitely many holes that avoid cubes and have only eleven full word squares compatible with factors of it. Moreover, this number is optimal, and all such squares xx satisfy |x| <= 4.

• 出版日期2011-7-1