Jean Berstel

Clelia De Felice

Dominique Perrin

Christophe Reutenauer

Giuseppina Rindone

Bifix codes and Sturmian words

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This paper studies a new relation between two objects previously unrelated: bifix codes and Sturmian words. We first give some elements on the background of both.

The study of bifix codes goes back to founding papers by Schützenberger [START_REF] Schützenberger | On an application of semigroup methods to some problems in coding[END_REF] and by Gilbert and Moore [START_REF] Gilbert | Variable length binary encodings[END_REF]. These papers already contain significant results. The first systematic study is in the papers of Schützenberger [START_REF] Schützenberger | On a family of submonoids[END_REF][START_REF] Schützenberger | On a special class of recurrent events[END_REF]. The general idea is that the submonoids generated by bifix codes are an adequate generalization of the subgroups of a group. This is illustrated by the striking fact that, under a mild restriction, the average length of a maximal bifix code with respect to a Bernoulli distribution on the alphabet is an integer. Thus, in some sense a maximal bifix code behaves as the uniform code formed of all the words of a given length. The theory of bifix codes was developed in a considerable way by Césari. He proved that all the finite maximal bifix codes may be obtained by internal transformations from uniform codes [START_REF] Césari | Sur un algorithme donnant les codes bipréfixes finis[END_REF]. He also defined the notion of derived code which allows to build maximal bifix codes by increasing degrees [START_REF] Césari | Propriétes combinatoires des codes bipréfixes[END_REF].

Sturmian words are infinite words over a binary alphabet that have exactly n + 1 factors of length n for each n ≥ 0. Their origin can be traced back to the astronomer J. Bernoulli III. Their first in-depth study is by Morse and Hedlund [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]. Many combinatorial properties were described in the paper by Coven and Hedlund [START_REF] Coven | Sequences with minimal block growth[END_REF]. Note that, although Sturmian words appear first in the work of Morse and Hedlund, their finitary version, Christoffel and standard words, appear much before in the work of Christoffel [START_REF] Christoffel | Observatio arithmetica[END_REF] and, apparently independently, in the work of Markoff [START_REF] André | Sur les formes quadratiques binaires indéfinies[END_REF][START_REF] André | Sur les formes quadratiques binaires indéfinies[END_REF]; the latter constructed the famous Markoff numbers by using them. The Markoff theory (which was designed to study minima's of quadratic forms) was revisited often by mathematicians, notably by Frobenius [START_REF] Georg | Über die Markoffschen Zahlen. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften[END_REF], Dickson [START_REF] Dickson | Studies in the theory of numbers[END_REF], H. Cohn [START_REF] Cohn | Markoff forms and primitive words[END_REF], Cusick and Flahive [START_REF] Cusick | The Markoff and Lagrange spectra[END_REF] and Bombieri [START_REF] Bombieri | Continued fractions and the Markoff tree[END_REF]. There, the connection with the free group on two generators was established. Other connection of Christoffel words with the free group may be found in Osborne and Zieschang [START_REF] Osborne | Primitives in the free group on two generators[END_REF] and Kassel and Reutenauer [START_REF] Kassel | Sturmian morphisms, the braid group B 4 , Christoffel words and bases of F 2[END_REF]. Moreover, the Sturmian morphisms (substitutions that preserve Sturmian words) are the positive endomorphisms of the free group on two generators, see Wen and Wen [START_REF] Xiong | Local isomorphisms of invertible substitutions[END_REF], Mignosi and Séébold [START_REF] Mignosi | Morphismes Sturmiens et règles de Rauzy[END_REF]. Thus Sturmian words are closely related to the free group. This connection is one of the main points of the present paper.

Sturmian words were generalized to arbitrary alphabets. Following an initial work by Arnoux and Rauzy [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] and developing ideas of De Luca [START_REF] De | Sturmian words: structure, combinatorics, and their arithmetics[END_REF], Droubay, Justin and Pirillo introduced in [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF] the notion of episturmian words which generalizes Sturmian words to arbitrary finite alphabets.

In this paper, we consider the extension of the results known for bifix codes maximal in the free monoid to bifix codes maximal in more restricted sets of words, and in particular the sets of factors of episturmian words.

We extend most properties of ordinary maximal bifix codes to bifix codes that are maximal in a recurrent set F of words (F -maximal bifix codes). We show in particular that the average length of a finite F -maximal bifix code of degree d in a recurrent set F with respect to an invariant probability distribution on F is equal to d (Corollary 4.3.8).

Our main objective is the case of the set of factors of an episturmian word. We actually work with the set of factors of a strict episturmian word, called simply a Sturmian set. The number of factors of length d of a strict episturmian word over an alphabet of k letters is known to be (k -1)d + 1. Our main result is that a maximal bifix code of degree d in a Sturmian set over an alphabet of k letters is always a basis of a subgroup of index d of the free group (Theorem 6.2.1). In particular, it has (k -1)d + 1 elements (Theorem 5.2.1). Since the set of all words of length d is a maximal bifix code of degree d, this yields a strong generalization of the previous property. In particular, every finite maximal bifix code of degree d over a two letter alphabet contains exactly d + 1 factors of any Sturmian word.

Finally, bifix codes X contained in restricted sets of words are used to study the groups in the syntactic monoid of the submonoid X * (Theorem 7.2.3). This aspect was first considered by Schützenberger in [START_REF] Schützenberger | A property of finitely generated submonoids of free monoids[END_REF]. He has studied the conditions under which parameters linked with the syntactic monoid M of a finitely generated submonoid X * of a free monoid A * can be bounded in terms of Card(X) only. One of his results is that, apart from a special case where the group is cyclic, the cardinality of a group contained in M is such a parameter. In [START_REF] Schützenberger | A property of finitely generated submonoids of free monoids[END_REF], Schützenberger conjectured a refinement of his result which was subsequently proved by Césari. This study led to the Critical Factorization Theorem that we will meet again here (Theorem 5. 3.8).

The extension of the results concerning codes in free monoids to codes in a restricted set of words has already been considered by several authors. However, most of them have focused on general codes rather than on the particular class of bifix codes. In [START_REF] Reutenauer | Ensembles libres de chemins dans un graphe[END_REF] the notion of codes of paths in a graph has been introduced. Such paths can also be viewed as words in a restricted set. The notion of a bifix code of paths has been studied in [START_REF] De | Finite biprefix sets of paths in a graph[END_REF] where the internal transformation is generalized. In [START_REF] Restivo | Codes and local constraints[END_REF], the notion of code in a factorial set of words was introduced. The definition of a code X in a factorial set F requires that the set X * of all concatenations of words in X is included in F . This approach was pushed further in [START_REF] Hong | Cyclic renewal systems[END_REF]. A more general notion was considered in [START_REF] Béal | Codes and sofic constraints. Theoret[END_REF]. It only requires that X ⊂ F and that no word of F has two distinct factorizations but not necessarily that X * ⊂ F . The connection with unambiguous automata was considered later in [START_REF] Béal | Completing codes in a sofic shift[END_REF]. Codes in Sturmian sets have been studied before in [START_REF] Carpi | Codes of central Sturmian words[END_REF]. Finally, prefix codes X contained in restricted sets of words are used in [START_REF] Perrin | On syntactic groups[END_REF] to study the groups in the syntactic monoid of the submonoid X * .

Our paper is organized as follows.

In a first section (Section 2), we recall some definitions concerning prefixclosed, factorial, recurrent and uniformly recurrent sets, in relation with infinite words. We also introduce probability distributions on these sets.

In Section 3, we introduce prefix codes in factorial sets, especially maximal ones. We introduce some basic notions on automata. We define the average length with respect to a probability distribution on the factorial set.

In Section 4, we develop the theory of maximal bifix codes in recurrent sets. We generalize most of the properties known in the classical case. In particular, we show that the notion of degree and that of derived code can be defined (Theorem 4.3.1). We show that, for a uniformly recurrent set F , any F -thin bifix code contained in F is finite (Theorem 4.4.3). In the case of Sturmian sets, we prove our main results. First, a bifix code of degree d maximal in a Sturmian set on a k-letter alphabet has (k -1)d + 1 elements (Theorem 5.2.1). Next, given an infinite word x, if there is a finite maximal bifix code X of degree d such that x has at most d factors of length d in X, then x is ultimately periodic (Corollary 5.3.3). The proof uses the Critical Factorization Theorem (see e.g. [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Crochemore | Two-way string-matching[END_REF]).

Section 6 presents our results concerning free groups. Our main result (Theorem 6.2.1) in this area states that for a Sturmian set F , a bifix code X ⊂ F is a finite and F -maximal bifix code of F -degree d if and only if it is a basis of a subgroup of index d of the free group on A. We finally present in Section 7 a consequence of Theorem 6.2.1 concerning syntactic groups. We show that any transitive permutation group of degree d which can be generated by k elements is a syntactic group of a bifix code with (k -1)d + 1 elements (Theorem 7.2.3).

Many results of this paper are extensions or generalizations of results contained in [START_REF] Berstel | Codes and Automata[END_REF]. We always give the reference of the corresponding result in [START_REF] Berstel | Codes and Automata[END_REF]. The proofs sometimes consist in the verification that the proof of the book still holds in the more general setting, and sometimes require new and more involved developments. In order to make the paper self contained, and to avoid repetitive references to the book, we have tried to always give complete proofs.

Factorial sets

In this section, we introduce the basic notions of prefix-closed, factorial, recurrent and uniformly recurrent sets. These form a descending hierarchy. These notions are closely related with the analogous notions for infinite words which are defined in Section 2.2. In Section 2.4, we introduce probability distributions on factorial sets.

We use the standard terminology and notation on words, in particular concerning prefixes, suffixes and factors (see [START_REF] Lothaire | Combinatorics on Words[END_REF] for example). Let A be a finite alphabet. All words considered below are supposed to be on the alphabet A. We denote by 1 the empty word. We denote by A * the set of all words on A and by A + the set of nonempty words.

The reversal of a word w = a 1 a 2 • • • a n , where a 1 , a 2 , . . . , a n are letters, is the word w = a n • • • a 2 a 1 . In particular, the reversal of the empty word is the empty word. A set X of words is closed under reversal if it contains the reversals of its elements.

Given a set X of words, we define, for a word u, the set u -1 X by

u -1 X = {y ∈ A * | uy ∈ X} .
Next, we say that a word is a prefix of X if it is a prefix of a word of X.

A nonempty set F ⊂ A * of words is said to be prefix-closed if it contains the prefixes of all its elements. Symmetrically, it is said to be suffix-closed if it contains the suffixes of all its elements. It is said to be factorial if it contains the factors of all its elements.

The right (resp. left ) order of a word w with respect to F is the number of letters a such that wa ∈ F (resp. aw ∈ F ).

A set F is said to be right essential if it is prefix-closed and if any w ∈ F has right order at least 1. If F is right essential, then for any u ∈ F and any integer n ≥ 1, there is a word v of length n such that uv ∈ F . Symmetrically, a set F is said to be left essential if it is suffix-closed and if any w ∈ F has left order at least 1.

Recurrent sets

A set F of words is said to be recurrent if it is factorial and if for every u, w ∈ F there is a v ∈ F such that uvw ∈ F . A recurrent set F = {1} is right and left essential.

Example 2.1.1 The set F = A * is recurrent.

Example 2.1.2 Let A = {a, b}. Let F be the set of words on A without factor bb. Thus F = A * \ A * bbA * . The set F is recurrent. Indeed, if u, w ∈ F , then uaw ∈ F .

A set F is said to be uniformly recurrent if it is factorial and right essential and if, for any word u ∈ F , there exists an integer n ≥ 1 such that u is a factor of every word in F ∩ A n . Proposition 2.1.3 A uniformly recurrent set is recurrent.

Proof. Let u, w ∈ F . Let n be such that w is a factor of any word in F ∩ A n . Since F is right essential, there is a word v of length n such that uv ∈ F . Since w is a factor of v, we have v = rws for some words r, s. Thus urw ∈ F .

The converse of Proposition 2.1.3 is not true as shown in the example below.

Example 2.1. [START_REF] Béal | Codes and sofic constraints. Theoret[END_REF] The set F = A * on A = {a, b} is recurrent but not uniformly recurrent since b ∈ F but b is not a factor of a n ∈ F for any n ≥ 1.

Recurrent words

We denote by F (x) the set of factors of an infinite word x ∈ A N . The set F (x) is factorial and right essential.

An infinite word x ∈ A N is said to be recurrent if for any word u ∈ F (x) there is a v ∈ F (x) such that uvu ∈ F (x). Equivalently, each factor of a recurrent word x has an infinite number of occurrences in x.

Proposition 2.2.1 For any recurrent set F there is an infinite word x such that F (x) = F .

Proof. Set F = {u 1 , u 2 , . . .}. Since F is recurrent and u 1 , u 2 ∈ F , there is a word

v 1 such that u 1 v 1 u 2 ∈ F . Further, since u 1 v 1 u 2 , u 3 ∈ F there is a word v 2 such that u 1 v 1 u 2 v 2 u 3 ∈ F . In this way, we obtain an infinite word x = u 1 v 1 u 2 v 2 • • • such that F (x) = F .
Proposition 2.2.2 For any infinite word x, the set F (x) is recurrent if and only if x is recurrent.

Proof. Set F = F (x). Suppose first that F is recurrent. For any u in F , there is a v ∈ F such that uvu ∈ F . Thus x is recurrent. Conversely, assume that x is recurrent. Let u, v be in F . Then there is a factorization x = puy with p ∈ F and y ∈ A N . Since x is recurrent, the word v is a factor of y. Set y = qvz with q ∈ F and z ∈ A N . Then uqv is in F . Thus F is recurrent.

An infinite word x ∈ A N is said to be uniformly recurrent if the set F (x) is uniformly recurrent. There exist recurrent infinite words which are not uniformly recurrent, as shown in the following example.

Example 2.2.3 Let x be the infinite word obtained by concatenating all binary words in radix order: by increasing length, and for each length in lexicographic order. Thus, x starts as follows.

x = ab aaabbabb aaaaababaabbbaababbbabbb • • •

The infinite word x is recurrent since every factor occurs infinitely often. However, x is not uniformly recurrent since each a n , for n > 1, is a factor of x, thus two consecutive occurrences of say the letter b may be arbitrarily far one from each other. The word x is closely related to the Champernowne word [START_REF] Gawen | The construction of decimals normal in the scale of ten[END_REF].

We use indifferently the terms of morphism or substitution for a monoid morphism from A * into itself. Let f : A * → A * be a morphism and assume there is a letter a ∈ A such that f (a) ∈ aA + . The words f n (a) for n ≥ 1 are prefixes of one another. If |f n (a)| → ∞ with n, then we denote by f ω (a) the infinite word which has all f n (a) as prefixes. It is called a fix-point of f . Example 2.2.4 Set A = {a, b}. The Thue-Morse morphism is the substitution [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] Example 1.5.10). We call Thue-Morse set the set of factors of the Thue-Morse word.

f : A * → A * defined by f (a) = ab and f (b) = ba. The Thue-Morse word x = abbabaab • • • is the fix-point f ω (a) of f . It is uniformly recurrent (see
An infinite word x ∈ A N avoids a set X of words if F (x) ∩ X = ∅. We denote by S X the set of infinite words avoiding a set X ⊂ A * . A (one sided) shift space is a set S of infinite words of the form S X for some X ⊂ A * .

A shift space S ⊂ A N is minimal if for any shift space T ⊂ S, one has T = ∅ or T = S.

For any infinite word x ∈ A N , we denote by S(x) the set of infinite words y ∈ A N such that F (y) ⊂ F (x). The set S(x) is a shift space. Indeed, we have y ∈ S(x) if and only if

F (y) ⊂ F (x) or equivalently F (y) ∩ X = ∅ for X = A * \ F (x).
The following property is standard (see for example [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] Theorem 1.5.9).

Proposition 2.2.5 An infinite word x ∈ A N is uniformly recurrent if and only if S(x) is minimal.

Episturmian words

A Sturmian word is an infinite word x on a binary alphabet A such that the set F (x) ∩ A n has n + 1 elements for any n ≥ 0. is the fix-point f ω (a) of f . It is a Sturmian word (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] Example 2.1.1). We call Fibonacci set the set of factors of the Fibonacci word.

Episturmian words are an extension of Sturmian words to arbitrary finite alphabets.

Recall that, given a set F of words over an alphabet A, the right (resp. left) order of a word u in F is the number of letters a such that ua ∈ F (resp. au ∈ F ). A word u is right-special (resp. left-special ) if its right order (resp. left order) is at least 2. A right-special (resp. left-special) word is strict if its right (resp. left) order is equal to Card(A). In the case of a 2-letter alphabet, all special words are strict.

By definition, an infinite word x is episturmian if F (x) is closed under reversal and if F (x) contains, for each n ≥ 1, at most one word of length n which is right-special.

Since F (x) is closed under reversal, the reversal of a right-special factor of length n is left-special, and it is the only left-special factor of length n of x. A suffix of a right-special factor is again right-special. Symmetrically, a prefix of a left-special factor is again left-special.

As a particular case, a strict episturmian word is an episturmian word x with the two following properties: x has exactly one right-special factor of each length and moreover each right-special factor u of x is strict, that is satisfies the inclusion uA ⊂ F (x) (see [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF]).

It is easy to see that for a strict episturmian word x on an alphabet A with k letters, the set F (x) ∩ A n has (k -1)n + 1 elements for each n. Thus, for a binary alphabet, the strict episturmian words are just the Sturmian words, since a Sturmian word has one right-special factor for each length and its set of factors is closed under reversal.

An episturmian word s is called standard if all its left-special factors are prefixes of s. For any episturmian word s, there is a standard one t such that F (s) = F (t). This is a rephrasing of Theorem 5 in [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF].

f ω (a) = abacabaabacababacabaabacabacabaabacab • • •
is the Tribonacci word . It is a strict standard episturmian word (see [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF]).

The following is, in the case of Sturmian words, Proposition 2.1.25 in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. The general case results from Theorems 2 and 5 in [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF].

Proposition 2.3.3 An episturmian word x is uniformly recurrent and S(x) is minimal.

The converse is false as shown by the following example. We recall now some notions and properties concerning episturmian words. A detailed exposition with proofs is given in [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF][START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF][START_REF] Justin | Episturmian words and episturmian morphisms[END_REF][START_REF] Justin | Episturmian words: shifts, morphisms and numeration systems[END_REF]. See also the survey paper [START_REF] Glen | Episturmian words: a survey[END_REF]. For a ∈ A, denote by ψ a the morphism of A * into itself, called elementary morphism, defined by

ψ a (b) = ab if b = a a otherwise
Let ψ : A * → End(A * ) be the morphism from A * into the monoid of endomorphisms of A * which maps each a ∈ A to ψ a . For u ∈ A * , we denote by ψ u the image of u by the morphism ψ. Thus, for three words u, v, w, we have

ψ uv (w) = ψ u (ψ v (w)).
A palindrome is a word w which is equal to its reversal. Given a word w, we denote by w (+) the palindromic closure of w. It is, by definition, the shortest palindrome which has w as a prefix.

The iterated palindromic closure of a word w is the word Pal(w) defined recursively as follows. One has Pal(1) = 1 and for u ∈ A * and a ∈ A, one has Pal(ua) = (Pal(u)a) (+) . Since Pal(u) is a proper prefix of Pal(ua), it makes sense to define the iterated palindromic closure of an infinite word x as the infinite word which is the limit of the iterated palindromic closure of the prefixes of x.

Justin's Formula is the following. For every words u and v, one has

Pal(uv) = ψ u (Pal(v)) Pal(u) .
This formula extends to infinite words: if u is a word and v is an infinite word, then Pal(uv) = ψ u (Pal(v)) .

(

2.1)

There is a precise combinatorial description of standard episturmian words (see e.g. [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF][START_REF] Glen | Episturmian words: a survey[END_REF]).

Theorem 2.3.5 An infinite word s is a standard episturmian word if and only if there exists an infinite word ∆ = a 0 a 1 • • • , where the a n are letters, such that

s = lim n→∞ u n ,
where the sequence (u n ) is defined by

u n = Pal(a 0 a 1 • • • a n-1
). Moreover, the word s is episturmian strict if and only if every letter appears infinitely often in ∆.

The infinite word ∆ is called the directive word of the standard word s. The description of the infinite word s can be rephrased by the equation

s = Pal(∆) .
As a particular case of Justin's Formula, one has

u n+1 = ψ a0•••an-1 (a n )u n . (2.
2)

The words u n are the only prefixes of s which are palindromes. Observe that ψ ab (c) = abac, so that indeed u 3 = abacu 2 , as claimed in (2.2).

Example 2.3.7 Let A = {a, b, c} and ∆ = c(ab) ω . Then, we have u 1 = c, u 2 = cac, u 3 = cacbcac, u 4 = cacbcacacbcac. By Justin's Formula 2.1, the limit is the word x = ψ c (y), where y = Pal((ab) ω ) is the Fibonacci word on {a, b}. This means that x is obtained from y by inserting a letter c before every letter of y. The word x is not strict. Indeed, the letters a and b are not right-special and the letter c is not strict right special since cc is not a factor.

Probability distributions

Let F ⊂ A * be a prefix-closed set of words. For w ∈ F , denote by S(w) the set

S(w) = {a ∈ A | wa ∈ F }. A right probability distribution on F is a map δ : F → [0, 1] such that (i) δ(1) = 1, (ii)
a∈S(w) δ(wa) = δ(w), for any w ∈ F . For a right probability distribution δ on F and a set X ⊂ F , we denote δ(X) = x∈X δ(x). See [START_REF] Berstel | Codes and Automata[END_REF] for the elementary properties of right probability distributions. Note in particular that for any u ∈ F and n ≥ 0, one has, as a consequence of condition (ii),

δ(uA n ∩ F ) = δ(u). (2.3)
In particular, if δ is a right probability distribution on F , then δ(F ∩ A n ) = 1 for all n ≥ 0. The distribution is said to be positive on F if δ(x) > 0 for any x ∈ F . Symmetrically, for a suffix-closed set F , a left probability distribution is a map δ : F → [0, 1] satisfying condition (i) above and

(iii) a∈P (w) δ(aw) = δ(w), for any w ∈ F , with P (w) = {a ∈ A | aw ∈ F }.
When F is factorial, an invariant probability distribution is both a left and a right probability distribution.

: F → [0, 1] defined for w = a 1 a 2 • • • a n by δ(w) = 1 d 0 d 1 • • • d n-1
where

d i = Card(S(a 1 • • • a i )) for 0 ≤ i < n. Since F is right essential, d i = 0 for 0 ≤ i < n. By convention, δ(1) = 1.
Let us verify that δ is a right probability distribution on F . Indeed, let

w = a 1 a 2 • • • a n . The set S(w) is nonempty. Let a ∈ S(w), we have δ(wa) = 1/d 0 d 1 • • • d n .
Since Card(S(w)) = d n , we obtain that δ satisfies condition (ii) and thus it is a right probability distribution. It is clearly positive.

We will now turn to the existence of positive invariant probability distributions.

A topological dynamical system is a pair (S, σ) of a compact metric space S and a continuous map σ from S into S. Any shift space S becomes a topological dynamical system when it is equipped with the shift map defined by σ

(x 0 x 1 • • • ) = x 1 x 2 • • • . Indeed, we consider A N as a metric space for the dis- tance defined for x = x 0 x 1 • • • and y = y 0 y 1 • • • by d(x, y) = 0 if x = y and d(x, y) = 2 -n
where n is the least integer such that x n = y n otherwise.

A subset T of a topological dynamical system (S, σ) is said to be stable under σ or stable for short if σ(T ) ⊂ T . A stable subset is also called (topologically) invariant.

The following property is well-known (although usually stated for two sidedinfinite words, see for example Proposition 1.5.1 in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]).

