Alexandre Blondin Massé

Geneviève Paquin
email: gpaquin@cstj.qc.ca

Hugo Tremblay
email: tremblay.hugo.5@courrier.uqam.ca

Laurent Vuillon
email: laurent.vuillon@univ-savoie.fr

On Generalized Pseudostandard Words Over Binary Alphabets

In this paper, we study generalized pseudostandard words over a two-letter alphabet, which extend the classes of standard Sturmian, standard episturmian and pseudostandard words, allowing different involutory antimorphisms instead of the usual 1 palindromic closure or a fixed involutory antimorphism. We first discuss about pseudoperiods, a useful tool for describing words obtained by iterated pseudopalindromic closure. Then, we introduce the concept of normalized directive bi-sequence (Θ, w) of a generalized pseudostandard word, that is the one that exactly describes all the pseudopalindromic prefixes of it. We show that a directive bi-sequence is normalized if and only if its set of factors does not intersect a finite set of forbidden ones. Moreover, we provide a construction to normalize any directive bi-sequence. Next, we present an explicit formula, generalizing the one for the standard episturmian words introduced by Justin, that computes recursively the next prefix of a generalized pseudostandard word in term of the previous one. Finally, we focus on generalized pseudostandard words having complexity 2n, also called Rote words. More precisely, we prove that the normalized bi-sequences describing Rote words are completely characterized by their factors of length 2.

Introduction

The Sturmian words form a well-known class of infinite words over a two-letter alphabet that occurs in many different fields, for instance in astronomy, symbolic dynamics, number theory, discrete geometry, crystallography, and of course, in combinatorics on words (see [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF]Chapter 2]). These words have many equivalent characterizations whose usefulness depends on the context. In discrete geometry, they are exactly the words that code the discrete approximations of lines with irrational slopes, using horizontal and diagonal moves. In symbolic dynamics, Sturmian words are obtained from two-intervals exchange transformations. They are also known as the balanced aperiodic infinite words over a two-letter alphabet. A remarkable subclass of the Sturmian words is the class of the so-called standard Sturmian words. To each Sturmian word corresponds a standard Sturmian one having the same language, i.e., the same set of factors. Thus, standard Sturmian words are, in a sense, representatives of all Sturmian words having the same language. Geometrically, they correspond to discrete lines starting at the origin. All the words in this subclass can be obtained by a construction called iterated palindromic closure [START_REF] De Luca | Sturmian words: structure, combinatorics, and their arithmetics[END_REF]. This operation establishes a bijection between standard Sturmian words and non-eventually constant infinite words over a binary alphabet. It can also be generalized for an alphabet with more than two letters and yields the standard episturmian words.

Another generalization of the standard episturmian words was introduced by de Luca and De Luca in [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF], where the authors considered pseudopalindromes instead of palindromes. In the paper, they first define the notion of ϑ-palindrome (called pseudopalindrome when ϑ is not mentioned), which is a word fixed by an involutory antimorphism ϑ. Moreover, they introduce the pseudopalindromic closure, which extends the usual palindromic closure to pseudopalindromes. These ideas lead one to naturally define words obtained by iterated pseudopalindromic closure. In particular, they consider a generalization of Sturmian and episturmian words: the pseudostandard words. Finally, toward the end of their paper, they define an even more general class of infinite words, called generalized pseudostandard words, these words being obtained by a directive bi-sequence (Θ, w), where Θ is a sequence of involutory antimorphisms and w is an infinite word. In that case, the type of pseudopalin-dromic closure changes at each step, applying the nth involutory antimorphism for the nth pseudopalindromic closure, after having added the nth letter of the word w. Different generalizations of standard episturmian words have been introduced and studied (see for instance [START_REF] Bucci | On different generalizations of episturmian words[END_REF][START_REF] Bucci | On some problems related to palindromic closure[END_REF][START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF]), but not much is known about generalized pseudostandard words except for the remarkable fact that the famous Thue-Morse word falls within this class of words (see [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF]).

In order to study generalized pseudostandard words, it is natural to search for an efficient way to construct it from its directive bi-sequence. In [START_REF] Justin | Episturmian morphisms and a Galois theorem on continued fractions[END_REF], Justin gives a formula that allows one to compute in linear time a prefix of a standard Sturmian (resp., episturmian) word, using its directive sequence, that is the sequence on which the iterated palindromic closure is performed, in order to construct the standard Sturmian (resp., episturmian) word. The main aim of this paper is to extend Justin's formula to generalized pseudostandard words on binary alphabets. In particular, this formula might be useful in the study of generalized pseudostandard word by mean of computer exploration.

The next sections are organized as follows. As usual, we first introduce the definitions and notation used in the next sections. We recall iterated palindromic and pseudopalindromic closure operators as well as the main topic of this paper: the generalized pseudostandard words. Section 3 is devoted to the structure of words having pseudoperiods (i.e. words such that w i = σ(w i + p ) for some permutation σ and some positive integer p). These results turn out to be very useful for studying generalized pseudostandard words. Next, we introduce in Section 4 the notion of normalized directive bi-sequence. Those normalized bi-sequences are representatives of all directive bi-sequences describing the same word, but having the special additional property that the successive prefixes obtained by pseudopalindromic closure coincide with all pseudopalindromic prefixes of the corresponding generalized pseudostandard word. We first prove the existence of such a normalized bi-sequence and we describe exactly the forbidden factors for a bi-sequence not to be normalized. Then we provide a simple way of constructing a normalized bi-sequence from any directive bi-sequence. In Section 5, we present a generalization of Justin's formula for generalized pseudostandard words whose proof depends strongly on the normalized form. Section 6 is devoted to the particular case of Rote words.

Notice that this paper is an complete and improved version of two conference communications. The content of Sections 4 and 5 was presented in Amiens (France) during the 13th Mons Theoretical Computer Science Days [START_REF] Blondin Massé | A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words[END_REF] (JM 2010), while the content of Section 6 was the main subject of a communication during the conference in honor of the 20th Anniversary of the Laboratoire de combinatoire et d'informatique mathmatique [START_REF] Massé | Generalized pseudostandard words having complexity 2n[END_REF] (LaCIM 2010).

Preliminaries

We introduce the definitions and notation in the next sections.

Words

We first recall notions on words (for more details, see for instance [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF]).

An alphabet A is a finite set of symbols called letters. A word over A is a sequence of letters from A. The empty word ε is the empty sequence. Equipped with the concatenation operation, the set A * of finite words over A is a free monoid with neutral element ε and set of generators A, and A + = A * \ ε. We denote by A ω the set of (right-) infinite words over A. The set A ∞ is defined as the set of finite and infinite words: A ∞ = A * ∪ A ω . Note that depending on the context, an infinite word is sometimes also called a sequence. For sake of clarity, variables denoting infinite words appear in bold.

If, for some words u, s ∈ A ∞ , v, p ∈ A * , u = pvs, then v is a factor of u, p is a prefix of u and s is a suffix of u. The set of factors of the word u is denoted by F (u). For u = vw, with v ∈ A * and w ∈ A ∞ , v -1 u denotes the word w and uw -1 denotes the word v. Negative powers are naturally extended by v -n u = (v n ) -1 u and u(w n ) -1 .

As usual, for a finite word u and a positive integer n, the nth power of u, denoted by u n , is the word ε if n = 0; otherwise u n = u n-1 u. If u = ε, u ω denotes the infinite word obtained by infinitely repeating u. Given a finite or an infinite word u, we denote by u i the ith letter of u and by u i . . . j the word u i u i + 1 • • • u j . Given a nonempty finite word u = u 1 u 2 • • • u n , the length |u| of u is the integer n. One has |ε| = 0. The number of occurrences of the letter a in the word u is denoted by |u| a . If |u| a = 0, then u is called an a-free word.

The reversal of the finite word

u = u 1 u 2 • • • u n , also called the mirror image, is R(u)= u n u n -1 • • • u 1 and if u = R(u), then u is called a palindrome.
The rightpalindromic closure (palindromic closure, for short) of the finite word u, denoted by u (+) , is defined by u (+) = u•R(p), with u = ps and s is the longest palindromic suffix of u. In other words, it is the shortest palindromic word having u as prefix.

Over a two-letter alphabet {0, 1}, there is a usual length preserving morphism, the complementation, defined by 0 = 1 and 1 = 0, which extends to words (finite or infinite). For instance, the complement of

u = u 1 u 2 • • • u n is the word u = u 1 u 2 • • • u n .
Sturmian words may be defined in many equivalent ways (see Chapter 2 in [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF] for more details). For instance, they are the non-ultimately periodic infinite words over a two-letter alphabet that have minimal complexity, that is the number of distinct factors of length n is (n + 1), for each positive integer n. They are also the set of non-ultimately periodic binary balanced words. Recall that a word w over A is balanced if for all factors f, f ′ having same length, and for all letters a ∈ A, one has

