Abstract Generalized pseudostandard words were introduced by de Luca and De Luca in 2006 [7]. In comparison to the palindromic and pseudopalindromic closure, only little is known about the generalized pseudopalindromic closure and the associated generalized pseudostandard words. In this paper we provide a necessary and sufficient condition for their periodicity over binary and ternary alphabet. More precisely, we describe how the directive bi-sequence of a generalized pseudostandard word has to look like in order to correspond to a periodic word. We state moreover a conjecture concerning a necessary and sufficient condition for periodicity over any alphabet. Introduction This paper focuses on a recent topic of combinatorics on words: generalized pseudostandard words. Such words were defined by de Luca and De Luca in 2006 [7] and generalize standard episturmian words, resp., pseudostandard words -instead of the palindromic closure, resp., one pseudopalindromic closure, an infinite sequence of involutory antimorphisms is considered. While standard episturmian and pseudostandard words have been studied intensively and a lot of their properties are known (see for instance [2, 3, 6, 7] ), only little has been shown so far about the generalized pseudopalindromic closure that gives rise to generalized pseudostandard words. In the paper [7] the authors have defined the generalized pseudostandard words and have proven there that the famous Thue-Morse word is an example of such words. Jajcayová et al. [4] have characterized generalized pseudostandard words in the class of generalized Thue-Morse words. Jamet et al. [5] deal with fixed points of the palindromic and pseudopalindromic closure and formulate an open problem concerning fixed points of the generalized pseudopalindromic closure. The most detailed study of generalized pseudostandard words has been so far provided by Blondin Massé et al. [1] : Introduction • An algorithm for normalization over binary alphabet is described. This algorithm transforms the directive bi-sequence in such a way that the obtained word remains unchanged and no pseudopalindromic prefix is missed during the construction. Introduction • An effective algorithm -the generalized Justin's formula -for producing generalized pseudostandard words is presented. Introduction • The standard Rote words are proven to be generalized pseudostandard words and the infinite sequence of antimorphisms that generates such words is studied. Introduction In this paper we provide a sufficient and necessary condition for periodicity of generalized pseudostandard words over binary and ternary alphabet. More precisely, we describe how the directive bi-sequence of a generalized pseudostandard word has to look like in order to correspond to a periodic word. Introduction The text is organized as follows. In Section 2 we introduce basics from combinatorics on words. In Section 3, the generalized pseudopalindromic closure is defined, the normalization algorithm over binary alphabet from [1] is recalled and some new partial results on normalization over ternary alphabet are provided. The main results are presented in the following two sections. A sufficient and necessary condition for periodicity of generalized pseudostandard words is given in Section 4 over binary alphabet and in Section 5 over ternary alphabet. Finally, a conjecture concerning a necessary and sufficient condition for periodicity over any alphabet is stated in the last section. Basics from combinatorics on words Any finite set of symbols is called an alphabet A, the elements are called letters. A (finite) word w over A is any finite sequence of letters. Its length |w| is the number of letters it contains. The empty word -the neutral element for concatenation of words -is denoted ε and its length is set |ε| = 0. The symbol A * stands for the set of all finite words over A. An infinite word u over A is any infinite sequence of letters. A finite word w is a factor of the infinite word u = u 0 u 1 u 2 . . . with u i ∈ A if there exists an index i 0 such that w = u i u i+1 . . . u i+|w|−1 . Let u, v, w ∈ A * , then for w = uv we mean by wv −1 the word u and by u −1 w the word v. The symbol L(u) is used for the set of factors of u and is called the language of u, similarly L n (u) stands for the set of factors of u of length n. Let w ∈ L(u). A left extension of w is any word aw ∈ L(u), where a ∈ A. The factor w is called left special if w has at least two left extensions. The (factor) complexity of u is the map C u : N → N defined as C u (n) = #L n (u). Basics from combinatorics on words The following results on complexity come from [8] . If an infinite word is eventually periodic, i.e., it is of the form wv ω , where w, v are finite words (w may be empty -in such a case we speak about a purely periodic word) and ω denotes an infinite repetition, then its factor complexity is bounded. An infinite word is not eventually periodic -such a word is called aperiodic -if and only if its complexity satisfies: C(n) n + 1 for all n ∈ N. If an infinite word u contains for every length n a left special factor of length n, the complexity is evidently strictly growing, hence u is aperiodic. An infinite word u is called recurrent if each of its factors occurs infinitely many times in u. It is said to be uniformly recurrent if for every n ∈ N there exists a length r(n) such that every factor of length r(n) of u contains all factors of length n of u. Basics from combinatorics on words An involutory antimorphism is a map ϑ : A * → A * such that for every v, w ∈ A * we have ϑ(vw) = ϑ(w)ϑ(v) and moreover ϑ 2 equals identity. It is clear that in order to define an antimorphism, it suffices to provide letter images. There are only two involutory antimorphisms over the alphabet {0, 1}: the reversal (mirror) map R satisfying R(0) = 0, R(1) = 1, and the exchange antimorphism E given by E(0) = 1, E(1) = 0. We use the notation 0 = 1 and 1 = 0, E = R and R = E. There are only four involutory antimorphisms over the alphabet {0, 1, 2}: the reversal map R satisfying R(0) = 0, R(1) = 1, R(2) = 2, and three exchange antimorphisms E 0 , E 1 , E 2 given by Basics from combinatorics on words Consider an involutory antimorphism ϑ over A. A finite word w is a ϑ-palindrome if w = ϑ(w). The ϑ-palindromic closure w ϑ of a word w is the shortest ϑ-palindrome having w as prefix. For instance, over binary alphabet 011 R = 0110, 011 E = 011001. We speak about the palindromic closure if ϑ = R and the pseudopalindromic closure if we do not need to specify which antimorphism ϑ is used. Generalized pseudopalindromic closure Generalized pseudostandard words form a generalization of infinite words generated by the palindromic or pseudopalindromic closure (see [2, 3, 6, 7] for more details on pseudostandard words); such a construction was first described and studied in [7] . Let us start with their definition and known properties; we use the papers [5, 7, 1] . Generalized pseudopalindromic closure the electronic journal of combinatorics 16 (2009), #R00 3.1 Definition of generalized pseudostandard words Definition 1. Let A be an alphabet and G be the set of all involutory antimorphisms on A * . Let ∆ = δ 1 δ 2 . . . and Θ = ϑ 1 ϑ 2 . . ., where δ i ∈ A and ϑ i ∈ G for all i ∈ N. The infinite generalized pseudostandard word u(∆, Θ) generated by the generalized pseudopalindromic closure is the word whose prefixes w n are obtained from the recurrence relation Generalized pseudopalindromic closure The sequence Λ = (∆, Θ) is called the directive bi-sequence of the word u(∆, Θ). Generalized pseudopalindromic closure If Θ = ϑ ω in the previous definition, then we deal with well known pseudostandard words. In such a case the sequence (w n ) n 0 is known to contain all ϑ-palindromic prefixes of u(∆, Θ). Generalized pseudopalindromic closure We will restrict our considerations to two cases: Generalized pseudopalindromic closure The following two properties are readily seen from the definition of u = u(∆, Θ): Generalized pseudopalindromic closure • If an involutory antimorphism ϑ is contained in Θ infinitely many times, then the language of u is closed under the antimorphism ϑ. Generalized pseudopalindromic closure • The word u is uniformly recurrent. Normalization over binary alphabet In contrast to pseudostandard words, the sequence (w n ) n 0 of prefixes of a binary generalized pseudostandard word u(∆, Θ) does not have to contain all palindromic and Epalindromic prefixes of u(∆, Θ). Blondin Massé et al. [1] have introduced the notion of normalization of the directive bi-sequence. Definition 2. A directive bi-sequence Λ = (∆, Θ) of a binary generalized pseudostandard word u(∆, Θ) is called normalized if the sequence of prefixes (w n ) n 0 of u(∆, Θ) contains all palindromic and E-palindromic prefixes of u(∆, Θ). Definition 2. . Let us write down the first prefixes of u(∆, Θ): Definition 2. The sequence w n does not contain for instance palindromic prefixes 0 and 0110 of u(∆, Θ). The authors of [1] have proven that every directive bi-sequence Λ can be normalized, i.e., transformed to such a form Λ that the new sequence ( w n ) n 0 contains already all palindromic and E-palindromic prefixes and Λ generates the same generalized pseudostandard word as Λ. Definition 2. Theorem 4. Let Λ = (∆, Θ) be a directive bi-sequence of a binary generalized pseudostandard word. Then there exists a normalized directive bi-sequence Λ = ( ∆, Θ) such that u(∆, Θ) = u( ∆, Θ). Definition 2. Moreover, in order to normalize the sequence Λ, it suffices firstly to execute the following changes to its prefixes (if they are of the corresponding form): Definition 2. and secondly to replace step by step from left to right every factor of the form: Definition 2. where a, b ∈ {0, 1} and ϑ ∈ {E, R}. Definition 2. Example 5. Let us normalize the directive bi-sequence Λ = ((011) ω , (EER) ω ) from Example 3. According to the procedure from Theorem 4, we transform first prefixes of Λ. We replace (0, E) with (01, RE) and get Λ 1 = (01(110) ω , RE(ERE) ω ). Some prefixes of Λ 1 are still of a forbidden form, we replace thus the prefix (011, REE) with (0110, RERE) and get Λ 2 = (0110(101) ω , RERE(REE) ω ). Prefixes of Λ 2 are now correct. It remains to replace from left to right the factors (101, REE) with (1010, RERE). Finally, we obtain Λ = (0110(1010) ω , RERE(RERE) ω ) = (01(10) ω , (RE) ω ), which is already normalized. Let us write down the first prefixes ( w n ) n 0 of u( Λ): Definition 2. We can notice that the new sequence ( w n ) n 0 now contains the palindromes 0 and 0110 that were skipped in Example 3. Normalization over ternary alphabet A normalized directive bi-sequence can be defined similarly as in Definition 2 over multiliteral alphabet. In contrast to binary alphabet, over ternary alphabet it is still clear that every directive bi-sequence may be normalized, however the algorithm for normalization the electronic journal of combinatorics 16 (2009), #R00 similar to the one over binary alphabet (Theorem 4) has not been found yet. Fortunately, in order to prove a sufficient and necessary condition for periodicity of ternary generalized pseudostandard words, even some partial results on normalization over ternary alphabet suffice. Let us introduce these partial results. Normalization over ternary alphabet We will focus on bi-sequences that contain infinitely many times exactly two distinct antimorphisms including R. Normalization over ternary alphabet Lemma 6. Let the directive bi-sequence (∆, Θ) of a ternary generalized pseudostandard word u contain as its factor (abc, ϑRR), resp., (abc, Rϑϑ), where ϑ ∈ {E 0 , E 1 , E 2 } and a, b, c ∈ {0, 1, 2} satisfy ϑ(b) = c. Denote w n = ϑ(w n ), w n+1 = R(w n+1 ) and w n+2 = R(w n+2 ), resp., w n = R(w n ), w n+1 = ϑ(w n+1 ) and w n+2 = ϑ(w n+2 ), the corresponding pseudopalindromic prefixes of u. Then between the pseudopalindromic prefixes w n+1 and w n+2 of the word u there is a ϑ-palindromic, resp., palindromic, prefix w of u followed by the letter b. Normalization over ternary alphabet Proof. Consider the first case, i.e., (abc, ϑRR) is a factor of (∆, Θ). The proof of the second case is left for the reader since it is analogous. Denote bsb the longest palindromic suffix of w n b. Then w n = ps, where p is a nonempty prefix of w n because w n is a ϑ-palindrome while s is a palindrome. We have w n+1 = psR(p). When constructing w n+2 , we look for the longest palindromic suffix of w n+1 c. It is easy to see that such a suffix is equal to ϑ(b)ϑ(s)c = cϑ(s)c. We can thus write Normalization over ternary alphabet Let us rewrite the word Normalization over ternary alphabet which is a prefix of w n+2 . We have Normalization over ternary alphabet We have used the facts: ϑ(ps) = ps, R(s) = s and ϑR = Rϑ. Clearly, we have that |w n+1 | < |w| < |w n+2 |, therefore the sequence (∆, Θ) is not normalized and w is the searched ϑ-palindromic prefix of u. Since w n+2 = wR(p) and p ends in b, the word R(p) starts in b. Consequently, w is followed by b. Corollary 7. Under the assumptions of Lemma 6 we have: If the factor (abc, ϑRR), resp., (abc, Rϑϑ), of the directive bi-sequence (∆, Θ) of the word u is replaced with the factor (abcb, ϑRϑR), resp., (abcb, RϑRϑ), the same generalized pseudostandard word is obtained. Proof. Consider again the first case, i.e., (abc, ϑRR) is a factor of the directive bi-sequence, and let for the reader the second one. Denote w n = ϑ(w n ), w n+1 = R(w n+1 ) and w n+2 = R(w n+2 ) the corresponding pseudopalindromic prefixes of u. Denote further in the same way as in Lemma 6 the skipped ϑ-palindrome by w. We know that the prefix w is followed by the letter b, thus it suffices to show that (w n+1 c) ϑ = w and (wb) R = w n+2 . We will start with the first claim. Assume for contradiction that there exists a ϑ-palindromic prefix v 1 such that (w n+1 c) ϑ = v 1 and |v 1 | < |w|. When constructing the ϑ-palindrome v 1 , we look for the longest ϑ-palindromic suffix ϑ(c)vc = bvc of the word w n+1 c. It is not difficult to see that |w n | |v| < |w n+1 |, where the first relation follows from the fact that bR(w n )c is a ϑ-palindromic suffix of w n+1 c. Corollary 7. The easiest way to check this equality is to notice that both v 1 and w are prefixes of u and have the same length according to the form of w defined in (1) . Since v is a ϑ-palindromic suffix of the palindrome w n+1 , its reversal R(v) is a ϑ-palindromic prefix between w n and w n+1 . Since w n+1 is the shortest palindrome having the prefix w n b, it has to satisfy at the same time Corollary 7. Let us however show that this leads to a contradiction. Denote bsb the longest palindromic suffix of w n b and b sb the longest palindromic suffix of Corollary 7. is a palindromic prefix shorter than w n+1 and longer than w n , which is a contradiction. Corollary 7. It remains to show that (wb) R = w n+2 . We have (w n+1 c) R = w n+2 , i.e., w n+2 is the shortest palindrome having w n+1 c as prefix. Hence the shortest palindrome with the prefix wb has to equal w n+2 since w n+1 c is a prefix of wb and wb is a prefix of w n+2 . Corollary 7. Example 8. Let us illustrate Lemma 6 and Corollary 7. Assume we have already constructed the prefix w k = 012 of a generalized pseudostandard word. Suppose further that the factor (120, E 1 RR) of the directive bi-sequence follows. It is readily seen that the assumptions of Lemma 6 are met (in particular we have E 1 (2) = 0). Let us write down the prefixes w k+1 , w k+2 and w k+3 . Corollary 7. It is evident that between the prefixes w k+2 and w k+3 there is an E 1 -palindrome 012101221012100121012 followed by 2. Corollary 7 moreover states that the generalized pseudostandard word remains the same if we replace the factor (120, E 1 RR) of the directive bi-sequence with the factor (1202, E 1 RE 1 R) -the reader can check it easily. exactly two distinct antimorphisms ϑ and R. The sequence ∆ = δ 1 δ 2 · · · contains infinitely many times two (not necessarily distinct) letters a, b such that ϑ(a) = b. Let further the bi-sequence Λ satisfy: There exists n 0 ∈ N such that for all n > n 0 we have: either Corollary 7. Then there exists a directive bi-sequence Corollary 7. Proof. We can certainly find m > n 0 such that the sequence Θ contains -starting from the index m -exactly two antimorphisms ϑ and R (both of them infinitely many times) and the sequence ∆ contains -starting from the index m -only letters a and b (not necessarily distinct). Let us find ℓ > m satisfying ϑ ℓ = R and ϑ ℓ+1 = ϑ. Using assumptions of Corollary 9, we get δ ℓ+1 = b and δ ℓ+2 = a (we assume without loss of generality that the antimorphism R is followed by the letter b). We have thus found a factor of the directive bi-sequence of the form (cba, Rϑζ 1 ) for some c ∈ {a, b} and ζ 1 ∈ {ϑ, R}. If now ζ 1 = ϑ, the assumptions of Corollary 7 are met, and consequently this factor may be replaced with the factor (cbab, RϑRϑ) and we get the same generalized pseudostandard word. If ζ 1 = R, then δ ℓ+3 = b and we get again a factor of the directive bi-sequence of the form (cbab, RϑRζ 2 ) for some ζ 2 ∈ {ϑ, R}, etc. A formal proof by induction is left as an exercise for the reader. Finally, we set v := δ 1 . . . δ ℓ+1 and σ := ϑ 1 . . . ϑ ℓ+1 . Corollary 7. At this moment, we know that if a directive bi-sequence satisfies the assumptions of Lemma 6, it is not normalized. The remaining question is whether the new bi-sequence whose existence is guaranteed by Corollary 9 is normalized (at least from a certain moment on). A partial answer to this question is provided in the following lemma. Corollary 7. Then for all n > n 0 = |v| the sequence (w n ) n>n 0 contains all palindromic, resp., ϑ-palindromic, prefixes of length larger than |w n 0 | of the word u followed by the letter b, resp., a. Corollary 7. Proof. Assume for contradiction that there exists n > n 0 such that between the prefixes w n = ϑ(w n ) and w n+1 = R(w n+1 ) (the converse case is analogous) another pseudopalindromic prefix w occurs: Corollary 7. • Either w is a palindrome. This is a contradiction with the fact that w n+1 is the shortest palindrome having w n a as prefix. Corollary 7. the electronic journal of combinatorics 16 (2009), #R00 Corollary 7. • Or w is a ϑ-palindrome followed by a (consider the shortest such w). Denote asa the longest palindromic suffix of w n a and a sa the longest palindromic suffix of wa. Since w n is a suffix of w, either | s| > |w n | or | s| = |s|. If | s| > |w n |, then ϑ( s) is a palindromic prefix shorter than w n+1 and longer than w n , which is a contradiction. Corollary 7. Since w n+1 is the shortest palindrome having the prefix w n a, it has to satisfy at the same time w n+1 = (w n a) R = (wa) R , and this is again a contradiction. Periodicity of binary generalized pseudostandard words Our first new result concerning generalized pseudostandard words is a necessary and sufficient condition for their periodicity over binary alphabet. We thus consider throughout this section binary infinite words. Periodicity of binary generalized pseudostandard words Theorem 11. A binary generalized pseudostandard word u(∆, Θ), where ∆ = δ 1 δ 2 . . . ∈ {0, 1} N and Θ = ϑ 1 ϑ 2 . . . ∈ {E, R} N , is periodic if and only if the directive bi-sequence (∆, Θ) satisfies the following condition: Periodicity of binary generalized pseudostandard words Remark 12. The condition for periodicity may be rewritten in a slightly less formal way: u(∆, Θ) is periodic if and only if there exists a bijection π : {E, R} → {0, 1} such that π(ϑ n ) = δ n+1 for all sufficiently large n. Periodicity of binary generalized pseudostandard words Let us point out that generalized pseudostandard words are either aperiodic or purely periodic -it follows from the fact that they are recurrent. Periodicity of binary generalized pseudostandard words In order to prove Theorem 11 we need the following lemma and remark. Periodicity of binary generalized pseudostandard words Lemma 13. Let (∆, Θ) be a normalized directive bi-sequence of a generalized pseudostandard word. Assume (∆, Θ) satisfies condition (4) and both E and R occur in Θ infinitely many times. Then there exist Periodicity of binary generalized pseudostandard words and |ν| = |σ|. Periodicity of binary generalized pseudostandard words Proof. Let us set ν = δ 1 . . . δ n 0 and σ = ϑ 1 . . . ϑ n 0 . Let us further denote b = δ n 0 +1 and ϑ = ϑ n 0 +1 . Since the directive bi-sequence satisfies condition (4), the same letter (say a) has to follow ϑ. Since both E and R occur in Θ infinitely many times, ϑ is repeated only finitely many times (say i + 1 times), i.e., ϑ n 0 +1 = . . . = ϑ n 0 +1+i = ϑ and ϑ n 0 +2+i = ϑ. According to (4) we have δ n 0 +2 = . . . = δ n 0 +2+i = a and δ n 0 +3+i =ā. By Theorem 4 a normalized directive bi-sequence cannot contain the factor (cdd, γγγ) for any c, d ∈ {0, 1}, γ ∈ {E, R}. Consequently, ϑ n 0 +3+i = ϑ. Consider now the prefix of (∆, Θ) of the form Periodicity of binary generalized pseudostandard words Then again by Theorem 4 and using (4), the prefix of (∆, Θ) of length |Λ k | + 2 is equal to Λ k+1 . Periodicity of binary generalized pseudostandard words The following remark follows easily from Theorem 4. Periodicity of binary generalized pseudostandard words Remark 14. Let a directive bi-sequence of a generalized pseudostandard word satisfy condition (4) . Then the corresponding normalized bi-sequence satisfies condition (4). Periodicity of binary generalized pseudostandard words Proof of Theorem 11. (⇐) : Periodicity of binary generalized pseudostandard words 1. Assume that the sequence Θ contains both E and R infinitely many times. Let us normalize Λ = (∆, Θ) and denote the new directive bi-sequence by Λ. By Remark 14 the sequence Λ satisfies condition (4). Applying Lemma 13 it is possible to write Λ = ( ν(aā) ω , σ(ϑϑ) ω ), where | ν| = | σ|. Without loss of generality suppose that σ = θ 1 ϑ. (Otherwise we would extend the sequence ν and σ by two consecutive members.) Set n 0 = | σ|. We will show that for all n > n 0 there exists k ∈ N such that either Periodicity of binary generalized pseudostandard words or Periodicity of binary generalized pseudostandard words where (w n ) n 0 is the sequence of prefixes associated with u( Λ) (we omit tildes for simplicity). It follows then directly from these forms that Periodicity of binary generalized pseudostandard words is the period of the generalized pseudostandard word u(∆, Θ). Periodicity of binary generalized pseudostandard words It is not difficult to show that if w n is of the form (5), then w n = ϑ(w n ). It suffices to take into account that ϑ n 0 = ϑ and therefore ϑ(w n 0 ) = w n 0 and ϑ(w n 0 +1 ) = w n 0 +1 . Similarly, if w n is of the form (6), then w n = ϑ(w n ). Periodicity of binary generalized pseudostandard words Let us proceed by induction: w n 0 and w n 0 +1 are of the form (5) or (6) -it suffices to set k = 0. Let n > n 0 + 1 and assume w ℓ is of the form (5) or (6) for all ℓ ∈ N, where n 0 + 1 < ℓ n. Periodicity of binary generalized pseudostandard words • Let w n be of the form (5). Then w n = ϑ(w n ) and by condition (4), we have δ n+1 = a. When constructing w n+1 , we search for the longest ϑ-palindromic suffix of w n a. Since Λ is normalized, the longest ϑ-palindromic prefix of w n is w n−1 , and consequently the longest ϑ-palindromic suffix of w n is ϑ(w n−1 ). Thanks to the form of Λ = ( ν(aā) ω , σ(ϑϑ) ω ) we further know that w n−1 is followed byā. Since w n is a ϑ-palindrome, the factor ϑ(w n−1 ) is preceded by the electronic journal of combinatorics 16 (2009), #R00 ϑ(ā). Consequently, ϑ(ā)ϑ(w n−1 )a is a candidate for the longest ϑ-palindromic suffix of w n a. On the one hand, if ϑ = R, this candidate equalsāR(w n−1 )a, which is an E-palindrome. On the other hand, if ϑ = E, then this candidate equals aE(w n−1 )a, which is an R-palindrome. Thus it is indeed the longest ϑ-palindromic suffix of w n a. Using the induction assumption and since w n−1 is a ϑ-palindrome, we have: Periodicity of binary generalized pseudostandard words n 0 w n 0 +1 ). Consequently, we obtain: Periodicity of binary generalized pseudostandard words which corresponds to the form (6). Periodicity of binary generalized pseudostandard words • For w n of the form (6) we proceed analogously. Periodicity of binary generalized pseudostandard words 2. Let the directive bi-sequence be of the form Λ = (νa ω , σϑ ω ). (In fact, the generalized pseudostandard word in question is either an E-standard or an R-standard word with seed as defined in [2] .) It is known in this case that the word is periodic [2] . Let us rewrite the directive bi-sequence so that |ν| = |σ| and σ = θ 1 ϑ and let n 0 = |σ|. It can be proven similarly as in the first case that for all n > n 0 there exists k ∈ N such that w n = w n 0 [w Periodicity of binary generalized pseudostandard words Therefore the period of the E-or R-standard word with seed in question is equal to w n 0 +1 w −1 n 0 . (⇒) : We will show that if condition (4) is not satisfied, then the generalized pseudostandard word u(∆, Θ) is aperiodic. More precisely, we will show that each of its prefixes is a left special factor. Let us restrict ourselves to the case where Θ contains E and R infinitely many times. Otherwise, we deal with E-or R-standard words with seed and the result is known from [2] . The negation of condition (4) reads: for all a ∈ {0, 1}, for all ϑ ∈ {E, R}, and for all n 0 ∈ N there exists n > n 0 such that Periodicity of binary generalized pseudostandard words Let v be a prefix of u(∆, Θ). Firstly, take a = 0, ϑ = R, and n 0 > |v|, then there exists Periodicity of binary generalized pseudostandard words Secondly, choose a = 1, ϑ = R, and n 0 > |v|, then there exists n 2 > n 0 such that (δ n 2 +1 = 1 ∧ ϑ n 2 = E) ∨ (δ n 2 +1 = 0 ∧ ϑ n 2 = R). The following four cases may occur: Periodicity of binary generalized pseudostandard words • δ n 1 +1 = 0, ϑ n 1 = E and δ n 2 +1 = 1, ϑ n 2 = E: In this case, both w n 1 and w n 2 are Epalindromes, thus E(v) is a suffix of both of them. Since δ n 1 +1 = 0 and δ n 2 +1 = 1, the words E(v)0 and E(v)1 are factors of u(∆, Θ). Since the language is closed under E, both 1v and 0v are factors of u(∆, Θ). Periodicity of binary generalized pseudostandard words the electronic journal of combinatorics 16 (2009), #R00 Periodicity of binary generalized pseudostandard words • δ n 1 +1 = 0, ϑ n 1 = E and δ n 2 +1 = 0, ϑ n 2 = R: Now, E(v) has the right extension E(v)0 and R(v) has the right extension R(v)0. Using the fact that the language is closed under E and R, one can see that both 1v and 0v are factors of u(∆, Θ). Periodicity of binary generalized pseudostandard words • δ n 1 +1 = 1, ϑ n 1 = R and δ n 2 +1 = 1, ϑ n 2 = E: This case is analogous to the previous one. Periodicity of binary generalized pseudostandard words • δ n 1 +1 = 1, ϑ n 1 = R and δ n 2 +1 = 0, ϑ n 2 = R: This case is similar to the first one. Periodicity of binary generalized pseudostandard words Example 15. Consider the directive bi-sequence Λ = ((011) ω , (EER) ω ) from Example 3. This sequence satisfies condition (4). According to Remark 14 the normalization of the directive bi-sequence preserves condition (4). It follows from Example 5 that the normalized form of the directive bi-sequence is Λ = (01(10) ω , RE(RE) ω ). Let us write down the first prefixes w k of u( Λ): Periodicity of binary generalized pseudostandard words In the proof of Theorem 11, the formula for the period (not necessarily the smallest one) of u(Λ) was given by (7): Periodicity of binary generalized pseudostandard words where ϑ = E, n 0 = 2, w n 0 = w 2 , and w n 0 +1 = w 3 . Thus the period equals 0110 = w 3 . Therefore u(Λ) = u( Λ) = (0110) ω . Periodicity of ternary generalized pseudostandard words For ternary generalized pseudostandard words, straightforward analogy of the binary case, i.e., of condition (4) from Theorem 11, does not work. Periodicity of ternary generalized pseudostandard words Example 16. Consider the ternary infinite word u = u((01) ω , (RE 1 ) ω ). It is easy to show that any prefix p of u is left special -both 1p and 2p are factors of u, thus u is an aperiodic word. Periodicity of ternary generalized pseudostandard words The condition for periodicity gets more complicated. 1. The sequences ∆ and Θ are eventually constant, i.e., ∆ = va ω for some v ∈ {0, 1, 2} Periodicity of ternary generalized pseudostandard words * and a ∈ {0, 1, 2} and Θ = σϑ ω for some σ ∈ {E 0 , E 1 , E 2 , R} * and ϑ ∈ {E 0 , E 1 , E 2 , R}. 2. • Θ contains exactly two antimorphisms ϑ and R infinitely many times; 2. • ∆ contains two (not necessarily distinct) letters a and b infinitely many times such that ϑ(a) = b; 2. • there exists n 0 ∈ N such that for every n > n 0 we have either 2. 3. The normalized directive bi-sequence ( ∆, Θ) of u satisfies 2. where v ∈ {0, 1, 2} * , σ ∈ {E 0 , E 1 , E 2 , R} * , |v| = |σ|, and i, j, k ∈ {0, 1, 2} are mutually different letters. 2. It is worth mentioning that for bi-sequences containing more antimorphisms including R, Theorem 17 provides an easy-to-check condition for recognizing periodicity, however for other bi-sequences containing more antimorphisms, it is not too practical since the algorithm for normalization is not known over ternary alphabet. 2. . Since E 0 (1) = 2, the second condition of Theorem 17 is satisfied. Let us write down the first few prefixes w n of u: 2. It is left for the reader to show that u = (021012) ω . 2. The third condition of Theorem 17 is satisfied. Let us write down the first few prefixes w n of u: In order to make the proof of Theorem 17 as comprehensible as possible, let us distinguish several cases according to the number of antimorphisms occurring infinitely many times in the directive bi-sequence. We will consider them in the following three sections. Putting then the results of Sections 5.1, 5.2 and 5.3 together, one obtains immediately the proof of Theorem 17. Directive bi-sequences containing one antimorphism Let us start with the simplest case, where Θ contains only one antimorphism infinitely many times. Directive bi-sequences containing one antimorphism Lemma 20. Let the directive bi-sequence Λ = (∆, Θ) be of the form Λ = (∆, σϑ ω ) for some σ ∈ {E 0 , E 1 , E 2 , R} * and ϑ ∈ {E 0 , E 1 , E 2 , R}. Then the word u = u(∆, Θ) is periodic if and only if ∆ = va ω for some v ∈ {0, 1, 2} * and a ∈ {0, 1, 2}. Directive bi-sequences containing one antimorphism Proof. (⇒): Assume the sequence ∆ contains infinitely many times two distinct letters, say a and b. Then the antimorphism ϑ is followed infinitely many times by both letters a and b. This implies that every prefix of u is a left special factor. Therefore u is aperiodic. (⇐): Let Λ = (va ω , σϑ ω ). Denote n 0 = max{|v|, |σ|}. Then w n 0 +2 = psϑ(p), where ϑ(a)sa is the longest ϑ-palindromic suffix of the word w n 0 +1 a. Let us now construct w n 0 +3 . The longest ϑ-palindromic suffix of w n 0 +2 a equals ϑ(a)w n 0 +1 a = ϑ(a)sϑ(p)a. We have used the fact that w n 0 +1 = ps = ϑ(ps) and s = ϑ(s) and that by the form of Λ, the factor w n 0 +1 is evidently the longest ϑ-palindromic prefix of w n 0 +2 followed by a. Thus w n 0 +3 = ps(ϑ(p)) Directive bi-sequences containing one antimorphism 2 . Repeating this process we get u = ps(ϑ(p)) ω . Directive bi-sequences containing two antimorphisms Let us consider directive bi-sequences (∆, Θ), where Θ contains infinitely many times exactly two distinct antimorphisms. The first lemma holds for any two antimorphisms, while in the sequel we will consider bi-sequences, where one of the antimorphisms equals R. Directive bi-sequences containing two antimorphisms Lemma 21. Let the directive bi-sequence Λ = (∆, Θ) satisfy: ∆ contains infinitely many times all letters 0, 1, 2 and Θ contains infinitely many times exactly two antimorphisms Directive bi-sequences containing two antimorphisms Proof. Thanks to the form of Λ it is possible to choose two sequences of indices, say Directive bi-sequences containing two antimorphisms , such that for all n ∈ N there exist two distinct letters δ 1 , δ 2 and an antimorphism ϑ satisfying δ kn = δ 1 , δ ℓn = δ 2 and ϑ kn−1 = ϑ ℓn−1 = ϑ. In other words, the same antimorphism is followed infinitely many times by two distinct letters. This implies that every prefix of u is left special. many times two (not necessarily distinct) letters a and b. Then the word u = u(∆, Θ) is periodic if and only if the directive bi-sequence (∆, Θ) satisfies: ϑ(a) = b and there exists n 0 ∈ N such that for all n > n 0 either Directive bi-sequences containing two antimorphisms Proof. (⇒): Directive bi-sequences containing two antimorphisms 1. If neither (11) nor (12) is met, then the letters a and b are necessarily distinct and it happens infinitely many times that the same antimorphism is followed by two distinct letters. This implies that every prefix of u is left special. Directive bi-sequences containing two antimorphisms 2. Assume without loss of generality that condition (11) is satisfied. If ϑ(a) = b, then every prefix of u is left special: Let v be a prefix of u. Let v be contained in the prefix Directive bi-sequences containing two antimorphisms Let us similarly find ℓ, where ℓ > n 0 , such that v is a prefix of w ℓ = ϑ(w ℓ ). Then w ℓ a ∈ L(u), and consequently ϑ(a)ϑ(w ℓ ) = ϑ(a)w ℓ ∈ L(u). Thanks to the assumption that ϑ(a) = b, the prefix v is a left special factor of u. Directive bi-sequences containing two antimorphisms (⇐): According to Corollary 9 we can assume without loss of generality that Λ = (v(ab) ω , σ(Rϑ) ω ), where v ∈ {0, 1, 2} * , σ ∈ {E 0 , E 1 , E 2 , R} * and |v| = |σ|. Denote n 0 = |σ|, i.e., w n 0 +1 = R(w n 0 +1 ) and w n 0 +2 = ϑ(w n 0 +2 ). Denote further ϑ(b)sb = asb the longest ϑ-palindromic suffix of the word w n 0 +1 b. We can thus write w n 0 +2 = psϑ(p) = pϑ(s)ϑ(p) = pϑ(ps) for some prefix p of the word w n 0 +1 . Thanks to Lemma 10, the factor w n 0 +1 is the longest palindromic prefix of w n 0 +2 followed by the letter b, therefore ϑ(b)ϑ(w n 0 +1 )a = aϑ(w n 0 +1 )a = aϑ(ps)a is the longest palindromic suffix of the word w n 0 +2 a. Consequently, we have w n 0 +3 = pϑ(ps)R(p) = psϑ(p)R(p). Let us show by induction that for all k 1 the following holds: Directive bi-sequences containing two antimorphisms For k = 1 the relations (13) and (14) hold. Let them hold for some k 1. Then w n 0 +2k+1 = (w n 0 +2k a) R . We know that ϑ(w n 0 +2k−1 ) is a palindromic suffix of the word w n 0 +2k preceded by the letter a = ϑ(b) and, thanks to Lemma 10, this suffix is the longest the electronic journal of combinatorics 16 (2009), #R00 palindromic suffix of the word w n 0 +2k preceded by the letter a = ϑ(b). It follows: Directive bi-sequences containing two antimorphisms Similarly, R(w n 0 +2k ) is the longest ϑ-palindromic suffix of the word w n 0 +2k+1 preceded by the letter R(a) = a. Directive bi-sequences containing two antimorphisms For arbitrary k 1 the factor w n 0 +2k−1 is a palindrome and is of the form (13), hence u is periodic with the period R(ϑ(p)R(p)) = pRϑ(p). Directive bi-sequences containing two antimorphisms Let us describe all combinations of antimorphisms and letters from Proposition 22 for which a periodic word occurs, i.e., for which either condition (11) or condition (12) is met and at the same time ϑ(a) = b. Using the notation from the proof of Proposition 22 we have w n 0 +1 = w 3 , s = 0120 and p = 021. The period of the word u( Λ) is therefore equal to pRE 0 (p) = 021012, i.e., u( Λ) = (021012) ω . Directive bi-sequences containing three or four antimorphisms Let us now treat the remaining bi-sequences. At first, we show that all generalized pseudostandard words having in their directive bi-sequence infinitely many times three or four antimorphisms such that one of them equals R are aperiodic. Directive bi-sequences containing three or four antimorphisms Proposition 24. Let u = u(∆, Θ), where Θ contains infinitely many times three or four antimorphisms including R. Then the word u is aperiodic. Directive bi-sequences containing three or four antimorphisms Proof. Assume without loss of generality that the bi-sequence (∆, Θ) is normalized. (It is easy to see that a normalized form always exists and the original bi-sequence is its subsequence.) Assume now for contradiction that the word u is periodic. It holds then: Directive bi-sequences containing three or four antimorphisms 1. There exists n 0 such that for all n > n 0 the following conditions are satisfied: Directive bi-sequences containing three or four antimorphisms where Θ = ϑ 1 ϑ 2 · · · , ∆ = δ 1 δ 2 · · · , a, b, c, i, j, k ∈ {0, 1, 2} and i, j, k are mutually different indices. If at least one of the above conditions is not met, then it can be easily shown that every prefix of u is left special, and the word u is thus aperiodic. Consider ℓ ∈ {0, 1, 2} such that RE ℓ occurs infinitely many times in Θ. Denote (e n a, RE ℓ ), n > n 0 , the corresponding factors of the bi-sequence (∆, Θ). Denote w corresponding palindromic prefixes and w (n) m+1 the corresponding E ℓ -palindromic prefixes and let e denote the letter that follows the E ℓ -palindromes w (n) m+1 . Let us now study the form of w (n) m+2 . It holds that the longest palindromic suffix of the word w (n) m+1 e is thanks to the normalized form of the directive bi-sequence equal to E ℓ (a)E ℓ (w (n) m )e since according to condition 2 we have E ℓ (a) = e. Moreover using again the fact that the directive bisequence is normalized, the factor E ℓ (a)E ℓ (w (n) m )e is the longest ϑ-palindromic suffix of the word w (n) m+1 e for any antimorphism ϑ. There exists n 1 > n 0 such that for all n > n 1 the factor w (n) m+2 is a palindrome. Suppose that such an index n 1 does not exist. It means that for infinitely many indices n, when constructing w (n) m+2 , we look for a shorter ϑ-palindromic suffix of the word w (n) m+1 e than its palindromic suffix E ℓ (a)E ℓ (w (n) m )e. If we now extend the longest suffix E ℓ (a)E ℓ (w (n) m )e stepwise by one letter to the right and one letter to the left so that the obtained word remains a palindrome, we get a palindrome s (n) that is surrounded by distinct letters from right and from left. Since L(u) is closed under the antimorphism R, the factor s Directive bi-sequences containing three or four antimorphisms is a bispecial factor and the word u is aperiodic, which is a contradiction. Directive bi-sequences containing three or four antimorphisms Similarly, it is possible to show that there exists n 2 > n 1 such that for all n > n 2 the factor w (n) m+3 is an E ℓ -palindrome. The above arguments imply that Θ = σ(RE ℓ ) ω for some σ ∈ {R, E 0 , E 1 , E 2 } * , which is a contradiction. Directive bi-sequences containing three or four antimorphisms Example 25. Since the construction of bispecials s (n) from the previous proof is quite complicated, let us illustrate it on an example. Consider u = u( (210) ω , (E 0 E 1 R) ω ). This bi-sequence is not normalized, however it serves as a simple example for illustration of the previous proof. Let us write down the first five prefixes: Indeed, E 0 (w 3 ) = 12200221 is a palindromic suffix of w 4 that may be extended stepwise so that the obtained word s = 00112200221100 is still a palindrome. The word s is underlined in the prefix w 5 . Moreover, we can see that s cannot be extended as a palindrome any more since the next factor is 1s2. The language L(u) is closed under R, therefore 2s1 is a factor of u, too. Since we work in the proof of Proposition 24 with a normalized bi-sequence, it is guaranteed that s cannot be extended to a prefix of u. In such a case s would be a skipped palindromic prefix of u. Directive bi-sequences containing three or four antimorphisms In order to treat the remaining directive bi-sequences in the last proposition, the following remark and corollary are needed. Remark 26. For i, j, k ∈ {0, 1, 2} mutually different, we have Directive bi-sequences containing three or four antimorphisms Corollary 27. Let for some i ∈ {0, 1, 2} and v ∈ {0, 1, 2} Directive bi-sequences containing three or four antimorphisms Proposition 28. Let u = u(∆, Θ) be a ternary generalized pseudostandard word, where Θ contains infinitely many times E i , E j , or E i , E j , E k with i, j, k mutually distinct. Then u is periodic if and only if Directive bi-sequences containing three or four antimorphisms where ( ∆, Θ) is the normalized form of (∆, Θ), v ∈ {0, 1, 2} * , σ ∈ {E 0 , E 1 , E 2 , R} * and |v| = |σ|. Directive bi-sequences containing three or four antimorphisms Proof. (⇒): Suppose that the normalized bi-sequence is not of the form (15). We will show that u = u( ∆, Θ) is aperiodic. Assume: Directive bi-sequences containing three or four antimorphisms 1. There exists n 0 such that for all n > n 0 the following conditions are satisfied: Directive bi-sequences containing three or four antimorphisms where Θ = ϑ 1 ϑ 2 · · · , ∆ = δ 1 δ 2 · · · , a, b, c, i, j, k ∈ {0, 1, 2} and i, j, k are mutually different indices. If at least one of the above conditions is not met, then it can be easily shown that every prefix of u is left special. Since condition (15) is not met, two possibilities occur: Directive bi-sequences containing three or four antimorphisms • The bi-sequence ( ∆, Θ) contains infinitely many times the factor (def, E ℓ E s E s ) for some d, e, f, ℓ, s ∈ {0, 1, 2} and ℓ, s mutually distinct. Denote w Directive bi-sequences containing three or four antimorphisms the corresponding ϑ-palindromic prefixes. Thanks to Corollary 27 and thanks to the fact that the bi-sequence ( ∆, Θ) is normalized, the E t -palindrome Directive bi-sequences containing three or four antimorphisms m )f , where t is different from ℓ, s, is the longest ϑ-palindromic suffix of the word w (n) m+1 f . (We use the equalities: Directive bi-sequences containing three or four antimorphisms m+2 is an E s -palindrome, another shorter ϑ-palindromic suffix of the word w (n) m+1 f has been chosen when constructing w (n) m+2 . This implies that if we extend the E t -palindrome p (n) stepwise by one letter from both sides so that the obtained factor is again an E t -palindrome, we get some E tpalindrome q (n) surrounded by two letters g, h satisfying E t (g) = h. Since L(u) is closed under E t , the factor q (n) is bispecial and the
{'paper_id': '7828221', 'title': 'A ug 2 01 5 On periodicity of generalized pseudostandard words', 's2_url': 'https://api.semanticscholar.org/CorpusID:7828221', 'source': 'S2ORC'}