Proposition 2.4.2 The shift spaces are the stable and closed subsets of (A N , σ).

Proof. It is clear that a shift space is both closed and stable. Conversely, let S ⊂ A N be closed and stable under the shift. Let X be the set of words which are not factors of words of S. Then S = S X . Indeed, if y ∈ S, then F (y)∩X = ∅ and thus y ∈ S X . Conversely, let y ∈ S X . Let w n be the prefix of length n of y. Since w n / ∈ X there is an infinite word y (n) ∈ S such that w n ∈ F (y (n) ). Since S is stable under the shift, we may assume that w n is a prefix of y (n) . The sequence y (n) converges to y. Since S is closed, this forces y ∈ S.

Let S be a metric space. The family of Borel subsets of S is the smallest family F of subsets of S containing the open sets and closed under complement and countable union. A function µ from F to R is said to be countably additive if µ( n≥0 X n ) = n≥0 µ(X n ) for any sequence (X n ) of pairwise disjoint Borel subsets of S. A Borel probability measure on S is a function µ from F into [0, 1] which is countably additive and such that µ(S) = 1.

Let (S, σ) be a topological dynamical system. A Borel probability measure on S is said to be invariant if µ(σ -1 (B)) = µ(B) for any B ∈ F . Note that since σ is continuous, σ -1 (B) ∈ F and thus µ(σ -1 (B)) is well defined.

The following result is from [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]Theorem 4.2].

Theorem 2.4.3 For any topological dynamical system, there exist invariant Borel probability measures.

A dynamical system (S, σ) is said to be minimal if the only closed stable subsets of S are S and ∅. Note that, by Proposition 2.4.2, this definition is consistent with the definition of a minimal shift space. A Borel probability measure µ on S is positive if µ(U ) > 0 for every nonempty open set U ⊂ S. Proposition 2.4.4 Any invariant Borel probability measure on a minimal topological dynamical system is positive.

Proof. Let µ be an invariant Borel probability measure on the topological dynamical system (S, σ).

Let U ⊂ S be a nonempty open set. Let Y = ∪ n≥0 σ -n (U ) and Z = S \ Y . Since U is open and σ is continuous, each σ -n (U ) is open.
Thus Y is open and Z is closed. The set Z is also stable. Indeed, if for z ∈ Z we had σ(z) / ∈ Z, then there would be an integer n ≥ 0 such that σ(z) ∈ σ -n (U ). Thus z ∈ σ -n-1 (U ) ⊂ Y , a contradiction. Thus σ(Z) ⊂ Z. Since (S, σ) is minimal, this implies that Z = ∅ or Z = S. Since U is nonempty, we have Z = ∅ and thus Y = S. Since µ is invariant, we have µ(σ -1 (U )) = µ(U ) and thus µ(σ -n (U )) = µ(U ) for all n ≥ 0. Hence we cannot have µ(U ) = 0 since it would imply µ(S) ≤ n≥0 µ(σ -n (U )) = 0, a contradiction since µ(S) = 1.

Corollary 2.4.5 For any recurrent set F there exists an invariant probability distribution on F . When F is uniformly recurrent, such a distribution is positive.

Proof. Let F be a recurrent set. By Proposition 2.2.1 there is a recurrent infinite word x such that F (x) = F , and if F is uniformly recurrent, then x is uniformly recurrent.

By Theorem 2.4.3 there is an invariant Borel probability measure µ on S = S(x).

Let δ be the map from F to [0, 1] defined by δ(w) = µ(wA N ∩S). Let us verify that δ is an invariant probability distribution. Indeed, one has δ

(1) = µ(S) = 1. Next, for w ∈ F a∈S(w) δ(wa) = a∈S(w) µ(waA N ∩ S) = µ(wA N ∩ S) = δ(w).
In the same way

a∈P (w) δ(aw) = a∈P (w) µ(awA N ∩ S) = µ(σ -1 (wA N ∩ S)) = µ(wA N ∩ S) = δ(w).
If x is uniformly recurrent, by Proposition 2.2.5, the shift space S = S(x) is minimal. By Proposition 2.4.4, the measure µ is positive. Since wA N ∩ S is a nonempty open set for any w ∈ F , we have δ(w) = µ(wA N ∩ S) > 0 and thus δ is positive.

In some cases, there exists a unique invariant probability distribution on the set F . A morphism f : A * → A * is primitive if there exists an integer k such that, for all a, b ∈ A, the letter b appears in f k (a). If f is a primitive morphism and if f (a) starts with the letter a for some a ∈ A, then x = f ω (a) is a fix-point of f and there is a unique invariant probability distribution δ F on the set F (x) ( [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]Theorem 5.6]). Moreover, this distribution is positive. We illustrate this result by the following examples. obtained as follows (see [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]). The vector v = δ F (a) δ F (b) is an eigenvector for the eigenvalue 1/λ of the A × A-matrix M defined by M ab = |f (a)| b . Here, we have

1 -λ 2λ -1 1 -λ 1 -λ 2λ -1 1 -λ 2λ -1 2 -3λ 2λ -1 2λ -1 2 -3λ 2λ -1 2 -3λ
M = 1 1 1 0 This implies v = λ 1 -λ .

Prefix codes in factorial sets

In this section, we study prefix codes in a factorial set. We will see that most properties known in the usual case are also true in this more general situation. Some of them are even true in the more general case of a prefix-closed set instead of a factorial set. In particular, this holds for the link between prefix codes and probability distributions (Proposition 3.3.4).

Recall that a set X ⊂ A + of nonempty words over an alphabet A is a code if the relation

x 1 • • • x n = y 1 • • • y m
with n, m ≥ 1 and x 1 , . . . , x n , y 1 , . . . , y m ∈ X implies n = m and x i = y i for i = 1, . . . , n. For the general theory of codes, see [START_REF] Berstel | Codes and Automata[END_REF].

Prefix codes

The prefix order is defined, for u, v ∈ A * , by u ≤ v if u is a prefix of v. Two words u, v are prefix-comparable if one is a prefix of the other. Thus u and v are prefix-comparable if and only if there are words x, y such that ux = vy or, equivalently, if and only if uA * ∩ vA * = ∅. The suffix order , and the notion of suffix-comparable words, are defined symmetrically. A set X ⊂ A + of nonempty words is a prefix code if any two distinct elements of X are incomparable for the prefix order. A prefix code is a code.

The dual notion of a suffix code is defined symmetrically with respect to the suffix order.

The submonoid M generated by a prefix code satisfies the following property: if u, uv ∈ M then v ∈ M . Such a submonoid of A * is said to be right unitary. One can show that conversely, any right unitary submonoid of A * is generated by a prefix code (see [START_REF] Berstel | Codes and Automata[END_REF]). The symmetric notion of a left unitary submonoid is defined by the condition v, uv ∈ M implies u ∈ M .

We denote by X the characteristic series of a set X ⊂ A * . By definition, for any

x ∈ A * , (X , x) = 1 if x ∈ X 0 otherwise
The following is Proposition 3.1.6 in [START_REF] Berstel | Codes and Automata[END_REF].

Proposition 3.1.1 Let X be a prefix code and let U = A * \ XA * . Then

A * = X * U and X -1 = U (A -1). (3.1)

Automata

We recall the basic results on deterministic automata and prefix codes (see [START_REF] Berstel | Codes and Automata[END_REF] for a more detailed exposition).

We denote A = (Q, i, T ) a deterministic automaton with Q as set of states, i ∈ Q as initial state and T ⊂ Q as set of terminal states. For p ∈ Q and w ∈ A * , we denote p • w = q if there is a path labeled w from p to the state q and p • w = ∅ otherwise.

The set recognized by the automaton is the set of words w ∈ A * such that i • w ∈ T . A set of words is rational if is recognized by a finite automaton.

All automata considered in this paper are deterministic and we call them simply automata.

The automaton A is trim if for any q ∈ Q, there is a path from i to q and a path from q to some t ∈ T .

An automaton is called simple if it is trim and if it has a unique terminal state which coincides with the initial state.

An automaton A = (Q, i, T ) is complete if for any state p ∈ Q and any letter a ∈ A, one has p • a = ∅.

For a set X ⊂ A * , we denote by A(X) the minimal automaton of X. The states of A(X) are the nonempty sets u -1 X = {v ∈ A * | uv ∈ X} for u ∈ A * . The initial state is the set X and the terminal states are the sets u -1 X for u ∈ X.

Let X ⊂ A * be a prefix code. Then there is a simple automaton A = (Q, 1, 1) that recognizes X * . Moreover, the minimal automaton of X * is simple.

Let X be a prefix code and let P be the set of proper prefixes of X. The literal automaton of X * is the simple automaton A = (P, 1, 1) with transitions defined for p ∈ P and a ∈ A by

p • a =      pa if pa ∈ P , 1 if pa ∈ X , ∅ otherwise.
One verifies that this automaton recognizes X * . Let A = (Q, i, T ) be an automaton. For w ∈ A * , we denote ϕ A (w) the partial map from Q to Q defined by pϕ A (w) = q if p • w = q. The transition monoid of A is the monoid of partial maps from Q to Q of the form ϕ A (w) for w ∈ A * .

Maximal prefix codes

Let F be a subset of A

* . A set X ⊂ A * is right dense in F ⊂ A * , or right F -dense, if any u ∈ F is a prefix of X. A set X ⊂ F is right complete in F , or right F -complete, if X * is right dense in F , that is if every word in F is a prefix of X * .
A prefix code X ⊂ F is maximal in F , or F -maximal, if it is not properly contained in any other prefix code Y ⊂ F . The notion of an F -maximal suffix code is symmetrical.

The following propositions are extensions of Propositions 3.3.1 and 3.3.2, and of Theorem 3.3.5 in [START_REF] Berstel | Codes and Automata[END_REF]. Proposition 3.3.1 Let F be a subset of A * . For any prefix code X ⊂ F , the following conditions are equivalent.

(i) Every element of F is prefix-comparable with some element of X, (ii) X is an F -maximal prefix code.

Proof. (i) implies (ii). Any word u ∈ F is prefix-comparable with some word of X. This implies that if u / ∈ X, then X ∪ u is no longer a prefix code. Thus X is an F -maximal prefix code.

(ii) implies (i). Assume that u ∈ F is not prefix-comparable to any word in X. Then X ∪ u is prefix, and X is not an F -maximal prefix code. Proposition 3.3.2 Let F be a factorial subset of A * . For any set X ⊂ F of nonempty words, the following conditions are equivalent.

(i) Every element of F is prefix-comparable with some element of X, (ii) XA * is right F -dense, (iii) X is right F -complete.

Proof. (i) implies (ii). Let u ∈ F . Let x ∈ X be prefix-comparable with u.

Then there exist v, w such that uv = xw. Thus XA * is right F -dense.

(ii) implies (iii). Consider a word u ∈ F . Let us show that u is a prefix of X * . Since XA * is right F -dense, one has uw = xw ′ for some word x ∈ X and w, w ′ ∈ A * . If u is a prefix of X, there is nothing to prove. Otherwise, x is a proper prefix of u. Thus u = xu ′ for some x ∈ X and u ′ ∈ A * . Since u is in F and since F is factorial, we have u ′ ∈ F . Since x = 1, we have |u ′ | < |u|. Arguing by induction, the word u ′ is a prefix of X * . Thus u is a prefix of X * .

(iii) implies (i). Let u ∈ F . Then u is a prefix of X * , and consequently u is prefix-comparable with a word in X.

The propositions have a dual formulation, replacing prefix by suffix, and right by left. The following is a generalization of Propositions 3.7.1 and 3.7.2 in [START_REF] Berstel | Codes and Automata[END_REF]. Proposition 3.3.4 Let F be a right essential set. Let δ be a positive right probability distribution on F . Any prefix code

X ⊂ F satisfies δ(X) ≤ 1. If X is finite, it is F -maximal if and only if δ(X) = 1.
Proof. Assume first that X is finite. Let n be the maximal length of the words in X. We have

x∈X xA n-|x| ∩ F ⊂ A n ∩ F (3.2)
and the terms of the union are pairwise disjoint. Thus, using Equation (2.3)

δ(X) = x∈X δ(xA n-|x| ∩ F ) ≤ δ(A n ∩ F ) = 1 . (3.3)
If X is maximal in F , any word in F ∩ A n has a prefix in X. Thus we have equality in (3.2) and thus also in (3.3). This shows that δ

(X) = 1. The converse is clear since δ is positive on F . If X is infinite, then δ(Y ) ≤ 1 for any finite subset Y of X. Thus δ(X) ≤ 1.
The statement has a dual for a suffix code included in a factorial set F with a positive left probability distribution on F . Example 3.3.5 Let F be the Fibonacci set. The set X = {a, ba} is a maximal prefix code (Example 3.3.3). One has δ F (X) = 1 where δ F is defined in Example 2.4.6.

We will use the following result in the proof of Proposition 4.4.5. Proposition 3.3.6 Let F be a right essential subset of A * , and let G ⊂ F be a right essential subset of F . For any finite F -maximal prefix code

X ⊂ F , the set X ∩ G is a finite G-maximal prefix code. Proof. Set Y = X ∩ G.
The set Y is clearly a finite prefix code. We show that every u ∈ G is prefix-comparable with some word in Y . This will imply that Y is G-maximal by Proposition 3.3.1. Let u ∈ G. Since G is right essential, there are arbitrary long words w such that uw ∈ G. Choose the length of uw larger than the maximal length of the words of X. Since X is an

F -maximal prefix code, uw has a prefix x in X. This prefix x is in Y since uw ∈ G. Thus u is prefix-comparable to x ∈ Y .
The following example shows that Proposition 3.3.6 is false for infinite prefix codes.

Example 3.3.7 Let F ⊂ A * be a right essential set with F = A * , and let x be a word which is not in F . Let X = A * x \ A * xA + be the prefix code of words in A * ending with x and having no other occurrence of x. X is a maximal prefix code, and X ∩ F = ∅ is not F -maximal.

We will use later the following result on transformations of prefix codes. It is adapted from Proposition 3.4.9 in [START_REF] Berstel | Codes and Automata[END_REF].

Proposition 3.3.8 Let F be a factorial set and let X ⊂ F be an F -maximal prefix code. Let w be a nonempty prefix of X and set D

= w -1 X. The set Y = (X \ wD) ∪ w is an F -maximal prefix code. Proof. It is clear that Y is a prefix code.
To show that it is F -maximal, we apply Proposition 3.3.1 and prove that every word u ∈ F is prefix-comparable with a word of Y . So consider a word u ∈ F . Since X is F -maximal, u is prefixcomparable with a word of X. Thus u is prefix-comparable with a word of X \ wD or it is prefix-comparable with a word of wD. In the second case, either u is a prefix of a word wd with d ∈ D or u has wd as a prefix. Consequently, u is prefix-comparable with w. This proves that u is prefix-comparable with a word of Y . Proposition 3.3.8 has a dual formulation for suffix codes.

Average length

Let F be a right essential set and let δ be a right probability distribution on F . Let X ⊂ F be a prefix code such that δ(X) = 1. The average length of X with respect to δ is the sum

λ(X) = x∈X |x|δ(x) .
Proposition 3.4.1 Let F be a right essential set and let δ be a positive right probability distribution on F . Let X ⊂ F be a finite F -maximal prefix code and let P be the set of proper prefixes of X. Then δ(X) = 1 and λ(X) = δ(P ).

Proof. We already know that δ(X) = 1 by Proposition 3.3.4. Let us show that for any p ∈ P ,

δ(p) = x∈pA + ∩X δ(x) . (3.4)
Let indeed n be an integer larger than the lengths of the words of X. Then by Equation (2.3), δ(p) = δ(pA n ∩ F ). Since X is an F -maximal prefix code, each word of pA n ∩ F has a prefix in X, and conversely, each word in X which has p as a prefix is itself a prefix of pA n ∩ F . Thus

pA n ∩ F = x∈pA + ∩X xA n+|p|-|x| ∩ F . Since δ(xA n+|p|-|x| ∩ F ) = δ(x), this proves Equation (3.4). By Equation (3.4), one gets p∈P δ(p) = p∈P x∈pA + ∩X δ(x) = x∈X p∈P :x∈pA + δ(x) = x∈X |x|δ(x) .
Thus

δ(P ) = p∈P δ(p) = x∈X |x|δ(x) = λ(X) .
A dual statement of Proposition 3.4.1 holds for a suffix code and its set of proper suffixes, for a positive left probability distribution.

Example 3.4.2 Let F be the Fibonacci set and let X = {a, ba}. We have already seen in Example 3.3.5 that X is an F -maximal prefix code and that δ F (X) = 1 where δ F is the unique invariant probability distribution on F defined in Example 2.4.6. We have λ(X) = λ + 2(1λ) = 2λ. On the other hand the set of proper prefixes of X is P = {1, b} and thus δ

F (P ) = 1 + (1 -λ) = 2 -λ.

Bifix codes in recurrent sets

In this section, we study bifix codes contained in a recurrent set. Since A * itself is a recurrent set, it is a generalization of the usual situation. We will see that all results on maximal bifix codes can be generalized in this way. In particular, the notions of degree, of kernel and of derived code can be defined in this more general framework.

Parses

Recall that a set X of nonempty words is a bifix code if any two distinct elements of X are incomparable for the prefix order and for the suffix order.

A parse of a word w with respect to a set X is a triple (v, x, u) such that w = vxu with v ∈ A * \ A * X, x ∈ X * and u ∈ A * \ XA * . Proposition 4.1.1 Let F be a factorial set and let X ⊂ F be a set. For any factorization w = uv of w ∈ F , there is a parse (s, yz, p) of w with y, z ∈ X * , sy = u and v = zp.

Proof. Since v ∈ F , there exist, by Proposition 3.1.1, words z ∈ X * and p ∈ A * \ XA * such that v = zp. Symmetrically, there exist y ∈ X * and s ∈ A * \ A * X such that u = sy. Then (s, yz, p) is a parse of w which satisfies the conditions of the statement.

The number of parses of a word w with respect to X is denoted by π X (w). The function π X : A * → N is the parse enumerator with respect to X.

The indicator of a set X is the series

L X defined for w ∈ A * by (L X , w) = π X (w). Example 4.1.2 Let X = ∅. Then π X (w) = |w| + 1.
The following is a reformulation of Proposition 6.1.6 in [START_REF] Berstel | Codes and Automata[END_REF].

Proposition 4.1.3 Let F be a factorial set and let X ⊂ F be a prefix code. For every word w ∈ F , the number π X (w) is equal to the number of prefixes of w which have no suffix in X.

Proof. For every prefix v of w which is in A * \ A * X, there is a unique parse of w of the form (v, x, u). Since any parse is obtained in this way, the statement is proved. Proposition 4.1.3 has a dual statement for suffix codes. Note that, as a consequence of Proposition 4.1.3, we have for two prefix codes X, Y , and for all words w,

X ⊂ Y ⇒ π Y (w) ≤ π X (w). (4.1)
Indeed, a word without suffix in Y is also a word without suffix in X.

Proposition 4.1.4 Let X be a prefix code and let The following is Proposition 6.1.11 in [START_REF] Berstel | Codes and Automata[END_REF].