||f | a -|f ′ | a | ≤ 1.
The Sturmian words are also infinite words that describe discrete approximations of irrational slopes (see [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF]). More precisely, an infinite word is Sturmian if and only if it is equal to one of the two infinite words s α,ρ , s ′ α,ρ ∈ {a, b} ω , defined by

s α,ρ n = a, if ⌊α(n + 1) + ρ⌋ = ⌊αn + ρ⌋; b, otherwise. and s ′ α,ρ n = a, if ⌈α(n + 1) + ρ⌉ = ⌈αn + ρ⌉; b, otherwise,
where α, ρ ∈ R, 0 ≤ α < 1 and α irrational.

The parameters ρ and α correspond respectively to the intercept and the slope of the line approximated by the word s. A Sturmian word is called standard (or characteristic) if ρ = α.

Pseudopalindromic closure

Given a finite word w, let us denote by ψ(w) the word obtained by iterating palindromic closure over w: ψ(ε) = ε and ψ(wa) = (ψ(w)a) (+) , for all letters a.

Note that the ψ operator is sometimes denoted by Pal in the works of Justin and Jamet et al (see for instance [START_REF] Jamet | On the fixed points of the iterated pseudopalindromic closure[END_REF][START_REF] Justin | Episturmian morphisms and a Galois theorem on continued fractions[END_REF]). By definition of iterated palindromic closure ψ, for any finite word w and letter a, ψ(w) is a prefix of ψ(wa). Thus, one can extend the iterated palindromic closure to any infinite word w = (a n ) n≥1 as follows:

ψ(w) = lim n→∞ ψ(a 1 . . . n ).
We say that the word w directs the word ψ(w). Also, we know from [START_REF] De Luca | Sturmian words: structure, combinatorics, and their arithmetics[END_REF] that ψ gives a bijection between the set of infinite words over {a, b} not of the form ua ω or ub ω , for some u ∈ {a, b} * , and the set of standard Sturmian words over {a, b}. The word w is then called the directive sequence of the standard Sturmian word ψ(w). Note that words of the form ψ(ua ω ) are periodic (see [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF]).

The ψ operator is also well-defined over a k-letter alphabet, with k ≥ 3. In this case, it is known [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF] that ψ(A ω ) is exactly the set of standard episturmian words, a generalization over a k-letter alphabet, k ≥ 3, of the family of standard Sturmian words (for more details, see [START_REF] Glen | Episturmian words: a survey[END_REF]).

Example 1. The infinite Fibonacci word

f = ψ((01) ω ) = 0 1001010010010100101 • • •
is a standard Sturmian word directed by the word (01) ω . Indeed:

ψ(0) = 0 ψ(010) = (ψ(01)0) (+) = 010010 ψ(01) = (ψ(0)1) (+) = 010 ψ(0101) = (ψ(010)1) (+) = 01001010010 . . . . . .
Notice that in the previous example, all the images are palindromes.

Example 2. The infinite word 01201002 • • • directs the standard episturmian word

w = ψ(01201002 • • • ) = 0 102010010201010201001020100 • • • .
As usual, we have underlined in the previous examples the letters of w corresponding to the directive words, for sake of clarity.

When generating words by iterated palindromic closure, it is useful to have an efficient way to compute the successive prefixes. In that perspective, it is too costly to compute the longest palindromic suffix every time a letter is added in the directive sequence. The key of this problem is found in a formula introduced by Justin [START_REF] Justin | Episturmian morphisms and a Galois theorem on continued fractions[END_REF]. Proposition 3. [START_REF] Justin | Episturmian morphisms and a Galois theorem on continued fractions[END_REF] Let w ∈ A * , a ∈ A. If w is not a-free, then we write w = v 1 av 2 with v 2 a-free and we have ψ(wa) = ψ(w)aψ(w), if w is a-free; ψ(w)ψ(v 1 ) -1 ψ(w), otherwise.

Algorithm 1 Computation of a word by iterated palindromic closure.

1: function IteratedPalindromicClosure(w)

2:

Input: Any word w 3:

Output: The iterated palindromic closure ψ(w) of w end for 17: end function Proposition 3 yields directly Algorithm 1. In the next sections, we generalize it to the so-called pseudopalindromes over binary alphabets, where the situation is more complicated, since there are two possible kinds of closure. A few years ago, de Luca and De Luca [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF] extended the notion of palindrome to what they call pseudopalindrome, using involutory antimorphisms. In order to define it, let us first recall that a map ϑ : A * → A * is called an antimorphism of A * if for all u, v ∈ A * one has ϑ(uv) = ϑ(v)ϑ(u). Moreover, an antimorphism is involutory if ϑ 2 = Id. Any antimorphism ϑ of A * can be constructed as ϑ = σ • R = R • σ, with σ a permutation of the alphabet A. We denote by σ ϑ the permutation associated with the antimorphism ϑ. Over a two-letter alphabet {a, b}, there are only two involutory permutations of letters σ R = (a)(b) and σ E = (ab), yielding the two antimorphisms R, the reversal antimorphism, and E, defined as E = σ E • R. The antimorphism E will be called, as usual, the exchange antimorphism.

We can now define the generalization of palindromes given in [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF]: a word w ∈ A * is called a ϑ-palindrome if it is the fixed point of the involutory antimorphism ϑ of the free monoid A * : ϑ(w) = w. When the antimorphism ϑ is not mentioned, w is called a pseudopalindrome. Notice that the R-palindromes are exactly the usual palindromes.

By analogy to the palindromic closure (+) , the ϑ-palindromic closure of the finite word u, also called the pseudopalindromic closure when the antimorphism is not specified, is defined by u ⊕ ϑ = sqϑ(s), where u = sq, with q the longest ϑ-palindromic suffix of u. The ϑpalindromic closure of u is the shortest ϑ-palindrome having u as prefix.

Example 4. Over the alphabet {0, 1}, since the longest E-palindromic suffix of w = 0010 is 10, w ⊕ E = 0010 • E(00) = 001011.

Notice that in the previous example, we have that 001011 is an E-palindrome, also called an antipalindrome, since E(001011) = R(001011) = R(110100) = 001011.

Extending the ψ operator to ϑ-palindromes, the ψ ϑ operator is naturally defined by ψ ϑ (ε) = ε and ψ ϑ (wa) = (ψ ϑ (w)a) ⊕ ϑ , for w ∈ A * and a ∈ A. Then, for w ∈ A ω , ψ ϑ (w) = lim n→∞ ψ ϑ (w 1 . . . n ). This limit exists since by the definition of ψ ϑ , for any involutory antimorphism ϑ, w ∈ A * and a ∈ A, ψ ϑ (w) is a prefix of ψ ϑ (wa). The infinite word obtained by the ψ ϑ operator is a ϑ-standard word, also called a pseudostandard word when the antimorphism is not specified. This new class of words is a general one that includes the standard Sturmian and the standard episturmian ones and was first introduced in [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF].

Example 5. Over A = {0, 1}:

ψ e (001) = ((ψ e (0)0) ⊕ E 1) ⊕ E = ((01 • 0) ⊕ E 1) ⊕ E = (0101 • 1) ⊕ E = 0101100101.

Generalized pseudostandard words

In [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF], the authors introduce the pseudostandard words as well as a new class of words, extending the pseudostandard words to a larger class of words: the generalized pseudostandard words. It consists mainly in allowing different types of pseudopalindromic closure while constructing the word from its directive sequence.

More formally, let I be the set of all involutory antimorphisms of A * , and I ω be the set of infinite sequences over I. Let Θ = ϑ 1 ϑ 2 ϑ 3 . . . ∈ I ω and let ⊕ i be the ϑ i -palindromic closure operator, for all i ≥ 1. We define inductively an operator ψ Θ by setting ψ Θ (ε) = ε, and

ψ Θ (w 1 . . . n + 1 ) = (ψ Θ (w 1 . . . n )w n + 1 ) ⊕ n+1 whenever w i ∈ A for i ≥ 1. If w = w 1 w 2 • • • w n • • • ∈ A ω , w i ∈ A for i ≥ 1, then ψ Θ (w 1 . . . i
) is a prefix of ψ Θ (w 1 . . . i + 1 ) for any i, so that the infinite word

ψ Θ (w) = lim n→∞ ψ Θ (w 1 . . . n )
is well-defined. We call ψ Θ (w) a generalized pseudostandard word and the pair (Θ, w) is called the directive bi-sequence of ψ Θ (w).

When we consider a finite word w and a finite sequence of involutory antimorphisms Θ, both of length |w|, we call the word ψ Θ (w) a prefix of a generalized pseudostandard word and the length of its directive bi-sequence is |w|.

Notice that one can set Θ = R ω (resp., Θ = ϑ ω ) in order to obtain standard episturmian (resp., ϑ-standard) words.

For the remainder of that paper, we fix A = {0, 1} so that the only two involutory antimorphisms are the reversal R and the exchange antimorphism E.

Moreover, we write R = E and E = R.

Example 6. Let w = 0100 and Θ = RERR. Then ψ Θ (w) = 01 . 0 010.

