Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/de-gruyter/pattern-avoidance-in-partial-words-over-a-ternary-alphabet-YkBYiaJ4HA
- Publisher
- de Gruyter
- Copyright
- Copyright © 2015 by the
- ISSN
- 2083-7402
- eISSN
- 2083-7402
- DOI
- 10.1515/umcsmath-2015-0013
- Publisher site
- See Article on Publisher Site
Abstract
Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 · 2m-1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words sequences, in which some characters are left "blank". Using method of entropy compression, we obtain the partial words version of the theorem for ternary words. 1. Introduction. Let = {a, b, c, . . . } and = {A, B, C, . . . } be finite alphabets. We refer to elements of as letters and to elements of as variables. A word w over some alphabet is a sequence of letters from this alphabet, an infinite word is an infinite sequence of letters. A factor of w is a subsequence of w consisting of consecutive letters. A prefix of w is a factor containing the first letter of w and a suffix is a factor containing its last letter. A pattern p is a word over and a doubled pattern is a pattern in which every variable occurs at least twice. A word w over is an instance of p if there exists a morphism h : + + such that h(p) = w. A word w is said to avoid p if no factor of w is an instance of p. For example, aabaac contains an instance of ABA and abaca avoids AA. A partial word over alphabet is a sequence of characters from extended alphabet = { }, an occurrence of is called a hole. For a partial word 2010 Mathematics Subject Classification. 68R15. Key words and phrases. Formal languages, combinatorics on words, pattern avoidance, partial words, entropy compression, probabilistic method. w we denote the set of positions of holes as holes(w). A partial word w is an instance of p if there exists a substitution of single letters from to holes(w) such that the resulting word is an instance of p. For example, w = a ab contains an instance of AAA but it avoids ABBA and holes(w) = {2}. The avoidability index (p) of pattern p is the size of the smallest alphabet such that there exists an infinite word over that avoids p. The partial avoidability index (p) of pattern p is the size of the smallest alphabet such that there exists an infinite partial word W over avoiding p and with |holes(W )| = . Blanchet-Sadri and Woodhouse [1] and independently Ochem and Pinlou [8] proved the following conjecture of Cassaigne [2]: Theorem 1.1 ([2]). Let p be a pattern with exactly k distinct variables. (1) If p has length at least 2k then (p) 3. (2) If p has length at least 3 · 2k-1 then (p) = 2. It was known previously that above bounds are the best possible [6]. Blanchet-Sadri and Woodhouse conjectured that for partial avoidability the first statement remains true for doubled patterns with at least 4 variables and the second remains true without changes. Proof of the first statement for partial words is the main result of this paper, i.e. we will prove that if p is a doubled pattern with k 4 variables and length at least 2k , then (p) 3. 2. Tools and notation. In this section we introduce a few classical combinatorial concepts and results which will be used in the proof. 2.1. Analytic combinatorics. First we need several concepts of analytic combinatorics. We send readers not familiar with this topic to an excellent book of Flajolet and Sedgewick [3]. We say that a number sequence (ai )iN is of exponential order K n , which we abbreviate as an K n iff: lim sup |an | = K. We will also use one of the basic ordinary generating functions operator, namely SEQ. The operator corresponds to the class of objects 1 + E + 1 + E2 + . . . and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have SEQ(f (z)) = 1 + n1 Z(En )(f (z), f (z 2 ), . . . , f (z n )) 1 = 1 + n1 f (z)n = . 1 - f (z) Analytic combinatorics will be used in the proof as a tool for bounding asymptotic growth of coefficients of the generating function f (z) defined by an equation of type f (z) = z · (f (z)). The following theorem will allow us to do that: Theorem 2.1 (Flajolet, Sedgewick [3], Proposition IV.5). Let be a function analytic at 0, having non-negative Taylor coefficients such that (0) = 0. Let R + be the radius of convergence of the series representing at 0. Under the condition, x (x) > 1, (1) lim xR- (x) there is a unique solution (0, R) of the characteristic equation: (2) ( ) = 1. ( ) Then, the formal solution y(z) of the equation y(z) = z · (y(z)) is analytic at 0 and its coefficients satisfies exponential growth formula: [z n ]f (z) where p = ( ) 1 ( ) . Based on the above theorem we introduce the general method for bounding the exponential order of combinatorial sequences proposed by Zydro [9]. Let f (z) = fi z i be a generating function satisfying an equation f (z) = i=0 z · (f (z)) where (y) satisfies the following conditions: I (0) = 0, II (y) is analytic in 0, III n0 [y n ](y) 0, IV limyR- (y) = +, where R is the finite radius of convergence of power series expansion of (y) at 0. f Define function z(f ) = (f ) an inversion of f (calculated from the equation defining f ). Note that the condition IV implies that: 0 > lim z (f ) = lim f R- f R- 1 f · (f ) - (f ) (f )2 f · (f ) > 1. lim (f ) f R- and hence that the condition (1) of Theorem 2.1 is satisfied. It means that (y) satisfies all conditions of Theorem 2.1 so there is precisely one solution of the equation (2) and hence also the equation z ( ) = 0. Note that z(0) = limf R- z(f ) = 0 and z(f ) is non-negative in the interval (0, R). Based on the above fact we deduce that z(f )'s only maximum in (0, R) is the point . Moreover, from thesis of Theorem 2.1 we get that z( ) is a radius of convergence of f (z). Based on the above observations we are ready to propose a general method for bounding exponential order of the coefficients of f : Step 1. Express generating function f as solution of the equation f (z) = z · (f (z)) where satisfies conditions IIV. Step 2. Basing on the above equation, calculate function z(f ) an inversion of f (z). Step 3. Find a point f0 inside the interval (0, R) where R is a radius of 1 convergence of (f ) such that z(f0 ) > K for some K. Step 4. Basing on Theorem 2.1, deduce that radius of convergence of 1 the function f (z) is greater than K and hence that its coefficients are of exponential order at most K n . Note that K does not need to be the maximal value of z(f ), which allows us to use numerical computations in the proof. 2.2. Dyck paths. A Generalized Dyck path of type (n, m) is a path on the square lattice with steps (1, 1) and (1, -1) from (0, 0) to (n, m) that never falls below the x-axis. We denote the number of all generalized Dyck paths of type (m, n) as Dm,n . Dyck paths are a standard example of structures counted by Catalan numbers - D2n,0 is equal to Cn . A sample generalized Dyck path of type (10, 2) 3. Proof. The proof follows the general framework of MoserTardosz algorithmisation of Lovasz local lemma [7] adjusted for application to sequences by Grytczuk, Kozik and Micek [4]. We will refer to this method as entropy compression. In the proof we assume that it is not possible to construct an infinite word over alphabet {a, b, c} avoiding pattern p and therefore there is such n that every word of length n contains an instance of p. Hence a naive algorithm that given an infinite sequence of letters S = {a, b, c} tries to construct a word W of length n avoiding pattern p never stops. We use this fact to get the desired contradiction by compressing initial segments of the sequence S to a better extent than it is actually possible. There are 3M possible prefixes of sequence S of length M and we want to show that it is possible to reconstruct any such prefix from a structure created by the algorithm and that there is strictly less than 3M such structures possible to obtain after M steps of the algorithm. Theorem 3.1. If p is a doubled pattern of length 2k with k 4 variables, then (p) 3. Proof. Let us fix a pattern p with at least 4 variables and arbitrarily large N . We will prove by contradiction that it is possible to construct a word W = w1 . . . wN over alphabet = {a, b, c} with holes(W ) = {i : 100 | i} avoiding p. We consider Algorithm 1 running on a random source S that tries to assign letters to all positions of W (even the ones with positions divisible by 100 for easier analysis) and retract all instances of p treating positions in holes(W ) as proper holes when it comes to pattern identification and retracting letters assigned to them normally. Algorithm 1: Avoiding pattern P 1 input: S : N = {a, b, c} 2 i 1, 3 j1 4 while Symbols are not assigned to entire W do 5 wj S(i) 6 i++ 7 j++ 8 if there is an occurrence R of pattern p ending in wj , then 9 let WR be the positions of R 10 for k WR do 11 erase the value of wk j index of the first point in WR 12 13 return W Note that by our assumption that appropriate assignment of letters does not exist, the algorithm never stops. Let us fix some input sequence S and run the algorithm for M steps (i.e. M iterations of the main loop). With every such run we associate some structure describing the behavior of the algorithm. Clearly such a structure depends only on M initial values of S. More importantly sequences S and S which differ on at least one of M initial positions would produce different structures. The structure we use for description of a run of the algorithm is a tuple (P, L, R, H, F ) where: (1) P = (p1 , . . . , pM ) is a sequence of numbers such that pi is the number of places with assigned symbols after i-th step (i.e. the number of indexes i for which wi is defined), (2) L = (L1 , . . . , Ls ) is a sequence of sets of numbers such that Li = {li,1 , . . . , li,k-1 } where li,j is a number of letters assigned to j-th variable in the i-th retracted occurrence of p during the runtime of the algorithm, (3) R = (r1 , . . . , rr ) is a sequence of letters such that after retraction of pattern p, letters assigned to variables A, B, C, . . . are added as suffixes of S, (4) H = {h1 , . . . hv } is a sequence of letters assigned to holes in retracted instances of p. After every retraction we add to H as many letters as many holes were retracted. It is somewhat redundant with R but it does not make an asymptotic difference, (5) F = (f1 , . . . , fn ) is a sequence of symbols left in the word W after M steps of the algorithm. Now we need to prove that this encoding of a prefix of S is loseless and that it is an actual compression for M large enough. Loselessness. We prove that it is possible to reconstruct the first M elements of the input sequence S from a tuple (P, L, R, H, F ) constructed in M steps of the algorithm. Given (P, L, R, H, F ) we are going to decode S(M ) and (P , L , R , H , F ) - tuple constructed by the algorithm running for M - 1 steps on the same input sequence S. Then by simple iteration we can extract all values S(i) for i {1, . . . , M }. We consider two cases: Case 1. If pM = pM -1 + 1 then no pattern instance was retracted during the last step of the algorithm. Then: S(M ) is simply the last element of F , P is one element shorter, L = L, R = R, H = H, F is one element shorter. Case 2. If pM = pM -1 - r + 1 where k > 0, then in the last step there was a retraction of r elements that formed an instance of the pattern p. Then from the last element of L we can reconstruct the structure of this instance, i.e. numbers of letters assigned to each of the variables. From the last element of P we know in which place of the word W an instance occurred and hence the number and placement of holes present in the instance. From the last elements of R we are able to reconstruct the exact letters forming an instance (number of letters we need to subtract from R is equal to the sum of lengths of subwords substituted to variables, which we already know from L). Note that these letters were not necessarily the letters assigned to the places with holes so finally from H we reconstruct the letters assigned to all holes in the instance (number of holes is already known from P ). Knowing precisely the structure of the retracted fragment, we can find the last element of S and the quintuple (P , L , R , H , F ): S(M ) is the last element of the reconstructed retracted fragment, P is one element shorter, L is one element (i.e. set) shorter, R is shorter by all elements used to reconstruct the retracted fragment, - H is shorter by as many elements as many holes were in the reconstructed fragment, - F is equal to F with the reconstructed fragment added as a suffix without the last element added at the end. Compression. We are concerned with the asymptotic number of descriptions when M tends to infinity. We will bound P, L, R together and then separately H and F . Bounding P, L, R. We use analytic combinatorics to find an exponential order of sequence (Ti )iN of possible tuples (P, L, R) occurring after i steps of the algorithm. Before we can use the previously presented method, we need to apply two transformations on P . First we transform P 's into generalized Dyck paths by adding downsteps for every retraction if in P number n follows number k and n < k we add between them all natural numbers between n and k. For example sequence (0, 1, 2, 3, 4, 1, 2, 0) would be transformed into (0, 1, 2, 3, 4, 3, 2, 1, 2, 1, 0). Such modified P is a sequence in which two consecutive numbers differ by exactly 1, which clearly corresponds to a generalized Dyck path. Note that this operation makes P at most two times longer. Second transformation we apply only to the paths ending on level other than first. Every such a path we artificially prolong by adding sequence of upward steps until it reaches level N and then sequence of downward steps until it reaches level 1. We add upward steps because we want to keep the condition that all the paths have descendances at least as long as many variables are in the pattern p. Note that if M (numbers of steps of Algorithm 1, which is now close to half of the length of paths) will be big enough in comparison to N , then such operation will not change the exponential order of the number of our paths. We construct the desired generating function step by step. Let P (z) be the generating function encoding all Dyck paths with falls of lengths being lengths of possible retractions in the algorithm, P L(z) be the generating function of such Dyck paths encoded together with possible L's and finally t(z) be the desired generating function for P, L and R. We will use Flajolet's symbolic operators notation [3] for operations on combinatorial classes. We use slightly modified last passages decomposition for Dyck paths. Let P0,n (z) be a generating function of possible paths starting at level 0 and ending at level n. Recording the times at which each level 0, . . . , n is last traversed gives us P0,n (z) = P0,1 (z)n-1 so summing up for all possible last descendances, we get P (z) = z(1 + SEQ(P (z))). Since together with last descendance we want to record L we need to divide it into k parts corresponding to variables in such a way that the part corresponding to the i-th variable occurring ui times in p is of length divisible by ui . We get P L(z) = z 1 + SEQ SEQui (P L(z)) Encoding it together with R, we get construction for t and transform it into generating function equation: t(z) = z 1 + SEQ SEQui (3 · t(z)) t(z) = z 1 + 3t(z)ui 1 - 3t(z)ui k 3z i Function (z) = 1+ satisfies conditions I -V I necessary 1-3z ui to use our method. Since t(z) is the formal solution of the equation t(z) = z· (t(z)) and we are interested in bounding exponential order of its coefficients x from above we need to investigate maximum of its inversion (x) . To do that we need to find for which u's the function achieves the smallest values. For this purpose we consider the function t (u1 , . . . , uk ) = k 3tu 1 + ( 1-3tiui ) for t (0, 0.6), u1 , . . . , uk 2 we can use this restriction on t since we x don't need to find the real maximum of (x) and restriction on u's comes from the fact that the pattern is doubled. Since (u1 , . . . , uk ) is convex for variables u1 , . . . , uk and maximal value in convex set {(u1 , . . . , uk ); 2 ui , k uk = 2k } is one of sets extremal points we get: k 3tui ( 1-3tui ) k-1 3t2 (1-3t2 ) 3t2 -2k+2 k 1-3t2 -2k+2 k 3tui 1-3tui 3 3t2 1-3t2 3t10 1-3t10 Using Maple software, we check that the right side of the last inequality achieves 0.471 for t = 0.487 so exponential order of Tn is at most 1/0.487 = 2.0533 and hence there is at most 2.0533M possible tuples P, L, R. Bounding H. Since a pattern p has length at least 2k for k 4 and its every retracted instance has at least one letter substituted to every variable then every retraction is of length at least 16. Also, since distance between |R| two holes is 100, every retraction adds at most 100 letters to H. Moreover, the sum of retraction lengths is at most M (we couldn't retract more than M we wrote) so there is at most 3 16 < 1.08M possible H's. Bounding F . Finite sequence is of length at most |W | - 1 so there are less then 4|W | possibilities of such sequence, because there can be assigned symbols 0, 1, 2 or no symbol assigned at every place. Symbols are assigned at prespecified positions so there is no need to encode them. Bounding P, L, R, H, F . Summing all bounds together, we get that for M big enough there is at most (2.0533 · 1.08)M · 4|W | < 2.2176M · 4|W | < 3M tuples and they fully describe 3M possible prefixes of S, which gives us the desired contradiction. 4. Concluding remarks. Overall, entropy compression is a useful method for proving results for partial words. It is mainly helpful to obtain bounds for bigger numbers of variables, since it needs to encode Dyck paths and takes advantage of the fact that short retractions never occur. Straightforward application of developed methods for the second part of the conjecture about binary words, provides the desired result for doubled patterns with at least 3 variables. To prove it for shorter patterns it may be necessary to use some other, possibly deterministic methods.
Journal
Annales UMCS, Mathematica – de Gruyter
Published: Jun 1, 2015