V = A * \ A * X. Then V = L X (1 -A) . (4.2) If X is bifix, one has 1 -X = (1 -A)L X (1 -A) . ( 4
Proposition 4.1.5 A function π : A * → N is the parse enumerator of some bifix code if and only if it satisfies the following conditions.

(i) For any a ∈ A and w

∈ A * 0 ≤ π(aw) -π(w) ≤ 1 . (4.4) (ii) For any w ∈ A * and a ∈ A 0 ≤ π(wa) -π(w) ≤ 1 . (4.5) (iii) For any a, b ∈ A and w ∈ A * π(aw) + π(wb) ≥ π(w) + π(awb) . (4.6) (iv) π(1) = 1 .
The following is a reformulation of Proposition 6.1.12 in [START_REF] Berstel | Codes and Automata[END_REF].

Proposition 4.1.6 Let X be a prefix code. For any u ∈ A * and a ∈ A, one has

π X (ua) = π X (u) if ua ∈ A * X π X (u) + 1 otherwise (4.7)
Proof. This follows directly from Proposition 4.1.3.

Proposition 4.1.6 has a dual for suffix codes expressing π X (au) in terms of π X (u).

Recall also that by Proposition 6.1.8 in [START_REF] Berstel | Codes and Automata[END_REF], for a bifix code X and for all u, v, w ∈ F such that uvw ∈ F , one has

π X (v) ≤ π X (uvw). (4.8)
Moreover, if uvw ∈ X and u, w ∈ A + then the inequality is strict, that is,

π X (v) < π X (uvw). (4.9)

Maximal bifix codes

Let F be set of words. A set X ⊂ F is said to be thin in F , or F -thin, if there exists a word of F which is not a factor of a word in X.

The following example shows that there exist a uniformly recurrent set F , and a bifix code X ⊂ F which is not F -thin.

if ū ∈ F . Consider the set X = {x n x n | n ≥ 1}. We have X ⊂ F . Indeed, for n ≥ 1, x n+2 = x n+1 xn+1 = x n xn xn x n implies that xn xn ∈ F and thus x n x n ∈ F . Next X is a bifix code.
Indeed, for n < m, x m begins with x n xn , and thus cannot have x n x n as a prefix. Similarly, since x m ends with xn x n or with x n xn , it cannot have x n x n as a suffix. Finally any element of F is a factor of a word in X. Indeed, any element u of F is a factor of some x n , and thus of x n x n ∈ X.

A simpler proof uses Theorem 4.4.3 proved later.

An internal factor of a word x is a word v such that x = uvw with u, w nonempty. Let F ⊂ A * be a factorial set and let X ⊂ F be a set. Denote by

I(X) = {w ∈ A * | A + wA + ∩ X = ∅}
the set of internal factors of words in X. 1When F is right essential and left essential, then X is F -thin if and only if

F \ I(X) = ∅. Indeed, the condition is necessary. Conversely, if w is in F \ I(X), let a, b ∈ A be such that awb ∈ F . Since awb cannot be a factor of a word in X, it follows that X is F -thin.
We say that a bifix code

X ⊂ F is maximal in F , or F -maximal, if it is not properly contained in any other bifix code Y ⊂ F .
The following is a generalisation of Proposition 6.2.1 in [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.2.2 Let F be a recurrent set and let X ⊂ F be an F -thin set. The following conditions are equivalent.

(i) X is an F -maximal bifix code. (ii) X is a left F -complete prefix code. (ii') X is a right F -complete suffix code.
(iii) X is an F -maximal prefix code and an F -maximal suffix code.

As a preparation for the proof of Theorem 4.2.2, we introduce the following notation. Let F be a recurrent set and let X ⊂ F .

A factorization of a word u is a pair (p, s) of words such that u = ps. We denote by Fact(u) the set of factorizations of u.

Let C(X, F ) be the set of pairs (u, v) of words such that uvu ∈ F , v = 1 and u is not an internal factor of X. We define for each pair (u, v) ∈ C(X, F ) a relation ϕ u,v on the set Fact(u) as follows. For π = (p, s), ρ = (q, t) ∈ Fact(u), one has (π, ρ) ∈ ϕ u,v if and only if the pair (π, ρ) satisfies one of the following conditions (see Figure 4.1).

(i) px = q for some x ∈ X, (ii) svq = x 1 • • • x n with n ≥ 1 and x i ∈ X for 1 ≤ i ≤ n, s is a proper prefix of x 1 and q is a proper suffix of x n . Since ps = qt, the condition (i) is equivalent to s = xt. This means that both conditions are symmetric for reading from left to right or from right to left.

x 1 x 2 • • • x n-1 x n u v q t u p s Figure 4.1: The relation ϕ u,v (case (ii)).
We prove a series of lemmas concerning the relations ϕ u,v (see Exercise 6.2.1 in [START_REF] Berstel | Codes and Automata[END_REF]).

Lemma 4.2.3 Let F be a recurrent set and let X ⊂ F be an F -thin set. If X is a prefix code, then for all pairs

(u, v) ∈ C(X, F ), the relation ϕ u,v is a partial function from Fact(u) into itself, that is (π, ρ), (π, ρ ′ ) ∈ ϕ u,v ⇒ ρ = ρ ′ . (4.10)
Conversely, if X is an F -maximal suffix code, and if (4.10) holds for all pairs (u, v) ∈ C(X, F ), then X is a prefix code.

Define the transpose ϕ ′ u,v of the relation ϕ u,v by the condition (ρ, π) ∈ ϕ ′ u,v if (π, ρ) ∈ ϕ u,v . Then (4.10) expresses the fact that the transpose ϕ ′ u,v is injective.

Proof. Assume first that X is a prefix code. For (u, v) ∈ C(X, F ), let π = (p, s), ρ = (q, t), ρ ′ = (q ′ , t ′ ) be three factorizations of u such that (π, ρ), (π, ρ ′ ) ∈ ϕ u,v . We prove that ρ = ρ ′ . By definition, the following cases may occur for (π, ρ), (π, ρ ′ ) .

(1) px = q and px ′ = q ′ , with x, x ′ ∈ X, (2) px = q with x ∈ X, and

svq ′ = x ′ 1 • • • x ′ m , with m ≥ 1 and x ′ 1 , . . . , x ′ m ∈ X, and moreover s is a proper prefix of x ′ 1 and q ′ is a proper suffix of x ′ m , (3) px ′ = q ′ with x ′ ∈ X and svq = x 1 • • • x n , with n ≥ 1 and x 1 , . . . , x n ∈ X,
and moreover s is a proper prefix of x 1 and q is a proper suffix of x n , (4

) svq = x 1 • • • x n and svq ′ = x ′ 1 • • • x ′ m , with n ≥ 1, m ≥ 1, x 1 , . . . , x n , x ′ 1 , . . . , x ′ m ∈ X,
and moreover s is a proper prefix both of x 1 and of x ′ 1 , q is a proper suffix of x n and q ′ is a proper suffix of x ′ m . (1) Assume that px = q, px ′ = q ′ , with x, x ′ ∈ X. Since q and q ′ are prefixes of u, they are prefix-comparable. Thus x and x ′ are also prefix-comparable. Since X is a prefix code, it follows that x = x ′ , whence q = q ′ and ρ = ρ ′ .

(2) We show that this case is impossible. Indeed, x is a prefix of s (by ps = qt = pxt) and s is a proper prefix of x ′ 1 , thus x is a proper prefix of x ′ 1 , and this is impossible because X is a prefix code. The same argument holds in the symmetric case [START_REF] Bartholdi | Rational subsets of groups[END_REF].

(4) Since u = qt = q ′ t ′ , the words q and q ′ are prefix-comparable. We may suppose that q = q ′ w (see Figure 4.2). Since svq, svq ′ are in X * and X is a prefix code, we have w ∈ X * . Since X is a code, the decompositions

svq = x 1 • • • x n = svq ′ w = x ′ 1 • • • x ′ m w coincide. Consequently, w = x m+1 • • • x n . By hypothesis, q = q ′ w = q ′ x m+1 • • • x n is a proper suffix of x n . This forces n = m, w = 1 and q = q ′ , hence ρ = ρ ′ . u v p s q t u q ′ w Figure 4.2:
The factorizations (p, s), (q, t) and (q ′ , t ′ ) with t ′ = wt.

Conversely, assume that X is an F -maximal suffix code and that it is not a prefix code. Let x ′ , x ′′ be distinct words in X such that x ′ is a prefix of x ′′ . Set Since X is left F -complete, p is a proper suffix of a word in X. Since u / ∈ I(X), p is a prefix of u. Thus z = 1 = t or z ∈ X + . In the latter case, set z = z 1 • • • z n with z i ∈ X. Since ut = pz, one of the following two cases holds:

x ′′ = x ′ r ′ with r ′ = 1. Since X is F -thin, there is a word w ∈ F \ I(X). Since F is recurrent, there is a word r ′′ such that x ′′ r ′′ w ∈ F . Let u = r ′ r ′′ w. Then x ′′ r ′′ w = x ′ u ∈ F . Let t be a word such that utx ′ u ∈ F . Set v = tx ′ . Thus (u, v) ∈ C(X, F ) (see
(1) u = pz ′ , with z ′ , t ∈ X * , (2) there is an i with 1 ≤ i ≤ n such that z i = rs with u = pz 1 • • • z i-1 r, t = sz i+1 • • • z n , and r = 1, s = 1.
In case (1), consider the three factorizations π = (u, 1), ρ = (1, u), ρ ′ = (r ′ , r ′′ w) of u. Since r ′ = 1, we have ρ = ρ ′ . We have v = tx ′ ∈ X + , and thus (π, ρ) ∈ ϕ u,v (this is case (ii) of the definition with s = q = 1). Next, vr ′ = tx ′ r ′ = tx ′′ ∈ X + , with t ∈ X * and where r ′ is a proper suffix of x ′′ . Hence (π, ρ ′ ) ∈ ϕ u,v . Thus, ϕ u,v is not a partial function.

In case [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF], let π = (pz 1 • • • z i-1 , r) and let ρ, ρ ′ be as above. We have

rv = rtx ′ = rsz i+1 • • • z n x ′ ∈ X + , whence (π, ρ) ∈ ϕ u,v . Next, rvr ′ = rsz i+1 • • • z n x ′ r ′ = rsz i+1 • • • z n x ′′ ∈ X + , and r ′ is a proper suffix of x ′′ . Thus (π, ρ ′ ) ∈ ϕ u,v . Since ρ = ρ ′ , ϕ u,v is not a partial function. t r ′ r ′′ w x ′ x ′′ p z u v u Figure 4.3: ϕ u,v is not a partial function.
Lemma 4.2.3 has a dual formulation for suffix codes: if X is a suffix code, then for all pairs (u, v) ∈ C(X, F ), the relation ϕ u,v is injective: if (π, ρ), (π ′ , ρ) ∈ ϕ u,v , then π = π ′ . Conversely, if X is an F -maximal prefix code, and if this implication holds for all pairs (u, v) ∈ C(X, F ), then X is a suffix code.

Recall that a set X ⊂ F is right F -complete if any word of F is a prefix of X * . Lemma 4.2.4 Let F be a recurrent set and let X ⊂ F be an F -thin set. The set X is right F -complete if and only if, for all pairs (u, v) ∈ C(X, F ), the relation ϕ u,v contains a total function from Fact(u) into itself, that is for every

π ∈ Fact(u), there exists ρ ∈ Fact(u) such that (π, ρ) ∈ ϕ u,v . Proof. Assume first that X is right F -complete. Let u, v ∈ F be such that (u, v) ∈ C(X, F ). Let π = (p, s) ∈ Fact(u)
. Suppose first that s has a prefix x in X. Let s = xt, with x ∈ X. Thus u = ps = pxt. Let q = px and ρ = (q, t). Then (π, ρ) ∈ ϕ u,v . Suppose next that s has no prefix in X. Since X is right F -complete, there exists a word w such that svuw

= x 1 • • • x m , with x 1 , . . . , x m ∈ X.
Let n be the smallest integer such that sv is a prefix of

x 1 • • • x n , 1 ≤ n ≤ m.
Let q be the prefix of uw such that svq = x 1 • • • x n . Since sv = 1, q is a proper suffix of x n . The word q is a prefix of u since u is not an internal factor of X. Define the factorization ρ = (q, t) of u by svq = x 1 • • • x n . Since s has no prefix in X, the word s is a proper prefix of x 1 . Therefore, (π, ρ) ∈ ϕ u,v . This shows that ϕ u,v contains a total function.

Conversely, assume that for all (u, v) ∈ C(X, F ), the relation ϕ u,v contains a total function from Fact(u) into itself. We show that any u ∈ F is prefixcomparable with a word of X. By Proposition 3.3.2, this implies that X is right F -complete.

Let u ∈ F . Since X is F -thin, the set F \I(X) is nonempty. Let w ∈ F \I(X) and let v be such that uvw ∈ F . Set r = uvw. Note that r ∈ F \I(X). Let z = 1 be such that rzr ∈ F . Then (r, z) ∈ C(X, F ). Set π = (1, r). Since ϕ r,z contains a total function, there is a factorization ρ = (q, t) of r such that (π, ρ) ∈ ϕ r,z . If q ∈ X, then r has the prefix q in X, the word u is prefix-comparable with q, and we obtain the conclusion. Otherwise, we have uvwzq = x 1 • • • x n with x i ∈ X and uvw is a prefix of x 1 , whence our conclusion again. Lemma 4.2.4 has a dual formulation for left F -complete sets: the set X is left F -complete if and only if, for all pairs (u, v) ∈ C(X, F ), the transpose of the relation ϕ u,v contains a total function from Fact(u) into itself. Proposition 4.2.5 Let F be a recurrent set and let X ⊂ F be an F -thin and Fmaximal prefix code. Then X is a suffix code if and only if it is left F -complete.

Proof. Since X is an F -maximal prefix code, by Lemmas 4.2.3 and 4.2.4, for any pair (u, v) ∈ C(X, F ), the relation ϕ u,v is a total function from Fact(u) into itself.

Assume first that X is a suffix code. Then, by the dual of Lemma 4.2.3, for any pair (u, v) ∈ C(X, F ), the function ϕ u,v from Fact(u) into itself is injective. Since Fact(u) is a finite set, ϕ u,v is also surjective for any pair (u, v) ∈ C(X, F ). This implies by the dual of Lemma 4.2.4 that X is left F -complete.

Assume conversely that X is left F -complete. By the dual of Lemma 4.2.4, the function ϕ u,v maps Fact(u) onto itself for every pair (u, v) ∈ C(X, F ). This implies as above that it is also injective. By the dual of Lemma 4.2.3, and since X is an F -maximal prefix code, X is a suffix code. Proposition 4.2.5 has a dual formulation for an F -maximal suffix code.

Proof of Theorem 4.2.2. We first show that (i) implies (ii). If X is an F -maximal suffix code, then X is left F -complete and thus condition (ii) is true. Assume next that X is an F -maximal prefix code. Since X is suffix, by Proposition 4.2.5, it is left F -complete and thus (ii) holds. Finally assume that X is neither an F -maximal prefix code nor an F -maximal suffix code. Let y, z ∈ F be such that X ∪ y is prefix and X ∪ z is suffix. Since F is recurrent, there is a word u such that yuz ∈ F . Then X ∪ yuz is bifix and thus we get a contradiction.

The proof that (i) implies (ii') is similar.

(ii) implies (iii). Consider the set Y = X \ A + X. It is a suffix code by defi- nition. It is prefix since it is contained in X. It is left F -complete. Indeed, one has A * X = A * Y and thus A * Y is left F -dense by the dual of Proposition 3.3.2.
Hence Y is an F -maximal suffix code. By the dual of Proposition 4.2.5, the set Y is right F -complete. Thus Y is an F -maximal prefix code. This implies that X = Y and thus that X is an F -maximal prefix code and an F -maximal suffix code.

The proof that (ii') implies (iii) is similar. It is clear that (iii) implies (i).

Example 4.2.6 Let A = {a, b} and let F be the set of words without factor bb (Example 2.1.2). The set X = {aaa, aaba, ab, baa, baba} is a finite F -maximal bifix code. As an example of computation of the relation ϕ u,v , note that for u = aaa and v = b, we have Fact(u) = {π 1 , π 2 , π 3 , π 4 } with π 1 = (1, aaa), π 2 = (a, aa), π 3 = (aa, a), π 4 = (aaa, 1). The function ϕ u,v is the cycle (π 1 π 4 π 3 ) and fixes π 2 .

The following example shows that Theorem 4.

2.2 is false if F is not recurrent. Example 4.2.7 Let F = a * b * . Then X = {aa, ab, b} is an F -maximal prefix code.
It is not a suffix code but it is left F -complete as it can be easily verified.

Let F ⊂ A * be a factorial set. The F -degree, denoted d F (X), of a set X ⊂ A * is the maximal number of parses of words of F with respect to X, that is

d F (X) = max w∈F π X (w) .
The F -degree of a set X is finite or infinite. The A * -degree is called the degree, and is denoted d(X). Observe that

d F (X) = d F (X ∩ F ), and that d F (X) ≤ d(X).
The following is a generalization of Theorem 6.3.1 in [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.2.8 Let F be a recurrent set and let X ⊂ F be a bifix code. Then X is an F -thin and F -maximal bifix code if and only if its F -degree d F (X) is finite. In this case,

I(X) = {w ∈ F | π X (w) < d F (X)} . (4.11)
Proof. Assume first that X is an F -thin and F -maximal bifix code. Since X is F -thin, F \I(X) is not empty. Let u ∈ F \I(X) and w ∈ F . Since F is recurrent, there is a word v ∈ F such that uvw ∈ F . Since X is prefix, by Proposition 4.1.3, the number of parses of u is equal to the number of prefixes of u which have no suffix in X. Since X is left F -complete, the set of words in F which have no suffix in X coincides with the set S of words which are proper suffixes of words in X. Since u is not an internal factor of a word in X, any prefix of uvw which is in S is a prefix of u. Thus π X (uvw) = (S A * , uvw) = (S A * , u) = π X (u). Since by Equation (4.8), π X (w) ≤ π X (uvw), we get π X (w) ≤ π X (u). This shows that π X is bounded, and thus that the F -degree of X is finite. Moreover, this shows that F \ I(X) is contained in the set of words of F with maximal value of π X . Conversely, consider w ∈ I(X). Then there exists w ′ ∈ X and p, s ∈ A + such that w ′ = pws. Then by Equation (4.9) π X (w ′ ) > π X (w), and thus π X (w) is not maximal in F . This proves Equation (4.11).

Conversely, let w ∈ F be a word with π X (w) = d F (X). For any nonempty word u ∈ F such that uw ∈ F we have uw ∈ XA * . Indeed, set u = au ′ with a ∈ A and u

′ ∈ F . Then π X (au ′ w) ≥ π X (u ′ w) ≥ π X (w) by Equation (4.8). This implies π X (au ′ w) = π X (u ′ w) = π X (w)
. By the dual of Equation (4.7) we obtain that uw ∈ XA * . This implies first that X is F -thin and next that XA * is right F -dense. Indeed suppose that w is an internal factor of a word in X. Let p, s ∈ F \ 1 be such that pws ∈ X. Since pw ∈ F , the previous argument shows that pw ∈ XA * , a contradiction. Thus w ∈ F \ I(X). This shows that X is F -thin.

Next, and since F is recurrent, for any v ∈ F , there is a word u ∈ F such that vuw ∈ F . Then vuw ∈ XA * by using again the above argument. Thus XA * is right F -dense and X is an F -maximal bifix code by Theorem 4.2.2.

Example 4.2.9 Let F be the Fibonacci set. The set X = {a, bab, baab} is a finite bifix code. Since it is finite, it is F -thin. It is an F -maximal prefix code as one may check on Figure 2.1. Thus it is, by Theorem 4.2.2, an F -thin and F -maximal bifix code. The parses of the word bab are (1, bab, 1) and (b, a, b). Since bab is not in I(X), one has d F (X) = 2.

Example 4.2.10 Let F be the Fibonacci set. The set X = {aaba, ab, baa, baba} is a bifix code. It is F -maximal since it is right F -complete (see Figure 2.1). It has F -degree 3. Indeed, the word aaba has three parses (1, aaba, 1), (a, ab, a) and (aa, 1, ba) and it is in F \ I(X).

The following result establishes the link between maximal bifix codes and Fmaximal ones. Theorem 4.2.11 Let F be a recurrent set. For any thin maximal bifix code

X ⊆ A + of degree d, the set Y = X ∩ F is an F -thin and F -maximal bifix code. One has d F (Y ) ≤ d with equality when X is finite. Proof. Recall that d F (Y ) = d F (X ∩ F ) = d F (X) ≤ d. Thus d F (Y )
is finite and by Theorem 4.2.8, Y is an F -thin and F -maximal bifix code. If X is finite, then each word which is in F and is longer than the longest words in X has d parses.

Thus d F (X) = d, whence d F (Y ) = d.
Example 4.2.12 The set X = a ∪ ba * b is a maximal bifix code of degree 2. Let F be the Fibonacci set. Then X ∩ F = {a, baab, bab} (see Figure 2.1).

As another example, let Z = {a 3 , a 2 ba, a 2 b 2 , ab, ba 2 , baba, bab 2 , b 2 a, b 3 }. The set Z is a finite maximal bifix code of degree 3 (see [START_REF] Berstel | Codes and Automata[END_REF]). Then Z ∩ F = {a 2 ba, ab, ba 2 , baba} (see Figure 2.1).

Example 4.2.13 Let F be the Thue-Morse set. Consider again X = a ∪ ba * b. Then X ∩ F = {a, baab, bab, bb} is a finite F -maximal bifix code of F -degree 2 (see Figure 2.2).

The following examples show that a strict inequality can hold in Theorem 4.2.11. The second example shows that this may happen even if all letters occur in the words of F . Example 4.2.14 Let A = {a, b} and let X = a ∪ ba * b. The set X is a maximal bifix code of degree 2. Let F = a * . Then F is a recurrent set. We have

Y = X ∩ F = a. The F -degree of Y is 1.
Example 4.2.15 Let A = {a, b} and let X ⊂ A + be the maximal bifix code of degree 3 with kernel K = {aa, ab, ba}. Let F be the Fibonacci set. Since

K = A 2 ∩ F , K is an F -maximal bifix code. Since K ⊂ X ∩ F and K is F - maximal, one has X ∩ F = K. Next K = A 2 ∩ F and Theorem 4.2.11 imply that d F (K) = 2. Thus d(X) = 3 and d F (X ∩ F ) = 2.

Derivation

We first show that the notion of derived code can be extended to F -maximal bifix codes. The following result generalizes Proposition 6.4.4 in [START_REF] Berstel | Codes and Automata[END_REF].

The kernel of a set of words X is the set of words in X which are internal factors of words in X. We denote by K(X) the kernel of X. Note that K(X) = I(X) ∩ X.

Theorem 4.3.1 Let F be a recurrent set. Let X ⊂ F be a bifix code of finite

F -degree d ≥ 2. Set I = I(X) and K = K(X). Let G = (IA ∩ F ) \ I and D = (AI ∩ F ) \ I. Then the set X ′ = K ∪ (G ∩ D) is a bifix code of F -degree d -1.
The code X ′ is called the derived code of X with respect to F or F -derived code.

The proof uses two lemmas. Let P be the set of proper prefixes of X and let S be the set of proper suffixes of X. Proof. By Theorem 4.2.8, the parse enumerator of X is bounded on F and F \ I(X) = F \ I is the set of words in F with maximal value d F (X). Let y = ha be in G with h ∈ I and a ∈ A. Since y / ∈ I, we have π X (ha) > π X (h). Thus, by Proposition 4.1.6, y = ha does not have a suffix in X. Since A * X is left F -dense, this implies that y is a proper suffix of a word in X. Thus y is in S. The proof that D ⊂ P is symmetrical.

Lemma 4.3.3 For any x ∈ X \ K, the shortest prefix of x which is not in I is in X ′ .

Proof. Since x / ∈ K, we have x / ∈ I. Let x ′ be the shortest prefix of x which is not in I or, equivalently such that π X (x ′ ) = d F (X). Let us show that x ′ ∈ X ′ . First, x ′ is a proper prefix of x. Set indeed x = pa with p ∈ A * and a ∈ A. Since x ∈ X, we have by Equation (4.7), π X (x) = π X (p). Thus p ∈ I and x ′ is a prefix of p.

Since 1 ∈ I, we have

x ′ = 1. Set x ′ = p ′ a ′ with p ′ ∈ A * and a ′ ∈ A. By definition of x ′ we have p ′ ∈ I. Thus x ′ ∈ G = (IA ∩ F ) \ I.
Next, set x ′ = a ′′ s with a ′′ ∈ A and s ∈ A * . Since x ′ / ∈ XA * , we have by the dual of Equation (4.7), π X (s) < π X (x ′ ). Thus s is in I. This shows that x ′ ∈ D. Thus we conclude that

x ′ ∈ G ∩ D ⊂ X ′ .
There is a dual of Lemma 4.3.3 concerning the shortest suffix of a word in X \ K. Proof of Theorem 4.3.1.

We first prove that X ′ is a prefix code. Suppose first that k ∈ K is a prefix of a word z in G ∩ D. By Lemma 4.3.2, a word in D is a proper prefix of X. Thus k ∈ X would be a proper prefix of X, which is impossible since X is prefix.

Suppose next that a word u of G ∩ D is a prefix of a word k in K. Since k is in I, it follows that u is in I, a contradiction.

Finally, no word y ∈ G∩D can be a proper prefix of another word y ′ in G∩D, otherwise y ′ = yz, with z ∈ A + . Therefore, since G ⊂ S by Lemma 4.3.2, there is t ∈ A + such that ty ′ = tyz ∈ X. Consequently, y ∈ G ∩ I, a contradiction.

Thus X ′ is a prefix code. To show that it is F -maximal, it is enough to show that any word in X has a prefix in X ′ .

Consider indeed x ∈ X. If x is in K then x ∈ X ′ . Otherwise, let x ′ be the shortest prefix of x which is not in I. By Lemma 4.3.3, we have x ′ ∈ X ′ .

Thus X ′ is an F -maximal prefix code.

A symmetric argument shows that X ′ is an F -maximal suffix code. Let us show that d F (X ′ ) = d F (X)-1. We first note that G∩D = ∅. Indeed, let x ∈ X be such that π X (x) is maximal on X. If x were an internal factor of a word y ∈ X, then by Equation (4.9) π X (x) < π X (y) which contradicts our assumption. Thus x / ∈ K. This shows that K is not an F -maximal bifix code and thus that

X ′ \ K = G ∩ D = ∅. Consider x ′ ∈ G ∩ D. Since (G ∩ D) ∩ I(X)
is empty, and since I(X ′ ) ⊂ I(X), x ′ cannot be in I(X ′ ). Thus the number of parses of x ′ with respect to X ′ is d F (X ′ ).

Let P ′ be the set of proper prefixes of X ′ . We show that x ′ has d F (X) -1 suffixes which are in P ′ . This will show that d F (X ′ ) = d F (X) -1 by the dual of Proposition 4.1.3.

Since x ′ ∈ F \ I, we have π X (x ′ ) = d F (X). Thus x ′ has d F (X) suffixes in P . One of them is x ′ itself since x ′ ∈ D ⊂ P . Let p be a proper suffix of x ′ which is in P . Let us show that p does not have a prefix in X ′ . Indeed, arguing by contradiction, assume that x ′′ ∈ X ′ is a prefix of p. We cannot have x ′′ ∈ K since p is a proper prefix of a word in X. We cannot have either x ′′ ∈ G ∩ D. Indeed, since x ′ is in AI, p is in I and thus also x ′′ ∈ I. Thus p cannot have a prefix in X ′ . Since X ′ is an F -maximal prefix code, this implies that p is a proper prefix of X ′ . Thus, the d F (X) -1 proper suffixes of x ′ which are in P are in P ′ . Example 4.3.4 Let F be the Fibonacci set. Let X = {a, bab, baab}. The set X is an F -thin and F -maximal bifix code of F -degree 2 (see Example 4.2.9). We have K = {a}, I = {1, a, aa}, G = {b, ab, aab} and D = {b, ba, baa}. Thus X ′ = {a, b}.

The following is a generalization of Proposition 6.3.14 in [START_REF] Berstel | Codes and Automata[END_REF].

Proposition 4.3.5 Let F be a recurrent set. Let X ⊂ F be a bifix code of F -degree d ≥ 2. Let S be the set of proper suffixes of X and set I = I(X). The set S \ I is an F -maximal prefix code and the set S ∩ I is the set of proper suffixes of the derived code X ′ .

The proof uses the following lemma. Lemma 4.3.6 Let F be a recurrent set. Let X ⊂ F be an F -thin and Fmaximal bifix code. Let S be the set of proper suffixes of X and set I = I(X). For any w ∈ F \ I the longest prefix of w which is in S is not in I.

Proof. Let s be the longest prefix of w which is in S. Set w = st. Let us show that for any prefix t ′ of t, we have π X (st ′ ) = π X (s). It is true for t ′ = 1. Assume that it is true for t ′ and let a ∈ A be the letter such that t ′ a is a prefix of t. Since st ′ a / ∈ S, we have st ′ a ∈ A * X. Thus by Equation (4.7), this implies π X (st ′ a) = π X (st ′ ). Thus π X (st ′ a) = π X (s). We conclude that π X (st) = π X (s). Since w = st is in F \ I, and since F \ I is the set of words in F with maximal value of π X , this implies that s ∈ F \ I.

This lemma has a dual statement for the longest suffix of a word in w ∈ F \ I which is in P . Let us now show that the set S ′ of proper suffixes of the words of X ′ is S ∩ I. Let s be a proper suffix of a word Conversely, let s be in S ∩ I. Let x ∈ X be such that s is a proper suffix of x. If x is in K then x is in X ′ and thus s is in S ′ . Otherwise, let y be the shortest suffix of x which is in not in I. By the dual of Lemma 4.3.3, the word y is in X ′ . Then s is a proper suffix of y (since s ∈ I and y / ∈ I) and therefore s is in S ′ .

x ′ ∈ X ′ . If x ′ ∈ K, then s is in S ∩ I. Suppose next that x ′ ∈ G ∩ D.
There is a dual version of Proposition 4.3.5 concerning the set of proper prefixes of an F -thin and F -maximal bifix code X ⊂ F .

The following property generalizes Theorem 6.3.15 in [START_REF] Berstel | Codes and Automata[END_REF].

S ′ \ 1 is a disjoint union of d -2 F -maximal prefix codes. Thus S \ 1 = Y ∪ (S ′ \ 1) is a disjoint union of d -1 F -maximal prefix codes.
The following generalizes Corollary 6.3.16 in [START_REF] Berstel | Codes and Automata[END_REF], with two restrictions. First, it applies only in the case of finite maximal bifix codes instead of thin bifix codes (in order to be able to use Proposition 3.3.4). Next, it applies only for recurrent sets such that there exists a positive invariant probability distribution (in order to be able to use Proposition 3.4.1).

Y i ) = 1 for 1 ≤ i ≤ d -1. Thus λ(X) = d.
Example 4.3.9 Let F be the Fibonacci set and let X = {a, bab, baab} (Example 4.3.4). The set X is an F -maximal bifix code of F -degree 2. With respect to the unique invariant probability distribution of F (Example 2.4.6), we have

λ(X) = λ + 3(2 -3λ) + 4(2λ -1) = 2.
Now we show that an F -thin and F -maximal bifix code is determined by its F -degree and its kernel. We first prove the following generalization of Proposition 6.4.1 from [START_REF] Berstel | Codes and Automata[END_REF]. Proposition 4.3.10 Let F be a recurrent set. Let X ⊂ F be a bifix code of finite F -degree d and let K be the kernel of X. Let Y be a set such that K ⊂ Y ⊂ X. Then for all w ∈ I(X) ∪ Y , π Y (w) = π X (w).

(4.12)

For all w ∈ F , π X (w) = min{d, π Y (w)}. (4.13)

Proof. Denote by F (w) the set of factors of the word w. Notice that Equation (4.3) is equivalent to L X = A * (1 -X )A * . Thus, to prove (4.12), we have to show that for any w ∈ I(X)∪Y one has F (w)∩X = F (w)∩Y . The inclusion

F (w) ∩ Y ⊂ F (w) ∩ X is clear. Conversely, if w is in I(X), then F (w) ∩ X ⊂ K and thus F (w) ∩ X ⊂ F (w) ∩ Y .
Next, assume that w is in Y . The words in F (w) ∩ X other than w are all in K. Thus we have again F (w) ∩ X ⊂ F (w) ∩ Y .

To show Equation (4.13), assume first that w ∈ I(X). Then π X (w) < d by Theorem 4.2.8. Moreover, π X (w) = π Y (w) by Equation (4.12). Thus Equation (4.13) holds. Next, suppose that w ∈ F \ I(X). Then π X (w) = d. Since Y ⊂ X, we have π X (w) ≤ π Y (w) by Equation (4.1). This proves (4.13). Proposition 4.3.10 will be used to prove the following generalization of Theorem 6.4.2 in [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.3.11 Let F be a recurrent set and let X ⊂ F be a bifix code of finite F -degree d. For any w ∈ F , one has

π X (w) = min{d, π K(X) (w)} .
In particular X is determined by its F -degree and its kernel.

Proof. Take Y = K(X) in Proposition 4.3.10. Then the formula follows from Equation (4.13). Next X is determined by L X , and so by π X , through Equation (4.3).

We now state the following generalization of Theorem 6.4.3 in [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.3.12 Let F be a recurrent set. A bifix code Y ⊂ F is the kernel of some bifix code of finite F -degree d if and only if

(i) Y is not an F -maximal bifix code, (ii) max{π Y (y) | y ∈ Y } ≤ d -1.
Proof. Let X be an F -thin and F -maximal bifix code of F -degree d and let Y = K(X) be its kernel. Condition (i) is satisfied because X = Y implies that X is equal to its derived code which has F -degree d -1. Moreover, for every y ∈ Y one has π X (y) ≤ d -1. Since π X (y) = π Y (y) by Equation (4.12), condition (ii) is also satisfied. Conversely, let Y ⊂ F be a bifix code satisfying conditions (i) and (ii). Let π : A * → N be the function defined by

π(w) = min{d, π Y (w)}.
It can be verified that the function π satisfies the four conditions of Proposition 4.1.5. Thus π is the parse enumerator of a bifix code Z. Let X = Z ∩ F . Then π X and π have the same restriction to F . Since π is bounded on F , the same holds for π X . This implies that the code X is an F -thin and F -maximal bifix code by Theorem 4.2.8. Since the code Y is not an F -maximal bifix code, the

F -parse enumerator π Y is not bounded. Consequently max{π(w) | w ∈ F } = d,
showing that X has F -degree d. Let us prove finally the Y is the kernel of X. Since, by condition (ii), max{π

Y (y) | y ∈ Y } ≤ d -1, we have Y ⊂ I(X).
Moreover, for w ∈ I(X) we have π

X (w) = π Y (w). Let L (resp. L Y ) be the indicator of X (resp. of Y ). Since 1 -X = (1 -A )L(1 -A ) and 1 -Y = (1 -A )L Y (1 -A ) by Equation (4.
3), we conclude that for w ∈ I(X), we have (X , w) = (Y , w). This implies that if w ∈ I(X), then w is in

X if and only if w is in Y . Thus K(X) = I(X) ∩ X = I(X) ∩ Y = Y and Y is the kernel of X.

Finite maximal bifix codes

The following generalizes Theorem 6.5.2 of [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.4.1 For any recurrent set F and any integer d ≥ 1 there is a finite number of finite F -maximal bifix codes X ⊂ F of F -degree d.

Proof. The only F -maximal bifix code of F -degree 1 is F ∩ A. Arguing by induction on d, assume that there are only finitely many finite F -maximal bifix codes of F -degree d. Each finite F -maximal bifix code X ⊂ F of F -degree d + 1 is determined by its kernel which is a subset of its derived code X ′ . Since X ′ is a finite F -maximal bifix code of F -degree d, there are only a finite number of kernels and we are done.

Example 4.4.2 Let A = {a, b} and let F be the set of words without factor bb. There are two finite F -maximal bifix codes of F -degree 2, namely the code {aa, ab, ba} with empty kernel and the code {aa, aba, b} with kernel b. The code of F -degree 2 with kernel a is a ∪ ba + b, and thus is infinite.

The following result shows that the case of a uniformly recurrent set contrasts with the case F = A * since in A * , as soon as Card(A) ≥ 2, there exist infinite maximal bifix codes of degree 2 and thus of all degrees d ≥ 2; see e.g. [6, Example 6.4.7] for degree 2 and [6, Theorem 6.4.6] for the general case.

Theorem 4.4.3 Let F be a uniformly recurrent set. Any F -thin bifix code X ⊂ F is finite. Any finite bifix code is contained in a finite F -maximal bifix code.

Proof. Let X ⊂ F be an F -thin bifix code. Since X is F -thin, there exists a word w ∈ F \ I(X). Since F is uniformly recurrent there is an integer r such that w is factor of every word in F r = F ∩ A r . Assume F k ∩ X = ∅ for some k ≥ r + 2, and let x ∈ F k ∩ X. Set x = pqs, with q ∈ F r ∩ I(X), and p, s nonempty. Then w is factor of q, hence w is in I(X), a contradiction. We deduce that each x in X has length at most r + 1. Thus X is finite.

Let X ⊂ F be a finite bifix code which is not F -maximal. Let d = max{π X (x) | x ∈ X}. By Theorem 4.3.12, X is the kernel of an F -thin and F -maximal bifix code Z ⊂ F of F -degree d + 1. By the previous argument, Z is finite. By Theorem 6.6.1 of [START_REF] Berstel | Codes and Automata[END_REF], any rational bifix code is contained in a maximal rational bifix code. We have seen that the situation is simpler for bifix codes in uniformly recurrent sets.

Example 4.4.4 Let F be the Fibonacci set. Let X = {a, bab}. Then X is contained in the bifix code {a, bab, baab} which has F -degree 2 (see Figure 4.4). It is also the kernel of {a, baabaab, baababaab, bab} which is a bifix code of Fdegree 3 (see Table 5.1).

The following is a generalization of Proposition 6.2.10 in [START_REF] Berstel | Codes and Automata[END_REF]. The equality d(Y ) = d(X) is stated as a comment following Proposition 6.3.9 in [6, page 243], in a more general framework. Proposition 4.4.5 Let F be a recurrent set, let X ⊂ F be a finite F -maximal bifix code and let w be a nonempty word in F . Let G = Xw -1 , and D = w -1 X.

If G = ∅ , D = ∅ , and Gw ∩ wD = ∅ , then the set Y = (X ∪ w ∪ (GwD ∩ F )) \ (Gw ∪ wD) (4.14)
is a finite F -maximal bifix code with the same F -degree as X.

We use in the proof the following proposition which is an extension of Corollary 3.4.7 of [START_REF] Berstel | Codes and Automata[END_REF]. Proposition 4.4.6 Let F be a recurrent set and let X ⊂ F be a F -maximal prefix code. Let X = X 1 ∪ X 2 be a partition of X into two prefix codes and let Y be a finite prefix code such that Y

∩ x -1 F is x -1 F -maximal for all x ∈ X 2 . Then the set Z = X 1 ∪ (X 2 Y ∩ F ) is an F -maximal prefix code.
Proof. We first prove that Z is a prefix code. Let z and z ′ be distinct words in Z. We show that they are not prefix-comparable. Since X 1 is a prefix code, this holds if both words are in X 1 . Assume next that z ∈ X 2 Y . Then z = xy with x ∈ X 2 and y ∈ Y .

If z ′ is in X 1 , then z ′ and x are not prefix-comparable because they are distinct since z ′ ∈ X 1 and x ∈ X 2 , and so z and z ′ are not prefix-comparable.

If z ′ ∈ X 2 Y , set z ′ = x ′ y ′ with x ′ ∈ X 2 and y ′ ∈ Y . Either x and x ′ are not prefix-comparable, and then so are z and z ′ , or x = x ′ . In the latter case, y and y ′ are not prefix-comparable because Y is a prefix code, and again z and z ′ are not prefix-comparable. Thus Z is a prefix code.

Let us show that Z is F -maximal. Let u ∈ F . Since X is an F -maximal prefix code, there is an x ∈ X which is prefix-comparable with u. If x is in X 1 , then x ∈ Z and thus u is prefix-comparable with a word of Z. Otherwise, we have x ∈ X 2 .

Suppose first that u is a prefix of x. Since Y is a finite x -1 F -maximal prefix code, it is not empty and u is a prefix of xv for every v ∈ Y ∩ x -1 F .

Suppose next that u = xv for some word v. Since v is in x -1 F and since Y ∩x -1 F is an x -1 F -maximal prefix code, the word v is prefix-comparable with some y ∈ Y ∩ x -1 F . Thus u is prefix-comparable with xy ∈ Z.

Proof of Proposition 4.4.5. The condition G = ∅ ( resp. D = ∅) means that w is a suffix of X (resp. a prefix of X). The condition Gw ∩ wD = ∅ implies that w is not in X.

By Theorem 4.2.2, the set X is an F -maximal prefix code. By Proposition 3.3.8, the set Y 1 = (X ∪ w) \ wD is an F -maximal prefix code. Next, we have

Y = (Y 1 \ Gw) ∪ (GwD ∩ F ).
We show that Y is an F -maximal prefix code, by applying Proposition 4.4.6. Indeed, consider the partition

Y 1 = X 1 ∪ X 2 with X 1 = Y 1 \ Gw and X 2 = Gw. Then Y = X 1 ∪ (X 2 D ∩ F ).
Clearly D is a finite w -1 F -maximal prefix code. Since (gw) -1 F is a subset of w -1 F for all g ∈ G, the set D ∩ (gw) -1 F is a finite (gw) -1 F -maximal prefix code for all g ∈ G by Proposition 3.3.6, So the claim follows from by Proposition 4.4.6. This proves that Y is an F -maximal prefix code. Since Y it is also a suffix code, it follows that Y is an F -maximal bifix code by Theorem 4.2.2. To show that X and Y have the same degree, consider a word u ∈ F which is not an internal factor of X nor Y . Such a word exists since X and Y are finite. Let P (resp. Q) be the set of proper prefixes of the words of X (resp. Y ). We define a bijection ϕ between the set P (u) of suffixes of u which are in P and the set Q(u) of suffixes of u which are in Q. This will imply that d F (X) = d F (Y ) by the dual of Proposition 4.1.3.

Let p ∈ P be a suffix of u and set u = rp. If w is not a prefix of p, then p is in Q. Otherwise, set p = ws. Since the words in P starting with w are all prefixes of wD, the word s is a proper prefix of D. Since G is an F w -1 -maximal suffix code, r is suffix-comparable with a word of G. If r is a proper suffix of G, then urws is an internal factor of GwD, a contradiction. Thus r has a suffix g ∈ G. This suffix is unique because G is a suffix code. Since gp = gws, the word gp is a proper prefix of GwD, and thus a proper prefix of Y . Thus gp ∈ Q(u). We set (see Figure 4.5)

ϕ(p) = p if p / ∈ wA * , gp if p ∈ wA * and g ∈ G is the suffix of r in G.
Thus ϕ maps P (u) into Q(u). We show that it is injective. Suppose that ϕ(p) = ϕ(p ′ ) for some p, p ′ ∈ P (u). Assume that ϕ(p) = gp and ϕ(p ′ ) = g ′ p ′ with g, g ′ ∈ G. Since p and p ′ start with w, the word gp = g ′ p ′ starts with the words gw and g ′ w which are in X. This shows that g = g ′ and thus p = p ′ . Assume next that p = g ′ p ′ with g ′ ∈ G and p ′ ∈ wA * . But then g ′ w is a prefix of p, with p in P and g ′ w in X, a contradiction. To show that ϕ is surjective, consider q ∈ Q(u). Assume first that q has a prefix x in X (see Figure 4.6). By Equation (4.14), one has x = gw and q = gws for some g ∈ G and s a proper prefix of the word d in D. Thus ws is a proper prefix of wD ⊂ X, and consequently ws is a proper prefix of X. Since ws is a suffix of q, it is a suffix of u. Thus ws ∈ P (u). Set u = rws. Then g is a suffix of r. Moreover ws ∈ wA * . Consequently ϕ(ws) = q.

Finally, if q has no prefix in X, then q is a proper prefix of X. Moreover, since q is a prefix of Y , either q is a proper prefix of w or q is not a prefix of wD. In both cases, w is not a prefix of q and therefore ϕ(q) = q. Thus ϕ is surjective.

The set Y defined by Equation (4.14), is said to be obtained from X by internal transformation (with respect to w). (i) it is closed under reversal, (ii) for each n, there is exactly one right-special word in F of length n, and this right-special word is strict.

Proof. If F = F (x) for some strict episturmian word, then the conclusions of the proposition hold.

Conversely, assume that F has the required properties. For each n, the reversal of the strict right-special word of length n is a strict left-special word. Since all these left-special words are prefixes one of the other, there is an infinite word x that such that all its prefixes are these strict left-special words. Clearly, F (x) ⊂ F . To show that x is strict episturmian, we verify that F (x) is closed under reversal. Let u ∈ F (x). Then u ∈ F . Since F is uniformly recurrent, there is an integer m such that u is a factor of the right-special word w of length m. Consequently the reversal u of u is a factor of the left-special word w of length m, and therefore is in F (x).

To prove that F ⊂ F (x), let u ∈ F . Since F is uniformly recurrent, there is an integer m such that u is a factor of the left-special word w of length m. Since w is a prefix of x, this shows that u ∈ F (x).

The following statement is a direct consequence of the previous proof. Proposition 5.1.2 Let F be a Sturmian set of words. There is a unique strict standard episturmian infinite word s such that F = F (s).

As a consequence of Proposition 5.1.2, for every left-special word w of a Sturmian set F , exactly one of the words wa, for a ∈ A, is left-special in F . Symmetrically, for every right-special word w in F , exactly one of the words aw for a ∈ A is right-special in F . More generally, for every n ≥ 1 there is exactly one word u of length n such that uw is a right-special word in F . Proof. Let indeed u ∈ F . Since F is uniformly recurrent, there is an integer n such that u is a factor of any word in F of length n. Let w be the right-special word of length n. Then u is a factor of w, thus w = pus for some words p, s. Since w is right-special, its suffix us is also right-special. Thus u is a prefix of a right-special word.

The following example shows that for a Sturmian set F , there exists bifix codes X ⊂ F which are not F -thin (we have seen such an example for a uniformly recurrent but not Sturmian set in Example 4.2.1).

Example 5.1.4 Let F be a Sturmian set. Consider the following sequence (x n ) n≥1 of words of F . Set x 1 = a, for some a ∈ A.

Suppose inductively that x 1 , . . . , x n have been defined in such a way that X n = {x 1 , x 2 , . . . , x n } is bifix and not F -maximal bifix. Define x n+1 as follows. By Theorem 4.2.2, X n is not right F -complete, thus there is a word u in F which is incomparable for the prefix order with the words of X n . By Proposition 5.1.3, the word u is a prefix of a right special word v in F . Symmetrically, since X n is not an F -maximal bifix code, there is a word w ∈ F which is incomparable with the words of X n for the suffix order. Since F is recurrent, there is a word t such that vatw ∈ F . Then we choose x n+1 = vatw.

The set X n+1 = X n ∪ x n+1 is a bifix code since x n+1 is incomparable with the words of X n for the prefix and for the suffix order. It is not an F -maximal prefix code since vb, for all letters b = a, is incomparable for the prefix order with the words of X n+1 : indeed, its prefix u is incomparable for the prefix order with all words in X n and vb is incomparable with x n+1 . Since it is finite, it is not an F -maximal bifix code by Theorem 4.2.2. The infinite set X = {x 1 , x 2 , . . .} is a bifix code included in F and it is not F -thin by Theorem 4.4.3.

Proposition 5.1.5 Let F be a Sturmian set and let X ⊂ F be a prefix code. Then X contains at most one left-special word. If X is a finite F -maximal prefix code, it contains exactly one left-special word.

Proof. Assume on the contrary that x, y ∈ X are two left-special words. We may assume that |x| < |y|. Let x ′ be the prefix of y of length |x|. Then x ′ is left-special and thus x, x ′ are two left-special words of the same length. This implies that x = x ′ . Thus x is a prefix of y. Since X is prefix, this implies x = y.

Assume now that X is a finite F -maximal prefix code. Let n be the maximal length of the words in X. Let u ∈ F be the left-special word of length n. Since XA * is right F -dense, there is a prefix x of u which is in X. Thus x is a leftspecial element of X. It is unique by the previous statement.

A dual of Proposition 5.1.5 holds for suffix codes and right-special words.

Cardinality

The following result shows that Theorem 4.4.3 can be made much more precise for Sturmian sets.

X ∩ F ) = d F (X) + 1 = d + 1.
The proof of Theorem 5.2.1 uses two lemmas.

Lemma 5.2.3 Let F be a Sturmian set. Let X ⊂ F be a finite bifix code of finite F -degree d and let P be the set of proper prefixes of X. There exists a right-special word u ∈ F such that π X (u) = d. The d suffixes of u which are in P are the right-special words contained in P .

Proof. Let n ≥ 1 be larger than the length of the words of X. By definition, there is a right-special word u of length n. Then u is not a factor of a word of X. By Theorem 4.2.8 it implies that π X (u) = d F (X).

By the dual of Proposition 4.1.3, the word u has d F (X) suffixes which are in P . They are all right-special words. Furthermore, any right-special word p contained in P is a suffix of u. Indeed, the suffix of u of the same length than p is the unique right-special word of this length.

The next lemma is a well-known property of trees translated into the language of prefix codes. Let X be a prefix code or the set {1} and let P be the set of proper prefixes of X. For p ∈ P , let d(p) = Card{a ∈ A | pa ∈ P ∪ X}. Lemma 5.2.4 Let A be an alphabet with k letters. Let X ⊂ A * be a finite prefix code or the set {1} and let P be the set of proper prefixes of the words of X. Assume that for all p ∈ P ,

d(p) = k or 1. Let Q X = {p ∈ P | d(p) = k}. Then, Card(X) = (k -1) Card(Q X ) + 1.
Proof. Let us prove the property by induction on the maximal length n of the words in X. The property is true for n = 0 since in this case X = {1} and

P = Q X = ∅. Assume n ≥ 1. If 1 / ∈ Q X ,
then all words of X begin with the same letter a. We have then X = aY , Y is a prefix code or the set {1} and Card(Q

Y ) = Card(Q X ). Hence, by induction hypothesis Card(X) = Card(Y ) = (k -1) Card(Q Y ) + 1 = (k -1) Card(Q X ) + 1. Other- wise, X = ∪ a∈A aX a . Set t a = Card(Q Xa ). We have a∈A t a = Card(Q X ) -1. By induction hypothesis, Card(X a ) = (k -1)t a + 1. Therefore, Card(X) = a∈A Card(X a ) = a∈A (k -1)t a + k = (k -1) Card(Q X ) + 1.
Proof of Theorem 5.2.1. Let P be the set of proper prefixes of X. An element p of P satisfies pA ⊂ P ∪ X if and only it is right-special. Thus the conclusion follows directly by Lemmas 5.2. [START_REF] Bartholdi | Rational subsets of groups[END_REF] Example 5.2.6 We may illustrate the proof of Theorem 5.2.1 on the code X = {a, baab, babaabaabab, babaabab} (see Table 5.1). According to Lemma 5.2.3, the right-special word ababaaba (which is the reversal of the prefix abaababa of the Fibonacci word) has exactly three suffixes which are proper prefixes of words of X, namely 1, ba and babaaba (these are the "fork nodes", that is the nodes with two childred, indicated in black on Figure 5.1). This implies, by Lemma 5.2.4, that X has four elements.

The following example shows that Theorem 5.2.1 is not true for the set of factors of an episturmian word which is not strict.

Example 5.2.7 Set A = {a, b, c}. Let y be the Fibonacci word and let x = ψ c (y) be the infinite word of Example 2.3.7. It is an episturmian word which is not strict. Set F = F (x). Let ψ : A * → G be the morphism from A * onto the group G = (Z/2Z) 3 defined by ψ(a) = (1, 0, 0), ψ(b) = (0, 1, 0) and ψ(c) = (0, 0, 1). Let Z be the group code such that Z * = ψ -1 (0, 0, 0). Since G has 8 elements, the degree of Z is 8 (see Proposition 6.1.5 below). The bifix code X = Z ∩ F has 10 elements obtained by inserting c in two possible ways in the 5 words of the bifix code Z ∩ F (y). The latter has degree 4 by Theorem 5.2.1. The bifix code X = Z ∩ F is given in Figure 5.2. The numbering of the nodes is for later use, in Example 7.2.7. By Theorem 4.2.11, X is an F -maximal bifix code. Its F -degree is 8. Indeed, the word acbcacbc has 8 parses. Thus Theorem 5.2.1 is not true in this case.

As a consequence of Theorem 5.2.1, an internal transformation does not change the cardinality of a finite F -maximal bifix code for a Sturmian set F . Indeed, by Proposition 4.4.5, an internal transformation preserves the F -degree.

Actually, if Y is obtained from X by internal transformation with respect to w, we have

Y = (X ∪ w ∪ (GwD ∩ F )) \ (Gw ∪ wD) (5.1)
and

Card(Y ) = Card(X) + 1 + Card(GwD ∩ F ) -Card(G) -Card(D).
The fact that internal transformations preserve the cardinality can be proved directly by the following statement. This statement applies to the internal transformation (5.1) because Gw ∪ wD is a bifix code, which implies property (i) and DA * = w -1 XA * (resp. A * G = A * Xw -1 ) which implies property (ii) (resp. (iii)).

g ′ g g ′′ G d ′ D ′ g ′ g g ′′ G d ′ a d ′ b D

Periodicity

Let x = a 0 a 1 • • • , with a i ∈ A, be an infinite word. It is periodic if there is an integer n ≥ 1 such that a i+n = a i for all i ≥ 0. It is ultimately periodic if the equalities hold for all i large enough. Thus, x is ultimately periodic if there is a word u and a periodic infinite word y such that x = uy. The following result, due to Coven and Hedlund, is well-known (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], Theorem 1.3.13).

Theorem 5.3.1 Let x ∈ A N be an infinite word on an alphabet with k letters. If there exists an integer d ≥ 1 such that x has at most d + k -2 factors of length d then x is ultimately periodic.

We will prove a generalization of this result. Let x be an infinite word and let X be a thin maximal bifix code. Let u be a prefix of x and set x = uy. Since F (y) ⊂ F (x), one has

d F (y) (X) ≤ d F (x) (X). The word x is called X-stable if d F (y) (X) = d F (x) (X)
for all suffixes y of x. Let u be a prefix of x such that d F (y) (X) is minimal. Then the infinite word y is X-stable.

For example, if x = ba ω and X = a ∪ ba * b, then an X-stable suffix of x is a ω . Theorem 5.3.2 Let X be a thin maximal bifix code and let x ∈ A N be an X-stable infinite word. If Card(X ∩ F (x)) ≤ d F (x) (X), then x is ultimately periodic.

Corollary 5.3.3 Let x ∈ A N be an infinite word. If there exists a finite maximal bifix code X of degree d such that Card(X ∩ F (x)) ≤ d, then x is ultimately periodic.

Proof. Since any long enough word has d parses, d F (x) (X) = d and x is X-stable. Since Card(X ∩ F (x)) ≤ d, the conclusion follows by Theorem 5.3.2.

Corollary 5.3.3 implies Theorem 5.3.1 in the case k = 2 since A d is a maximal bifix code of degree d.

Example 5.3.4 Let us consider again the finite maximal bifix code X of degree 3 defined by X = {a 3 , a 2 ba, a 2 b 2 , ab, ba 2 , baba, bab 2 , b 2 a, b 3 } (see Example 4.2.12). Assume that X ∩ F = {a 2 ba, ab, baba}, where F = F (x) and x ∈ A N . Since ba is a factor of x, there exist a word u and an infinite word y such that x = ubay. Next, the first letter of y is b (otherwise, ba 2 ∈ X ∩ F ) and the second letter of y is a (otherwise, bab 2 ∈ X ∩ F ). This argument shows that whenever uba is a prefix of x then ubaba is also a prefix of x, i.e., x = u(ba) ω , with u ∈ A * .

Example 5.3.5 The set X = a ∪ ba * b is a maximal bifix code of degree 2. An argument similar to the previous one shows that any infinite word x ∈ A N such that X ∩ F (x) = {a, bab} belongs to the set a * (ba) ω . Thus it is ultimately periodic.

Corollary 5.3.6 Let x ∈ A N be an infinite word and let X be a thin maximal bifix code. Let y be an X-stable suffix of x and let F = F (y). If Card(X ∩ F ) ≤ d F (X), then x is ultimately periodic. Proof. By Theorem 5.3.2, the word y is ultimately periodic, and so is x.

The following example shows that Corollary 5.3.6 may become false if we replace F = F (y) by F = F (x) in the statement.

Example 5.3.7 Let X be the maximal bifix code of degree 4 on the alphabet A = {a, b, c} with kernel K = {a, b} 2 .

Let x = ccay where y is an infinite word without any occurrence of c. Then cca has no factor in X. Indeed, a word of X of length at most 3 is in the kernel of X and thus is not a factor of cca. Thus cca has 4 parses with respect to X, namely (1, 1, cca), (c, 1, ca), (cc, 1, a) and (cca, 1, 1). Thus we have d F (x) (X) = 4. On the other hand X ∩ F (x) ⊂ {a, b} 2 and thus Card(X ∩ F (x)) ≤ d F (x) (x) although x need not be ultimately periodic. This shows that we cannot replace F (y) by F (x) in the statement of Corollary 5.3.6.

The proof uses the Critical Factorization Theorem (see [START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Crochemore | Two-way string-matching[END_REF]) that we recall below. For a pair of words (p, s) = (1, 1), consider the set of nonempty words r such that

A * p ∩ A * r = ∅, sA * ∩ rA * = ∅ .
This is the set of nonempty words r which are prefix-comparable with s and suffix-comparable with p. This set is nonempty since it contains r = sp. The repetition rep(p, s) is the minimal length of such a nonempty word r.

Let w = a 1 a 2 • • • a m be a word with a i ∈ A. An integer n ≥ 1 is a period of w if for 1 ≤ i ≤ j ≤ m, j -i = n implies a i = a j .
Recall that a factorization of a word w ∈ A * is a pair (p, s) of words such that w = ps. Theorem 5.3.8 (Critical Factorization Theorem) For any word w ∈ A + , the maximal value of rep(p, s) for all factorizations (p, s) of w is the least period of w.

We will also use the following lemma. Lemma 5.3.9 Let x be an infinite word and n ≥ 1 be an integer such that the least period of an infinite number of prefixes of x is at most n. Then x is periodic.

Proof. Since the least period of an infinite number of prefixes of x is at most n, an infinity of them have the same least period. Let p be such that an infinite number of prefixes of x have least period p. Set x = a 0 a 1 • • • with a i ∈ A. For each i ≥ 0, there is a prefix of x of length larger than i + p with least period p. Thus a i = a i+p . This shows that x is periodic.

Proof of Theorem 5.3.2. Let S = A * \ A * X and P = A * \ XA * . Set F = F (x) and d = d F (X). Since Card(X ∩ F ) ≤ d F (X) ≤ d(X), the set X ∩ F is finite. Since x is X-stable,
there are an infinite number of factors and therefore also of prefixes of x which have d parses with respect to X. Indeed, for any factorization x = uy, we have d F (y) (X) = d and thus y has a factor which has d parses, so it has a prefix w with d parses, and finally uw is a prefix of x with d parses.

Let n be the maximal length of the words in X ∩ F . Let u be a prefix of x of length larger than n which has d parses and set x = uy. Let w be a nonempty prefix of y and set y = wz. Let v be a prefix of z of length larger than n which has d parses.

Let (p, s) be a factorization of w. We show that rep(p, s) ≤ n.

Since up has d parses with respect to X, there are d suffixes p 1 , p 2 , . . . , p d of up which are in P . We may assume that p 1 = 1. Similarly, there are d prefixes s 1 , s 2 , . . . , s d of sv which are in S. We may assume that s 1 = 1.

Since upsv has d parses, for each p i with 2 ≤ i ≤ d there is exactly one s j with 2 ≤ j ≤ d such that p i s j ∈ X. Indeed, there is a prefix s ′ of sv such that p i s ′ ∈ X. Since s ′ must be one of the s j , the conclusion follows.

We may renumber the s i in such a way that p i s i ∈ X for 2 ≤ i ≤ d. Set x i = p i s i . Since up / ∈ S, we have up ∈ A * X. Let x 0 be the word of X which is a suffix of up. Similarly, let x 1 be the word of X which is a prefix of sv (see Figure 5.5).

x i u p s v u v x 0 x 1 Figure 5.5: The d + 1 words x 0 , x 1 , . . . , x d . Since Card(X ∩ F ) ≤ d, two of the d + 1 words x 0 , x 1 , . . . , x d are equal. If x 0 = x 1 , then rep(p, s) ≤ n. If x 0 = x i for an index i with 2 ≤ i ≤ d, then s i is a suffix of up (since it is a suffix of x 0 ) and a prefix of sv (by definition of s i ). Furthermore |s i | ≤ n (since n is the maximal length of the words of X ∩ F ). Thus rep(p, s) ≤ |s i | ≤ n.
The case where x i = x 1 for an index i with 2 ≤ i ≤ d is similar. Assume finally that x i = x j for some indices i, j such that 2 ≤ i < j ≤ d. We may assume that |p i | < |p j |. Thus p j = p i t, ts j = s i . As a consequence, t is both a suffix of up (since it is a suffix of p j ) and a prefix of sv (since it is a prefix of s i ). Thus again, rep(p, s) ≤ |t| ≤ n.

By the Critical Factorization Theorem, this implies that the least period of w is at most equal to n. Thus an infinite number of prefixes of y have least period at most n. By Lemma 5.3.9, it implies that y is periodic.

Bases of subgroups

In this section, we push further the study of bifix codes in Sturmian sets. The main result of Section 6.2 is Theorem 6.2.1. It states that a F -maximal bifix code X ⊂ F of F -degree d is a basis of a subgroup of index d of the free group on A. The proof uses two sets of preliminary results. The first part concerns bases of subgroups composed of words over A, already considered in [START_REF] Reutenauer | Une topologie du monoïde libre[END_REF]. The second one uses the first return words, which were introduced independently in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF], [START_REF] Holton | Descendants of primitive substitutions[END_REF], and which we use in the framework of [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF] and [START_REF] Vuillon | A characterization of Sturmian words by return words[END_REF], up to a leftright symmetry (see also [START_REF] Araújo | Words derivated from Sturmian words[END_REF]).

We denote by A • the free group generated by A. The rank of A • is Card(A). Note that all sets generating a free group of rank k have at least k elements. A basis is a minimal generating set. All bases have exactly k elements (see e.g. [START_REF] Lyndon | Combinatorial group theory[END_REF]).

Let H be a subgroup of rank n and of index d of a free group of rank k.

Then n = d(k -1) + 1 . (6.1)
Formula (6.1) is called Schreier's Formula. The free monoid A * is viewed as embedded in A • . An element of the free group is represented by its unique reduced word on the alphabet A ∪ A -1 . The elements of the free monoid A * are themselves reduced words since they do not contain any letter in

A -1 . Thus A * is a submonoid of A • . The subgroup of A • generated by a subset X of A • is denoted X .
In any group G, the right cosets of a subgroup H are the sets of the form Hg for g ∈ G. Two right cosets of the same subgroup are disjoint or equal. The index of a subgroup is the number of its distinct right cosets. If K is a subgroup of the subgroup H, then the index of K in G is the product of the index of K in H and of the index of

H in G. If H, K are two subgroups of index d of a group G, then H ⊂ K implies H = K.
Assume now that G is a group of permutations over a set Q. For any q in Q, the set of elements of G that fixes q is a subgroup of G.

The group G is transitive if, for all p, q ∈ Q, there is an element g ∈ G such that pg = q. In this case, the subgroup H of permutations fixing a given element p of Q has index Card(Q). Indeed, for each q ∈ Q let g q be an element of G such that pg q = q. If g ∈ G is such that pg = q, then pgg -1 q = p and consequently gg -1 q ∈ H, whence g ∈ Hg q . Thus each g ∈ G is in one of the right cosets Hg q , for q ∈ Q. Since these right cosets are pairwise disjoint, the index of H is Card(Q).

Group automata

A simple automaton A = (Q, 1, 1) is said to be reversible if for any a ∈ A, the partial map ϕ A (a) : p → p • a is injective. This condition allows to construct the reversal of the automaton as follows: whenever q • a = p in A, then p • a = q in the reversal automaton. The state 1 is the initial and the unique terminal state of this automaton. Any reversible automaton is minimal [START_REF] Reutenauer | Une topologie du monoïde libre[END_REF]. The set recognized by a reversible automaton is a left and right unitary submonoid. Thus it is generated by a bifix code.

An automaton A = (Q, 1, 1) is a group automaton if for any a ∈ A the map ϕ A (a) : p → p • a is a permutation of Q. When Q is finite, a group automaton is a reversible automaton which is complete.

The following result is from [START_REF] Reutenauer | Une topologie du monoïde libre[END_REF] (see also Exercise 6.1.2 in [START_REF] Berstel | Codes and Automata[END_REF]).

Proposition 6.1.1 Let X ⊂ A + be a bifix code. The following conditions are equivalent.

(i) X * = X ∩ A * ;

(ii) the minimal automaton of X * is reversible.

Let A = (Q, i, T ) be a deterministic automaton. A generalized path is a sequence (p 0 , a 1 , p 1 , a 2 , . . . , p n-1 , a n , p n ) with a i ∈ A ∪ A -1 and p i ∈ Q, such that for 1 ≤ i ≤ n, one has p i-1 •a i = p i if a i ∈ A and p i •a -1 i = p i-1 if a i ∈ A -1 .
The label of the generalized path is the element a 1 a 2 • • • a n of the free group A • . Note that if A = (Q, 1, 1), the set of labels of generalized paths from 1 to 1 in A is a subgroup of A • . It is called the subgroup described by A.

A path in an automaton is a particular case of a generalized path. In the case where A has a unique terminal state which is equal to the initial state, the submonoid of A * recognized by A is contained in the subgroup of A • described by A. For any subgroup H of A • , the submonoid H ∩ A * is right and left unitary. Thus H ∩ A * is generated by a bifix code. Proposition 6.1.3 Let A be a simple automaton and let X be the prefix code generating the submonoid recognized by A. The subgroup described by A is generated by X.

Proof. Set H = X . Let K be the subgroup described by A. Let us show that

K = H. First, X ⊂ K implies X = H ⊂ K. To prove the converse inclusion, let h = a 1 a 2 • • • a n ∈ K with a i ∈ A ∪ A -1 .
Let r be the number of indices i such that a i ∈ A -1 . We show by induction on r that h ∈ H. This holds clearly if r = 0. Assume that it is true for r -1. Let i be the least index such that a

i ∈ A -1 . Set u = a 1 • • • a i-1 , a = a -1 i , v = a i+1 • • • a n in
such a way that h = ua -1 v. Set also p = 1 • u and define q ∈ Q by q • a = p. Since A is trim there exist words w, t ∈ A * such that p • t = 1 and 1 • w = q. Since 1 • ut = 1 • wat = 1 • wv (see Figure 6.1), we have ut, wat ∈ X * . By induction hypothesis, we have wv ∈ H. Then ua -1 v = utt -1 a -1 w -1 wv = ut(wat) -1 wv is in H and thus h ∈ H. Thus K ⊂ H and this completes the proof that K = H. A subgroup H of A • is positively generated if there is a set X ⊂ A * which generates H. In this case, the set H ∩ A * generates the subgroup H. Let X be the bifix code which generates the submonoid H ∩ A * . Then X generates the subgroup H. This shows that, for a positively generated subgroup H, there is a bifix code which generates H. Proposition 6.1.4 For any positively generated subgroup H of A • , there is a unique reversible automaton A such that H is the subgroup described by A.

Proof. Let X be the bifix code generating the submonoid H ∩ A * , so that X * = H ∩ A * . Since H is positively generated, the subgroup generated by X is equal to H, that is X = H. Thus X * = X ∩A * . In view of Proposition 6.1.1, the minimal automaton A of X * is reversible.

If B is another reversible automaton such that H is the subgroup described by B, then B recognizes the set H ∩ A * . Since B is minimal and since minimal automata are unique, the uniqueness follows.

The submonoid recognized by A is H ∩ A * . Thus the last assertion follows.

The reversible automaton A such that H is the subgroup described by A is called the Stallings automaton of the subgroup H. It can also be defined for a subgroup which is not positively generated (see [START_REF] Bartholdi | Rational subsets of groups[END_REF] or [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF]). Proposition 6.1.5 The following conditions are equivalent for a submonoid M of A * .

(i) M is recognized by a group automaton with d states.

(ii) M = ϕ -1 (K), where K is a subgroup of index d of a group G and ϕ is a surjective morphism from A * onto G.

(iii) M = H ∩ A * , where H is a subgroup of index d of A • .
If one of these conditions holds, the minimal generating set of M is a maximal bifix code of degree d.

Proof. (i) implies (ii). Let A = (Q, 1, 1) be a group automaton with d states and let M be the set recognized by A. Since a composition of permutations is a permutation, the monoid G = ϕ A (A * ) is a permutation group. Since A is trim, there is a path from every state q to any state q ′ in A. Consequently, G is transitive. Let K be the subgroup of G formed of the permutations fixing 1. As we have seen earlier, K has index d. Then M = ϕ -1 A (K). (ii) implies (iii). Let ψ be the morphism from A • onto G extending ϕ. Then H = ψ -1 (K) is a subgroup of index d of A • and M = H ∩ A * . (iii) implies (i). Let Q be the set of right cosets of H with 1 denoting the right coset H. The representation of A • by permutations on Q defines a group automaton A with d states and M is recognized by A.

Finally, let X be the minimal generating set of a submonoid M satisfying one of these conditions. It is clearly a bifix code. Let P be the set of proper prefixes of X. The number of suffixes of a word which are in P is at most equal to d. Indeed, let A = (Q, 1, 1) be a group automaton recognizing X * . If s, t are distinct suffixes of a word w which are in P , then 1 • s = 1 • t. Indeed, otherwise, since s and t are suffix-comparable, we may assume that s = ut. Let p = 1 • u.

Then p • t = 1 • ut = 1 • s = 1 • t and thus p = 1 since A is reversible. Thus s = t.
Let w be a word with the maximal number of suffixes in P . Then w cannot be an internal factor of X. Moreover the number of suffixes of w in P is equal to d. Indeed, since A is a group code, for any q ∈ Q, there is a state q ′ such that q ′ • w = q. Since w is not an internal factor of X, there is a factorization Proof. The set A d is a group code (see Example 6.1.7), and therefore is a maximal bifix code. The set A d ∩ F is a finite bifix code. By Theorem 4.2.11, it is an F -maximal bifix code and has F -degree d. The corollary follows from Theorem 6.2.1. Indeed

A d ∩ F = A d since both are subgroups of A • of index d.
The following is also a complement to Theorem 4.2.11. Corollary 6.2.3 Let F be a Sturmian set. The map which associates to X ⊂ F the subgroup X of A • generated by X is a bijection between F -maximal bifix codes of F -degree d and subgroups of A • of index d. Such a bifix code X is a basis of X . The reciprocal bijection associates, to a subgroup H of A • , the set Z ∩ F where Z is the group code which is the minimal generating set of the submonoid H ∩ A * of A * .

Proof. Let first X be a finite F -maximal bifix code of F -degree d. Then X is a subgroup of index d by Theorem 6.2.1.

Conversely, let H be a subgroup of index d of A • and let Z be the group code such that Z * = H ∩ A * . By Theorem 4.2.11, the set X = Z ∩ F is an F -maximal bifix code of F -degree e ≤ d. By Theorem 4.4.3, X is finite. By Theorem 6.2.1, the subgroup X has index e. Since X is a subgroup of H, e is a multiple of d. Thus d = e and X = H.

Finally, let X be an F -maximal bifix code of F -degree d. Then H = X is a subgroup of index d of A • . Let Z be the group code such that Z * = H ∩ A * and let Y = Z ∩ F . Then X ⊂ Y and thus X = Y since X is an F -maximal bifix code. This shows that the two maps are mutually inverse.

A set W of words of {a, b} * is balanced if for all w, w ′ ∈ W , |w| = |w ′ | implies ||w| a -|w ′ | a | ≤ 1.
It is a classical property that the set of factors of a Sturmian word is balanced (Theorem 2.1.5 in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]). Thus any Sturmian set on two letters is balanced.

Following Richomme and Séébold [START_REF] Richomme | On factorially balanced sets of words[END_REF], we say that a subset X of {a, b} * is factorially balanced if the set of factors of words of X is balanced. They show that a finite set X ⊂ {a, b} * is contained in some Sturmian set if and only if it is factorially balanced. Thus, we have the following consequence of Theorem 6.2.1. Corollary 6.2.4 Let X ⊂ {a, b} * be a bifix code. The following conditions are equivalent.

(i) There exists a Sturmian set F ⊂ {a, b} * such that X ⊂ F and X is a finite F -maximal bifix code. (ii) X is a factorially balanced basis of a subgroup of finite index of {a, b} • .

As a further consequence of Theorem 6.2.1, we have the following result. Corollary 6.2.5 Let F be a Sturmian set on an alphabet with k letters. The number N d,k of finite F -maximal bifix codes X ⊂ F of F -degree d satisfies N 1,k = 1 and

N d,k = d(d!) k-1 - d-1 i=1 [(d -i)!] k-1 N i,k .
The formula results directly from the formula, due to Hall [START_REF] Hall | Subgroups of finite index in free groups[END_REF], for the number of subgroups of index d in a free group of rank k.

The values for k = 2 are given by the recurrence

N d,2 = d d! - d-1 i=1 (d -i)!N i,2 .
The first values are The formula is known to enumerate also the indecomposable permutations on d + 1 elements (see [START_REF] Dress | Parametrizing the subgroups of finite index in a free group and related topics[END_REF], [START_REF] Ossona | Transitivity and connectivity of permutations[END_REF] and [START_REF] Cori | Indecomposable permutations, hypermaps and labeled Dyck paths[END_REF]).

Incidence graph

Let X be a set, let P be the set of its proper prefixes and S be the set of its proper suffixes. Set P ′ = P \ 1 and S ′ = S \ 1. The incidence graph of X is the undirected graph G defined as follows. The set of vertices is V = 1 ⊗ P ′ ∪ S ′ ⊗ 1. Similarly to the proof of Proposition 5.2.8, the tensor product notation is used to emphasize that V is made of two disjoint copies of P ′ and S ′ . The edges of G are the pairs {1 ⊗ p, s ⊗ 1}, for p ∈ P ′ and s ∈ S ′ , such that ps ∈ X.

Let C be a connected component of G, that is a maximal set of vertices connected by paths. The trace of C on P ′ is the set of p ∈ P ′ such that 1 ⊗ p ∈ C. Similarly, the trace of C on S ′ is the set of s ∈ S ′ such that The following lemma uses an argument similar to Lemma 5.2.4.

s ⊗ 1 ∈ C.
Lemma 6.3.2 Let v 1 , v 2 , . . . , v n+1 be words such that v i , v i+1 are not prefixcomparable for 1 ≤ i ≤ n. Let p i be the longest common prefix of v i , v i+1 , for 1 ≤ i ≤ n. If two of the v i are prefix-comparable, then two of the p i are equal.

Proof. Let V = {v 1 , . . . , v n+1 }, let P be the set of proper prefixes of V and let W = V \ P . The set W is the set of words of V which have no proper prefix in V . The set W is a prefix code. If two distinct words in V are prefix-comparable, then Card(W ) < Card(V ) ≤ n + 1.

Let m be the number of distinct p i . Since v i , v i+1 are not prefix-comparable for 1 ≤ i ≤ n, for each p i there are at least two distinct letters a, b such that p i a, p i b ∈ P ∪ W . This implies m < Card(W ). Indeed, the set W can be seen as the set of leaves in a tree, and each p i is a fork node (i. e. a node with at least two children) in this tree. It is well-known that the number of fork nodes is strictly less than the number of leaves. If two of the v i are prefix-comparable, the inequality Card(W ) < n + 1 implies m < Card(W ) ≤ n, and consequently two of the p i are equal. Lemma 6.3.3 Let F be a Sturmian set and let X ⊂ F be a bifix code. Let P ′ (resp. S ′ ) be the set of nonempty proper prefixes (resp. suffixes) of X and let G be the incidence graph of X.

(i) The graph G is acyclic, that is a union of trees.

(ii) The trace on P ′ (resp. on S ′ ) of a connected component C of G is a suffix (resp. prefix) code. (iii) In particular, this trace on P ′ (resp. on S ′ ) contains at most one rightspecial (resp. left-special) word.

Proof. The last assertion follows from the second by Proposition 5.1.5. We call a path reduced if it does not use equal consecutive edges. We prove by induction on n ≥ 1 that if s ⊗ 1 and t ⊗ 1 (resp. 1 ⊗ p and 1 ⊗ q) are connected by a reduced path of length 2n in G, then s, t are not prefix-comparable (resp. p, q are not suffix-comparable). This shows that G is acyclic. Indeed, if there were a cycle from s to t = s in G, then s and t would be prefix-comparable. This shows also that two words in the same trace on P ′ (resp. on S ′ ) are not suffix-comparable (resp. are not prefix-comparable).

s q t s u 1 v 2 . . . v n u n t Figure 6
.4: A path (s ⊗ 1, 1 ⊗ q, t ⊗ 1) on the left, and a path of length 2n on the right.

The property holds for n = 1. Indeed, a reduced path of length 2 from s ⊗ 1 to t ⊗ 1 is of the form (s ⊗ 1, 1 ⊗ q, t ⊗ 1) with qs, qt ∈ X. Since the path is reduced, s = t, and since X is prefix, s and t are not prefix-comparable, see Figure 6.4. The proof for prefixes is similar.

Let n ≥ 2. A path of length 2n from s

⊗ 1 to t ⊗ 1 is a sequence (v 1 ⊗ 1, 1 ⊗ u 1 , v 2 ⊗ 1, . . . , 1 ⊗ u n , v n+1 ⊗ 1) with s = v 1 and t = v n+1 such that the 2n words defined for 1 ≤ i ≤ n by x 2i-1 = u i v i , x 2i = u i v i+1 .
are in X. Moreover, since the path is reduced, one has x j = x j+1 for 1 ≤ j < 2n.

For 1 ≤ i ≤ n, let p i be the longest common prefix of v i , v i+1 . Since x 2i-1 = x 2i and since the code X is prefix, the words v i and v i+1 are not prefix-comparable.

Arguing by contradiction, assume that v 1 and v n+1 are prefix-comparable. By Lemma 6.3.2, we have p i = p j for some indices i, j with 1 ≤ i < j ≤ n.

Set v i = p i v ′ i and v i+1 = p i v ′′ i . Since v i , v i+1 are not prefix-comparable, the words v ′ i , v ′′ i are nonempty. Since their longest common prefix is empty, their initial letters are distinct. Thus u i p i is right-special. Similarly u j p j is rightspecial. Thus u i p i and u j p j are suffix-comparable. Since p i = p j , u i and u j are suffix-comparable. But 1 ⊗ u i and 1 ⊗ u j are connected by the path (1

⊗ u i , v i+1 ⊗ 1, . . . , v j ⊗ 1, 1 ⊗ u j ) of length 2(j -i) ≤ 2(n -1)
. By the induction hypothesis, u i and u j are not suffix-comparable, a contradiction.

The proof that if 1 ⊗ p and 1 ⊗ q are connected by a path of length 2n in G, then p, q are not suffix-comparable is similar.

Let X be a bifix code and let P be the set of proper prefixes of X. Consider the equivalence θ X on P which is the transitive closure of the relation formed by the pairs p, q ∈ P such that ps, qs ∈ X for some s ∈ A + . Such a pair corresponds, when p, q = 1, to a path (1 ⊗ p, s ⊗ 1, 1 ⊗ q) in the incidence graph of X. Thus a class of θ X is either reduced to the empty word or it is the trace on P \ 1 of a connected component of the incidence graph of X. The following property relates the equivalence θ X with the right cosets of H = X . Proposition 6.3.5 Let X be a bifix code, let P be the set of proper prefixes of X and let H be the subgroup generated by X. For any p, q ∈ P , p ≡ q mod θ X implies Hp = Hq. Example 6.5.1 Let F be the Fibonacci set. The sets R F (u) and R ′ F (u) are given below for the first small words of F . Vuillon has shown in [START_REF] Vuillon | A characterization of Sturmian words by return words[END_REF] that x is a Sturmian word if and only if R ′ F (u) has exactly two elements for every factor u of x. Another proof of this result is given by Justin and Vuillon in [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF].

In fact, they show in [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF] the following theorem. Since this result is not exactly formulated in [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF] as stated here, we show how it follows easily from their article. Theorem 6.5.2 Let F be a Sturmian set. For any word u ∈ F , the set R F (u) (and the set R ′ F (u)) is a basis of the free group A • . By Equation (6.2), the sets R F (u) and R ′ F (u) are conjugate in the free group. Conjugacy by an element u is an automorphism of the free group. It follows that R F (u) is a basis if and only if R ′ F (u) is a basis. Thus, it suffices to prove the claim for R ′ F (u). We quote the following result of [32, Theorem 4.4, Corollaries 4.1 and 4.5], with the notations of Section 2.3. Proposition 6.5.3 Let s be a standard strict episturmian word over A, let ∆ = a 0 a 1 • • • be its directive word, and let (u n ) be its sequence of palindrome prefixes.

(i) The first left return words to u n are the words ψ a0•••an-1 (a) for a ∈ A.

(ii) For each factor u of s, there exist a word z and an integer n such that the first left return words to u are the words zyz -1 , where y ranges over the first left return words to u n .

Proof of Theorem 6.5.2. We may assume that F = F (s) for some standard and strict episturmian word s. By Proposition 6.5.3(i), the set of first left return words to u n is the image of the alphabet by the endomorphism ψ a0•••an-1 . It is easily seen that these endomorphisms define automorphisms of the free group. We deduce that the set of first left return words to u n is a basis of the free group on A. By Proposition 6.5.3(ii), the set of first left return words to u is a basis, too. This ends the proof.

Proof of the main result

Some preliminary results are needed for the proof of Theorem 6.2.1.

Proposition 6.6.1 Let F be a Sturmian set and let X ⊂ F be a finite Fmaximal bifix code. Then X ∩ F = X * ∩ F .

Any v ∈ V defines a permutation of Q. Indeed, suppose that for p, q ∈ Q, one has pv, qv ∈ Hr for some r ∈ Q. Then rv -1 is in Hp∩Hq. This forces Hp = Hq and thus p = q by Corollary 6.6.2. The set V is a subgroup of A • . Indeed, 1 ∈ V . Next, let v ∈ V . Then for any q ∈ Q, since v defines a permutation of Q, there is a p ∈ Q such that pv ∈ Hq. Then qv -1 ∈ Hp. This shows that v -1 ∈ V . Next, if v, w ∈ V , then Qvw ⊂ HQw ⊂ HQ and thus vw ∈ V .

We show that the set R F (u) is contained in V . Indeed, let q ∈ Q and y ∈ R F (u). Since q is a suffix of u, qy is a suffix of uy, and since uy is in F (by definition of Γ F (u)), also qy is in F . The fact that X is F -maximal implies that there is a word r ∈ P such that qy ∈ X * r. We verify that the word r is a suffix of u. Since y ∈ R F (u), there is a word y ′ such that uy = y ′ u. Consequently, r is a suffix of y ′ u, and in fact the word r is a suffix of u. Indeed, one has |r| ≤ |u| since otherwise u is in I(X) and this is not the case. Thus we have r ∈ Q (see Figure 6.7). Since X * ⊂ H and r ∈ Q, we have qy ∈ HQ. Thus y ∈ V . By Theorem 6.5.2, the group generated by R F (u) is A • . Since R F (u) ⊂ V , and since V is a subgroup of A • , we have V = A • . Thus Qw ⊂ HQ for any w ∈ A • . Since 1 ∈ Q, we have in particular w ∈ HQ. Thus A • = HQ. Since Card(Q) = d, and since the right cosets Hq for q ∈ Q are pairwise disjoint, this shows that H is a subgroup of index d. By Theorem 5.2.1 and in view of Schreier's Formula, X is a basis of H.

Assume conversely that the bifix code X ⊂ F is a basis of the group H = X and that X has index d. Since X is a basis, by Schreier's Formula, we have Card(X) = (k -1)d + 1, where k = Card(A). The case k = 1 is straightforward; thus we assume k ≥ 2. By Theorem 4.4.3, there is a finite F -maximal bifix code Y containing X. Let e be the F -degree of Y . By the first part of the proof, Y is a basis of a subgroup K of index e of A • . In particular, it has (k -1)e + 1 elements. Since X ⊂ Y , we have (k -1)d + 1 ≤ (k -1)e + 1 and thus d ≤ e. On the other hand, since H is included in K, d is a multiple of e and thus e ≤ d. We conclude that d = e and thus that X = Y . We end this section with a combinatorial consequence of Theorem 6.2.1. Proposition 6.6.4 Let F be a Sturmian set on an alphabet with k letters and let X ⊂ F be a finite F -maximal bifix code of F -degree d. Let P (resp. S) be the set of proper prefixes (resp. suffixes) of X. Then We will use the following proposition, of independent interest. Proposition 6.6.5 Let F be a Sturmian set and let X ⊂ F be a finite Fmaximal bifix code of F -degree d. The coset automaton B X is a group automaton with d states. Each state of B X other than 1 is an F -maximal suffix code.

Proof. Let A = (P, 1, 1) be the literal automaton of X * and let B = (R, 1, 1) be the coset automaton of X * . By Lemma 6.4.2, the automaton B is reversible and describes the subgroup H generated by X.

By Theorem 6.2.1, the subgroup H has index d in A • . Since B is reversible, it is minimal. Thus Proposition 6.1.6 applies, showing that B is a group automaton. Its number of states is d since a group automaton with d states describes a subgroup of index d.

Finally, consider r ∈ R and let X r = {p ∈ P | 1 • p = r}. Let us show that any w ∈ F is suffix-comparable with an element of X r . We may assume that w is longer than any word of X. Since B X is a group automaton, there is an u ∈ R such that u • w = r. Since w is longer than any word of X, the path from u to r labeled w passes through state 1. Thus w has a parse (s, x, p) such that 1 • p = r and thus w has a suffix in X r . This shows that X r is an F -maximal suffix code.

Note that the fact that the set P of nonempty proper prefixes of X is a disjoint union of d -1 F -maximal suffix codes is also a consequence of Theorem 4.3.7.

Proof of Proposition 6.6.4. Let H be the subgroup generated by X. By Theorem 6.2.1, the set X is a basis of H and the index of H is equal to d = d F (X). Let G be the incidence graph of X. Let E be the set of edges of G. One has

Card(E) = x∈X (|x| -1) = x∈X |x| -Card(X) = x∈X |x| -(k -1)d -1 .
By Proposition 6.6.5, the classes of θ X are the set {1} and d -1 F -maximal suffix codes denoted P i , for i = 1, . . . , d -1. Each of the latter is the trace on P \ 1 of a connected component C i of G. Let G i be the subgraph of G induced by its connected component C i . By Lemma 6.3.3, G i is a tree.

Similarly, let S i be the trace on S \ 1 of the connected component C i . Let E i be the set of edges of G i . Since G i is a tree, we have Card(

E i ) = Card(P i ) + Card(S i ) -1 for i = 1, . . . , d -1. Finally Card(E) = d-1 i=1 Card(E i ) = d-1 i=1 (Card(P i ) + Card(S i ) -1) = Card(P \ 1) + Card(S \ 1) -(d -1) ,
whence the result.

Syntactic groups

In this section, we introduce the notion of F -group of a bifix code X ⊂ F of finite F -degree. It is a permutation group of degree d F (X). We investigate the relation between this group and the notion of group of a maximal bifix code (Theorem 7.2.5). We use Theorem 6.2.1 to prove a new result on the syntactic groups of bifix codes: any transitive permutation group G of degree d and with k generators is a syntactic group of a bifix code with (k -1)d + 1 elements (Theorem 7.2.3).

Preliminaries

We first recall the basic terminology on groups in monoids (see [START_REF] Berstel | Codes and Automata[END_REF] for a more detailed exposition). We are mainly concerned with monoids of maps from a set into itself. The maps considered in this section are partial maps.

Let M be a monoid. A group in M is a subsemigroup of M which is isomorphic to a group. Note that the neutral element of a group contained in M needs not be equal to the neutral element of M .

A group in M is maximal if it not included in another group in M . Proof. Two elements g, h ∈ G have the same image. Indeed, let k be the inverse of g in G. Then h = hkg and thus the image of h is contained in the image of g. The converse inclusion is shown analogously. Then G is a permutation group on the common image I of its elements. Indeed, let e be the neutral element of G. Then for any p ∈ I, let q ∈ Q be such that qe = p. Then pe = qe 2 = qe = p. This shows that e is the identity on I. Next, for any g ∈ G the inverse k of g is such that gk = kg = e. Thus g is a permutation on I. Let g, g ′ ∈ G be such that they have the same restriction to I. Then for each p ∈ Q, p(eg) = (pe)g = (pe)g ′ = p(eg ′ ) since pe ∈ I. Since eg = g and eg ′ = g ′ , we obtain g = g ′ . This shows that the representation of G by permutations on I is faithful.

Let G be a group in a monoid of maps from Q into itself as above. The canonical representation of G by permutations is the restriction of the maps in G to their common image.

A syntactic group of a prefix code X is the canonical representation by permutations of a maximal group in the monoid of transitions of the minimal automaton A(X * ) of X * .

Let X be a prefix code and let A = A(X * ). A syntactic group G of X is called special if ϕ -1 A (G) is a cyclic submonoid of A * . In particular a special syntactic group is cyclic.

The degree of a permutation group G on a set R is the cardinality of R. Recall that the group G is transitive if for any r, s ∈ R there is some g ∈ G such that rg = s.

A permutation group G on a set R and a permutation group H on a set S are equivalent if there exists a bijection β : R → S and an isomorphism σ : G → H such that, for all g ∈ G and r ∈ R, one has Let us recall the notation concerning Green relations in a monoid M (see [START_REF] Berstel | Codes and Automata[END_REF]). We denote by R the equivalence in M defined by mRn if m, n generate the same right ideal, i.e. if mM = nM . We denote by R(m) the R-class of m.

Symmetrically, we denote by L the equivalence defined by mLn if m, n generate the same left ideal, i.e. if M m = M n. We denote by L(m) the L-class of m.

It is well known that the equivalences L and R commute. We denote by D the equivalence LR = RL. Finally, we denote by H the equivalence L ∩ R.

A D-class D is regular if it contains an idempotent. In this case, there is at least an idempotent in each L-class of D and in each R-class of D. The following statement is known as Clifford and Miller's Lemma. For m, n ∈ M , one has mn ∈ R(m) ∩ L(n) if and only if R(n) ∩ L(m) contains an idempotent.

Assume that M is a monoid of maps from a finite set Q into itself. If m, n ∈ M are L-equivalent, then they have the same image. If they are Requivalent, then they have the same nuclear equivalence (the nuclear equivalence of a partial map m from Q into itself is the partial equivalence, for which p, q ∈ Q are equivalent if m is defined on p and q and pm = qm).

If m, n ∈ M are H-equivalent, they have the same image and the same nuclear equivalence. The converse is not true but it holds in the following important particular case. Proof. If m and e are H-equivalent, they have the same nuclear equivalence ρ and the same image I. Conversely, we have me = m since e is the identity on its image I. For any p ∈ Q, pe 2 = pe implies that p and pe are in the same class of ρ. This implies that pem = pm. Thus em = m.

Finally, the restriction of m to I is a permutation. Indeed, pm = qm for p, q ∈ I implies pe = qe which forces p = q. Let k > 0 be such that the restriction of m k to I is the identity. Then m k and e are two idempotents with the same nuclear equivalence and the same image. This implies that they are equal. Thus m and e are in the same H-class.

Let F be a recurrent set and let X ⊂ F be a bifix code of finite F -degree d. Let A = (Q, 1, 1) be a simple automaton recognizing X * . We set ϕ = ϕ A and we denote by M the transition monoid ϕ(A * ) of A.

For a word w, we denote by Im(w) the image of w with respect to A, that is the set Im(w) = {p • w | p ∈ Q}. The rank of w (with respect to the automaton A) is the number rank(w) = Card(Im(w)). Then Im(w) is also the image of the map ϕ(w) (recall that the action of M is on the right of the elements of Q), and the rank of w is also the rank of ϕ(w). Clearly rank(uwv) ≤ rank(w) for all u, w, v.

Group of a bifix code

Let M be a monoid. The H-class of an idempotent e is denoted H(e). It is the maximal group contained in M and containing e.

All groups H(e) for e idempotent in a regular D-class D are isomorphic. The structure group (or Schützenberger group) of D is any one of them. When M is a monoid of maps from a set Q into itself, the canonical representations of the groups H(e) are equivalent permutation groups. See [START_REF] Berstel | Codes and Automata[END_REF]Proposition 9.1.9]. We then also consider the structure group as a permutation group.

Let F be a recurrent set and let X ⊂ F be a bifix code of finite F -degree d. Let A = (Q, 1, 1) be a simple automaton recognizing X * . Set ϕ = ϕ A . The structure group of the D-class of elements of rank d of ϕ(F ) is a permutation group of degree d. By Proposition 9.5.1 in [START_REF] Berstel | Codes and Automata[END_REF], this group does not depend on the choice of the simple automaton A recognizing X * . It is called the F -group of the code X and denoted G F (X).

When F = A * , the group G F (X) is the group G(X) of the code X defined in [START_REF] Berstel | Codes and Automata[END_REF]. Indeed, in this case, the D-class of elements of rank d coincides with the minimal ideal of the monoid ϕ(A * ).

The following example shows that the F -group of an F -maximal bifix code is not always transitive.

Example 7.2.1 Let X = {ab, ba} and let F = F ((ab) * ). Then X is an Fmaximal bifix code of F -degree 2. It can be verified easily that the syntactic monoid of X * contains only trivial subgroups (see also Exercises 7.1.1, 7.2.1 in [START_REF] Berstel | Codes and Automata[END_REF]). Thus G F (X) is reduced to the identity. We have represented on Figure 7.3 the D-class of elements of rank 4 meeting ϕ(F ). It is composed of three L-classes and three R-classes. Each L-class is represented by a column and each R-class by a row. On top of each column, we have indicated the common image of the its elements. On the left of each row, we have indicated the common nuclear equivalence of its elements (recall that two elements are equivalent for the nuclear equivalence if and only if they have the same image). The H-classes containing an idempotent are indicated by a star. Each H-class has four elements, and five of them are groups (this happens when the image is a system of representatives of the nuclear equivalence). For instance, the five classes in the nuclear equivalence of ϕ(ba) are {1}, {2}, {4, 9}, {5} and {8}, and the H-class of (the image of) ba is composed of the following elements: Word Permutation ba (18)(24) baaba (12)(48) baba

(1) babaaba (14) [START_REF] Holton | Descendants of primitive substitutions[END_REF] The structure group of this D-class is the Abelian group Z/2Z × Z/2Z. It is the F -group of the code. The aim of this section is to prove the following theorem.

Theorem 7.2.3 Any transitive permutation group of degree d which can be generated by k elements is a syntactic group of a bifix code with (k -1)d + 1 elements.

Theorem 7.2.3 was known before in particular cases. In [START_REF] Perrin | Sur les groupes dans les monoïdes finis[END_REF] it is shown that any transitive permutation group is a syntactic group of a finite bifix code. The bound d + 1 on the cardinality of the bifix code is proved for the case of a group generated by a d-cycle and another permutation. In [START_REF] Rindone | Construction d'une famille de codes associés à certains groupes finis[END_REF], it is proved that for an Abelian group of rank 2 and order d there exists a bifix code X such that Card(X) -1 = d . The proof is based on the fact that the Cayley graph of an Abelian group contains a Hamiltonian cycle.

Let us call minimal rank of a group G the minimal cardinality of a generating set for G. Theorem 7.2.3 is related to the following conjecture [START_REF] Perrin | Sur les groupes dans les monoïdes finis[END_REF]. α(g) = ψ(y) and α(g ′ ) = ψ(y ′ ) imply that ψ(y) = ψ(y ′ ). By (7.1), ψ(y) = ψ(y ′ ) implies that χ(y) = χ(y ′ ) and thus g = g ′ . Since Y generates the free group A • , the map is surjective. Indeed, for any a ∈ A we have a = y The following example shows that Theorem 7.2.5 does not hold for the set of factors of an episturmian word which is not strict. These permutations generate a group which has two orbits: {1, 6, 14, 25} and {4, 13, 21, 32}. The restriction to each orbit is isomorphic to (Z/2Z) 2 . Thus the F -group of X is (Z/2Z) 2 . However X = Z ∩ F where Z is a group code such that G(Z) = (Z/2Z) 3 .

Proof of Theorem 7.2.3. Let G be a transitive permutation group of degree d and let Z be a group code on an alphabet A with k letters such that G(Z) = G. Let F be a Sturmian set on the alphabet A and let X = Z ∩ F . Then, by Theorem 7.2.5, G F (X) = G and, by Theorem 5.2.1, X has (k -1)d+1 elements.

Example 2 . 3 . 1

 231 Set A = {a, b}. The Fibonacci morphism is the substitution f : A * → A * defined by f (a) = ab and f (b) = a. The Fibonacci word x = abaababaabaababaababaabaababaabaab • • •

Example 2 . 3 . 2

 232 Consider the following generalization of the Fibonacci word to the ternary alphabet A = {a, b, c}. Consider the morphism f : A * → A * defined by f (a) = ab, f (b) = ac and f (c) = a. The fix-point

Example 2 . 3 . 4

 234 The Thue-Morse word of Example 2.2.4 is not Sturmian. Indeed, it has four factors of length 2.

Example 2 . 3 . 6

 236 The Fibonacci word x of Example 2.3.1 is a standard episturmian word. It has the directive word (ab) ω , that is x = Pal((ab) ω )[START_REF] Glen | Episturmian words: a survey[END_REF]. The Tribonacci word of Example 2.3.2 has the directive word ∆ = (abc) ω[START_REF] Justin | Return words in Sturmian and episturmian words[END_REF]. The corresponding sequence (u n ) starts with u 1 = a, u 2 = aba, u 3 = abacaba.

Example 2 . 3 . 8

 238 Let A = {a, b, c} and ∆ = abc ω . It is easily checked that Pal(∆) is the periodic word (abac) ω . The only right-special factors of this word are 1 and a ([26]).

Proposition 2 . 4 . 1

 241 For any right essential set F of words, there exists a positive right probability distribution δ on F . Proof. Consider the map δ

Example 2 . 4 . 6

 246 Let F be the Fibonacci set (see Example 2.3.1). Since the morphism f defined by f (a) = ab and f (b) = a is primitive, there is a unique invariant probability distribution on F . Its values on the words of length at most 4 are shown on Figure 2.1 with λ = ( √ 5 -1)/2. The values of δ F can be 1 λ

Figure 2 . 1 :

 21 Figure 2.1: The invariant probability distribution on the Fibonacci set.

Figure 2 . 2 :

 22 Figure 2.2: The invariant probability distribution on the Thue-Morse set.

Example 3 . 3 . 3

 333 The set X = {a, ba} is a maximal prefix code in the Fibonacci set F since XA * is right F -dense.

. 3 )

 3 Proof. Set L = L X . Let U = A * \ XA * . By definition of the indicator, we have L = V X * U . Since X is prefix, we have by Proposition 3.1.1, the equality A * = X * U . Thus we obtain L = V A * (note that this is actually equivalent to Proposition 4.1.3). Multiplying both sides on the right by (1 -A ), we obtain Equation (4.2).If X is suffix, we have by the dual of Proposition 3.1.1, the equality 1 -X = (1-A )V . This gives Equation (4.3) by multiplying both sides of Equation (4.2) on the left by 1 -A .

Example 4 . 2 . 1

 421 Let F be the Thue-Morse set, which is the set of factors of a fix-point of the substitution f defined by f (a) = ab, f (b) = ba (see Example 2.2.4). Set x n = f n (a) for n ≥ 1. Note that x n+1 = x n xn where u → ū is the substitution defined by ā = b and b = a. Note also that u ∈ F if and only

Figure 4 .

 4 Figure 4.3). By the dual of Equation (3.1), there exist p ∈ A * \ A * X and z ∈ X * such that ut = pz.Since X is left F -complete, p is a proper suffix of a word in X. Since u / ∈ I(X), p is a prefix of u. Thus z = 1 = t or z ∈ X + . In the latter case, set z = z 1 • • • z n with z i ∈ X. Since ut = pz, one of the following two cases holds:

Lemma 4 . 3 . 2

 432 One has G ⊂ S and D ⊂ P .

  Proof of Proposition 4.3.5. Set Y = S \ I. Let us first show that Y is prefix. Assume that u, uv ∈ Y . Since uv ∈ S there is a nonempty word p such that puv ∈ X. Since u / ∈ I, this forces v = 1. Thus Y is prefix. We show next that Y A * is right F -dense. Consider u ∈ F and let w ∈ F \ I. Since F is recurrent, there exists v ∈ F such that uvw ∈ F . Let s be the longest word of S which is a prefix of uvw. By Lemma 4.3.6, we have s ∈ F \ I. Thus s ∈ S \ I = Y and uvw ∈ Y A * . This shows that Y A * is right F -dense.

  Since G ⊂ S by Lemma 4.3.2, we have s ∈ S. Furthermore, since D ⊂ AI, we have s ∈ I. This shows that s ∈ S ∩ I.

Theorem 4 . 3 . 7

 437 Let F be a recurrent set. Let X be a bifix code of finite Fdegree d. The set of its nonempty proper suffixes is a disjoint union of d -1 F -maximal prefix codes.Proof. Let S be the set of proper suffixes of X. If d = 1, then S \ 1 is empty. If d ≥ 2, by Proposition 4.3.5, the set Y = S \ I is an F -maximal prefix code and the set S ∩ I is equal to the set S ′ of proper suffixes of the words of the derived code X ′ . Arguing by induction, the set

Corollary 4 . 3 . 8

 438 Let F be a recurrent set such that there exists a positive invariant probability distribution δ on F . Let X be a finite bifix code of finite F -degree d. The average length of X with respect to δ is equal to d.Proof. Let δ be a positive invariant probability distribution on F . By the dual of Proposition 3.4.1, one has λ(X) = δ(S). In view of Theorem 4.3.7, we haveS \ 1 = Y 1 ∪ . . . ∪ Y d-1where each Y i is a finite F -maximal prefix code. By Proposition 3.3.4, we have δ(

Figure 4 . 4 :

 44 Figure 4.4: The three F -maximal bifix codes of F -degree 2 in the Fibonacci set F .

Figure 4 . 5 :

 45 Construction of ϕ(p) (second case).

Figure 4 . 6 :

 46 Figure 4.6: Reconstruction of the factorization.

Example 4 . 4 . 7

 447 Let F be the Fibonacci set. The set X = {aa, ab, ba} is an F -maximal bifix code of F -degree 2. Then Y = {aa, aba, b} is a bifix code of F -degree 2 which is obtained from X by internal transformation with respect to w = b. Indeed, here G = D = {a}, Gw = {ab}, wD = {ba} and GwD = {aba}. Proposition 5.1.1 A set F is Sturmian if and only if it is uniformly recurrent and

Proposition 5 . 1 . 3

 513 Any word in a Sturmian set F is a prefix of some rightspecial word in F .

Theorem 5 . 2 . 1

 521 Let F be a Sturmian set on an alphabet with k letters. For any finite F -maximal bifix codeX ⊂ F , one has Card(X) = (k -1)d F (X) + 1.The following corollary is strong generalization of a result related to Sturmian words. Corollary 5.2.2 Let x be a Sturmian word over A = {a, b}, and let X ⊂ A + be a finite maximal bifix code of degree d. Then Card(X ∩ F (x)) = d + 1. Indeed, since A d is a finite maximal bifix code of degree d, this corollary (re)proves that any Sturmian word x has d+1 factors of length d, and it extends this to arbitrary finite maximal bifix code of degree d. A similar extension holds for strict episturmian words. Proof of Corollary 5.2.2. Set F = F (x). In view of Theorem 4.2.11, one has d = d F (X ∩ F ). Consequently, by the formula of Theorem 5.2.1, Card(

Example 5 . 2 . 5 Figure 5 . 1 :

 52551 Figure 5.1: The F -maximal bifix code of F -degree 3 with kernel {a, baab}.

Figure 5 . 2 :

 52 Figure 5.2: An F -maximal bifix code with 10 elements. The numbers in the vertices are for later use.

Figure 5 . 3 :Figure 5 . 4 :

 5354 Figure 5.3: The graphs H ′ and H.

Example 6 . 1 . 2

 612 Let A = (Q, 1, 1) be the automaton defined byQ = {1, 2}, 1 • a = 1 • b = 2 and 2 • a = 2 • b = ∅. The submonoid recognized by A is {1}.The subgroup described by A is the cyclic group generated by ab -1 .

Figure 6 . 1 :

 61 Figure 6.1: Paths in the automaton A

  values for d = 2, 3 are consistent with Examples 4.3.13 and 5.2.6.

Figure 6 . 2 :Example 6 . 3 . 1 Figure 6 . 3 :

 6263163 Figure 6.2: The F -maximal bifix code of F -degree 3 with kernel {a, baab}.

Example 6 . 3 . 4 Figure 6 . 5 :

 63465 Figure 6.5: The two suffix codes which are classes of the equivalence θ X .

  aabab aba baa aabab aba baaba babaabaa

Example 6 . 6 . 3 Figure 6 . 8 : 6 Figure 6 . 9 :

 66368669 Figure 6.8: An F -maximal bifix code of F -degree 4.

  x∈X |x| = Card(P ) + Card(S) + (k -2)d.

Proposition 7 . 1 . 1

 711 Let G be a group in a monoid M of partial maps from a set Q into itself. All elements of G have the same image I. The restriction of the elements of G to I is a faithful representation of G as a permutation group on I.

Figure 7 . 1 :

 71 Figure 7.1: Equivalent permutation groups.

Proposition 7 . 1 . 2

 712 Let M is a monoid of maps from a finite set Q into itself. Let e ∈ M be an idempotent. An element m of M is in the H-class of e if and only if it has the same nuclear equivalence and the same image as e.

Proposition 7 . 1 . 3

 713 The set of elements of ϕ(F ) of rank d is included in a regular D-class of M .We use the following lemmas. Lemma 7.1.4 A word w ∈ F which has d parses with respect to X has rank d with respect to A. Moreover, Im(w) is the set of states 1 • p for all p such that Set p = ϕ(wv). Then p = ϕ(w)n and, with the previous notation, n = ne ′ = nqϕ(u)p, so L(n) = L(p). Thus mp = ϕ(uwv) ∈ R(m) ∩ L(p), and by Clifford and Miller's Lemma, R(p) ∩ L(m) contains an idempotent. Thus the D-class of m, p and n is regular.

Figure 7 . 2 :Figure 7 . 3 :

 7273 Figure 7.2: An F -maximal bifix code of F -degree 4.

ǫ1 1 •Figure 7 . 4 :Example 7 . 2 . 6 Figure 7 . 5 :

 17472675 Figure 7.4: The equivalence of G and G ′ .

Example 7 . 2 . 7

 727 Let F and X be as in Example 5.2.7. The bifix code X has F -degree 8. Let A be the minimal automaton of X * represented on Figure 5.2. The image of ϕ(bc) is the set I = {1, 4, 6, 13, 14, 21, 25, 32}. The submonoid U = {u ∈ A * | I • u = I} is generated by acbc and acacbc. The restrictions to I of ϕ(acbc) and ϕ(acacbc) are (1 14)(25 6)(4 21)(32 13), (1 6)(14 25)(4 13)(21 32).

Table 5 .

 5

	and 5.2.4.

1: The 13 F -maximal bifix codes of F -degree 3 in the Fibonacci set F .

The set I(X) is denoted by H(X) in[START_REF] Berstel | Codes and Automata[END_REF].

Acknowledgments We wish to thank Mike Boyle, Aldo De Luca, Thierry Monteil, Patrice Séébold, Martine Queffélec and Gwénaël Richomme for their help in the preparation of this manuscript.

The following theorem is due to Césari. It is Theorem 6.5.4 in [START_REF] Berstel | Codes and Automata[END_REF].

Theorem 4.4.8 For any finite maximal bifix code X over A of degree d, there is a sequence of internal transformations which, starting from the code A d , gives the code X.

Theorem 4.4.8 has been generalized to finite F -maximal bifix codes when F is the set of paths in a strongly connected graph (see [START_REF] De | Finite biprefix sets of paths in a graph[END_REF]). It is not true in any recurrent, or even uniformly recurrent set, as shown by the following example.

Example 4.4.9 Let F be the Fibonacci set. The set X = {a, bab, baab} is a finite bifix code of F -degree 2. It cannot be obtained by a sequence of internal transformations from the code A 2 ∩ F = {aa, ab, ba}. Indeed, the only internal transformation which can be realized is with respect to w = b. The result is {aa, aba, b} by Example 4.4.7. Next, no internal transformation can be realized from this code. See also Figure 4.4.

A more general form of internal transformation is described in [START_REF] Berstel | Codes and Automata[END_REF] in Proposition 6.2.8. We do not know whether its adaptation to finite F -maximal bifix codes allows one to obtain all finite F -maximal bifix codes of F -degree d starting with the code A d ∩ F .

Bifix codes in Sturmian sets

In this section, we study bifix codes in Sturmian sets. This time, the situation is completely specific. First of all, as we have already seen, any F -thin bifix code included in a uniformly recurrent set F is finite (Theorem 4.4.3). Next, in a Sturmian set F , any bifix code of finite F -degree d on k letters has (k -1)d + 1 elements (Theorem 5.2.1). Since A d is a bifix code of degree d, this generalizes the fact that Card(F ∩ A d ) = (k -1)d + 1 for all d ≥ 1.

Additionally, if an infinite word x is X-stable, that is if , for some thin maximal bifix code X, one has d F (y) (X) = d F (x) (X) for all suffixes y of x, then the inequality Card(X ∩ F (x)) ≤ d F (x) (X) implies that x is ultimately periodic (Theorem 5.3.2).

Sturmian sets

Let F be a factorial set on the alphabet A. Recall that a word w is strict right-special if wA ⊂ F . It is strict left-special if Aw ⊂ F . A suffix of a (strict) right-special word is (strict) right-special, a prefix of a (strict) left-special word is (strict) left-special.

A set of words F is called Sturmian if it is the set of factors of a strict episturmian word. By Proposition 2.3.3 a Sturmian set F is uniformly recurrent. Moreover, every right-special (left-special) word in F is strict.

The following statement gives a direct definition of Sturmian sets.

Proposition 5.2.8 Let F be Sturmian set, let w ∈ F be a nonempty word and let D, G be finite sets such that (i) any word u has at most one factorization u = gwd with g ∈ G and d ∈ D, (ii) wD is a prefix code contained in F and DA * is right

be a set made of copies of G and D. The tensor product notation is used to emphasize that the copies of G and D are disjoint. Let H = (V, E) be the undirected graph having V as set of vertices and as edges the pairs {1 ⊗ g, d ⊗ 1} such that gwd ∈ F (this graph is close to, but slightly different from the incidence graph for GwD as it will be defined in Section 6.3). We have Card(V ) = Card(G) + Card(D) and, by condition (i), Card(E) = Card(GwD ∩ F ). We show that the graph H is a tree. This implies our conclusion since, in a tree, one has Card(E) = Card(V ) -1.

Let us prove that the graph H is a tree by induction on the sum of the lengths of the words of D, assuming that the pair G, D satisfies conditions (ii) and (iii). Assume first that

Since DA * is w -1 F -dense, the word wd ′ is not right-special. Thus for each g ∈ G, we have gwd ′ ∈ F if and only if gwd ∈ F . This shows that the graph H is isomorphic to the graph H ′ corresponding to the pair (G, D ′ ). The set D ′ satisfies condition (ii). By induction H ′ is a tree. Consequently H is a tree.

Suppose next that d ′ A ∩ D has more than one element. Then d ′ is rightspecial and

. Let H ′ be the graph corresponding to the pair (G, D ′ ). By induction hypothesis, the graph H ′ is tree. Since wD ⊂ F , wd ′ is right-special. Let uwd ′ be a right-special word such that u is longer than any word of G. Since A * G is F w -1 -dense, and since u ∈ F w -1 , u has a suffix g in G. Thus gwd ′ is rightspecial. We have {1 ⊗ g, d ′ a ⊗ 1} ∈ E for all a ∈ A. For any other element g ′ ∈ G such that g ′ wd ′ ∈ F , since g ′ wd ′ is not right-special, there is exactly one a ′ ∈ A such that g ′ wd ′ a ′ ∈ F . There is a path between g and every g ′ = g, since {1 ⊗ g ′ , 1 ⊗ d ′ a ′ } ∈ E for some a ′ and {1 ⊗ g, 1 ⊗ d ′ a ′ } ∈ E for all a ′ (see Figure 5.3). Thus the graph H is connected and acyclic, and therefore is a tree.

The following example shows that condition (i) is necessary.

Example 5.2.9 Let F be the Fibonacci set. Let G = {ab, aba}, w = a and D = {ab, b}. Then conditions (ii) and (iii) are satisfied but not condition (i). We have GwD = {abaab, abab} and thus the conclusion of Proposition 5.2.8 is false.

w = sxp such that q ′ • s = 1, 1 • x = 1 and 1 • p = q, and such that (s, x, p) is a parse of w. Thus X has degree d.

A bifix code Z such that Z * satisfies one of the equivalent conditions of the proposition 6.1.5 is called a group code.

The following proposition shows in particular that a subgroup of finite index is positively generated. Proposition 6.1.6 Let H be a subgroup of finite index of A • . The minimal automaton A of H ∩ A * is a group automaton which describes the subgroup H. Let X be the group code such that A recognizes X * . The subgroup generated by X is H.

Proof. By Proposition 6.1.5, the monoid H ∩ A * is recognized by a group automaton A = (Q, 1, 1), which is the minimal automaton of H ∩ A * . The morphism ϕ A from A * onto the group G = ϕ A (A * ) of Proposition 6.1.5 extends to a morphism ψ from A • onto G. The subgroup K is composed of the permutations that fix 1, and the subgroup H is formed of the elements w ∈ A • such that the permutation ψ(w) fixes 1. There is a generalized path in A from p to q labeled w if and only if pψ(w) = q. Thus ψ(w) fixes 1 if and only there is a generalized path from 1 to 1 labeled w, that is if w ∈ H. Thus the subgroup described by A is H. By Proposition 6.1.3, the subgroup H is generated by X. Example 6.1.7 The set A d is a group code by Proposition 6.1.5(ii). Thus it is a maximal bifix code of degree d. The intersection of the subgroup generated by A d with A * is the submonoid generated by A d (Proposition 6.1.6). It is composed of the words with length a multiple of d.

Main result

We will prove the following result. Theorem 6.2.1 Let F be a Sturmian set and let d ≥ 1 be an integer

Note that Theorem 5.2.1 is contained in Theorem 6.2.1 (we will use Theorem 5.2.1 in the proof of Theorem 6.2.1). Indeed, let X be an F -maximal bifix code of F -degree d. By Theorem 4.4.3, X is finite. By Theorem 6.2.1, the subgroup X has rank Card(X) and index d in the free group A • . By Schreier's Formula (6.1), one get Card(X) = (Card(A) -1)d + 1.

Before proving Theorem 6.2.1, we list some corollaries. Proof. Let s ∈ A + be such that ps, qs ∈ X. Then p, q ∈ Hs -1 and thus Hp = Hq.

Let A = (P, 1, 1) be the literal automaton of X * (see Section 3.2). We show that the equivalence θ X is compatible with the transitions of the automaton A in the following sense. Lemma 6.3.6 Let F be a Sturmian set. Let X ⊂ F be a bifix code and let P be the set of proper prefixes of X. Let p, q ∈ P and a ∈ A.

Proof. Let G be the incidence graph of X.

Let p, q ∈ P and a ∈ A be such that p ≡ q mod θ X and p•a, q•a = ∅. If p = 1, then q = 1 and the conclusion holds. Thus we may assume that p = 1, q = 1, and that p = q. Let (1

We may assume that the words u i are pairwise distinct, and that the v i are pairwise distinct. Moreover, since p • a, q • a = ∅ there exist words v, w such that pav, qaw ∈ X.

The proof is in two steps. In the first step, we assume that v 1 and v n both start with a. In the second step, we show that this condition is always fulfilled.

Assume that v 1 and v n begin with a. There are two cases. Case 1: Assume first that pa, qa ∈ P . Then p • a = pa and q • a = qa. If all words v i begin with a, then clearly the equivalence pa ≡ qa mod θ X holds. Thus assume the contrary, and let i > 1 be minimal such that v i begins with a letter distinct of a and let i ≤ j < n be maximal such that v j begins with a letter distinct of a. Then both words u i-1 and u j are right-special (since u i-1 v i-1 starts with u i-1 a and u i-1 v i starts with u i-1 b for some letter b = a and similarly for u j ). But since u i-1 and u j are in the same trace on P ′ of a connected component of G, Lemma 6.3.3 implies that u i-1 = u j , that is i -1 = j. But this contradicts the inequality i ≤ j.

Case 2: Suppose now that pa ∈ X. This implies that v 1 = a, since pv 1 = u 0 v 1 is in X and begins with pa. If v n = aw, then since v 1 and v n , if they are distinct, are not prefix-comparable by Lemma 6.3.3, one n = 1 and w = 1. If

a and aw, if they are distinct, are not prefix-comparable. Thus, one has again w = 1. In both cases, qa ∈ X and therefore p • a = 1 = q • a.

We now show that the assumption that v 1 begins with a letter distinct of a leads to a contradiction (the case where v n starts with a letter distinct from a is handled symmetrically). In this case since u 0 v 1 is in X and u 0 av = pav ∈ X, the word u 0 is right-special. Let i be the largest integer such that v i begins with a letter distinct of a for 1 ≤ i ≤ n. If i < n, then u i is right-special. This contradicts Lemma 6.3.3(iii), since u 0 and u i are distinct (because i ≥ 1) elements of the trace on P ′ of a connected component of G. If i = n, then u 0 and u n are right-special since u n v n ∈ X and u n aw = qaw ∈ X. We obtain again a contradiction since u 0 and u n are distinct.

Coset automaton

Let F be a Sturmian set and let X ⊂ F be a bifix code. We introduce a new automaton denoted B X or B for short, and called the coset automaton of X. Let R be the set of classes of θ X with the class of 1 still denoted 1. The coset automaton of X is the automaton B X = (R, 1, 1) with set of states R and transitions induced by the transitions of the literal automaton A = (P, 1, 1) of X * . Formally, for r, s ∈ R and a ∈ A, one has r • a = s in the automaton B if there exist p in the class r and q in the class s such that p • a = q in the automaton A.

Observe first that the definition is consistent since, by Lemma 6.3.6, if p • a and p ′ • a are nonempty and p, p ′ are in the same class r, then p • a and p ′ • a are in the same class. Since the class p • a is uniquely defined, the automaton is indeed deterministic.

Observe next that if there is a path from p to p ′ in the automaton A labeled w , then there is a path from the class r of p to the class r ′ of p ′ labeled w in B X . Observe that the word bb is in Z * but it is not in X * .

The following result shows that the coset automaton of X is the Stallings automaton of the subgroup generated by X. Lemma 6.4.2 Let F be a Sturmian set, and let X ⊂ F be a bifix code. The coset automaton B X is reversible and describes the subgroup generated by X. Moreover X ⊂ Z, where Z is the bifix code generating the submonoid recognized by B X .

Proof. Set B X = (R, 1, 1). Let r, s ∈ R and a ∈ A be such that r • a = s • a is nonempty. Let p, q ∈ P be elements of the classes r and s respectively, such that p • a, q • a are nonempty. Then pa, qa ∈ P ∪ X. To show that B X is reversible, it is enough to show that p ≡ q mod θ X .

Suppose first that pa ∈ X. Then r • a = s • a = 1 and thus qa ∈ X since 1 is isolated mod θ X . Thus p ≡ q mod θ X . Suppose next that pa, qa ∈ P . Then there is a path (1 ⊗ u 0 , v 1 ⊗ 1, . . . , v n ⊗ 1, 1 ⊗ u n ) in the incidence graph G of X, with pa = u 0 and qa = u n . We may assume that the nodes of the path are pairwise distinct, except for a possible equality u 0 = u n .

If all the words u i end with a, then p ≡ q mod θ X .

Otherwise, let i be minimal such that u i ends with a letter distinct of a and j, with 1 ≤ i ≤ j < n be maximal such that u j ends with a letter distinct of a. Then v i and v j+1 are left-special and they are distinct since j + 1 > i. This contradicts Lemma 6.3.3(iii) since v i and v j+1 are distinct elements of the same trace on S ′ .

Thus the coset automaton is reversible.

Let Z be the bifix code generating the submonoid recognized by B X . To show the inclusion X ⊂ Z, consider a word x ∈ X. There is a path from 1 to 1 labeled x in A, hence also in B X . Since the class of 1 modulo θ X is reduced to 1, this path in B does not pass by 1 except at its ends. Thus x is in Z.

Let us finally show that the coset automaton describes the group H = X . By Proposition 6.1.3, the subgroup described by B X is equal to Z . Set K = Z . Since X ⊂ Z, we have H ⊂ K. To show the converse inclusion, let us show by induction on the length of w ∈ A * that, for p, q ∈ Q, there if there is a path from the class of p to the class of q in B X with label w then Hpw = Hq. It is true for w = 1. Next, assume that it is true for w and consider wa with a ∈ A. Assume that there is a path p w -→ q a -→ r in B X . By induction hypothesis, we have Hpw = Hq. Next, by definition of B X , there is an s ≡ q mod θ X such that sa ≡ r mod θ X . By Proposition 6.3.5, we have Hs = Hq and Hsa = Hr. Thus Hpwa = Hqa = Hsa = Hr. This property shows that if z ∈ Z, then Hz = Z, that is z ∈ H. Thus Z ⊂ H and finally H = K.

Return words

Let F be a factorial set. For u ∈ F , define

. When F = F (x) for an infinite word x, the sets Γ F (u) and R F (u) are respectively the set of right return words to u and first right return words to u in x, and Γ ′ F (u) and R ′ F (u) are respectively the set of left return words to u and first left return words to u in x. The relation between R F (u) and R ′ F (u) is simply

Words in the set uR F (u) = R ′ F (u)u are called complete return words in [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF]. When there is no ambiguity, we will call the (first) right return words simply the (first) return words, omitting the 'right' specification.

Proof.We have X * ∩ F ⊂ X ∩ F . To show the converse inclusion, consider the bifix code Z generating the submonoid recognized by the coset automaton B X associated to X.

Let us show that Z ∩ F = X. By Lemma 6.4.2, we have X ⊂ Z and thus X ⊂ Z ∩ F . Since X is an F -maximal bifix code, this implies that X = Z ∩ F .

Since any reversible automaton is minimal and since the automaton B X is reversible by Lemma 6.4.2, it is equal to the minimal automaton of Z * . Let K be the subgroup generated by Z. By Proposition 6.1.1, we have

This shows that

The first inclusion holds because X ⊂ Z implies X ⊂ K. The last equality follows from the fact that if

, which was to be proved.

Note the following consequence of Proposition 6.6.1.

Corollary 6.6.2 Let F be a Sturmian set and let X ⊂ F be a finite F -maximal bifix code. Each right coset of the subgroup X generated by X contains at most one right-special proper prefix of X.

Proof. Set H = X . Let Q be the set of those proper prefixes of the words of X which are right-special. Let us show that if p, q ∈ Q belong to the same right coset, then p = q. We may assume that p = uq. Since Hp = Hq, one has Huq = Hq. Consequently, Hu = H and thus u ∈ H. By Proposition 6.6.1, since u ∈ F , this implies that u ∈ X * and thus u = 1 since p is a proper prefix of X.

Proof of Theorem 6.2.1.

Assume first that X is an F -maximal bifix code of F -degree d. Let P be the set of proper prefixes of X. Let Q be the set of words in P which are right-special. Let H be the subgroup generated by X.

By Lemma 5.2.3 there is a right-special word u such that π X (u) = d. The d suffixes of u which are in P are the elements of Q. By Theorem 4.2.8, the word u is not an internal factor of X. u u y q r Figure 6.7: A word y ∈ R F (u).

there is a parse (s, x, p) of w. For all q ∈ Im(w), there is a unique proper prefix p of P which is a suffix of w, and such that q = 1 • p.

Proof. Consider first two states q, r ∈ Q and suppose that q • w = r. Since A is simple, it is trim. Consequently there exist two words u, v such that 1 • u = q and r • v = 1. It follows that uwv ∈ X * . Since w has d parses, by Theorem 4.2.8 it is not an internal factor of a word in X. Thus there is a parse (s, x, p) of w such that us, pv ∈ X * . Then r = 1 • p. The relation r → (s, x, p) is a function. Indeed, let us show that if (s, x, p) and (s ′ , x ′ , p ′ ) are two distinct parses of w, then 1 • p = 1 • p ′ . Assume the contrary. Then we have pv, p ′ v ∈ X * for the same word v. Since p, p ′ are suffixes of w, they are suffix-comparable and thus p = p ′ since X is bifix. This is impossible if the parses are distinct. Of course, the function r → (s, x, p) is injective since A is deterministic. Conversely, let (s, x, p) be a parse of w. Since X is an F -maximal bifix code, there exist by Theorem 4.2.2 words u, v such that us, pv ∈ X * . Thus we have 1

Proof. Since X is F -thin, there exists w ∈ F which is not a factor of a word in X. This word w has d parses. Assume uv ∈ F . Since F is recurrent, there exists a word t such that uvtw ∈ F . Then uvtw also has d parses. By Lemma 7.1.4, this implies that the rank of uvtw is d. Since d = rank(uvtw) ≤ rank(uv) ≤ rank(u) = d, one has rank(uv) = d.

Proof of Proposition 7.1.3. Let u, v ∈ F be two words of rank d. Set m = ϕ(u) and n = ϕ(v). Let w be such that uwv ∈ F . We show first that mRϕ(uwv) and nLϕ(uwv).

For this, let t be such that uwvtu ∈ F . Set z = wvtu. By Lemma 7.1.5, the rank of uz is d. Since Im(uz) ⊂ Im(z) ⊂ Im(u), this implies that the images are equal. Consequently, the restriction of ϕ(z) to Im(u) is a permutation. Since Im(u) is finite, there is an integer ℓ ≥ 1 such that ϕ(z) ℓ is the identity on Im(u). Set e = ϕ(z) ℓ and s = tuz ℓ-1 . Then, since e is the identity on Im(u), one has m = me. Thus m = ϕ(uwv)ϕ(s), and since ϕ(uwv) = mϕ(wv), it follows that m and ϕ(uwv) are R-equivalent.

Similarly n and ϕ(uwv) are L-equivalent. Indeed, set z ′ = tuwv. Then Im(vz ′ ) ⊂ Im(z ′ ) ⊂ Im(v). Since vz ′ is a factor of z 2 and z has rank d, it follows that d = rank(z 2 ) ≤ rank(vz ′ ) ≤ rank(v) = d. Therefore, vz ′ has rank d and consequently the images Im(vz ′ ), Im(z ′ ) and Im(v) are equal. There is an integer ℓ ′ ≥ 1 such that ϕ(z ′ ) ℓ ′ is the identity on Im(v). Set e ′ = ϕ(z ′ ) ℓ ′ . Then n = ne ′ = nϕ(z ′ ) ℓ ′ -1 ϕ(tuwv) = nqϕ(uwv), with q = ϕ(z ′ ) ℓ ′ -1 ϕ(t). Since ϕ(uwv) = ϕ(uw)n, one has nLϕ(uwv). Thus m, n are D-equivalent, and ϕ(uwv) ∈ R(m)∩ L(n).

Let X be a finite bifix code and let G be a transitive permutation group of degree d and minimal rank k. If G is a syntactic group of X, then Card(X) ≥ (k -1)d + 1.

Theorem 7.2.3 shows that the lower bound is sharp.

The following result, which is from [START_REF] Perrin | On syntactic groups[END_REF], shows that the conjecture holds for k = 2. Theorem 7.2.4 Let G be a permutation group of degree d. If G is a nonspecial syntactic group of a finite prefix code X, then Card(X) ≥ d + 1. Theorem 7.2.4 is clearly not true for special syntactic groups since Z/nZ is a syntactic group of X = a n for any n ≥ 1.

Theorem 7.2.3 is a consequence of the following theorem which can be viewed as a complement to Theorem 4.2.11. The proof itself makes use of Theorem 6.2.1.

Theorem 7.2.5 Let Z ⊂ A * be a group code of degree d. Let F be a Sturmian set. The set X = Z ∩ F is an F -maximal bifix code of F -degree d and G F (X) = G(Z).

Proof. The fact that X is an F -maximal bifix code of F -degree d results from Corollary 6.2. Let G ′ be the maximal group contained in ϕ(A * ) which contains e. It is a permutation group on I which is equivalent to G F (X).

For y ∈ Y * , let χ(y) be the restriction of ϕ(y) to the set I.

For any y ∈ Y * , eϕ(y)e has the same nuclear equivalence and the same image as e. By Proposition 7.1.2 it implies that they are in the same H-class. Thus eϕ(y)e is in G ′ .

Since eϕ(y)e and ϕ(y) have the same restriction to I and since eϕ(y)e belongs to the H-class of e, χ is a morphism from Y * into the permutation group

Let us show that G and G ′ are equivalent as permutation groups.

For this, let us define a bijection β : I → R as follows. Let P be the set of proper prefixes of the words of X and let S be the set of elements of P which are suffixes of u. For i ∈ I, there is a unique q ∈ S such that i = 1 • q by Lemma 7.1.4. Set β(i) = 1ψ(q). We show that β is injective. Let q, t ∈ S be such that 1ψ(q) = 1ψ(t). Assume that |q| ≤ |t|. Since q, t are suffix-comparable, we have t = vq. Since 1ψ(t) = 1ψ(v)ψ(q) = 1ψ(q) and since ψ(q) is a permutation, we have 1ψ(v) = 1 and thus v ∈ Z * . Since v is in F and since Z * ∩ F ⊂ X * , this implies v ∈ X * and thus v = 1. This shows that q = t and thus that β is injective. Since Card(R) = Card(I) = d, we have shown that β is a bijection.

Let us verify that for any i, j ∈ I and y ∈ Y * , we have iϕ(y) = j ⇐⇒ β(i)ψ(y) = β(j).

Let us first prove (7.1) for y ∈ Y . For this, let q, t ∈ S be such that i = 1 • q, j = 1 • t. The states q, t exist by Lemma 7.1.4. Then iϕ(y) = j ⇐⇒ 1ϕ(qy) = 1ϕ(t) ⇐⇒ qy ∈ X * t.

The last equivalence holds because 1 • qy = 1 • v for the word v ∈ P such that qy ∈ X * v. But since uy ∈ A * u, v is a suffix of u and thus v ∈ S. This forces t = v.

Since qy ∈ F , we have qy ∈ X * t ⇐⇒ qy ∈ Z * t and thus, we obtain iϕ(y) = j ⇐⇒ qy ∈ Z * t ⇐⇒ β(i)ψ(y) = β(j).

This proves (7.1) for y ∈ Y . Next, let us show that if y, z ∈ Y * satisfy (7.1) for all i, j ∈ I, the same is true for yz. Assume first that for i, j ∈ I, one has iϕ(yz) = j. Since the restrictions of ϕ(y), ϕ(z) to I are permutations, there is a unique k ∈ I such that iϕ(y) = k and kϕ(z) = j. Then, since y, z satisfy (7.1), we have β(i)ψ(y) = β(k) and β(k)ψ(z) = β(j). Thus β(i)ψ(yz) = β(j).

Conversely, assume that β(i)ψ(yz) = β(j). Since β is a bijection from I onto R, there is a unique k ∈ I such that β(k) = β(i)ψ(y). Then β(k)ψ(z) = β(j). By (7.1), we have iϕ(y) = k and kϕ(z) = j whence iϕ(yz) = j. This proves that yz satisfies (7.1). Equation (7.1) shows that we may define a morphism α from G ′ to G by α(g) = ψ(y) for y ∈ Y * such that χ(y) = g. This map is injective. Indeed, if α(g) = α(g ′ ), let y, y ′ ∈ Y * be such that χ(y) = g and χ(y ′ ) = g ′ . Then,