Note that in the previous example, we have underlined (resp., under-dotted) the letter in the generalized pseudostandard word ψ Θ (w) where a R-closure (resp., E-closure) is performed.

A remarkable property of this class of words is that it contains the well-known Thue-Morse word T as shown in [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF], whose construction by iterated pseudopalindromic closure coincides with the one consisting of concatenating the successive prefixes with their complement. More precisely: Theorem 7. [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF] The Thue-Morse word is described by ψ (ER) ω (01 ω ).

Pseudoperiodicity

In the conference version of this extended article [START_REF] Blondin Massé | A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words[END_REF], we introduced the notion of pseudoperiod. We also provided a theorem in the spirit of Fine and Wilf for binary alphabets that was generalized to arbitrary alphabets in [START_REF] Blondin Massé | Pseudoperiodic words[END_REF]. We briefly discuss here this concept and provide lemmas (17, 18 and 19) that turn out to be essential in the next section to describe the structure of words obtained by iterated pseudopalindromic closure.

First, we recall the definition of pseudoperiod from [START_REF] Blondin Massé | A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words[END_REF].

Definition 9. [2]
Let w be a finite word and σ be a permutation of the alphabet. We say that the positive integer p is a σ-period of w if for each integer i such that 1 ≤ i ≤ |w| -p, we have w i = σ(w i + p ).

Example 10. Let σ R = (0) [START_REF] Blondin Massé | Pseudoperiodic words[END_REF] and σ E = (01). Then the word 011011 has the σ R -period 3 and the σ E -period 5, since 011011 = 011 • σ R (011) and 011011 = 01101

• σ E (0).
As we can see in the previous example, the σ R -periods are the usual periods on words. Finally, the reader verifies easily that if p is a σ-period of a word w, then ord(σ)p is a period of w, where ord(σ) is the order of the permutation σ, i.e. the smallest number k such that σ k is the identity.

It shall be mentioned that the word pseudoperiod is also used in [START_REF] Czeizler | An extension of the Lyndon Schützenberger result to pseudoperiodic words[END_REF][START_REF] Manea | Fine and Wilf's theorem and pseudo-repetitions[END_REF], but its meaning is not equivalent to Definition 9. More precisely, the authors say from a positive integer p that it is a σ-period of a word w if w may be written as an arbitrary product of elements in {u, σ(u)}, where u is a word of length p. For instance, the number 2 is a σ-period of the word w = 12323212 for σ : 1 → 3, 2 → 2, 3 → 1, since w = uσ(u)σ(u)u, for u = 12. On the other hand, Definition 9 imposes an alternance of the word with its complement and applies even if p does not divide |w|. Moreover, in the case of a binary alphabet, for every word w, 1 is trivially a σ E -period of w when considering the definition of pseudoperiod of [START_REF] Czeizler | An extension of the Lyndon Schützenberger result to pseudoperiodic words[END_REF].

It is known that overlapping palindromes yield periodicity (see for instance [START_REF] De Luca | Sturmian words: structure, combinatorics, and their arithmetics[END_REF]). These periodic properties may be generalized naturally to overlapping pseudopalindromes. The following lemma shows that pseudoperiodic pseudopalindromes may be extended into longer ones or broken into smaller ones.

Lemma 11. Let w be a ϑ-palindrome and p be a σ-period of w, where σ is an involutory permutation and p < |w|, u is the suffix of w of length p. Moreover, let i = ⌊|w|/p⌋. Then (i) w(σ(u)u) j is a ϑ-palindrome for all integers j ≥ -⌊i/2⌋;

(ii) wσ(u)(uσ(u)) j is a (ϑ • σ)-palindrome for all integers j ≥ -⌊i/2⌋.

Proof. (i) Since p is a σ-period of w, there exist a word x, a nonempty word y and a positive integer k such that |xy| = p and w ∈ {(xyσ(xy)) k x, (xyσ(xy)) k xyσ(x)}. We first consider the case w = (xyσ(xy)) k x. In particular, k = ⌊i/2⌋ and u = σ(y)x. Moreover, since w is a ϑ-palindrome, we deduce that x = ϑ(x) and y = (ϑ • σ)(y). Let j ≥ -⌊i/2⌋ be an integer. Then w(σ(u)u) j = (xyσ(xy)) k+j x, which is indeed a ϑ-palindrome, since x = ϑ(x) and y = (ϑ • σ)(y). The case w = (xyσ(xy)) k xyσ(x) is verified similarly, as well as (ii).

Roughly speaking, Lemma 11 states that if a given ϑ-palindrome is σ-periodic and sufficiently long, then one can construct a sequence of alternating ϑ-palindromes and (ϑ • σ)palindromes by erasing the repetitions or by extending the period.

Example 12. Let σ = σ E , ϑ = R and w = 001011101000101110100. Then 5 is an σ Eperiod of w and w is an R-palindrome. Also, Lemma 11 applies, so that w(10100) -1 = 0010111010001011 and w(0101110100) -1 (10100) -1 = 001011 are E-palindromes. On the other hand, the words w(0101110100) -1 = 00101110100 and w(0101110100) -2 = 0 are Rpalindromes.

In [START_REF] Blondin Massé | Pseudoperiodic words[END_REF], the authors generalized Fine and Wilf's Theorem for pseudoperiodic words.

Theorem 13.

[1] Let p, q be two positive integers and σ 1 , σ 2 two permutations such that σ 1 and σ -1 2 commute. Then any word w of length at least p + q admitting p as a σ 1 -period and q as a σ 2 -period also admits gcd(p, q) as a σ-period, where σ = σ x 1 σ -y 2 and x, y are any integers such that gcd(p, q) = xp -yq.

It is worth mentioning that Theorem 13 holds even if σ 1 and σ 2 are not involutory. The binary case is proved in [START_REF] Blondin Massé | A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words[END_REF]. It also directly follows from Theorem 13: Theorem 14. [START_REF] Blondin Massé | A Fine and Wilf's theorem for pseudoperiods and Justin's formula for generalized pseudostandard words[END_REF] Let p, q be two positive integers and σ 1 , σ 2 two permutations on a binary alphabet A. Then any word w of length at least p + q admitting p as a σ 1 -period and q as a σ 2 -period also admits gcd(p, q) as a σ-period, where

σ = σ R , if σ 1 = σ 2 = σ R ; σ E , otherwise.
Proof. On binary alphabet, the permutations σ R and σ -1 E = σ E commute. Moreover, any pair of integers verifying gcd(p, q) = xp-yq, also called Bezout coefficients, may be chosen so that one is even and the other is odd. If σ 1 = σ 2 = σ R , then σ = σ R and the theorem follows. Otherwise, since x and y have different parity, then σ x 1 σ -y 2 = σ E = σ, which concludes the proof.

Example 15. The word w = 01010101 admits the σ R -period 4 and the σ E -period 3. By Theorem 14, gcd(4, 3) = 1 is also an σ E -period of w.

Remark 16. The bound |w| ≥ p + q in Theorem 14 is tight, as illustrated by the following example. Let p be any positive integer and q = p + 1. Moreover, let w = 0 p 1 p . Then w has the σ E -periods p and q. On the other hand, 1 = gcd(p, q) is not an σ E -period of w and |w| = 2p < 2p + 1 = p + q. Actually, one may show that there is no word of length 2p + 1 admitting the σ E -periods p and q.

We conclude this section with three lemmas about local periodicity in words. The first lemma holds for any alphabet.

Lemma 17. Let u be a finite word over an arbitrary alphabet, p be a ϑ 1 -palindrome and q be a ϑ 2 -palindrome for some involutory antimorphisms ϑ 1 ,ϑ 2 , such that pu = q. Then q has the (σ ϑ 2 • σ ϑ 1 )-period |u|.

Proof. Let i be an integer satisfying 1 ≤ i ≤ |p|. Since p is a prefix of q and since p is a ϑ 1 -palindrome, one has q i = σ ϑ 1 (q |p| + 1 -i ). But q is a ϑ 2 -palindrome, which implies that

q i = σ ϑ 1 (q |p| + 1 -i ) = (σ ϑ 2 • σ ϑ 1 )(q |q| + 1 -|p| -1 + i ) = (σ ϑ 2 • σ ϑ 1 )(q |q| -|p| + i ) = (σ ϑ 2 • σ ϑ 1 )(q i + |u| ),
and the result follows.

Not any pseudoperiod may exist in a given word.

Lemma 18. Let w be a finite binary word, p a σ 1 -period of w and q a σ 2 -period of w, where σ 1 , σ 2 ∈ {σ R , σ E }. Assume that |w| > p > q and p = mq for some integer m ≥ 2. Then one of the two following conditions holds:

(i) σ 1 is the identity and m is even;

(ii) σ 1 = σ 2 and m is odd.

Proof. Let i be an integer such that 1 ≤ i ≤ |w| -p. Note that σ 1 and σ 2 commute since the alphabet is binary. Therefore,

