Avoidable Binary Patterns in Partial Words REVISED PAPER

F. Blanchet-Sadri1 Robert Merca2 s Eric Weissenstein4 November 16, 2011 Sean Simmons3

Abstract The problem of classifying all the avoidable binary patterns in (full) words has been completely solved (see Chapter 3 of M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002). In this paper, we classify all the avoidable binary patterns in partial words, or sequences that may have some undened positions called holes. In particular we show that, if we do not substitute any variable of the pattern by a partial word consisting of only one hole, the avoidability index of the pattern remains the same as in the full word case. Keywords: Combinatorics on words; Partial words; Binary patterns; Avoidable patterns; Avoidability index.
This material is based upon work supported by the National Science Foundation under Grant No. DMS0754154. The Department of Defense is also gratefully acknowledged. Part of this paper was presented at LATA 2010 [4]. We thank the referees of some preliminary versions of this paper for their very valuable comments and/or suggestions. A World Wide Web server interface has been established at www.uncg.edu/cmp/research/unavoidablesets4 for automated use of the program. Authors work was partially supported by Research Grant No. 1323 U07 E30 N2008/InvAct/Bel, G./BJ01 and Research Grant No. 1355 U07 E30 N-2010PFR-URV-B202 of the University Rovira i Virgili. 1 Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 274026170, USA, [email protected] 2 GRLMC, Departament de Filologies Rom`niques, Universitat Rovira i Virgili, Av. a Catalunya 35, Tarragona, 43002, Spain, [email protected] 3 Department of Mathematics, The University of Texas at Austin, 2515 Speedway Rm 8, Austin, TX 787120233, USA 4 Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Amos Eaton 301, 110 8th Street, Troy, NY 12180, USA

Introduction

A pattern p is a word over an alphabet E of variables, denoted by , , , . . ., and the associated set, over a nite alphabet A, is built by replacing ps variables with non-empty words over A, so that the occurrences of the same variable be replaced with the same word. The concept of unavoidable pattern, see Section 2, was introduced, in the context of (full) words, by Bean, Ehrenfeucht and McNulty [1] (and by Zimin who used the terminology blocking sets of terms [15]). Although they characterized such patterns (in fact, avoidability can be decided using the Zimin algorithm by reduction of patterns), there is no known characterization of the patterns unavoidable over a k-letter alphabet (also called k-unavoidable). An alternative is to nd all unavoidable patterns for a xed alphabet size. The unary patterns, or powers of a single variable , were investigated by Thue [13, 14]: is unavoidable, is 2-unavoidable but 3-avoidable, and m with m 3 is 2-avoidable. Schmidt proved that there are only nitely many binary patterns, or patterns over E = {, }, that are 2-unavoidable [11, 12]. Later on, Roth showed that there are no binary patterns of length six or more that are 2-unavoidable [10]. The classication of unavoidable binary patterns was completed by Cassaigne [5] who showed that is 2-avoidable. In this paper, our goal is to classify all binary patterns with respect to partial word avoidability. A partial word is a sequence of symbols from a nite alphabet that may have some undened positions, called holes, and denoted by s. Here is compatible with, or matches, every letter of the alphabet. In this context, in order for a pattern p to occur in a partial word, it must be the case that for each variable of p, all its substituted partial words be pairwise compatible. The contents of our paper is as follows: In Section 2, we recall some basic denitions regarding partial words, and dene our terminology on unavoidable patterns in this context. In Section 3, we start our investigation of avoidability of binary patterns in partial words. There, using iterated morphisms, we construct binary partial words with innitely many holes that avoid the patterns and . In Section 4, using noniterated morphisms, we construct such words that avoid the patterns and . In Section 5, by proving that over a binary alphabet there exist partial words with innitely many holes that non-trivially avoid the pattern , we reach one of our goals of proving that all binary patterns 2avoidable in full words are also non-trivially 2-avoidable in partial words (an occurrence of a pattern is non-trivial if none of its variables is substituted 2

by a partial word consisting of only one hole). In fact, our results show that the so-called avoidability index of a binary pattern remains unchanged in the context of non-trivial avoidability in partial words. Finally in Section 6, we conclude by characterizing almost all binary patterns in terms of (not restricted to non-trivial) avoidability in partial words.

Preliminaries

For more information regarding concepts on partial words, the reader is referred to [2]. Cassaignes Chapter 3 of [8] provides background on unavoidable patterns in the context of full words. Let A be a non-empty nite set of symbols called an alphabet. Each element a A is called a letter. A (full) word over A is a sequence of letters from A. A partial word over A is a sequence of symbols from A = A { }, the alphabet A being augmented with the hole symbol (a full word is a partial word without holes). We denote by u(i) the symbol at position i of a partial word u. The length of u is denoted by |u| and represents the number of symbols in u. The empty word is the sequence of length zero and is denoted by . The set containing all full words (respectively, non-empty full words) over A is denoted by A (respectively, A+ ), while the set of all partial words (respectively, non-empty partial words) over A is denoted by A (respectively, A+ ). For a partial word u, the powers of u are dened recursively by u0 = and for n 1, un = uun1 . Furthermore, lim un is denoted by u . n If u and v are two partial words of equal length, then u is said to be contained in v, denoted u v, if u(i) = v(i) for all i such that u(i) A. Partial words u and v are compatible, denoted u v, if there exists a partial word w such that u w and v w. If u, v are non-empty compatible partial words, then uv is called a square. A partial word u is a factor of a partial word v if there exist x, y such that v = xuy (the factor u is proper if u = and u = v). We say that u is a prex of v if x = and a sux of v if y = . Let E be a non-empty nite set of symbols, distinct from A, whose elements are denoted by , , , etc. Symbols in E are called variables, and words in E are called patterns. The pattern language, over A, associated with a pattern p E , denoted by p(A+ ), is the subset of A containing all partial words compatible with (p), where is any non-erasing morphism from E to A that maps every variable in E to an arbitrary non-empty word. A partial word w A meets the pattern p (or p occurs in w) if for 3

some factorization w = xuy, we have u p(A+ ). Otherwise, w avoids p. To be more precise, let p = 0 m , where i E for i = 0, . . . , m. Dene an occurrence of p in a partial word w as a factor u0 um of w, where for all i, j {0, . . . , m}, if i = j , then ui uj . Stated dierently, for all i {0, . . . , m}, ui (i ), where is any non-erasing morphism from E to A as described earlier. These denitions also apply to (one-sided) innite partial words w over A which are functions from N to A . Considering the pattern p = , the language associated with p over the alphabet {a, b} is p({a, b, }+ ) = {u1 v1 v2 u2 | u1 , u2 , v1 , v2 {a, b, }+ such that u1 u2 and v1 v2 }. The partial word ab ba bba meets p (take () = bb and () = a), while the word babbbaaab avoids p. Let p and p be two patterns. If p meets p, then p divides p , which we denote by p | p . For example, but | . When both p | p and p | p hold, the patterns p and p are equivalent, and this happens when and only when they dier by a permutation of E. For instance, and are equivalent. Remark 1. Let p, p E be such that p meets p . If an innite partial word avoids p , then it also avoids p. A pattern p E is k-avoidable if there are innitely many partial words in A with h holes, for any integer h > 0, that avoid p, where A is any alphabet of size k. Note that if there is a partial word over A with innitely many holes that avoids p, then p is obviously k-avoidable. On the other hand, if, for some integer h 0, every long enough partial word in A with h holes meets p, then p is k-unavoidable (it is also called unavoidable over A). Finally, a pattern p E which is k-avoidable for some k is simply called avoidable, and a pattern which is k-unavoidable for every k is called unavoidable. The avoidability index of p is the smallest integer k such that p is k-avoidable, or is if p is unavoidable. For the remaining of this paper, we only consider binary patterns, hence we can x E = {, }. We dene = and = as being the complements of and respectively. The complement of a pattern p over E is then the pattern p built by complementing each variable of p. Similarly, if A = {a, b}, we can dene a = b and b = a, as well as the complement of a word over A. In the context of full words all binary patterns avoidability indices have been characterized. Theorem 1 ([8]). For full words, binary patterns fall into three categories: 1. The binary patterns , , , , and their complements, are unavoidable (or have avoidability index ). 4

2. The binary patterns , , , , , , , , their reverses, and complements, have avoidability index 3. 3. All other binary patterns, and in particular all binary patterns of length six or more, have avoidability index 2. Theorem 1 gives us a lower bound for the avoidability index of a binary pattern in the context of partial words. Indeed, since a full word is a partial word without holes, the avoidability index of a binary pattern in full words is not greater than the avoidability index of that pattern in partial words. So all the binary patterns in Theorem 1(1) have avoidability index in partial words. In Section 3, we prove that the patterns and are 2avoidable by iterated morphisms, while in Section 4 that and are 2-avoidable by non-iterated morphisms. Similar results were shown in [5, 10] in the context of full words (in fact, in full words, the patterns and are 2-unavoidable by iterated morphisms, but are 2-avoidable). In Section 5, we show that the pattern is non-trivially 2-avoidable by iterated morphisms.

Binary Patterns 2-Avoidable by Iterated Morphisms

Let be the morphism that maps a to aab and b to bba. Dene the sequence produced by as t0 = a, and tn = (tn1 ). Recall that t = (a) avoids and [8]. Lemma 1. For any n 0, tn+1 = tn tn tn , where ti is the ith iteration of the sequence produced by . Theorem 2. Over a binary alphabet there exist innitely many partial words, containing innitely many holes, that avoid the pattern . Proof. Let p = , and let t = (a) be the xed point of the morphism . Denote by t5 the word obtained by replacing the letter b at position 58 in t5 by , and by t the word where innitely many non-overlapping occurrences of the factor t5 have been replaced by t5 :

t5 =aabaabbbaaabaabbbabbabbaaabaabaabbbaaabaabbbabbabbaaabbbab aaabb babbaaabaabaabbbaaabaabbbaaabaabbbabbabbaaabaabaabbbaaabaabbbab babbaaabbbabbaaabbbabbaaabaabaabbbabbabbaaabbbabbaaabaabaabbbabb abbaaabbbabbaaabaabaabbbaaabaabbbaaabaabbbabbabbaaab Assume, to get a contradiction, that the pattern occurs somewhere in t . So there exists a factor x1 y1 x2 y2 y3 x3 in t that contains h holes, with the xi s and the yi s pairwise compatible for all i {1, 2, 3}, and no occurrence of p with less than h holes exists. Let x1 , x2 , x3 x and y1 , y2 , y3 y for some non-empty x, y. It is not hard to verify with a computer program that |x| 9 or |y| 9, since a hole is more than 58 positions far from either end of t5 . If |x| > 4 and there exists a hole in xi , for 0 < i 3, then there exists xj , with j = i, that has a factor that is compatible with a word from {aaaab, baaaa, abaaa, babaa, bbaba} (note that the underlined letter is the one that corresponds to the hole in xi ). Note that it is impossible to have a hole at another position than the underlined one, in any of the previously mentioned factors. We conclude that xi = xj since, otherwise, we have that t contains one of the factors aaaa, abaaa or baba, which is a contradiction. The same proof works for yi , where 0 < i 3. It follows that either t does not avoid the pattern or there exists in t an occurrence of the pattern with less than h holes, which are both contradictions. Thus, either |x| 4 and yi contains no holes for 0 < i 3, or |y| 4 and xi contains no holes for 0 < i 3 (otherwise we have that |x1 y1 x2 y2 y3 x3 | 24 contains more than two holes, which is a contradiction since between each two holes there are at least 72 symbols according to our construction). Let us rst assume that a hole is in one of x1 , x2 or x3 . If x1 contains a hole then, since |x| 4 and y1 contains no hole, looking at the factor following we conclude that the corresponding position in x2 must also contain a hole. Now, if x2 contains a hole then, it follows from the previous observation that x1 has to contain a hole, and moreover, since y1 and y3 contain no holes, looking at the factor preceding the hole, we get that x3 has a hole at the corresponding position. Finally, if x3 contains a hole, according to the previous observation, x2 has a hole. We conclude that if xi has a hole, then xi = xj , for all i, j {1, 2, 3}. Hence, there exists an occurrence of p having no holes, a contradiction. Since the case when a hole is in one of y1 , y2 or y3 is similar, we conclude that t does not contain any occurrence of the pattern . 6

Remark 2. If uu is a factor of the xed point of the morphism , for some word u with |u| > 3, it must be that |u| 0 mod 3. Moreover, for all dierent occurrences of the same factor v with |v| > 3, there exist unique words x, y, z such that v = x(y)z, with |x|, |z| < 3. In other words, all occurrences of the same factor start at the same position of an iteration of . Theorem 3. Over a binary alphabet there exist innitely many partial words, containing innitely many holes, that avoid the pattern . Proof. Let p = , t be again the xed point of the morphism , and denote by t5 the word obtained from t5 by replacing position 57 by : t5 =aabaabbbaaabaabbbabbabbaaabaabaabbbaaabaabbbabbabbaaabbba baaabb babbaaabaabaabbbaaabaabbbaaabaabbbabbabbaaabaabaabbbaaabaabbbab babbaaabbbabbaaabbbabbaaabaabaabbbabbabbaaabbbabbaaabaabaabbbabb abbaaabbbabbaaabaabaabbbaaabaabbbaaabaabbbabbabbaaab Moreover, denote by t the word obtained by replacing in t innitely many non-overlapping occurrences of t5 by t5 . We proceed by contradiction. Assume there does exist an occurrence x1 x2 y1 x3 y2 y3 of in t containing h > 0 holes, and none exists with less than h holes. Let x1 , x2 , x3 x and y1 , y2 , y3 y for some non-empty x, x1 , x2 , x3 , y, y1 , y2 , y3 . Note that it is enough to consider the case when some xi contains a hole, the case of some yi containing a hole is symmetrical. By putting a hole at position 57 of t5 , we get that |x1 x2 y1 x3 y2 y3 | 54 (it is not hard to verify this with a computer program since we have put a hole more than 54 positions from either end of t5 to create t5 ). The only cases that need to be checked are those where either |x| 9 or |y| 9. Assume that for some 0 < i 3, xi contains a hole. If the hole is not at the last position, and |x| > 6 then, we get that xj , for all j = i and j {1, 2, 3}, contains a hole at the same position as xi , and we get a contradiction with the fact that an instance of the pattern having less than h holes exists (this is easily done by looking at all possible factors). Let us now assume that |x| 6. We have that either no yj has a hole, or if one does, then the hole is at the last position and |y| > 73 (otherwise x1 x2 y1 x3 y2 y3 has length at most 36 and contains at least two holes, a contradiction with the way t is constructed). If either x1 or x2 has a hole, we can look for all the factors containing a hole in t , and having length at most 12. It can be checked that the only squares that appear are bba bba and 7

bbabbaaab babbaaabb abbaaabbb bbaaabbba baaabbbab aaabbbabb aabbbabba abbbabbaa

bbabbaaab babbaaabb abbaaabbb bbaaabbba baaabbbab aaabbbabb aabbbabba abbbabbaa

where the underlined symbol is represented by the hole. It follows that there exists an occurrence of p containing less than h holes, a contradiction (not changing the b into a hole makes no dierence). If x3 has a hole, then, according to the above, neither x1 nor x2 has holes. Since both prexes of length 5 of y1 and y2 consist of full words, the hole in x3 is followed by baaa. Thus, the last position in x2 is followed by baaa, and so it has a b. It follows that the hole in x3 is not needed and so we get a contradiction with h being the minimum number of holes an occurrence of p has. The last case that needs to be considered is when |x| > 6 and there are holes at the last positions of some of the xi s. If |y| = 1, since all xi s start with baaa, for 0 < i 3, it follows that y = b, and we get the factor x1 x2 bx3 bb. Moreover, the xi s dier only in the last position so we have x c1 x c2 bx c3 bb, for some word |x | > 70 and some c1 , c2 , c3 {a, }. In this case using Remark 2, we reach a contradiction. Now let |y| > 1. If x1 has a hole it follows that all xi s start with baaa, for 0 < i 3. Thus, yi ends in b, for all 0 < i 3. If any of the yi s end in , then an occurrence of the pattern with less than h holes exists, a contradiction. Furthermore, all yi s start with baaa. But this implies that both x2 and x3 end in b or , a contradiction with the fact that there does not exist an occurrence of p with less than h holes. If x2 or x3 has a hole, it follows that all yi s start with baaa and all xi s start with ab, where 0 < i 3. Moreover, it follows that y2 ends in b or . But, since x3 starts with ab, and so y1 ends in a, we get that y2 ends in . Thus, x1 x2 y1 x3 y2 y3 = abx a abx baaay a abx baaay baaay c

with c {a, }. But this implies that x represents an image of , and so, x1 is preceded by an a. Thus, t5 has as a factor aabx aabx bbaaay aabx bbaaay bbaaay

with the underlined bs standing for the ones changed into s in t . This is a contradiction since we know that t5 avoids the pattern . The cases when the yi s end in s are similar.

Binary Patterns 2-Avoidable by Non-Iterated Morphisms

Let us now look at the pattern . Let A = {a, b} and A = A {c}, and let : A A be the morphism dened by (a) = abc, (b) = ac and (c) = b. It is well known that (a) avoids , in other words it is square-free [8]. Furthermore, dene the morphism : A A with (a) = aa, (b) = aba, and (c) = abbb. If w = ( (a)), then we know from [5] that w does not contain any occurrence of . Moreover, let 4 = ( 4 (a)). Since 4 (a) occurs innitely often as a factor of (a), it follows that 4 occurs innitely often as a factor of w. Hence, we can write w = w0 4 w1 4 w2 4 , for some words wi with |wi | > 1, for all i. Now, let us replace the a in position 23 of 4 by and denote the new partial word by 4 : 4 =aaabaabbbaaabbbabaaaaba bbbabaaaabbbaaabaabbbaaabbb abaaaabbbaaabaabbbaba

Lemma 2. Let u1 u2 denote a factor of w = w0 4 w1 4 w2 4 , that is obtained by inserting holes in v1 v2 , a factor of w with u1 v1 and u2 v2 . If u1 u2 , but v1 = v2 , then |u1 | 4, more specically, either u1 or u2 is in { , b, bb, a , a b, a bb, ba }. Proof. Obviously, if u1 u2 but v1 = v2 , then a hole appears in u1 and there is no hole at the corresponding position in u2 , or vice versa. Without loss of generality we can assume that a hole appears in u1 . Assume that u1 { , b, bb, a , a b, a bb, ba }. It follows that u1 has as a factor bbb, / aba or ba b. Moreover, note that the only occurrence of bbb in w is in the factors abbba and bbba. Similarly, the only time aba appears as a factor of w is as a factor of abaa and aba , and the only time a word x compatible with ba b appears in w is when x = ba b or x = baab. We see that in all of these cases the corresponding factor in u2 must be abbba, abaa or baab, a contradiction since we always have v1 = v2 . 9

Lemma 3. There exists no factor uu of w = ( (a)), such that either aaab or aba is a prex of u. Proof. Assume there exists an u with prex aaab so that uu = w(i) w(i + 2l 1), for some integers i, l with l > 3. Note that aaab only appears as a prex of (x), for some word x {a, b, c}+ . Moreover, since the second u also starts with aaab, we have that u = (x). Hence, uu is actually (xx), for some word x {a, b, c}+ . It follows that (a) contains the square xx, which is a contradiction with the nature of the morphism. Similarly, aba only appears as an image of (b). Theorem 4. Over a binary alphabet there exist innitely many partial words, containing innitely many holes, that avoid the pattern . Proof. Let p = . To prove this claim, we assume that the partial word w is not p-free and get a contradiction. Let x1 x2 y1 y2 x3 be an occurrence of p in w , and denote by x1 x2 y1 y2 x3 the factor of the full word w in which holes were inserted to get p. Note that if x1 = x2 = x3 and y1 = y2 , then we have an occurrence of p in w, which is a contradiction. Therefore one of the equalities fails. Also, note that if xi = xj then either xi or xj contains a hole, where i, j {1, 2, 3}, while if y1 = y2 then either y1 or y2 contains a hole. Moreover, if x1 = x2 or y1 = y2 , according to Lemma 2, x1 or x2 or, y1 or y2 is in { , b, bb, a , a b, a bb, ba }. By looking at the factor 4 , it is easy to check that the only possibilities are for x1 or y1 to be in { , b} and for x2 or y2 to be in { , a , a b}. If y1 = b, it is easy to check that x3 must start with aba. According to Lemma 3, we cannot have that x1 = x2 . It follows, according to Lemma 2, that |x1 | 4, a contradiction with the factor preceding the hole. The proof is identical for the case when x1 = b. If y1 = , then x3 starts with bba. Thus, x2 starts with bba and x1 ends in ab or b. It follows that x2 ends in ab or b, thus, y1 is preceded by ab, which is a contradiction. If x1 = , then y1 and y2 start with bba and x3 is a b. From Lemma 2, y1 = y2 . Thus, y1 y2 bb is a factor of w. It follows that for some word z {a, b}+ , y1 y2 bb = bb(zc)(zc) is a factor of w. We get a contradiction with the fact that (a) is square-free. If x2 or y2 is in { , a , a b}, then either y1 or x3 is a factor of a word in {bbba, bba}. A contradiction is reached again with the help of Lemma 2 and the fact that (a) is square-free. The nal case that needs to be analyzed is when x1 = x2 and y1 = y2 , and x3 x1 and x3 = x1 . Let us denote x = x1 = x2 and y = y1 = y2 . We

10

get that w has xxyyx3 as a factor and there exists at least one hole in x3 that corresponds to bs in x1 and x2 . If |x| > 4 it follows that x has abab, babb, bbbb as a factor (the underlined b represents the letter corresponding to the hole in x3 ). Since none of these are possible factors of w, we conclude that it is impossible. Hence, x3 { , b, bb, a , a b, a bb, ba }. It follows that xx {b2 , (bb)2 , (bbb)2 , (ab)2 , (abb)2 , (abbb)2 , (bab)2 } But, only bb is a possible factor of w. It is easy to check that in this case |y| > 6 and we conclude that y has either aaa, aba, baaa or baba as a prex. In all of these cases, using Lemma 3 we reach a contradiction. Since all cases lead to contradictions we conclude that is avoidable over a binary alphabet. Finally, let us look at the pattern . According to [8, Lemma 3.3.2], ( (a)) avoids , where : {a, b, c} {a, b} with (a) = aaa, (b) = bbb, and (c) = ababab. Moreover, the only squares that occur in w = ( (a)) are a2 , b2 , (aa)2 , (ab)2 , (ba)2 , (bb)2 and (baba)2 . Finally, note that (a) does not contain any of the factors aba or cbc. Let us replace the b in position 84 of 5 = ( 5 (a)) by and denote the new partial word by 5 : 5 =aaabbbabababaaaabababbbbaaabbbabababbbbaaaabababaaabbbabababaaaa bababbbbaaaabababaaa bbabababbbbaaabbbabababaaaabababbbbaaabbbab ababbbbaaaabababaaabbbabababbbbaaabbbabababaaaabababbbbaaaababab Moreover, let us denote by w the word obtained from w after the insertion of a hole at position 84 of an occurrence of 5 . Proposition 1. Over a binary alphabet there exist innitely many innite partial words, containing exactly one hole, that avoid the pattern . Proof. Let us assume, to get a contradiction, that there exists an occurrence of p = in w , and denote this occurrence by x1 y1 x2 x3 y2 , for xi , yj {a, b, }+ , 0 < i 3 and 0 < j < 3. Either x1 = x2 = x3 = x or y1 = y2 = y, for some words x and y, but not both. Note that if the variable containing the hole has length greater than 3 then the hole is among the last three symbols. Otherwise the corresponding variable has as a factor abba (the underlined a stands for the hole position in the rst variable), which is a contradiction. 11

Case 1. The factor with the hole has length greater than three. Here, x1 = x (otherwise w has the factor xx with |x| > 3, which is a contradiction). If the hole is in y1 , then x must be one of the squares aforementioned. Moreover, since the hole is among the last three symbols of y1 , by looking at the symbols following the hole, x {b, ab}. If x = b, then by bby a with y1 = y for some word y . But, since |y| > 3, we get that y ends in aaa, and it follows that y = (cz), for some word z {a, b, c} . We get that (a) either contains cczbczc or bczbczc as a factor. Since both of these contain squares and (a) is square-free, we reach a contradiction. If the hole is in y2 , then for some prex y of y we get xy1 xxy2 {xy axxy , xy abxxy b, xy abbxxy bb} If y1 = y a, since |y| > 3, y ends in aaa. It follows that x = ba. Hence, we have the factor bay ababay . In this case y = b(z), for some word z, and so (a) has c(z)c(z) as a factor, a contradiction with the fact that it is square-free. If y1 = y abb, then x {ba, baba}. It is easy to check that in this case we must have |y | > 2. We get that w has aaaabb as a factor, a contradiction. Finally, if y1 = y ab, then y ends in aa. We obtain x = ab. But then we have that xy abxxy b = aby abababy b. Hence, we reach a contradiction with the fact that (a) cannot have czcz as a factor, where y = (z) for some word z. If the hole is in x3 , then since x1 y x3 y, the hole must be within the last two symbols of x3 (otherwise we once again have in w the factor abba). It follows that x1 = x aaax , for some words x , x {a, b} . We get that xyxx3 y = x aaax yx aaax x aa x y. It follows that |x x | > 3, and since |x | < 2, x has aba as a sux. Moreover, if |x y| > 1, then x y has bb as a prex, and so w has aaaabb as a factor, a contradiction. Thus, we conclude that x = and y = b. We get the factor x aaabx aaax aa b. But since ba is a sux of x , ba is a prex of x . We also get that abba is a factor of w, a contradiction. If the hole is in x2 , then we have the factor xyx2 xy. Denoting x = x ax , for some words x , x {a, b} , we obtain the factor x ax yx x x ax y, where |x x | > 2. It can be checked that in this case x ends in aaa. It follows that ax yx and bx x are both the image of some words through . We get that x = , ay = (z1 )b and bx = (z2 ), for some words z1 , z2 {a, b, c}. In addition, bxyx2 xy is obtained by introducing a hole in (z2 )(z1 )(z2 )(z2 )(z1 ). This is a contradiction since w avoids the pattern . 12

Case 2. The factor with the hole has length at most three. It is easy to check that in this case we cannot have a hole in y1 or y2 , and we reach contradictions whenever we consider a hole in x2 or x3 . If the hole is in x1 , then x {a, aa, ab}. In all the cases we get contradictions because of possible forms of y (we get contradictions because y1 starts either with ba or bba). Theorem 5. Over a binary alphabet there exist innitely many partial words, containing innitely many holes, that avoid the pattern . Proof. Let us denote by w the word obtained from w after innitely many non-overlapping occurrences of 5 starting at an even position have been replaced by 5 . Furthermore, let us assume, to get a contradiction, that the pattern p = is unavoidable and denote by x1 y1 x2 x3 y2 an occurrence of p containing h > 1 holes, such that no occurrence of the pattern p having less than h holes appears in w . Here, we assume that x1 , x2 , x3 x and y1 , y2 y for some x, y. Since, according to Proposition 1, h > 1 and the distance between every two holes is at least 170, it follows that |xy| > 85. Thus, there exist z, z {x1 , x2 , x3 , y1 , y2 }, z = z , z z , z = z1 z2 and z = z1 az2 , for some words zi , zi , with zi zi for i = 1, 2. If |z2 | > 2, then z2 has a prex compatible with bba. Since the only factor in w compatible with bba is bba we conclude that az2 has abba as a prex, which is a contradiction with the fact that abba is a valid factor of w. It follows that |z2 | < 3. Moreover, if z {x1 , x3 }, since y1 follows x1 and y2 follows x3 , we get x1 y1 x3 y3 . If |y| > 2 a conclusion similar to the previous one is reached. It follows that 0 < |z2 y1 | < 3. In this case, |z1 | > 82 and the hole is preceded by abaaa. If z2 = or |y1 | > 1, then w has baaaabb as a factor, a contradiction. It must be that z = z1 and y = b. Since abaaa is a sux of z1 , by looking at x2 , we get that z1 has as a prex a factor compatible with bababb. So is followed by a factor compatible with bbababb, a contradiction. If x2 = z, we get the factor z1 az2 y1 z1 z2 z1 az2 y2 . Note that here we denote x1 = z1 az2 = x3 , since otherwise we fall in the previous case. Moreover, it is easy to check that in this case |z1 | > 10 (there is no square that contains a in the rst part and has length less than 2 13). It follows that aabababaaa is a sux of z1 , and since it is the only word compatible with a factor of w it is also a sux of z1 . It follows that z2 y1 and z2 y2 are both preceded by aabababaaaa. Thus, z2 y1 z1 starts with baba, and so, w has (acac) as a factor, a contradiction with the fact that (a) is square-free. It follows that x1 = x2 = x3 , and x1 , x2 , x3 are compatible with words from the set {a, b, aa, ab, ba, bb, baba}. Since the number of holes is minimal, 13

we can only consider the factors xz1 z2 xxz1 az2 and xz1 az2 xxz1 z2 , where |z2 | < 3. If the factor is xz1 z2 xxz1 az2 , looking at the letters following the hole and the possible values of x, we conclude that we have either bz1 bbz1 a, baz1 bbabaz1 ab or abz1 bbababz1 abb. In the second case, it follows that z1 , and respectively z1 , starts with ab, giving us the prex baab, which is not a valid factor of w . In the last case, we get that z1 , and respectively z1 , ends in aaa, giving us the sux aaaabb, which is not a valid factor of w . Finally, in the case of bz1 bbz1 a, we get that z1 is preceded by a factor compatible with bbb. It follows that the factor that we have before changing the b following z1 into a hole is bbbz1 bbbz1 a. In this case, taking = b and = bz1 , we get an occurrence of the pattern , for less than h holes, a contradiction. Finally, let us assume that we have the factor xz1 az2 xxz1 z2 with |z2 | < 3. Since in this case z1 ends in abaaa, it follows that z1 a ends in abaaaa and so, the only possibilities for x are ab and ba. If x = ab, it follows that z2 = b and we have the factor abz1 abababz1 b. We get that z1 ends in abaaa, and moreover, has a prex compatible with bbb. It follows that z1 , z1 bbb(z)abababaaa, for some word z {a, b, c} , and we have a factor compatible with abababbbbzabaaaabababbbbzabaaa b. We see that in this case, (a) has cbzca cbzca b as a factor, a contradiction with the fact that (a) is square-free. If x = ba, it follows that z2 = and we have the factor abz1 ababaz1 . Since z1 has a sux compatible with abaaaa, we get that z1 has a prex compatible with bbbb. Once more, it follows that z1 , z1 bbbb(z)abababaaa, for some word z {a, b, c} . We have that (a) has cbzca cbzca b as a factor, a contradiction with the fact that (a) is square-free. Using Theorem 5, since | , Theorem 2 can be easily obtained in a non-iterative way.

Non-trivially Avoidable Binary Patterns

In [3], it is shown that is 3-avoidable in partial words. Furthermore, since a and a represent occurrences of the pattern , we conclude that is unavoidable in the context of partial words. What restriction do we need to impose on the concept of avoidability in order to construct innitely many binary partial words with innitely many holes that avoid the pattern (the pattern )?

14

Denition 1. Let p = 0 m , where i E for i = 0, . . . , m. Dene an occurrence u0 um of p in a partial word w as non-trivial if ui = for all i {0, . . . , m}. We call w non-trivially p-free if it contains no non-trivial occurrence of p. In [3], it was shown that there exist innitely many partial words with innitely many holes over a 3-letter alphabet that non-trivially avoid , and so the non-trivial avoidability index of in partial words is 3. Since in full words all binary patterns with avoidability index 3 meet , using Remark 1 we conclude that all binary patterns in Theorem 1(2) also have non-trivial avoidability index 3 in the context of partial words. Moreover, in [9], the case of patterns of the form m , m 3 was considered, the avoidability index in partial words being 2. In Theorems 2, 3, 4 and 5, we have proved that the patterns , , and are 2-avoidable. Thus, according to [8], if we can nd the non-trivial avoidability index in partial words of , then we will have completed the classication of the patterns in Theorem 1(3) in terms of non-trivial avoidability in partial words. In this section, we prove in particular the following result. Theorem 6. With respect to non-trivial avoidability in partial words, the avoidability index of a binary pattern is the same as in Theorem 1. Let us recall the iterative Thue-Morse morphism such that (a) = ab and (b) = ba. It is well known that (a) avoids [7]. Proposition 2. Over a binary alphabet there exist innitely many innite partial words, containing exactly one hole, that non-trivially avoid the pattern . Proof. Let p = , and t = (a) be the xed point of the Thue-Morse morphism. We show that there exist innitely many positions in t in which one can replace the letter at that position with a hole and obtain a new word t that is still non-trivially p-free. Also, since all factors of the innite Thue-Morse word t avoid p, it follows that any occurrence of p in t must contain the hole. Let x1 , x2 , x3 x and y1 , y2 y, for some x, x1 , x2 , x3 , y, y1 , y2 such that |x|, |y| 1. We start by proving that there does not exist a non-trivial occurrence of p, x1 y1 x2 y2 x3 , in t such that |x| 8 or |y| 8. We proceed by contradiction. We analyze the following three cases based on the possible positions of the hole. Case 1. The hole is in x1 . 15

Note that this case is symmetrical to when the hole is in x3 (we are using the fact that if w is a factor of the Thue-Morse word t, then so is rev(w)). Since t is overlap-free, the only possibility is to have in t a factor of the form x cx yx cx yx cx , with c {a, b}, and x1 = x x , x2 = x3 = x cx = x and y1 , y2 = y, for some words x , x {a, b} with |x x | 7 or |y| > 7. Moreover, x is non-empty since, otherwise, t contains the factor x ycx ycx which is impossible since t is p-free. Looking at the symbols that precede and follow in x1 and c in x2 , we get that if |x x | 7 either ccccc is a factor of x2 = x cx when c is preceded by c in x cx , or ccccc is a factor of x cx when c is preceded by c in x cx . Finally, if |y| > 7 either ccccc is a factor of x cx when is preceded by c in x1 , or ccccc is a factor of x2 = x cx when is preceded by c in x1 . All cases lead to contradiction with the fact that t is overlap-free. Let us illustrate by an example how this works. Let us consider the case when c is preceded by a c, |x | = 1 and |y| > 7. We look at the factors x1 y1 and x2 y2 that dier at only one position. We have that y1 starts with c, so that ccc is not a prex of our factor. It follows that x y2 starts with cc so we do not get the cube ccc in t. But, in x1 y1 we have the factor cccc, which must be followed by c. Again looking at the prex of x y2 , we get cccc. It follows that ccx y has as prex cccccc which contains an overlap, a contradiction with the fact that t is overlap-free. Case 2. The hole is in y1 . Note that this case is symmetrical to when the hole is in y2 . Since t is overlap-free, the only possibility is to have in t a factor of the form xy cy xy cy x, with c {a, b}, and x1 = x2 = x3 = x, y1 = y y , y2 = y cy , for some words y , y {a, b} with |y | + |y | 1. Since at least one of y and y is non-empty, and either |x| > 7 or |y y | 7, the proof follows from the previous case. Case 3. The hole is in x2 . Since t is overlap-free, the only possibility is to have in t a factor of the form x cx yx cx yx cx , with c {a, b}, and x1 = x3 = x cx , x2 = x x and y1 = y2 = y, for some words x , x {a, b} with |x | + |x | 1. Again, since at least one of x and x is non-empty, and either |y| > 7 or |x x | 7, the proof follows from the rst case. We have thus shown that if |x| 8 or |y| 8, there are no non-trivial occurrences x1 y1 x2 y2 x3 , where x1 , x2 , x3 x and y1 , y2 y, of p in t , therefore any such occurrence in t must satisfy |x1 y1 x2 y2 x3 | < 36. We now put a hole at position 47 of t7 = 7 (a) to create t7 : t7 =abbabaabbaababbabaababbaabbabaabbaababbaabbabaa abbabaabbaababba 16

baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaab

It is not hard to verify (using a computer program) that there are no occurrences of p in t7 . Furthermore, we have put the hole more than 36 positions from either end of t7 . Note that t7 occurs as a factor of t innitely often. We can choose any arbitrary occurrence of the factor t7 in t, and replace it with t7 in order to obtain an innite word with one hole that non-trivially avoids p. Theorem 7. Over a binary alphabet there exist innitely many partial words, containing innitely many holes, that non-trivially avoid the pattern . Proof. Let p = , and let t be the xed point of the Thue-Morse morphism. Note, there are innitely many non-overlapping occurrences of t7 starting at an even position in t [9]. For each such occurrence, we put a hole at position 47 of the factor t7 . We claim that the resulting word is non-trivially p-free. We proceed by induction. Let t denote a word obtained by replacing any h positions in t with holes in the manner described above. We have already proven the h = 1 case in Proposition 2, so assume that t , a word obtained by replacing any h 1 positions in t with holes also in the manner described above, non-trivially avoids p. We show that t non-trivially avoids p. Assume the contrary. Thus, there is some factor x1 y1 x2 y2 x3 of t such that x1 , x2 , x3 u and y1 , y2 v for some words u, v {a, b} . Observe that by the way we insert holes, there are at least 127 letters in between any two holes. Also, x1 y1 x2 y2 x3 must contain all h holes (otherwise there is an occurrence of p in some t ). Hence, |x1 y1 x2 y2 x3 | 129 when h 2. There are several cases to consider: the cases where there exist at least one hole in x1 , or in x3 , or in y1 , or in y2 , and the case where all holes are in x2 . Case 1. At least one hole is in x1 . Note that the case when x3 contains at least one hole is similar. We have x1 = w11 c1 w12 , x2 = w21 c2 w22 , x3 = w31 c3 w32 where wij uj for any i {1, 2, 3} and j {1, 2}, c1 = and u1 u2 u. In order for the inductive hypothesis to hold, we have either c2 = a or c3 = a. Additionally, note that we cannot have that both c2 = b and c3 = b since, otherwise, the hole at c1 is unnecessary to create a non-trivial occurrence of p. Moreover, since we are dealing with a non-trivial occurrence of p and a hole is in x1 , we have |x1 | 2. Thus, either |u1 | > 0 or |u2 | > 0. 17

If |u2 | > 1, it follows that t has w12 y1 w21 c2 w22 y2 w31 c3 w32 as a factor. Here, taking u2 as image for and vu1 c as image for , with c2 , c3 c, we get a contradiction with the inductive hypothesis. If |u1 | > 0 and |u2 | = 1, it follows that c1 is preceded by a. It is easy to check that |u2 v| > 2 (otherwise we get that t contains overlaps as factors). Thus, c1 is also followed by ab. It follows that c2 is also preceded by a factor x compatible with a and followed by a factor x that is compatible with ab, such that x c2 x is compatible with aaab and contains at most one hole. Since the hole is always followed by ab, it follows that c2 = a. But, since |u1 | > 0 and |u2 | = 1, c3 must be an a, and the only possibility for a hole here is the following position (the rst position of w32 ). Since this hole is an odd number of positions apart from c1 = , and the holes are always put at odd positions, this is a contradiction. If |u2 | = 1 and |u1 | = 0, since the hole is always put at an odd position, it follows that w32 = a is at an even position and is followed by b (one of the images of ). Moreover, y1 starts with b and y2 has a prex compatible with b. It follows that t has a factor compatible with aby a a y a ab, where y1 , y2 by . Taking ab for image of and y a as image for , p occurs in t , which is a contradiction with our inductive hypothesis. If |u2 | = 0, it follows that the hole is preceded by an a. Since c3 is an odd number of positions apart from c1 , it must be the case that c3 = a (if c3 = then we have a hole at an even position, and if c3 = b we have an occurrence of p in t ). Moreover, since c3 is at an odd position, it follows that c3 is preceded by b. This is a contradiction since c1 is preceded by a. Case 2. At least one hole is in y1 . Here, x1 , x3 are full (the case when at least one hole is in y2 is similar). Let y1 = w11 c1 w12 and y2 = w21 c2 w22 where wij vj for any i, j {1, 2}, c1 = and v1 v2 v. In order for the inductive hypothesis to hold, we need to have c2 = a. Since |x1 y1 x2 y2 x3 | 129, either c1 is preceded by aa and followed by a or c1 is preceded by a and followed by ab. Moreover, since x1 y1 x2 x2 y2 x3 , c2 = a is also preceded by factors compatible with aa or a and is followed by factors compatible with a or ab. Since a hole is always followed by ab and replaces a b, we see that none of these other positions contains one, giving us that t contains a cube aaa, which is a contradiction. Case 3. All the holes are in x2 . Let x1 = w11 cw12 , x2 = w21 w22 , x3 = w31 cw32 where wij uj for every i {1, 2, 3} and j {1, 2}, and c = a. In the case |u1 | 1, it follows that the c in x1 is preceded and followed by as. We get that t contains aaa as a factor, which is a contradiction. 18

Otherwise, it follows that |y2 u2 | 2. Hence, since the hole is preceded by aa, the c in x3 is preceded by aa. Again we get a contradiction with the fact that aaa is not a factor of t. We have thus shown that we can insert innitely many holes in t and nontrivially avoid p. Moreover, we can choose an arbitrary number of positions where we have holes, replace them back with bs, and obtain innitely many partial words with innitely many holes that non-trivially avoid p.

Avoidable Binary Patterns

In the previous sections we have proved that all binary patterns that are kavoidable in full words are also k-avoidable in partial words, with k {2, 3}, when considering non-trivial avoidability. A question that arises is how the classication of the binary patterns looks like when considering general avoidability in partial words (not restricted to non-trivial avoidability). With respect to general avoidability in partial words, the binary patterns , , , and have avoidability index 2 and the patterns , , , and , and their complements, are all unavoidable (or have avoidability index ). The following lemmas are straightforward. Lemma 4. The binary patterns , and are unavoidable in partial words. Proof. Since in a partial word with an innity of holes, there must exist a symbol a A, that has at least two occurrences preceded or followed by , it follows easily that there always exist factors of the form ax, aya and az a, for some x, y, z A . We see that these factors represent occurrences of the aforementioned patterns. Lemma 5. The patterns , and have avoidability index 3 in partial words. Proof. For the last two patterns we see that both meet the pattern which is non-trivially avoidable. Hence, the conclusion follows. For the pattern, , let us consider a word w that non-trivially avoids . In [3], such a word is provided over a three-letter alphabet, having the property that each two holes are at least 10 positions apart. If our pattern has an occurrence, say x1 x2 y1 y2 with x1 x2 and y1 y2 , then |x1 | = |y1 | = 1 and the factor contains two holes. This is a contradiction with the construction of w.

19

We are left considering the pattern and all patterns from Theorem 1(3). By looking at all possible factors of a binary pattern of length up to 7, we conclude the following. Remark 3. All patterns of length seven or more are 2-avoidable. Thus, the only patterns that we have to consider in order to characterize all binary patterns, are and , their reverses, and complements, as well as . Moreover, since is 3-avoidable, and both and are 2-avoidable, we conclude that is either 2- or 3-avoidable. Theorem 8. Over a binary alphabet, there exist innitely many partial words, containing innitely many holes, that avoid the pattern . Proof. Let us consider the Thue-Morse word t = (a). In Theorem 7 it was proved that t , the word obtained after arbitrarily many holes were inserted in t, non-trivially avoids . It follows that if our pattern occurs in t, since meets our pattern, either the image corresponding to or the one corresponding to has length one. Let us assume towards a contradiction that there exists an occurrence of in t . It follows that there exists in t a factor x1 y1 x2 y2 x3 x4 with xi xj and y1 y2 , for all i, j {1, 2, 3, 4}. Let us rst consider the case where x1 y1 x2 y2 x3 x4 contains only one hole. If the hole is in x1 it follows that our factor is of the form yayaa, where x1 = , y1 = y2 = y and x2 = x3 = x4 = a. This is due to the fact that the occurrence of the pattern must be trivial, and moreover, the replaces an a in t, so it should correspond to bs in our occurrence of the pattern. But, since the is always followed by an a in t, we get that a is a prex of y, and so yayaa is an overlap that occurs in t. This is a contradiction with the fact that t is overlap-free. If the hole is in x2 we get ay yaa. It is easy to check that in this case it must be that |y| > 2. Hence, y has baa as a sux. It follows that for some word y with y = y baa we have the factor ay baa y baaaa, a contradiction with the fact that t is overlap-free and so aaa is not a factor of it. If the hole is in x3 we get ayay a, with baa a sux of y. A contradiction follows as in the previous case. Note that we cannot have x4 = , since otherwise we have that t is not overlap-free. When y1 = , and the occurrence of the factor is x xaxx, we get the non-trivial overlap x xax. Finally, when y2 = , and the occurrence of the 20

factor is xax xx, we get that x has aa as a sux. It follows that a xx is a non-trivial occurrence of the pattern in t , again a contradiction. Now let us assume that there exist more than one hole in x1 y1 x2 y2 x3 x4 , and at least one of the images of our variables is . In this case we use the fact that each two holes in t are at least 129 positions apart. It follows that if the corresponds to , the yi s have length at least 120, and if the corresponds to , the xi s have length at least 120. Using the fact that the is always preceded by baa and so the symbol corresponding to it in the other occurrences of the same variable is either or b, and the reasoning from the one hole case, the conclusion follows. The proof for the reverse of the pattern is almost identical. Hence, the only patterns left to classify are and . Since is 3avoidable in full words, we conclude that the pattern is 2-unavoidable in partial words. The next natural question though is if is 3-avoidable or not in partial words. In order to nd an upper bound for the avoidability index of , let us again consider an innite partial word w {a, b, c} that avoids all squares except f and f , for some f {a, b, c}. According to [3], such a word exists. In this word let us replace all occurrences of by d, for a new symbol d, and get a new partial word w that has innitely many holes. We prove that w avoids . Proposition 3. The pattern is 4-avoidable. Proof. It is quite straightforward to see that since w avoids non-trivial squares so does w . Hence, if an occurrence of exists in w , then the image of has length 1. Let us assume that such an occurrence exists and denote by x1 a1 a2 x2 the factor corresponding to our pattern, where x1 x2 and a1 or a2 is a hole. It follows that either a2 = d or d is a prex of x2 . We consider the later case, the former one being quite similar. It follows that x1 has either d or as a prex. If x1 has as a prex, since a1 = and the holes cannot be too close together according to the construction of w, then x2 has dd as a prex, a contradiction with the way w has been constructed. Hence, it must be the case that x1 starts with d. But, in this case, it follows that before the ds were inserted, the factors corresponding to x1 and x2 were still compatible. Since, is compatible with any letter of the alphabet it follows that w has a non-trivial square, which is a contradiction. Using the same strategy as in the case of factors of length six or more, starting with the factors a a and a b we get the following. 21

Remark 4. If a ternary word meeting the pattern exists, it must be that the word is not square-free after replacing the holes with any symbol. A question that arises is if there exist iterated morphisms for which, replacing some of the letters of the xed point with holes, gives us a ternary word that avoids the pattern . In particular, note that since the word cannot be square-free, it must be that factors of the form xx exist. Hence, we get arbitrarily long such factors after iterated applications of the morphism on this factor. Moreover, it follows that applications of the morphism on the word formed from the symbol following the pattern and the one preceding the factor, will always be unbordered. We can now reformulate Theorem 1 for partial words. Theorem 9. For partial words, binary patterns fall into ve categories: 1. The binary patterns , , , , , , , , and their complements, are unavoidable (or have avoidability index ). 2. The binary pattern has avoidability index 3 or 4. 3. The binary patterns , and , their reverses, and complements, have avoidability index 3. 4. The binary pattern has avoidability index 2 or 3. 5. All other binary patterns, and in particular all binary patterns of length six or more, have avoidability index 2.

References
[1] D. R. Bean, A. Ehrenfeucht, and G. McNulty. Avoidable patterns in strings of symbols. Pacic Journal of Mathematics, 85:261294, 1979. [2] F. Blanchet-Sadri. Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL, 2008. [3] F. Blanchet-Sadri, R. Merca, and G. Scott. A generalization of s Thue freeness for partial words. Theoretical Computer Science, 410(810):793800, 2009. [4] F. Blanchet-Sadri, R. Merca, S. Simmons, and E. Weissenstein. Avoids able binary patterns in partial words. In A.-H. Dediu, H. Fernau, and C. Mart n-Vide, editors, LATA 2010, 4th International Conference on 22

Language and Automata Theory and Applications, Trier, Germany, volume 6031 of Lecture Notes in Computer Science, pages 106117, Berlin, Heidelberg, 2010. Springer-Verlag. [5] J. Cassaigne. Unavoidable binary patterns. Acta Informatica, 30:385 395, 1993. [6] V. Halava, T. Harju, T. Krki, and P. Sbold. Overlap-freeness in a ee innite partial words. Theoretical Computer Science, 410(8-10):943 948, 2009. [7] M. Lothaire. Combinatorics on Words. Cambridge University Press, Cambridge, 1997. [8] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, 2002. [9] F. Manea and R. Merca. Freeness of partial words. Theoretical Coms puter Science, 389(12):265277, 2007. [10] P. Roth. Every binary pattern of length six is avoidable on the twoletter alphabet. Acta Informatica, 29:95106, 1992. [11] U. Schmidt. Motifs invitables dans les mots. Technical Report LITP e 8663 Th`se Paris VI, 1986. e [12] U. Schmidt. Avoidable patterns on two letters. Theoretical Computer Science, 63:117, 1989. [13] A. Thue. Uber unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana, 7:122, 1906. (Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, Norway (1977), pp. 139158). [14] A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana, 1:167, 1912. (Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, Norway (1977), pp. 413478). [15] A. I. Zimin. Blocking sets of terms. Mathematics of the USSR-Sbornik, 47(2):353364, 1984.

23