σ R (w i ) = w i = σ 1 (w i + p ) = σ 1 (w i + mq ) = (σ m 2 • σ 1 )(w i ), so that σ R = σ m 2 • σ 1 . As a consequence, if m is even, then σ 1 = σ R , and if m is odd, then σ R = σ 1 • σ 2 , which implies σ 1 = σ 2 .
It is worth mentioning that Lemma 18 holds for arbitrary alphabets whenever all letters occur in the prefix of length |w| -p of w, i.e. whenever we have σ R (a) = (σ m ϑ 2 • σ ϑ 1 )(a) for all letters a.

The last lemma is a simple extension of Lemma 8.1.3 of [START_REF] Lothaire | Encyclopedia of Mathematics and its Applications[END_REF] giving condition for a local period to propagate to the whole word. As for Lemma 18, it could be extended to arbitrary alphabets provided that all letters occur in some prefix of w, but since this paper is devoted to binary alphabets, for sake of simplicity, we only present this case.

Lemma 19. Let w be a finite binary word and v be a factor of w. Assume that p is a σ 1 -period of w such that |v| > p and q is a σ 2 -period of v such that q divides p, where σ 1 , σ 2 ∈ {σ R , σ E }. Then q is a σ 2 -period of w.

Proof. First consider the case q = p. Then p = q is both a σ 1 -period and a σ 2 -period of v and |v| > p. This means that σ 1 = σ 2 and the lemma follows. For the rest of the proof, we may suppose q < p and p = qm for some positive integer m ≥ 2.

Let k be an integer, 1

≤ k ≤ |w|, such that v = w k w k + 1 • • • w k + |v| -1 . Let V = {k, k + 1, . . . , k + |v| -1}
be the set of indices of v in w. Moreover, let i be an integer such that 1 ≤ i ≤ |w| -q. Since |v| > p, there exists an integer i ′ ∈ V such that i ′ ≡ i mod p. Therefore, since p is a σ 1 -period of w, we have w i ′ = σ |ℓ| 1 (w i ), where ℓ is the integer satisfying i ′ -i = pℓ. Since σ 1 is involutory, we have w i = σ |ℓ| 1 (w i ′ ) as well. Let j = i + q. Using a similar argument as above, we find that there exists at least one integer j ′ ∈ V such that j ′ ≡ j mod p. In particular, we may choose j ′ so that j ′ ∈ {i ′ + q, i ′ + q -p}. Indeed, we have i ′ + q ≡ i ′ + q -p ≡ i + q mod p and at least one value among i ′ + q and i ′ + q -p must fall in V (since |v| > p and i ′ ∈ V ). Thus, we may write j ′ -j = pℓ ′ , for some integer ℓ ′ ∈ {ℓ -1, ℓ}, so that w j ′ = σ |ℓ ′ | 1 (w j ). We distinguish two cases. Assume first that ℓ ′ = ℓ so that j ′ = i ′ + q. Since q is a σ 2 -period of v, we have w i ′ = σ 2 (w j ′ ). Then w j = (σ

|2ℓ| 1 •σ 2 )(w i ) = σ 2 (w i ). On the other hand, suppose that ℓ ′ = ℓ -1 so that j ′ = i ′ + q -p. Recall that p = qm. Then j ′ = i ′ + (1 -m)q so that w i ′ = σ |1-m| 2 (w j ′ ). This implies w j = (σ |2ℓ-1| 1 • σ |1-m| 2 )(w i ) = (σ 1 • σ |1-m| 2 )(w i ).
We know from Lemma 18 that either σ 1 = R and m is even or σ 1 = σ 2 and m is odd. Both cases imply w j = σ 2 (w i ). Hence, we have shown that w i + q = σ 2 (w i ) for any integer i such that 1 ≤ i ≤ |v| -q, i.e. q is a σ 2 -period of w.

Normalized form

Words obtained by iterated palindromic closure are the limit of a sequence of palindromes that are prefixes of each other. The idea is the same when considering iterated pseudopalindromic closure. A first trivial and useful observation is the following.

Lemma 20. Let u = ψ(w) = ψ R ω (w) be a word on an arbitrary alphabet. The word v is a palindromic prefix of u if and only if there exists a nonnegative integer n such that v = ψ R n (w 1 . . . n ).

Proof. (⇒) By contradiction, assume that such a word v exists. Let n be the integer such that Roughly speaking, Lemma 20 states that no palindromic prefix is missed by the iterated palindromic closure. In the following, Lemma 20 is used several times without being referenced. This fact also holds for any ϑ-standard word (see Proposition 4.1, [START_REF] De Luca | Pseudopalindrome closure operators in free monoids[END_REF]), i.e. no ϑ-palindromic prefix is missed by the iterated ϑ-palindromic closure. However, this is not the case if different pseudopalindromic closures are allowed. For instance, the word w = ψ RERE (0011) = 00 . 111001 . 100011 misses the palindrome 00 while the word u = ψ RRE (011) = 0 101 . misses the E-palindrome 01. On the other hand, w = ψ RRERE (00111) and u = ψ RERE (0101), i.e. it is possible to rewrite the directive bi-sequences of w and u so that they do not miss any pseudopalindromic prefixes. As we will see (and prove) in the sequel, it is always possible to rewrite any directive bi-sequence of a generalized pseudostandard word in a "normalized" form. Definition 21. A finite or infinite directive bi-sequence (Θ, w) is called normalized if it verifies the following condition: v is a pseudopalindromic prefix of ψ Θ (w) if and only if there exists a non negative integer n such that v = ψ Θ 1..n (w 1..n ). A pseudopalindromic prefix v that does not satisfy the previous condition is called a missed pseudopalindrome and the we say that (Θ, w) misses v.

|ψ R n-1 (w 1 . . . n -1 )| < |v| < |ψ R n (w 1 . . . n )|. Then ψ R n (w 1 . . . n ) is not the shortest palindromic suffix having ψ R n-1 (w 1 . . . n-1 )
The length of any missed pseudopalindrome is constrained. The next results only apply to binary alphabets. First, the following fact is easily observed.

Lemma 23. The shortest prefixes of a normalized directive bi-sequence containing exactly two different letters are of the form: (R i+1 , a i a) for i ≥ 2, or (R i E, a i a) for i ≥ 1 and a ∈ {0, 1}.

Proof. By direct inspection. One notices in particular that no normalized bi-sequence starts with the antimorphism E.

Generalized pseudostandard words have periods to different scale. In particular, if a bisequence is not normalized, we can extract useful information about the antimorphisms and the letters involved.

Lemma 24. Let (Θ, w) be a finite normalized directive bi-sequence of length n ≥ 1 of a prefix of a generalized pseudostandard binary word. Suppose that (Θτ, wa) is not normalized, where τ ∈ {R, E} and a ∈ A. Let u = ψ Θ (w), v = ψ Θτ (wa) and t be a pseudopalindromic prefix missed by (Θτ, wa). Finally, let p = |v| -|u|, q = |v| -|t| and g = gcd(p, q). Then exactly one of the following conditions hold.

(i) g is an σ E -period of v, p = 2g, q = g and ϑ n = τ , where ϑ n is the last antimorphism of Θ;

(ii) (Θτ, wa) = (R n E, a n+1 ); Proof. The situation is depicted in Figure 1. Notice that t is a τ -palindrome, otherwise v would not be the shortest τ -palindrome having ua as a prefix. Moreover, it follows from Lemma 17 that p is a (σ ϑn •σ τ )-period of v, since v is a τ -palindrome and u is a ϑ n -palindrome, where, ϑ n is the last antimorphism of Θ. Similarly, q is a (σ τ • σ τ )-period (i.e. an σ E -period) of v.

First, suppose that |v| ≥ p + q. Then Theorem 14 applies so that v has the σ E -period g = gcd(p, q). By Lemma 11, we conclude that the prefix y of v of length |v| -2g is a τ -palindrome. Since no τ -palindrome occurs between u and v (otherwise v would not be the shortest τ -palindrome having ua as a prefix), we must have |y| ≤ |u|, i.e. p = |v| -|u| ≤ 2g. Since 0 < q < p ≤ 2g and g divides both p and q, we have p, q ∈ {g, 2g}. But q < p, so that q = g and p = 2g. In particular, u = y is a τ -palindrome and we are in case (i).

It remains to consider the case |v| < p+q. Notice that, by definition of pseudopalindromic closure, one has |v| ≤ 2|u| + 2, with |v| = 2|u| + 2 only if v is an E-palindrome. We first show that |v| = 2|u| + 2. Arguing by contradiction, suppose that |v| ≤ 2|u| + 1. Then

|v| < p + q = |v| -|u| + |v| -|t| ≤ 2|u| + 1 -|t| + |v| -|u| = |u| + 1 -|t| + |v| ≤ |u| + 1 -|u| -1 + |v| (1) = |v|,
which is absurd. Note that Inequality (1) follows from the inequality |t| ≥ |u| + 1. Hence, |v| = 2|u| + 2. This implies that τ = E and t is a R-palindrome (since τ = R).

Next, suppose that |t| ≥ |u| + 2. Then q ≤ |u|. Since u is a ϑ n -palindrome and q is a σ E -period of u, Lemma 11 implies that the prefix of v of length |u| + q is a σ ϑn -palindrome. Therefore, σ ϑn = τ , otherwise, v would not be of minimum length, which implies ϑ n = τ and then ϑ n = R. As a consequence, p -q is a σ E -period of t. Moreover, we know that q is a σ E -period of t as well since it is a period of v. We can apply Theorem 14 to t since q + (p -q) = p = |u| + 2 ≤ |t|, so that gcd(q, p -q) = gcd(q, p) = g is a σ E -period of t which propagates to v, by Lemma 19. Once again by Lemma 11, we conclude that the prefix of v of length |u| + 2g is a ϑ n -palindrome, i.e. a τ -palindrome. This implies |u| + 2g ≥ |v| = 2|u| + 2, so that 2g ≥ |u| + 2 = p. Since g divides both p and q and since q < p, this means that q = g and p = 2g, which corresponds also to case (i).

Finally, assume that |t| = |u| + 1. There are two cases to consider. If ϑ n = R, then Lemma 17 implies that 1 is a σ R -period of t, so that t = a n+1 , u = a n , v = a n+1 a n+1 and (Θτ, wa) = (R n E, a n+1 ), which yields case (ii). Otherwise, again by Lemma 17, ϑ n = E and 1 is a σ E -period of t. Since t is an R-palindrome, we must have t = (aa) k a for some positive integer k. But every prefix of t is either an R-palindrome or an E-palindrome and (Θ, w) is normalized: Therefore, |u| = n which implies u = (aa) n/2 , t = (aa) n/2 a and v = (aa) n/2+1 . But n + 2 = |v| = 2|u| + 2 = 2n + 2, so that n = 0, a contradiction.

There are forbidden patterns that necessarily lead to non normalized bi-sequences.

Lemma 25. Let Θ be a sequence of involutory antimorphisms, ϑ ∈ {R, E}, w ∈ A * and a, b ∈ A, where A is a binary alphabet. Suppose that (Θϑϑ, wab) is normalized. Also, let u = ψ Θϑ (wa), v = ψ Θϑϑ (wab), p = |v| -|u| and s be the suffix of length p of v. Then (i) p is the minimum σ E -period of v;

(ii) ψ Θϑϑϑ (uabb) = vs;

(iii) ψ Θϑϑϑ (uabb) = vss;

(iv) (Θϑϑϑ, uabb) is not normalized, (Θϑϑϑϑ, uabbb) is normalized and both bi-sequences generate the same word.

Proof. (i) It follows from Lemma 17 that p is a σ E -period of v since σ ϑ • σ ϑ = σ E . It remains to show that p is minimal. By contradiction, assume that there exists a σ E -period p ′ < p. Let s ′ be the word of length p ′ such that us ′ is a prefix of v. By Lemma 11, us ′ is a ϑpalindrome and, by construction of v, b is the first letter of s ′ , contradicting the fact that v is the shortest ϑ-palindrome having ub as a prefix.

(ii) Since v is a ϑ-palindrome having p as a σ E -period, it follows from Lemma 11 that vs is a ϑ-palindrome. Now, assume that vs is not the shortest ϑ-palindrome having vb as a prefix. Let x be the longest ϑ-palindrome suffix of v. Then |x| > |v| -p and, by Lemma 17, v has the σ E -period |v| -|x| < p, contradicting the minimality of p.

(iii) It suffices to apply the same reasoning as in part (ii).

(iv) Parts (ii) and (iii) implies that (Θϑϑϑ, uabb) is not normalized since it misses the pseudopalindrome vs. Moreover, (Θϑϑϑϑ, uabbb) is normalized since it does not verify any of the conditions of Lemma 24. Finally, applying twice part (ii) and once part (iii) shows that both bi-sequence generate the same word.

Let (Θ, w) be an infinite (resp., a finite) directive bi-sequence of a (resp., prefix of a) generalized pseudostandard word. The concept of factor is naturally extended to bi-sequences. More precisely, (ϑ i • • • ϑ i+k , w i . . . i + k ) is called a factor of (Θ, w) for any integers i, k ≥ 1.

We are now ready to describe the forbidden factors and prefixes of normalized bisequences.

Proposition 26. A finite directive bi-sequence s on a binary alphabet is normalized if and only if it does not have a prefix of one of the following forms: that p = 2g and q = g, where g = gcd(p, q). Also,

(i) (RR, aa), (ii) (R i-1 E, a i ), (iii) (R i EE, a i
ϑ n-1 = ϑ n .
where a, b ∈ {0, 1}, i ≥ 1 is an integer and (Θ, w) is a finite directive bi-sequence.

Proof. (⇒) We prove the contrapositive, i.e. we suppose that the prefix of the directive bi-sequence is of one of these four forms and prove that it is not normalized. Clearly, (i) ψ RR (aa) = aaa misses the E-palindromic prefix aa, (ii) ψ R i-1 E (a i ) = a i a i misses the palindromic prefix a i and (iii) ψ R i EE (a i a a) = a i a i+1 a i+1 a i misses the palindromic prefix a i a i+1 a i . Case (iv) follows directly from Lemma 25.

(⇐) We prove the contrapositive, i.e. we suppose that s is not normalized. If |s| ≤ 2, then inspection shows that the only possible non-normalized directive bi-sequences fall in case (i) or (ii). Now, assume that |s| ≥ 3. Let (Θ, w) be the shortest non-normalized prefix of s and n = |w|. Let

u = ψ ϑ 1 ϑ 2 •••ϑ n-1 (w 1 w 2 • • • w n -1 ), v = ψ Θ (w)
and t be a ϑ n -palindrome missed by (Θ, w) (see Figure 2). Moreover, let p = |v| -|u|, q = |v| -|t| and g = gcd(p, q). By Lemma 24, either we are in case (ii) or (iv), or (Θ, w) ends with a factor in {(RRR, abc), (EEE, abc), (ERR, abc), (REE, abc)}, where a, b, c are letters. On the other hand, Lemma 24 implies that |v| ≥ p + q, g is an σ E -period of v, p = 2g, q = g and u is a ϑ n -palindrome, i.e. ϑ n-1 = ϑ n . Let y be the prefix of lenght n -2 of ψ Θ (w), that is

y = ψ ϑ 1 ϑ 2 •••ϑ n-2 (w 1 w 2 • • • w n -2 ).
Notice that |u| -|y| ≤ g. Otherwise, there would exist a ϑ n -palindromic prefix between y and u, namely the suffix of v of length |v| -3g by Lemma 11, contradicting the fact that (ϑ

1 ϑ 2 • • • ϑ n-1 , w 1 w 2 • • • w n -1 ) is normalized. Let g ′ = |u| -|y|. If g ′ = g, then ϑ n-2 = ϑ n
and c = b, i.e. s ends with (ERR, abb) or (REE, abb). By Lemma 25, we know that s is not normalized, and this corresponds to case (iv). It remains to consider the case g ′ < g. We show in the next paragraphs that this implies case (iii).

First, we show that |y| < g. Proceeding by contradiction, assume that |y| ≥ g. This implies |u| ≥ g + g ′ . Since g is an σ E -period of v and in particular an σ E -period of u and, by Lemma 17, g ′ is a (σ ϑ n-2 • σ ϑn )-period of u, it follows from Theorem 14 that g ′′ = gcd(g, g ′ ) is an σ E -period of u. Moreover, that σ E -period g ′′ propagates to the whole word v in virtue of Lemma 19 applies, yielding a contradiction: this would imply that there is a ϑ n -palindrome between the ϑ n -palindromes u and v, namely the prefix of v of length |v| -2g ′′ (by Lemma 11). But g ′′ < g (since g ′ < g). Hence, the claim |y| < g is proved.

Now, we prove that |v| = 4g - Finally, notice that, since |v| ≥ p + q = 3g, the prefix z of v of length |v| -3g is a ϑ n -palindrome, i.e. an R-palindrome, by Lemma 11. But Lemma 17 implies that |y| -|z| = g -g ′ = 1 is an (σ ϑ n-2 • σ R )-period of y, i.e. an σ ϑ n-2 -period of y. If ϑ n-2 = R and since y has length g -1, contains the letter b and

ϑ 1 = R, we find y = b g-1 , so that u = b g-1 b g-1 and v = b g-1 b g b g b g-1
, which corresponds to case (iii). It only remains to consider the case ϑ n-2 = E. Then y = (dd) (g-1)/2 for some letter d, since 1 is a σ E -period of y and |y| = g -

But ϑ n = ϑ n-1 = E and (ϑ 1 ϑ 2 • • • ϑ n-1 , w 1 w 2 • • • w n -1
) is normalized, which implies that w n -1 = d (otherwise the palindrome (dd) (g-1)/2 d would be missed). Therefore, u = (dd) (g-1)/2 (dd) (g-1)/2 . Finally, notice that the condition |v| = 2|u| + 2 implies that the longest σ E -palindromic suffix of uw n = ε. This is impossible since dd is a σ E -palindromic suffix of ud and dd(dd) (g-1)/2-1 dd is a σ E -palindromic suffix of ud.

The following theorem explains how to replace the forbidden factors in order to normalize a directive bi-sequence.

Theorem 27. Let (Θ, w) be a directive bi-sequence, with Θ a finite or infinite sequence of involutory antimorphisms and w a binary word having same length as Θ. Then there exists a normalized directive bi-sequence (Θ ′ , w ′ ) such that ψ Θ (w) = ψ Θ ′ (w ′ ). Moreover, in order to get the normalized directive bi-sequence (Θ ′ , w ′ ) from (Θ, w), it is sufficient to replace the prefix (if it is of one of the following forms):

(i) (RR, aa) by (RER, aaa);

(ii) (R i-1 E, a i ) by (R i E, a i a);
(iii) (R i EE, a i a a) by (R i ERE, a i a aa); for i ≥ 1 and then, to replace from left to right any factor (iv) (ϑϑϑ, abb) by (ϑϑϑϑ, abbb), where ϑ ∈ {R, E} and a, b ∈ {0, 1}.

Proof. Proposition 26 indicates precisely which prefixes and factors cannot occur in a normalized directive bi-sequence, while Lemma 25 tells us how to replace any factor of the form (ϑϑϑ, abb) in order to normalize the directive bi-sequence. It remains to prove how to correct the non-normalized prefixes of the form (i), (ii) and (iii). By Proposition 26, we know that the prefixes (RER, aaa), (R i E, a i a) and (R i ERE, a i a aa) are normalized, since they are not in the set of forbidden prefixes and factors. In order to conclude the proof, we let the reader verify that ψ RR (aa

) = ψ RER (aaa), ψ R i-1 E (a i ) = ψ R i E (a i a) and ψ R i EE (a i a a) = ψ R i ERE (a i a aa).
Example 28. Let us normalize the directive bi-sequence d = (RRR, 011). Since it has a prefix of the form (i) in Theorem 27, we rewrite d as d ′ = (RER • R, 010 • 1), with (RER, 010) normalized. The second step is to replace all the factors of the form (ϑϑϑ, abb) by (ϑϑϑϑ, abbb). There is only one factor of this form: (ERR, 101). We then obtain the new directive bi-sequence d ′′ = (RERER, 01010), which is normalized. Indeed, one can verify that d ′′ does not contain any forbidden prefix or factor. Finally, d and d ′′ direct the same generalized pseudostandard word: ψ RRR (011) = 0 1010 and ψ RERER (01010) = 01 . 01 . 0.

A generalization of Justin's formula

The previous section gives us the main tool to prove Theorem 29, that is the existence of the normalization of a directive bi-sequence: Given a generalized pseudostandard word, it is always possible to find a directive bi-sequence that describes all its pseudopalindromic prefixes.

As pointed out in previous sections, the naive way to compute ψ ΘR (wa) (resp., ψ ΘE (wa)) when ψ Θ (w) is known, is to find the longest palindromic (resp., E-palindromic) suffix p of ψ Θ (w) preceded by a. Then ψ ΘR (wa) = ψ Θ (w)p -1 ψ Θ (w) (resp., ψ ΘE (wa) = ψ Θ (w)p -1 ψ Θ (w)). However, this turns out to be very costly since at each step, one must find the longest pseudopalindromic suffix of words that grow more and more in size. We are now ready to state and prove one of the main theorem of this paper, thus providing an efficient way to compute binary generalized pseudostandard words.

Theorem 29. Let (Θ, w) be a normalized finite directive bi-sequence of length n on a binary alphabet and, for i = 1, 2, . . . , n, let

ψ i = ψ ϑ 1 ϑ 2 •••ϑ i (w 1 . . . i ), ψ 0 = ε and α i be the last letter of ψ i for 1 ≤ i ≤ n. (i) If |w 1 w 2 • • • w n -1 | w n = 0 or |ϑ 1 ϑ 2 • • • ϑ n-1 | ϑn = 0, then ψ n =      ψ n-1 w n ψ n-1 , if ϑ n = R; ψ n-1 ψ n-1 , if ϑ n = E and α n-1 = w n ; ψ n-1 w n w n ψ n-1 , if ϑ n = E and α n-1 = w n . (ii) If one can write (Θ, w) = (Θ ′ ϑ n Θ ′′ , w ′ (ϑ n-1 •ϑ n )(w n )w ′′ ) such that i := |w ′ | = |Θ ′ |+1
with |Θ ′ | maximum, then

ψ n = ψ n-1 (ϑ n-1 • ϑ n ) ψ -1 i ψ n-1 .
(iii) Otherwise,

ψ n = ψ n-1 ϑ n (ψ n-1 ), if ϑ n = R or α n-1 = w n ; ψ n-1 w n w n ψ n-1 , if ϑ n = E and α n-1 = w n .
Notice that the algorithms of normalization and of computation of generalized pseudostandard words have been implemented in Python by the first author and should be included soon in the Sage words library [START_REF] Stein | palindrome, pseudopalindrome, iterated pseudopalindromic closure, generalized pseudostandard word, normalization, directive bi-sequence, Justin's formula, Fine and Wilf theorem[END_REF].

To conclude this section, let us see how Theorem 29 may be used in order to construct the Thue-Morse word.

Example 31. Theorem 7 tells us that the Thue-Morse word is a generalized pseudostandard word T = ψ (ER) ω (01 ω ). In order to apply Theorem 29 to the construction of T , we have to normalize the directive bi-sequence d = ((ER) ω , 01 ω ). Using Theorem 27, we get d ′ = ((RE) ω , 01 ω ), which is normalized. Theorem 29 yields the successive prefixes t i of T , with t 0 = ε: t 1 = 0; t 2 = t 1 t 1 = 01, by Theorem 29 (i), second case;

t 3 = t 2 E(t -1 0 t 2 ) = 01E(01) = 0110
, by Theorem 29 (ii); t 4 = t 3 E(t 3 ) = 01101001, by Theorem 29 (iii), first case; t 5 = t 4 E(t 4 ) = 0110100101101001, by Theorem 29 (iii), first case and so on, which corresponds to the usual construction of the Thue-Morse word.

Rote words

This section is devoted to the study of Rote words obtained by iterated pseudopalindromic closure. They deserve some attention since they provide a natural characterization of the palindromic prefixes in standard Sturmian words. Moreover, their corresponding normalized bi-sequences are easy to characterize. The so-called Rote words or complementary-symmetric words are sequences of letters having complexity 2n and such that their language is closed under the complementation operator. Let w be a binary word on {0, 1}. The difference of w, denoted by ∆(w), is the word

v = v 1 v 2 • • • v |w|-1 defined by v i = (w i+1 -w i ) mod 2, for i = 1, 2, . . . , |w| -2.
Complementary-symmetric words are connected to Sturmian words by a structural theorem.

Theorem 32 (Rote [START_REF] Rote | Sequences with subword complexity 2n[END_REF]). An infinite word w is a complementary-symmetric Rote word if and only if the infinite word ∆(w) is a Sturmian word.

We say that a complementary-symmetric words r is a standard Rote word if both 0r and 1r are complementary-symmetric words. Equivalently, a word r is standard Rote if and only if ∆(r) is standard Sturmian.

The aim of this section is to provide an explicit construction of standard Rote words by iterated pseudopalindromic closure. The key idea is to exploit the link with Sturmian words by looking at the palindrome and antipalindrome prefixes of the Rote word. First, we state without proof some elementary properties of the operator ∆. If they are odd, they share the same central letter, so that θ(ucd) ends with αβα, where α ∈ {o, a}. In both cases, by the induction hypothesis, the two last letters of θ(uc) are distinct, and so are the two last letters of θ(ucd).

(ii) Suppose that c = d and |uc| d = 0. Then ψ(ucd) = ψ(uc)dψ(uc) by Proposition 3. In particular |ψ(ucd)| is odd. Moreover, uc is the power of a letter, which means that the previous palindrome prefixes are all powers of the same letter. Hence, one of the two previous palindrome prefixes is of odd length while the other is of even length, so that α = β. Finally, |ψ(ucd)| is of odd length and has central letter different from all shorter odd palindrome prefixes. Hence, γ = α, β, as desired.

(iii) Suppose that c = d and |uc| d > 0. Write u = u 1 dc k with u 1 ∈ A * and k a non negative integer, so that ucd = u 1 dc k+1 d. Again by Proposition 3, one deduces ψ(ucd) = ψ(uc)ψ(u 1 ) -1 ψ(uc), which means that ψ(ucd) and ψ(u 1 ) share the same parity and, if odd, the same central letter. Hence, it suffices to show that θ(u 1 ) ends with γ.

It follows from (i) that θ(uc) ends with (αβ) k/2 if k is even and with β(αβ) k/2 otherwise. Moreover, by the induction hypothesis θ(uc) ends with γ(αβ) k/2 if k is even, or with γβ(αβ) k/2 otherwise. In both cases, this implies that θ(u 1 ) ends with γ. But ψ(u 1 ) and ψ(ucd) are of the same type, so that θ(u 1 ) ends with γ, as desired. In particular, β and γ are distinct.

The values of θ(uc) are represented in Figure 3 for short words. , where w is a binary word. For instance, if w = 010, then its corresponding node is (0 1 0 0 1 0, eoae) and one verifies that the palindrome prefixes ε, 0, 010 and 010010 of ψ(w) are indeed of types e, o, a and e.

From now on, we consider only standard Rote word starting with 0. Since the complement of a Rote word is also a Rote word, it is easy to extend the results to standard Rote words starting with 1, but for sake of simplicity, we restrict our study by fixing the first letter as 0. Observations found in Example 36 lead naturally to the following statement: Lemma 37. Let s be a standard Sturmian word and r be the standard Rote word starting with 0 such that ∆(r) = s. Let p 0 = ε, p 1 , p 2 , . . . be the palindrome prefixes of s, enumerated with increasing length, and q 0 = ε, q 1 , q 2 , . . . be the pseudopalindrome prefixes of r, enumerated with increasing length as well. Then ∆(q i+1 ) = p i for all integers i ≥ 0.

Proof. First, notice that since s has infinitely many palindrome prefixes, then r has infinitely many pseudopalindrome prefixes, in virtue of Lemma 33(ii). We proceed by contradiction. Let i ≥ 0 be the smallest integer such that ∆(q i+1 ) = p i . We know from Lemma 33(ii) that ∆(q i+1 ) is a palindrome. Hence, it means that ∆(q i+1 ) = p j for some integer j > i. This is impossible since the prefix q of r such that ∆(q) = p i is a pseudopalindrome, again by Lemma 33(ii), i.e. there would exist a pseudopalindrome q having length between |q i | and |q i+1 |.

Therefore, standard complementary-symmetric words are generalized pseudostandard words.

Lemma 38. Let s be a standard Sturmian word directed by some infinite binary sequence x and r be the standard Rote words starting with 0 such that ∆(r) = s. Then there exists an infinite bi-sequence (Θ, w) such that r = ψ Θ (w), i.e. r is a generalized pseudostandard word.

Proof. As in Lemma 37, let p 0 = ε, p 1 , p 2 , p 3 , . . . be the palindrome prefixes of s and q 0 = ε, q 1 , q 2 , q 3 , . . ., be the list of pseudopalindrome prefixes of r enumerated with increasing length. For i = 0, 1, 2, . . ., let w i+1 = r |q i | + 1 , i.e. w i+1 is the letter following the pseudopalindrome prefix q i . Finally, let

ϑ i = R, if q i is an R-palindrome; E, if q i is an E-palindrome. We show that (Θ, w) = (ϑ 1 ϑ 2 ϑ 3 • • • , w 1 w 2 w 3 • • • ) is a directive bi-sequence of r. Let ψ i = ψ ϑ 1 ϑ 2 •••ϑ i (w 1 w 2 • • • w i ) for i = 1, 2, . . ..
It suffices to prove that q i+1 = ψ i+1 for i = 1, 2, . . .. Arguing by contradiction, suppose that i is the smallest integer such that q i = ψ i but q i+1 = ψ i+1 . Clearly, q i+1 and ψ i+1 are both ϑ i+1 -palindromes and share the prefix q i w i+1 . Therefore, |ψ i+1 | < |q i+1 |, otherwise ψ i+1 would not be the shortest ϑ i+1 -palindrome having q i w i+1 = ψ i w i+1 . By Lemma 38, we have ∆(q i+1 ) = p i which implies that ∆(q i w i+1 ) = p i-1 a, with a ∈ A, is a prefix of both p i and ∆(ψ i+1 ). But ∆(ψ i+1 ) is a palindrome and |∆(ψ i+1 )| < |p i |, contradicting the fact that p i is the shortest palindrome having prefix p i-1 a.

(ϑ 1 ϑ 2 • • • ϑ n , y 1 y 2 • • • y n )
be its associated output word. Let q = abα = i, q ′ = cdβ be the two last states visited when reading x. Then c = b, β = x n and θ(x) ends with cd.

Proof. The proof is done by induction on n. For n = 1, we have q = oe0. There are two cases to consider according to the value of x 1 . If x 1 = 0, then q ′ = eo0 so that c = b = e, β = x 1 = 0 and θ(x) = θ(0) = eo. On the other hand, if x 1 = 1, then q ′ = ea1 so that c = b = e, β = x 1 = 1 and θ(x) = θ(1) = ea.

Consider now the general case. By inspection of T , one observes that c = b and β = x i for any transition, except the one starting with the initial state i. The fact that θ(x) ends with cd follows from inspection of T and Proposition 35.

We are now ready to show the main theorem of this section. The key idea is to observe that one may derive the directive bi-sequence from the directive sequence of the Sturmian word by looking at the palindrome types (a, e or o) at each step.

Theorem 40. Let x be an infinite binary sequence directing some Sturmian word s and let r be the Rote word starting with 0 and such that ∆(r) = s. Then the output word (Θ, y) obtained from x in the transducer T is a directive bi-sequence of r.

Proof. We know from Lemma 37 that the palindrome prefixes of s and the pseudopalindromic prefixes of r are in 1-to-1 correspondence. It only remains to describe the letters and type of pseudopalindromes involved in the iterated pseudopalindromic closure.

For every positive integer n, let x = x 1 x 2 • • • x n and (Θ, y) = (ϑ 1 ϑ 2 • • • ϑ n , y 1 y 2 • • • y n ). Moreover, let q = abα and q ′ = cdβ be the two last states visited when reading x. We prove by induction on n that (Θ, y) is the output word obtained from T by reading x. This is clear for n = 1.

For the general case, we know from Lemma 39 that q ′ remembers the two last palindrome type encountered in ψ(x), i.e. As a consequence, we have a complete characterization of standard Rote words obtained from iterated pseudopalindromic closure. Proof. If ψ Θ (w) is a standard Rote word, then it must be obtained from T . But every path of length 2 in T yields an output word in {(RR, 00), (RR, 11), (RE, 01), (RE, 10), (ER, 00), (ER, 01), (ER, 10), (ER, 11)}.

Conversely, if (Θ, w) contains a factor in D, then it cannot be obtained from T . Hence, the first claim is proved. The fact that (Θ, w) is normalized follows directly from Proposition 26 since all forbidden factors for a bi-sequence do not appear in any output word of T .

Concluding remarks

Theorem 29 does not provide the most efficient way of computing the Thue-Morse word. However, it may be very useful for large directive bi-sequences having less regularity. It is also a great tool, combined with the normalization, to compute a generalized pseudostandard word over a two-letter alphabet.

Algorithm 2 takes as input any directive bi-sequence of length n for a two-letter alphabet, normalized or not, and computes, in linear time with respect to the length of the directive bi-sequence, a prefix of the corresponding generalized pseudostandard word, using both the normalization and the generalization of Justin's formula (Theorem 29) for generalized pseudostandard words.

The main results of this paper are the generalization of Justin's formula for generalized pseudostandard words (Theorem 29) over a two-letter alphabet and the characterization of the directive bi-sequences of standard Rote words. They should be of considerable help for future investigations about generalized pseudostandard words. It shall be noted that some stated lemmas could be generalized for words over an alphabet with three or more letters, but it remains an interesting open problem to generalize all of them.

Another topic of interest would be to compute the maximum complexity of generalized pseudostandard words. Since they include Sturmian words, which have complexity n + 1, Rote words of complexity 2n and the Thue-Morse word, whose complexity oscillates around 3n, it seems reasonable to conjecture that it is at most linear. Indeed, empirical observation suggests that, over binary alphabets, no word has a complexity greater than 4n: Conjecture 43. Let w be a generalized pseudostandard words over a binary alphabet. Then there exists some integer n 0 such that f w (n) ≤ 4n, for all n ≥ n 0 .

Interestingly, the bi-sequence yielding the highest complexity we have been able to provide, so far, is constructed only from forbidden factors as detailed in Proposition 26. For instance, in Sage, we may compute the number of factors of each length between 1 and 300 for the prefix of length 5 000 of the word ψ (REEEEERRRE) ω ((0001101011) ω ):

Example 8 .

 8 As an example, let us construct the first prefixes of the Thue-Morse word. ψ E (0) = 0 . 1 ψ ERE (011) = 0 . 1101 . 001 ψ ER (01) = 0 . 110 ψ ERER (0111) = 0 . 1101 . 00110010110.

  w n as a prefix, contradicting the definition of the palindromic closure. (⇔) By definition of palindromic closure, ψ R n (w 1 . . . n ) is a palindrome for any integer n ≥ 0.

Lemma 22 .

 22 Let (Θ, w) be a finite directive bi-sequence describing a prefix of a generalized pseudostandard word on any alphabet. If (Θ, w) is normalized and (Θτ, wx) is not, with x ∈ A and τ ∈ {E, R}, any missed ϑ-palindromic prefix p is such that |ψ Θ (w)| < |p| < |ψ Θτ (wx)|. Proof. It is obvious that |p| < |ψ Θτ (wx)|. If |p| ≤ |ψ Θ (w)|, then a contradiction occurs, since (w, Θ) is supposed normalized.

Figure 1 :

 1 Figure 1: Illustration of the proof of Lemma 24.

Figure 2 :

 2 Figure 2: Illustration of Part (⇐) in the proof of Proposition 26. It follows from Lemma 24that p = 2g and q = g, where g = gcd(p, q). Also, ϑ n-1 = ϑ n .

2 .

 2 Recall that by definition of pseudopalindromic closure, |v| ≤ 2|u| + 2. Moreover, |v| = |u| + 2g, |y| ≤ g -1 and g ′ = |u| -|y| ≤ g -1. On the first hand, we have |v| ≤ 2|u| + 2 = 2|v| -4g + 2 which implies |v| ≥ 4g -2. On the other hand, |v| = |u| + 2g ≤ |y| + g -1 + 2g ≤ g -1 + g -1 + 2g = 4g -2, thus |v| = 4g -2. In particular, in virtue of the equalities and inequalities |v| = 4g -2, |v| -|u| = 2g, |u| -|y| ≤ g -1 and |y| ≤ g -1, we have |y| = g -1, |u| = 2g -2 and |v| = 2|u| + 2. Hence, ϑ n = E and g ′ = |u| -|y| = g -1.

Lemma 33 .

 33 Let u, v ∈ Σ * , where |u|, |v| ≥ 2. Then(i) Suppose that c = d. Then ψ(ucd) = ψ(uc)ψ(u) -1 ψ(uc) by Proposition 3. Therefore, |ψ(ucd)| and |ψ(u)| have same parity. If they are even, then θ(ucd) ends with eβe.

Example 36 .Figure 3 :

 363 Figure3: Representation of Proposition 35 by a tree, describing the possible palindrome type sequences for any finite binary word. Each node is a couple (ψ(w), θ(w)), where w is a binary word. For instance, if w = 010, then its corresponding node is (0 1 0 0 1 0, eoae) and one verifies that the palindrome prefixes ε, 0, 010 and 010010 of ψ(w) are indeed of types e, o, a and e.

Figure 4 :

 4 Figure 4: Transducer computing the directive bi-sequence of a Rote standard word r starting with 0 from the directive sequence of a Sturmian standard word s such that ∆(r) = s. Consider the transducer T on {0, 1} × ({R, E} × {0, 1}) represented in Figure 4. The next lemma states some observations about T . Lemma 39. Let x = x 1 x 2 • • • x n be an input word of length n ≥ 1 of T and

  θ(x) ends with ab. Moreover, c = b and β = x n . Next, observe that since ψ(x) is a palindrome of type c = b, we deduce by inspection of T thatψ ϑ 1 ϑ 2 •••ϑn (y 1 y 2 • • • y n ) is a R-palindrome if c = b ∈ {o, e} and is a E-palindrome if c = b = a.Finally, one verifies in T that y n+1 = x n if c = b ∈ {o, e} and y n+1 = (x n + 1) mod 2 if c = b = a. Example 41. Let x = 001101. When reading x in T , one visits states i, oe0, eo0, oe0, ea1, ae1, eo0 and oa1 and obtains the output word (ϑ, y) = (RRRERRE, 0001001). Moreover, ψ(x) = 0 0 10010001001001000100100 ψ ϑ (y) = 0 0 01 . 1100001110001 . 111000111 and we indeed have ∆(ψ ϑ (y)) = ψ(x).

Corollary 42 .

 42 Let (Θ, w) be a directive bi-sequence. Then ψ Θ (w) is a standard Rote word if and only if no factor of length 2 of (Θ, w) is in the setD = {(EE, ab) | a, b ∈ A} ∪ {(RR, aa) | a ∈ A} ∪ {(RE, aa) | a ∈ A}.Moreover, (Θ, w) is normalized.

Proof. (i) Assume first that w = a n-1 a for some a ∈ A. Then Θ ∈ {R n , R n-1 E}, otherwise (Θ, w) would not be normalized by Lemma 23. The result follows according to the value of Θ n , w n and α n . If |ϑ 1 ϑ 2 • • • ϑ n-1 | ϑn = 0 and |w 1 w 2 • • • w n -1 | w n = 0, again by Lemma 23, since (Θ, w) is normalized, we know that ϑ 1 = R so that ϑ n = E, except if n = 1. But since no E-palindrome occurs as a prefix, and then as a suffix of ψ n-1 , we deduce that the longest E-palindromic suffix of ψ ϑ 1 ϑ 2 •••ϑ n-1 (w 1 w 2 • • • w n -1 )w n is either ε or α n-1 α n-1 and the result follows.

(ii) By hypothesis, there exists a ϑ n -palindromic prefix ψ i of ψ n-1 followed by the letter (ϑ n-1 • ϑ n )(w n ). Moreover, since (Θ, w) is normalized, |Θ ′ | is maximum and by its construction, ψ i is exactly the longest ϑ n -palindromic prefix of ψ n-1 followed by the letter

which concludes this part. Notice that Equation ( 3) is obtained from Equation (2), using the fact that for any word u, v ∈ A * , (uv) -1 = v -1 u -1 , and that Equation (5) follows from Equation (4), since ψ i is a ϑ n -palindrome and ψ n-1 is a ϑ n-1 -palindrome.

(iii) Since the hypothesis of cases (i) and (ii) are not satisfied, we can assume here that ψ n-1 does not have a nonempty ϑ n -palindromic suffix that is preceded by the letter ϑ n (w n ) and that |w 1

Then w n = α n-1 , otherwise we contradict the hypothesis, since it implies that ψ n-1 necessarily has a palindromic suffix that is preceded by the letter ϑ n (w n ) = w n , namely a suffix of the form w n w n i . Thus, ϑ n = R implies w n = α n-1 and consequently,

Combining all those cases yields the statement.

It is worth mentioning that Proposition 3 is a special case of Theorem 29. Indeed, if Θ = R n , then (Θ, w) directs a standard Sturmian sequence and we retrieve case (i) if w = a n-1 a, for a ∈ {0, 1} and then, ψ n = ψ n-1 w n ψ n-1 . Otherwise, case (ii) applies and we get

On the other hand, if Θ = E n , the directive bi-sequence (E n , w) cannot be a normalized one, by Lemma 23. In this case, we can use the same idea as in the proof of Theorem 29 in order to get the following generalization of Justin's formula for E-standard words.

Proposition 30. Let (E n+1 , wa) be a directive bi-sequence of a E-standard word, with w ∈ {0, 1} n . If w is not a-free, then we write w = v 1 av 2 with v 2 a-free and we have

where γ is the unique letter distinct from α and β.

Proof. The proof is done by induction on |u|. Clearly, the two palindrome prefixes of ψ(0) = 0 are ε, 0, so that θ(0) = eo. Similarly, one notices that θ(1) = ea. Now, there are three cases to consider:

Algorithm 2 Computation of a finite generalized pseudostandard word.

1: function IteratedPseudoPalindromicClosure(Θ, w) 2: if (RR, aa) is prefix of (Θ, w) then 3:

Θ ← RER(RR) -1 Θ, w ← aaa(aa) -1 w 4:

else if (R i-1 E, a i ) is prefix of (Θ, w), for some integer i ≥ 1 then 5:

Θ ← RΘ, w ← a i aa -i w 6:

else if (R i EE, a i a a) is prefix of (Θ, w) for some integer i ≥ 1 then 7:

Θ ← R i ERE(R i EE) -1 Θ, w ← a i a aa(a i a a) -1 w 8:

end if 9:

ψ 0 ← ε 10:

for i ∈ {1, 2, . . . , n} do 11:

end if 25:

end for 26:

return ψ n 27: end function E,E,E,E,E,R,R,R,E] + [R,E,E,E] sage: w = A([0,0,0,1,1,0,1,0,1,1] + [0,0,0,1]) sage: u = iterated_right_palindromic_closure(w,T) sage: v = u[:5000] sage: [round(float(v.number_of_factors(i)/(4*i)),3) for i in range(1,300)] [0.5, 0.5, 0.5, 0.5, 0.5, 0.583, 0.643, 0.688, 0.722, 0.8, 0.864, 0.917, 0.962, 1.0, 1.033, 1.063, 1.088, 1.111, 1.132, 1.15, 1.167, 1.182, 1.196, 1.208 Observe that the f (n) may be greater than 4n up to n = 200, but it then decreases beyond 4n, suggesting Conjecture 43.

Acknowledgement

The authors wish to thank the referees for a number of comments and suggestions that have led to improvements in this paper.