text:
Valérie Berthé

Clelia De Felice

Francesco Dolce

Julien Leroy

Dominique Perrin

Christophe Reutenauer

Giuseppina Rindone

Bifix codes and interval exchanges

à 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 is part of a research initiated in [2] which studies the connections between the three subjects formed by symbolic dynamics, the theory of codes and combinatorial group theory. The initial focus was placed on the classical case of Sturmian systems and progressively extended to more general cases.

The starting point of the present research is the observation that the family of Sturmian sets is not closed under decoding by a maximal bifix code, even in the more simple case of the code formed of all words of fixed length n. Actually, the decoding of the Fibonacci word (which corresponds to a rotation of angle α = (3 -√ 5)/2) by blocks of length n is an interval exchange transformation corresponding to a rotation of angle nα coded on n + 1 intervals. This has lead us to consider the set of factors of interval exchange transformations, called interval exchange sets. Interval exchange transformations were introduced by Oseledec [START_REF] Oseledec | The spectrum of ergodic automorphisms[END_REF] following an earlier idea of Arnold [START_REF] Arnold | Small denominators and problems of stability of motion in classical and celestial mechanics[END_REF]. These transformations form a generalization of rotations of the circle.

The main result in this paper is that the family of regular interval exchange sets is closed under decoding by a maximal bifix code (Theorem 3.13). This result invited us to try to extend to regular interval exchange transformations the results relating bifix codes and Sturmian words. This lead us to generalize in [START_REF] Berthé | The finite index basis property[END_REF] to a large class of sets the main result of [2], namely the Finite Index Basis Theorem relating maximal bifix codes and bases of subgroups of finite index of the free group.

Theorem 3.13 reveals a close connection between maximal bifix codes and interval exchange transformations. Indeed, given an interval exchange transformation T each maximal bifix code X defines a new interval exchange transformation T X . We show at the end of the paper, using the Finite Index Basis Theorem, that this transformation is actually an interval exchange transformation on a stack, as defined in [START_REF] Michael | An extension of Lagrange's theorem to interval exchange transformations over quadratic fields[END_REF] (see also [START_REF] Veech | Finite group extensions of irrational rotations[END_REF]).

The paper is organized as follows.

In Section 2, we recall some notions concerning interval exchange transformations. We state the result of Keane [12] which proves that regularity is a sufficient condition for the minimality of such a transformation (Theorem 2.3).

We study in Section 3 the relation between interval exchange transformations and bifix codes. We prove that the transformation associated with a finite S-maximal bifix code is an interval exchange transformation (Proposition 3.8).

We also prove a result concerning the regularity of this transformation (Theorem 3.12).

We discuss the relation with bifix codes and we show that the class of regular interval exchange sets is closed under decoding by a maximal bifix code, that is, under inverse images by coding morphisms of finite maximal bifix codes (Theorem 3.13).

In Section 4 we introduce tree sets and planar tree sets. We show, reformulating a theorem of [START_REF] Ferenczi | Languages of k-interval exchange transformations[END_REF], that uniformly recurrent planar tree sets are the regular interval exchange sets (Theorem 4.3). We show in another paper [START_REF] Berthé | Maximal bifix decoding[END_REF] that, in the same way as regular interval exchange sets, the class of uniformly recurrent tree sets is closed under maximal bifix decoding.

In Section 4.3, we explore a new direction, extending the results of this paper to a more general case. We introduce exchange of pieces, a notable example being given by the Rauzy fractal. We indicate how the decoding of the natural codings of exchange of pieces by maximal bifix codes are again natural codings of exchange of pieces. We finally give in Section 4.4 an alternative proof of Theorem 3.13 using a skew product of a regular interval exchange transformation with a finite permutation group.

Acknowledgements This work was supported by grants from Région Ile-de-France, the ANR projects Eqinocs and Dyna3S, the Labex Bezout, the FARB Project "Aspetti algebrici e computazionali nella teoria dei codici, degli automi e dei linguaggi formali" (University of Salerno, 2013) and the MIUR PRIN 2010-2011 grant "Automata and Formal Languages: Mathematical and Applicative

Aspects". We thank the referee for his useful remarks on the first version of the paper which lead us to separate it in two parts.

Interval exchange transformations

Let us recall the definition of an interval exchange transformation (see [START_REF] Cornfeld | Ergodic theory, volume 245 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF] or [START_REF]Combinatorics, automata and number theory[END_REF]).

A semi-interval is a nonempty subset of the real line of the form [α,

β[= {z ∈ R | α ≤ z < β}.
T (z) = z + α a if z ∈ I a .
Observe that the restriction of T to I a is a translation onto J a = T (I a ), that µ a is the right boundary of I a and that ν a is the right boundary of J a . We additionally denote by γ a the left boundary of I a and by δ a the left boundary of J a . Thus Since < 1 and < 2 are total orders, there exists a unique permutation π of A such that a < 1 b if and only if π(a) < 2 π(b). Conversely, < 2 is determined by < 1 and π and < 1 is determined by < 2 and π. The permutation π is said to be associated with T .

I a = [γ a , µ a [, J a = [δ a , ν a [. Note that a < 2 b implies ν a <

If we set

A = {a 1 , a 2 , . . . , a s } with a 1 < 1 a 2 < 1 • • • < 1 a s , the pair (λ, π)
formed by the family λ = (λ a ) a∈A and the permutation π determines the map T . We will also denote T as T λ,π . The transformation T is also said to be an s-interval exchange transformation.

It is easy to verify that if T is an interval exchange transformation, then T n is also an interval exchange transformation for any n ∈ Z. Set A = {a 1 , a 2 , . . . , a s } with a 1 < 1 a 2 < 1 . . . < 1 a s , µ i = µ ai and δ i = δ ai . The points 0, µ 1 , . . . , µ s-1 form the set of separation points of T , denoted Sep(T ). Note that the singular points of the transformation T (that is the points z ∈ [0, 1[ at which T is not continuous) are among the separation points but that the converse is not true in general (see Example 3.9).

An interval exchange transformation T λ,π is called regular if the orbits of the nonzero separation points µ 1 , . . . , µ s-1 are infinite and disjoint. Note that the orbit of 0 cannot be disjoint of the others since one has T (µ i ) = 0 for some

i with 1 ≤ i ≤ s -1.
The term regular was introduced by Rauzy in [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF]. A regular interval exchange transformation is also said to be without connections or satisfying the idoc condition (where idoc stands for infinite disjoint orbit condition).

Note that since δ 2 = T (µ 1 ), . . . , δ s = T (µ s-1 ), T is regular if and only if the orbits of δ 2 , . . . , δ s are infinite and disjoint.

As an example, the 2-interval exchange transformation of Example 2.1 which is the rotation of angle α is regular if and only if α is irrational.

Note that if T is a regular s-interval exchange transformation, then for any n ≥ 1, the transformation T n is an n(s-1)+1-interval exchange transformation.

Indeed, the points T i (µ j ) for 0 ≤ i ≤ n -1 and 1 ≤ j ≤ s -1 are distinct and define a partition in n(s -1) + 1 intervals.

The following result is due to Keane [12].

Theorem 2.3 (Keane) A regular interval exchange transformation is minimal.

The converse is not true. Indeed, consider the rotation of angle α with α irrational, as a 3-interval exchange transformation with λ = (1 -2α, α, α) and π = (132). The transformation is minimal as any rotation of irrational angle but it is not regular since µ 1 = 1 -2α, µ 2 = 1α and thus µ 2 = T (µ 1 ).

The following necessary condition for minimality of an interval exchange transformation is useful. A permutation π of an ordered set A is called decomposable if there exists an element b ∈ A such that the set B of elements strictly less than b is nonempty and such that π(B) = B. Otherwise it is called indecomposable. If an interval exchange transformation T = T λ,π is minimal, the permutation π is indecomposable. Indeed, if B is a set as above, the set S = ∪ a∈B I a is closed under T and strictly included in [0, 1[.

The following example shows that the indecomposability of π is not sufficient for T to be minimal.

Example 2.4 Let A = {a, b, c} and λ be such that λ a = λ c . Let π be the transposition (ac). Then π is indecomposable but T λ,π is not minimal since it is the identity on I b .

Natural coding

Let A be a finite nonempty alphabet. All words considered below, unless stated explicitly, are supposed to be on the alphabet A. We denote by A * the set of all words on A. We denote by 1 or by ε the empty word. We refer to [START_REF] Berstel | Codes and Automata[END_REF] for the notions of prefix, suffix, factor of a word.

Let T be an interval exchange transformation relative to (I a ) a∈A . For a given real number z ∈ [0, 1[, the natural coding of T relative to z is the infinite

word Σ T (z) = a 0 a 1 • • • on the alphabet A defined by a n = a if T n (z) ∈ I a . For a word w = b 0 b 1 • • • b m-1
, let I w be the set

I w = I b0 ∩ T -1 (I b1 ) ∩ . . . ∩ T -m+1 (I bm-1 ). (2.1)
Note that each I w is a semi-interval. Indeed, this is true if w is a letter. Next, assume that I w is a semi-interval. Then for any a ∈ A, T (I aw ) = T (I a ) ∩ I w is a semi-interval since T (I a ) is a semi-interval by definition of an interval exchange transformation. Since I aw ⊂ I a , T (I aw ) is a translate of I aw , which is therefore also a semi-interval. This proves the property by induction on the length.

Set J w = T m (I w ). Thus

J w = T m (I b0 ) ∩ T m-1 (I b1 ) ∩ . . . ∩ T (I bm-1 ). (2.2)
In particular, we have J a = T (I a ) for a ∈ A. Note that each J w is a semiinterval. Indeed, this is true if w is a letter. Next, for any a ∈ A, we have T -1 (J wa ) = J w ∩ I a . This implies as above that J wa is a semi-interval and proves the property by induction. We set by convention

I ε = J ε = [0, 1[. Then
one has for any n ≥ 0

a n a n+1 • • • a n+m-1 = w ⇐⇒ T n (z) ∈ I w (2.3)
and

a n-m a n-m+1 • • • a n-1 = w ⇐⇒ T n (z) ∈ J w . (2.4)
Let (α a ) a∈A be the translation values of T . Note that for any word w,

J w = I w + α w (2.

Uniformly recurrent sets

A set S of words on the alphabet A is said to be factorial if it contains the factors of its elements.

A factorial set is said to be right-extendable if for every w ∈ S there is some a ∈ A such that wa ∈ S. It is biextendable if for any w ∈ S, there are a, b ∈ A such that awb ∈ S.

A set of words S = {ε} is recurrent if it is factorial and if for every u, w ∈ S there is a v ∈ S such that uvw ∈ S. A recurrent set is biextendable. It is said to be uniformly recurrent if it is right-extendable and if, for any word u ∈ S, there exists an integer n ≥ 1 such that u is a factor of every word of S of length n. A uniformly recurrent set is recurrent.

We denote by A N the set of infinite words on the alphabet A. For a set X ⊂ A N , we denote by F (X) the set of factors of the words of X.

Let S be a set of words on the alphabet A.

For w ∈ S, set R(w) = {a ∈ A | wa ∈ S} and L(w = {a ∈ A | aw ∈ S}. A word w is called right-special if Card(R(w)) ≥ 2 and left-special if Card(L(w)) ≥ 2. It is bispecial if it is both
right and left-special.

An infinite word on a binary alphabet is Sturmian if its set of factors is closed under reversal and if for each n there is exactly one right-special word of length n.

An infinite word is a strict episturmian word if its set of factors is closed under reversal and for each n there is exactly one right-special word w of length n, which is moreover such that Card(R(w)) = Card(A).

A morphism f : A * → A * is called primitive if there is an integer k such that for all a, b ∈ A, the letter b appears in f k (a). If f is a primitive morphism, the set of factors of any fixpoint of f is uniformly recurrent (see [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF], Proposition 1.2.3 for example).

Example 2.5 Let A = {a, b}. The Fibonacci word is the fixpoint

x = f ω (a) = abaababa . . . of the morphism f : A * → A * defined by f (a) = ab and f (b) = a.
It is a Sturmian word (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]). The set F (x) of factors of x is the Fibonacci set.

Example 2.6 Let A = {a, b, c}. The Tribonacci word is the fixpoint

x = f ω (a) = abacaba • • • of the morphism f : A * → A * defined by f (a) = ab, f (b) = ac, f (c) = a.
It is a strict episturmian word (see [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF]). The set F (x) of factors of x is the Tribonacci set.

Interval exchange sets

Let T be an interval exchange set. The set

F (Σ T (z)) is called an interval exchange set. It is biextendable.
If T is a minimal interval exchange transformation, one has w ∈ F (Σ T (z))

if and only if I w = ∅. Thus the set F (Σ T (z)) does not depend on z. Since it depends only on T , we denote it by F (T ). When T is regular (resp. minimal), such a set is called a regular interval exchange set (resp. a minimal interval exchange set).

Let T be an interval exchange transformation. Let M be the closure in A N of the set of all Σ T (z) for z ∈ [0, 1[ and let σ be the shift on M . The pair (M, σ) is a symbolic dynamical system, formed of a topological space M and a continuous transformation σ. Such a system is said to be minimal if the only closed subsets invariant by σ are ∅ or M (that is, every orbit is dense). It is well-known that (M, σ) is minimal if and only if F (T ) is uniformly recurrent (see for example [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] Theorem 1.5.9).

We have the following commutative diagram (Figure 2.2).

[

0, 1[ [0, 1[ M M T Σ T σ Σ T Figure 2.2:
The transformations T and σ.

The map Σ T is neither continuous nor surjective. This can be corrected by embedding the interval [0, 1[ into a larger space on which T is a homeomophism (see [12] or [START_REF]Combinatorics, automata and number theory[END_REF] page 349). However, if the transformation T is minimal, the symbolic dynamical system (M, S) is minimal (see [START_REF]Combinatorics, automata and number theory[END_REF] page 392). Thus, we obtain the following statement.

Proposition 2.7 For any minimal interval exchange transformation T , the set

F (T ) is uniformly recurrent.
Note that for a minimal interval exchange transformation T , the map Σ T is injective (see [12] page 30).

The following is an elementary property of the intervals I u which will be used below. We denote by < 1 the lexicographic order on A * induced by the order < 1 on A.

Proposition 2.8 One has I u < I v if and only if u < 1 v and u is not a prefix of v.

Proof. For a word u and a letter a, it results from (2.1) that

I ua = I u ∩T -|u| (I a ).
Since (I a ) a∈A is an ordered partition, this implies that (T |u| (I u ) ∩ I a ) a∈A is an ordered partition of T |u| (I u ). Since the restriction of T |u| to I u is a translation, this implies that (I ua ) a∈A is an ordered partition of I u . Moreover, for two words u, v, it results also from (2.1) that

I uv = I u ∩ T -|u| (I v ). Thus I uv ⊂ I u .
Assume that u < 1 v and that u is not a prefix of v. We denote by < 2 the order on A * defined by u < 2 v if u is a proper suffix of v or if u = waz and v = tbz with a < 2 b. Thus < 2 is the lexicographic order on the reversal of the words induced by the order < 2 on the alphabet.

We denote by π the morphism from A * onto itself which extends to A * the permutation π on A. Then u < 2 v if and only if π -1 (ũ) < 1 π -1 (ṽ), where ũ denotes the reversal of the word u.

The following statement is the analogue of Proposition 2.8.

Proposition 2.9 Let T λ,π be an interval exchange transformation. One has

J u < J v if and only if u < 2 v and u is not a suffix of v.
Proof. Let (I ′ a ) a∈A be the family of semi-intervals defined by I ′ a = J π(a) . Then the interval exchange transformation T ′ relative to (I ′ a ) with translation values -α a is the inverse of the transformation T . The semi-intervals I ′ w defined by Equation (2.1) with respect to T ′ satisfy I ′ w = J π( w) or equivalently J w =

I ′ π -1 ( w) . Thus, J u < J v if and only if I ′ π -1 (ũ) < I ′ π -1 (ṽ) if and only if (by Proposition 2.8) π -1 (ũ) < 1 π -1 (ṽ) or equivalently u < 2 v.
3 Bifix codes and interval exchange

In this section, we first introduce prefix codes and bifix codes. For a more detailed exposition, see [START_REF] Berstel | Codes and Automata[END_REF]. We describe the link between maximal bifix codes and interval exchange transformations and we prove our main result (Theorem 3.13).

Prefix codes and bifix codes

A prefix code is a set of nonempty words which does not contain any proper prefix of its elements. A suffix code is defined symmetrically. A bifix code is a set which is both a prefix code and a suffix code.

A coding morphism for a prefix code

X ⊂ A + is a morphism f : B * → A * which maps bijectively B onto X.
Let S be a set of words. A prefix code X ⊂ S is S-maximal if it is not properly contained in any prefix code Y ⊂ S. Note that if X ⊂ S is an Smaximal prefix code, any word of S is comparable for the prefix order with a word of X.

A map λ : A * → [0, 1] such that λ(ε) = 1 and, for any word The fact that λ is an invariant probability measure is equivalent to the fact that the Lebesgue measure on [0, 1[ is invariant by T . It is known that almost all regular interval exchange transformations have no other invariant probability measure (and thus are uniquely ergodic, see [START_REF]Combinatorics, automata and number theory[END_REF] for references). The following result is a particular case of a result from [2] (Proposition

w a∈A λ(aw) = a∈A λ(wa) = λ(w), (3.1

3.3.4).

Proposition 3.2 Let T be a minimal interval exchange transformation, let S = F (T ) and let λ be an invariant probability distribution on S. For any finite S-

maximal prefix code X, one has x∈X λ(x) = 1. 1 1 -α α 1 -2α α α 1 -2α α 1 -2α 3α -1 1 -2α 1 -2α 3α -1 1 -2α 3α -1
I aa = [0, 1 -2α[, I ab = [1 -2α, 1 -α[, I b = [1 -α, 1[.
The values of the lengths of the semi-intervals (the invariant probability distribution) can also be read on Figure 3.1.

A symmetric statement holds for an S-maximal suffix code, namely that the family (J w ) w∈X is an ordered partition of [0, 1[ for the order < 2 on X.

Maximal bifix codes

Let S be a set of words. A bifix code X ⊂ S is S-maximal if it is not properly contained in a bifix code Y ⊂ S. For a recurrent set S, a finite bifix code is S-maximal as a bifix code if and only if it is an S-maximal prefix code (see [2],

Theorem 4.2.2).

A parse of a word w with respect to a bifix code X is a triple (v, x, u) such that w = vxu where v has no suffix in X, u has no prefix in X and x ∈ X * . We denote by δ X (w) the number of parses of w with respect to X.

The number of parses of a word w is also equal to the number of suffixes of w which have no prefix in X and the number of prefixes of w which have no suffix in X (see Proposition 6.1.6 in [START_REF] Berstel | Codes and Automata[END_REF]).

By definition, the S-degree of a bifix code X, denoted d X (S), is the maximal number of parses of a word in S. It can be finite or infinite.

The set of internal factors of a set of words X, denoted I(X), is the set of words w such that there exist nonempty words u, v with uwv ∈ X.

Let S be a recurrent set and let X be a finite S-maximal bifix code of Sdegree d. A word w ∈ S is such that δ X (w) < d if and only if it is an internal factor of X, that is

I(X) = {w ∈ S | δ X (w) < d} (Theorem 4.2.8 in [2]
). Thus any word of S which is not a factor of X has d parses. This implies that the S-degree d is finite.

Example 3.5 Let S be a recurrent set. For any integer n ≥ 1, the set S ∩ A n is an S-maximal bifix code of S-degree n.

The kernel of a bifix code X is the set K(X) = I(X) ∩ X. Thus it is the set of words of X which are also internal factors of X. By Theorem 4.3.11 of [2], a finite S-maximal bifix code is determined by its S-degree and its kernel. Proof. This results from Proposition 3.3 and its symmetric and from the fact that, since S is recurrent, a finite S-maximal bifix code is both an S-maximal prefix code and an S-maximal suffix code.

Let T be a regular interval exchange transformation relative to (I a ) a∈A . Let (α a ) a∈A be the translation values of T . Set S = F (T ). Let X be a finite S-maximal bifix code on the alphabet A.

Let T X be the transformation on [0, 1[ defined by

T X (z) = T |u| (z) if z ∈ I u with u ∈ X.
I u = [0, 1 -2α[, I v = [1 -2α, 1 -α[ I w = [1 -α, 1[
and

J v = [0, α[, J w = [α, 2α[ J u = [2α, 1[
The transformation T f is represented in Figure 3.2. It is actually a representa- 3.2: The transformation T f . tion on 3 intervals of the rotation of angle 2α. Note that the point z = 1α is a separation point which is not a singularity of T f . The first row of Table 3.1 gives the two orders on X. The next two rows give the two orders for each of the two other S-maximal bifix codes of S-degree 2 (there are actually exactly three S-maximal bifix codes of S-degree 2 in the Fibonacci set, see [2]).

0 1 -2α 1 -α 1 u v w 0 α 2α 1 v w u Figure
Let T be a minimal interval exchange transformation on the alphabet A.

Let x be the natural coding of T relative to some z ∈ [0, 1[. Set S = F (x). Let X be a finite S-maximal bifix code. Let f : B * → A * be a morphism which maps bijectively B onto X. Since S is recurrent, the set X is an S-maximal (X, < 1 ) (X, < 2 ) aa, ab, ba ab, ba, aa a, baab, bab bab, baab, a aa, aba, b b, aba, aa Table 3.1: The two orders on the three S-maximal bifix codes of S-degree 2.

prefix code. Thus x has a prefix x 0 ∈ X. Set x = x 0 x ′ . In the same way x ′ has a prefix x 1 in X. Iterating this argument, we see that

x = x 0 x 1 • • • with x i ∈ X.
Consequently, there exists an infinite word y on the alphabet B such that x = f (y). The word y is the decoding of the infinite word x with respect to f . Proposition 3.10 The decoding of x with respect to f is the natural coding of the transformation associated with f relative to z:

Σ T (z) = f (Σ T f (z)).
Proof. Let y = b 0 b 1 • • • be the decoding of x with respect to f . Set

x i = f (b i )
for i ≥ 0. Then, for any n ≥ 0, we have showing that y is the natural coding of T f relative to z.

T n f (z) = T |un| (z) (3.2) with u n = x 0 • • • x n-1 (note that |u n | denotes the length of u n with respect to the alphabet A). Indeed, this is is true for n = 0. Next T n+1 f (z) = T f (t) with t = T n f (z). Arguing by induction, we have t = T |un| (z). Since x = u n x n x n+1 • • • , t is in I xn by (2.
Example 3.11 Let T, α, X and f be as in Example 3.9. Let x = abaababa • • • be the Fibonacci word. We have x = Σ T (α). The decoding of x with respect to

f is y = vuwwv • • • .

Bifix codes and regular transformations

The following result shows that for the coding morphism f of a finite S-maximal bifix code, the map T → T f preserves the regularity of the transformation.

Theorem 3.12 Let T be a regular interval exchange transformation and let S = F (T ). For any finite S-maximal bifix code X with coding morphism f , the transformation T f is regular.

Proof. Set A = {a 1 , a 2 , . . . , a s } with a 1 < 1 a 2 < 1 • • • < 1 a s . We denote δ i = δ ai . By hypothesis, the orbits of δ 2 , . . . , δ s are infinite and disjoint. Set

X = {x 1 , x 2 , . . . , x t } with x 1 < 1 x 2 < 1 • • • < 1 x t .
Let d be the S-degree of X.

For x ∈ X, denote by δ x the left boundary of the semi-interval J x . For each

x ∈ X, it follows from Equation (2.2) that there is an i ∈ {1, . . . , s} such that

δ x = T k (δ i ) with 0 ≤ k < |x|. Moreover, we have i = 1 if and only if x = x 1 .
Since T is regular, the index i = 1 and the integer k are unique for each x = x 1 .

And for such x and i, by (2.4), we have Σ T (δ i ) = uΣ T (δ x ) with u a proper suffix of x.

We now show that the orbits of δ x2 , . . . , δ xt for the transformation T f are infinite and disjoint. Assume that δ xp = T n f (δ xq ) for some p, q ∈ {2, . . . , t} and n ∈ Z. Interchanging p, q if necessary, we may assume that n ≥ 0. Let i, j ∈ {2, . . . , s} be such that

δ xp = T k (δ i ) with 0 ≤ k < |x p | and δ xq = T ℓ (δ j ) with 0 ≤ ℓ < |x q |. Since T k (δ i ) = T n f (T ℓ (δ j )) = T m+ℓ (δ j )
for some m ≥ 0, we cannot have i = j since otherwise the orbits of δ i , δ j for the transformation T intersect.

Thus i = j. Since δ xp = T k (δ i ), we have Σ T (δ i ) = uΣ T (δ xp ) with |u| = k, u
proper suffix of x p . And since

δ xp = T n f (δ xq ), we have Σ T (δ xq ) = xΣ T (δ xp ) with
x ∈ X * . Since on the other hand δ xq = T ℓ (δ i ), we have Σ T (δ i ) = vΣ T (δ xq ) with |v| = ℓ and v a proper suffix of x q . We obtain

Σ T (δ i ) = uΣ T (δ xp ) = vΣ T (δ xq ) = vxΣ T (δ xp )
Since |u| = |vx|, this implies u = vx. But since u cannot have a suffix in X, u = vx implies x = 1 and thus n = 0 and p = q. This concludes the proof.

Let f be a coding morphism for a finite S-maximal bifix code X ⊂ S. The set f -1 (S) is called a maximal bifix decoding of S.

Theorem 3.13 The family of regular interval exchange sets is closed under maximal bifix decoding.

Proof. Let T be a regular interval exchange transformation such that S = F (T ).

By Theorem 3.12, T f is a regular interval exchange transformation. We show that f -1 (S) = F (T f ), which implies the conclusion.

Let x = Σ T (z) for some z ∈ [0, 1[ and let y = f -1 (x). Then S = F (x) and

F (T f ) = F (y).
For any w ∈ F (y), we have f (w) ∈ F (x) and thus w ∈ f -1 (S).

This shows that F (T f ) ⊂ f -1 (S). Conversely, let w ∈ f -1 (S) and let v = f (w).

Since S = F (x), there is a word u such that uv is a prefix of x. Set z ′ = T |u| (z)

and x ′ = Σ T (z ′ ). Then v is a prefix of x ′ and w is a prefix of y ′ = f -1 (x ′ ).
Since T f is regular, it is minimal and thus F (y ′ ) = F (T f ). This implies that

w ∈ F (T f ).
Since a regular interval exchange set is uniformly recurrent, Theorem 3.13 implies in particular that if S is a regular interval exchange set and f a coding morphism of a finite S-maximal bifix code, then f -1 (S) is uniformly recurrent. This is not true for an arbitrary uniformly recurrent set S, as shown by the following example.

Example 3.14 Set A = {a, b} and B = {u, v}. Let S be the set of factors of (ab) * and let f : B * → A * be defined by f (u) = ab and f (v) = ba. Then

f -1 (S) = u * ∪ v * which is not recurrent.
We illustrate the proof of Theorem 3.12 in the following example. The following example shows that Theorem 3.13 is not true when X is not bifix.

Example 3.16 Let S be the Fibonacci set and let X = {aa, ab, b}. The set X is an S-maximal prefix code. Let B = {u, v, w} and let f be the coding morphism for X defined by

f (u) = aa, f (v) = ab, f (w) = b. The set W = f -1 (S)
is not an interval exchange set. Indeed, we have vu, vv, wu, wv ∈ W . This implies that both J v and J w meet I u and I v , which is impossible in an interval exchange transformation.

Tree sets

We introduce in this section the notions of tree sets and planar tree sets. We first introduce the notion of extension graph which describes the possible two-sided extensions of a word.

Extension graphs

Let S be a biextendable set of words. For w ∈ S, we denote

L(w) = {a ∈ A | aw ∈ S}, R(w) = {a ∈ A | wa ∈ S} and
E(w) = {(a, b) ∈ A × A | awb ∈ S}.
For w ∈ S, the extension graph of w is the undirected bipartite graph G(w) on the set of vertices which is the disjoint union of two copies of L(w) and R(w

)
with edges the pairs (a, b) ∈ E(w).

Recall that an undirected graph is a tree if it is connected and acyclic.

Let S be a biextendable set. We say that S is a tree set if the graph G(w) is a tree for all w ∈ S.

Let < 1 and < 2 be two orders on A. For a set S and a word w ∈ S, we say that the graph G(w) is compatible with the orders < 1 and < 2 if for any

(a, b), (c, d) ∈ E(w), one has a < 1 c =⇒ b ≤ 2 d.
Thus, placing the vertices of L(w) ordered by < 1 on a line and those of R(w) ordered by < 2 on a parallel line, the edges of the graph may be drawn as straight noncrossing segments, resulting in a planar graph.

We say that a biextendable set S is a planar tree set with respect to two orders < 1 and < 2 on A if for any w ∈ S, the graph G(w) is a tree compatible with < 1 , < 2 . Obviously, a planar tree set is a tree set.

The following example shows that the Tribonacci set is not a planar tree set. the three graphs planar.

Interval exchange sets and planar tree sets

The following result is proved in [START_REF] Ferenczi | Languages of k-interval exchange transformations[END_REF] with a converse (see below).

Proposition 4.2 Let T be an interval exchange transformation on A ordered by < 1 and < 2 . If T is regular, the set F (T ) is a planar tree set with respect to < 2 and < 1 .

Proof. Assume that T is a regular interval exchange transformation relative to (I a , α a ) a∈A and let S = F (T ).

Since T is minimal, w is in S if and only if I w = ∅. Thus, one has

(i) b ∈ R(w) if and only if I w ∩ T -|w| (I b ) = ∅ and (ii) a ∈ L(w) if and only if J a ∩ I w = ∅.
Condition (i) holds because I wb = I w ∩ T -|w| (I b ) and condition (ii) because

I aw = I a ∩ T -1 (I w ), which implies T (I aw ) = J a ∩ I w .
In particular, (i) implies that (I wb ) b∈R(w) is an ordered partition of I w with respect to < 1 .

We say that a path in a graph is reduced if does not use consecutively the same edge. For a, a ′ ∈ L(w) with a < 2 a ′ , there is a unique reduced path in 4.2). Note that the hypothesis that T is regular is needed here since otherwise the right boundary of J ai could be the left boundary of

G(w) from a to a ′ which is the sequence a 1 , b 1 , . . . a n with a 1 = a and a n = a ′ with a 1 < 2 a 2 < 2 • • • < 2 a n , b 1 < 1 b 2 < 1 • • • < 1 b n-1 and J ai ∩ I wbi = ∅, J ai+1 ∩ I wbi = ∅ for 1 ≤ i ≤ n -1 (see Figure
I wbi . Thus G(w) is a tree. It is compatible with < 2 , < 1 since the above shows that a < 2 a ′ implies that the letters b 1 , b n-1 such that (a, b 1 ), (a ′ , b n-1 ) ∈ E(w) satisfy b 1 ≤ 1 b n-1 . I wb1 I wb2 I w b n-1 J a1 J a2 J an-1 J an Figure 4.2: A path from a 1 to a n in G(w).
By Proposition 4.2, a regular interval exchange set is a planar tree set, and thus in particular a tree set. Note that the analogue of Theorem 3.13 holds for the class of uniformly recurrent tree sets [START_REF] Berthé | Maximal bifix decoding[END_REF].

The main result of [START_REF] Ferenczi | Languages of k-interval exchange transformations[END_REF] states that a uniformly recurrent set S on an alphabet

A is a regular interval exchange set if and only if A ⊂ S and there exist two orders < 1 and < 2 on A such that the following conditions are satisfied for any word w ∈ S.

(i) The set L(w) (resp. R(w)) is formed of consecutive elements for the order

< 2 (resp. < 1 ). (ii) For (a, b), (c, d) ∈ E(w), if a < 2 c, then b ≤ 1 d.
(iii) If a, b ∈ L(w) are consecutive for the order < 2 , then the set R(aw)∩R(bw) is a singleton.

It is easy to see that a biextendable set S containing A satisfies (ii) and (iii)

if and only if it is a planar tree set. Actually, in this case, it automatically satisfies also condition (i). Indeed, let us consider a word w and a, b, c ∈ A with This shows that the following reformulation of the main result of [START_REF] Ferenczi | Languages of k-interval exchange transformations[END_REF] is equivalent to the original one. We have already seen that the Tribonacci set is a tree set which is not a planar tree set (Example 4.1). The next example shows that there are uniformly recurrent tree sets which are neither Sturmian nor regular interval exchange sets.

Exchange of pieces

In this section, we show how one can define a generalization of interval exchange transformations called exchange of pieces. In the same way as interval exchange is a generalization of rotations on the circle, exchange of pieces is a generalization of rotations of the torus. We begin by studying this direction starting from the Tribonacci word. For more on the Tribonacci word, see [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF] and also [START_REF] Lothaire | Applied combinatorics on words[END_REF]Chap. 10].

The Tribonacci shift The Tribonacci set S is not an interval exchange set but it is however the natural coding of another type of geometric transformation, namely an exchange of pieces in the plane, which is also a translation acting on the two-dimensional torus T 2 . This will allow us to show that the decoding of the Tribonacci word with respect to a coding morphism for a finite S-maximal bifix code is again a natural coding of an exchange of pieces.

The Tribonacci shift is the symbolic dynamical system (M x , σ), where M Natural coding Let Λ be a full-rank lattice in R d . We say that an infinite word x is a natural coding of a toral translation

T t : R d /Λ → R d /Λ, x → x + t
if there exists a fundamental domain R for Λ together with a partition R =

R 1 ∪ • • • ∪ R k such that on each R i (1 ≤ i ≤ k)
, there exists a vector t i such that the map T t is given by the translation along t i , and x is the coding of a point

x ∈ R with respect to this partition. A symbolic dynamical system (M, σ) is a natural coding of (R d /Λ, T t ) if every element of M is a natural coding of the orbit of some point of the d-dimensional torus R d /Λ (with respect to the same partition) and if, furthermore, (M, σ) and (R d /Λ, T t ) are measurably conjugate.

Definition of the Rauzy fractal Let β stand for the Perron-Frobenius eigenvalue of the Tribonacci substitution. It is the largest root of z 3z 2z -1.

Consider the translation R β : T 2 → T 2 , x → x + (1/β, 1/β 2 ). Rauzy introduces in [START_REF] Rauzy | Nombres algébriques et substitutions[END_REF] a fundamental domain for a two-dimensional lattice, called the Rauzy fractal (it has indeed fractal boundary), which provides a partition for the symbolic dynamical system (M x , σ) to be a natural coding for R β . The Tribonacci word is a natural coding of the orbit of the point 0 under the action of the toral translation in T 2 : x → x + ( 1 β , 1 β 2 ). Similarly as in the case of interval exchanges, we have the following commutative diagram

T 2 -→ R β T 2     M x σ -→ M x
The Abelianization map f of the free monoid {1, 2, 3} * is defined by f : The Rauzy fractal is divided into three pieces, for i = {1, 2, 3}

{1, 2, 3} * → Z 3 , f (w) = |w| 1 e 1 + |w| 2 e 2 +
R(i) := {π(f (x 0 • • • x n-1 )); x n = i, n ∈ N}, R ′ (i) := {π(f (x 0 • • • x n )); x n = i, n ∈ N}.
It has been proved in [START_REF] Rauzy | Nombres algébriques et substitutions[END_REF] that these pieces have non-empty interior and are disjoint up to a set of zero measure. The following exchange of pieces E is thus well-defined

E : Int R 1 ∪ Int R 2 ∪ Int R 3 → R, x → x + π(e i ), when x ∈ Int R i . One has E(R i ) = R ′ i , for all i.
We consider the lattice Λ generated by the vectors π(e i )π(e j ), for i = j.

The Rauzy fractal tiles periodically the plane, that is, ∪ γ∈Λ γ + R is equal to the plane x + y + z = 0, and for γ = γ ′ ∈ Λ, γ + R and γ ′ + R do not intersect (except on a set of zero measure). This is why the exchange of pieces is in fact measurably conjugate to the translation R β . Indeed the vector of coordinates of π(f

(x 0 x 1 • • • x n-1
)) in the basis (π(e 3 )π(e 1 ), π(e 3 )π(e 2 )) of the plane

x + y + z = 0 is n • (1/β, 1/β 2 ) -(|x 0 x 1 • • • x n-1 | 1 , |x 0 x 1 • • • x n-1 | 2 )
. Hence the coordinates of E n (0) in the basis (e 3e 1 , e 3e 2 ) are equal to R n β (0) modulo

Z 2 .
Bifix codes and exchange of pieces Let (R a ) a∈A and (R ′ a ) a∈A be two families of subsets of a compact set R incuded in R d . We assume that the families (R a ) a∈A and the (R ′ a ) a∈A both form a partition of R up to a set of zero measure. We assume that there exist vectors e a such that R ′ a = R a + e a for any a ∈ A. The exchange of pieces associated with these data is the map E defined on R (except a set of measure zero) by E(z) = z + e a if z ∈ R a . The notion of natural coding of an exchange of pieces extends here in a natural way.

Assume that E is an exchange of pieces as defined above. Let S be the set of factors of the natural codings of E. We assume that S is uniformly recurrent.

By analogy with the case of interval exchanges, let I a = R a and let J a = E(R a ). For a word w ∈ A * , one defines similarly as for interval exchanges I w and J w .

Let X be a finite S-maximal prefix code. The family I w , w ∈ X, is a partition (up to sets of zero measure) of R. If X is a finite S-maximal suffix code, then the family J w is a partition (up to sets of zero measure) of R. Let f be a coding morphism for X. If X is a finite S-maximal bifix code, then E X is the exchange of pieces E f (defined as for interval exchanges), hence the decoding of x with respect to f is the natural coding of the exchange of pieces associated with f . In particular, S being the Tribonacci set, the decoding of S by a finite S-maximal bifix code is again the natural coding of an exchange of pieces. If X is the set of factors of length n of S, then E f is in fact equal to R n β (otherwise, there is no reason for this exchange of pieces to be a translation).

The analogues of Proposition 3.8 and 3.10 thus hold here also.

Subgroups of finite index

We denote by F G(A) the free group on the set A.

Let S be a recurrent set containing the alphabet A. We say that S has the finite index basis property if the following holds: a finite bifix code X ⊂ S is an S-maximal bifix code of S-degree d if and only if it is a basis of a subgroup of index d of F G(A).

The following is a consequence of the main result of [START_REF] Berthé | The finite index basis property[END_REF].

Theorem 4.5 A regular interval exchange set has the finite index basis property.

Proof. Let T be a regular interval exchange transformation and let S = F (T ).

Since T is regular, S is uniformly recurrent and by Proposition 4.2, it is a tree set. By Theorem 4.4 in [START_REF] Berthé | The finite index basis property[END_REF], a uniformly recurrent tree set has the finite index basis property, and thus the conclusion follows.

Note that Theorem 4.5 implies in particular that if T is a regular s-interval exchange set and if X is a finite S-maximal bifix code of S-degree d, then Card(X) = d(s -1) + 1. Indeed, by Schreier's Formula a basis of a subgroup of index d in a free group of rank s has d(s -1) + 1 elements.

We use Theorem 4.5 to give another proof of Theorem 3.12. For this, we recall the following notion. (where qψ(z) is the result of the action of the permutation ψ(z) on q ∈ Q).

Such a transformation is equivalent to an interval exchange transformation via the identification of I × Q with an interval obtained by placing the d = Card(Q) copies of I in sequence. This is called an interval exchange transformation on a stack in [START_REF] Michael | An extension of Lagrange's theorem to interval exchange transformations over quadratic fields[END_REF] (see also [START_REF] Veech | Finite group extensions of irrational rotations[END_REF]). If T is regular, then U is also regular.

Let T be a regular interval exchange transformation and let S = F (T ). Let The transformation induced by the skew product U on I × {1} is clearly equivalent to the transformation T f = T X where f is a coding morphism for the S-maximal bifix code X. Thus T X is a regular interval exchange transformation.

  Thus it is a left-closed and right-open interval. For two semi-intervals ∆, Γ, we denote ∆ < Γ if x < y for any x ∈ ∆ and y ∈ Γ. Let (A, <) be an ordered set. A partition (I a ) a∈A of [0, 1[ in semi-intervals is ordered if a < b implies I a < I b . Let A be a finite set ordered by two total orders < 1 and < 2 . Let (I a ) a∈A be a partition of [0, 1[ in semi-intervals ordered for < 1 . Let λ a be the length of I a . Let µ a = b≤1a λ b and ν a = b≤2a λ b . Set α a = ν aµ a . The interval exchange transformation relative to (I a ) a∈A is the map T : [0, 1[→ [0, 1[ defined by

  ν b and thus J a < J b . This shows that the family (J a ) a∈A is a partition of [0, 1[ ordered for < 2 . In particular, the transformation T defines a bijection from [0, 1[ onto itself. An interval exchange transformation relative to (I a ) a∈A is also said to be on the alphabet A. The values (α a ) a∈A are called the translation values of the transformation T . Example 2.1 Let R be the interval exchange transformation corresponding to A = {a, b}, a < 1 b, b < 2 a, I a = [0, 1-α[, I b = [1-α, 1[. The transformation R is the rotation of angle α on the semi-interval [0, 1[ defined by R(z) = z + α mod 1.

a µ b µ c ν b ν c ν a Figure 2 . 1 :

 a21 Figure 2.1: A 3-interval exchange transformation

5 ) with α w = m- 1 j=0

 51 α bj as one may verify by induction on |w| = m. Indeed it is true for m = 1. For m ≥ 2, set w = ua with a = b m-1 . One has T m (I w ) = T m-1 (I w ) + α a and T m-1 (I w ) = I w + α u by the induction hypothesis and the fact that I w is included in I u . Thus J w = T m (I w ) = I w + α u + α a = I w + α w . Equation (2.5) shows in particular that the restriction of T |w| to I w is a translation.

  Then u = ℓas and v = ℓbt with a, b two letters such that a < 1 b. Then we have I ℓa < I ℓb , with I u ⊂ I ℓa and I v ⊂ I ℓb whence I u < I v . Conversely, assume that I u < I v . Since I u ∩ I v = ∅, the words u, v cannot be comparable for the prefix order. Set u = ℓas and v = ℓbt with a, b two distinct letters. If b < 1 a, then I v < I u as we have shown above. Thus a < 1 b which implies u < 1 v.

  ) is called an invariant probability distribution on A * . Let T λ,π be an interval exchange transformation. For any word w ∈ A * , denote by |I w | the length of the semi-interval I w defined by Equation (2.1). Set λ(w) = |I w |. Then λ(ε) = 1 and for any word w, Equation (3.1) holds and thus λ is an invariant probability distribution.

Example 3 . 1

 31 Let S be the set of factors of the Fibonacci word (see Example 2.5). It is the natural coding of the rotation of angle α = (3 -√ 5)/2 with respect to α (see [13], Chapter 2). The values of the map λ on the words of length at most 4 in S are indicated in Figure 3.1.

Figure 3 . 1 :Example 3 . 4

 3134 Figure 3.1: The invariant probability distribution on the Fibonacci set.

Example 3 . 6 Proposition 3 . 7

 3637 Let S be the Fibonacci set. The set X = {a, baab, bab} is the unique S-maximal bifix code of S-degree 2 with kernel {a}. Indeed, the word bab is not an internal factor and has two parses, namely (1, bab, 1) and (b, a, b).The following result shows that bifix codes have a natural connection with interval exchange transformations. If X is a finite S-maximal bifix code, with S as in Proposition 3.3, the families (I w ) w∈X and (J w ) w∈X are ordered partitions of [0, 1[, relatively to the orders < 1 and < 2 respectively.

  The transformation is well-defined since, by Proposition 3.7, the family (I u ) u∈X is a partition of [0, 1[. Let f : B * → A * be a coding morphism for X. Let (K b ) b∈B be the family of semi-intervals indexed by the alphabet B with K b = I f (b) . We consider B as ordered by the orders < 1 and < 2 induced by f . Let T f be the interval exchange transformation relative to (K b ) b∈B . Its translation values are β b = m-1 j=0 α aj for f (b) = a 0 a 1 • • • a m-1 . The transformation T f is called the transformation associated with f . Proposition 3.8 Let T be a regular interval exchange transformation relative to (I a ) a∈A and let S = F (T ). If f : B * → A * is a coding morphism for a finite S-maximal bifix code X, one has T f = T X . Proof. By Proposition 3.7, the family (K b ) b∈B is a partition of [0, 1[ ordered by < 1 . For any w ∈ X, we have by Equation (2.5) J w = I w + α w and thus T X is the interval exchange transformation relative to (K b ) b∈B with translation values β b . In the sequel, under the hypotheses of Proposition 3.8, we consider T f as an interval exchange transformation. In particular, the natural coding of T f relative to z ∈ [0, 1[ is well-defined. Example 3.9 Let S be the Fibonacci set. It is the set of factors of the Fibonacci word, which is a natural coding of the rotation of angle α = (3 -√ 5)/2 relative to α (see Example 3.1). Let X = {aa, ab, ba} and let f be the coding morphism defined by f (u) = aa, f (v) = ab, f (w) = ba. The two partitions of [0, 1[ corresponding to T f are

  3). Thus by Proposition 3.8, T f (t) = T |xn| (t) and we obtain T n+1 f (z) = T |xn| (T |un| (z)) = T |un+1| (z) proving (3.2). Finally, for u = f (b) with b ∈ B, b n = b ⇐⇒ x n = u ⇐⇒ T |un| (z) ∈ I u ⇐⇒ T n f (z) ∈ I u = K b

Example 3 .Figure 3 µ x2 µ x3 µ x4 δ x4 δ x3 δ x2 δ x1 1 Figure 3 . 3 :Figure 3 . 4 :

 3313334 Figure 3.3.

Example 4 . 1 Figure 4 . 1 .Figure 4 . 1 :

 414141 Figure 4.1. One sees easily that it not possible to find two orders on A making a b c

a < 1 b < 1 c

 1 such that wa, wc ∈ S but wb / ∈ S. Since b ∈ S there is a (possibly empty) suffix v of w such that vb ∈ S. We choose v of maximal length. Since wb / ∈ S, we have w = uv with u nonempty. Let d be the last letter of u. Then we have dva, dvc ∈ S and dvb / ∈ S. Since G(v) is a tree and b ∈ R(v), there is a letter e ∈ L(v) such that evb ∈ S. But e < 2 d and d < 2 e are both impossible since G(v) is compatible with < 2 and < 1 . Thus we reach a contradiction.

Theorem 4 . 3 (

 43 Ferenczi, Zamboni) A set S is a regular interval exchange set on the alphabet A if and only if it is a uniformly recurrent planar tree set containing A.

Example 4 . 4

 44 Let S be the Tribonacci set on the alphabet A = {a, b, c} and let f : {x, y, z, t, u} * → A * be the coding morphism for X = S ∩ A 2 defined byf (x) = aa, f (y) = ab, f (z) = ac, f (t) = ba, f (u) = ca. By Theorem 7.1 in [4],the set W = f -1 (S) is a uniformly recurrent tree set. It is not Sturmian since y and t are two right-special words. It is not either a regular interval exchange set. Indeed, for any right-special word w of W , one has Card(R(w)) = 3. This is not possible in a regular interval exchange set T since, Σ T being injective, the length of the interval J w tends to 0 as |w| tends to infinity and it cannot contain several separation points. It can of course also be verified directly that W is not a planar tree set.

  x = {σ n (x) : n ∈ N} is the closure of the σ-orbit of x where x is the Tribonacci word. By uniform recurrence of the Tribonacci word, (M x , σ) is minimal and M x = M y for each y ∈ M x ([16, Proposition 4.7]). The Tribonacci set is the set of factors of the Tribonacci shift (M x , σ).

|w| 3 e 3 ,

 3 where |w| i denotes the number of occurrences of the letter i in the word w, and (e 1 , e 2 , e 3 ) stands for the canonical basis of R 3 .Let f be the morphism a → ab, b → ac, c → a such that the Tribonacci word is the fixpoint of f (see Example 2.6). The incidence matrix F of f is defined by F = (|f (j)| i ) (i,j)∈A 2 , where |f (j)| i counts the number of occurrences of the letter i in f (j). One has F = The incidence matrix F admits as eigenspaces in R 3 one expanding eigenline (generated by the eigenvector with positive coordinates v β = (1/β, 1/β 2 , 1/β 3 ) associated with the eigenvalue β).We consider the projection π onto the antidiagonal plane x + y + z = 0 along the expanding direction of the matrix F .One associates with the Tribonacci word x = (x n ) n≥0 a broken line starting from 0 in Z 3 and approximating the expanding line v β as follows. The Tribonacci broken line is defined as the broken line which joins with segments of length 1 the points f (x 0 x 1 • • • x n-1 ), n ∈ N. In other words we describe this broken line by starting from the origin, and then by reading successively the letters of the Tribonacci word x, going one step in direction e i if one reads the letter i. Thevectors f (x 0 x 1 • • • x n ), n ∈ N,stay within bounded distance of the expanding line (this comes from the fact that β is a Pisot number). The closure of the set of projected vertices of the broken line is called the Rauzy fractal and is represented on Figure 4.3. We thus define the Rauzy fractal R as R := {π(f (x 0 • • • x n-1 )); n ∈ N}, where x 0 . . . x n-1 stands for the empty word when n = 0.

Figure 4 . 3 :

 43 Figure 4.3: The Rauzy fractal

Let

  T be an interval exchange transformation on I = [0, 1[ relative to (I a ) a∈A . Let G be a transitive permutation group on a finite set Q. Let ϕ : A * → G be a morphism and let ψ be the map from I into G defined by ψ(z) = ϕ(a) if z ∈ I a . The skew product of T and G is the transformation U on I × Q defined by U (z, q) = (T (z), qψ(z))

X

  be a finite S-maximal bifix code of S-degree d = d X (S). By Theorem 4.5, X is a basis of a subgroup H of index d of F G(A). Let G be the representation of F G(A) on the right cosets of H and let ϕ be the natural morphism from F G(A) onto G. We identify the right cosets of H with the set Q = {1, 2, . . . , d} with 1 identified to H. Thus G is a transitive permutation group on Q and H is the inverse image by ϕ of the permutations fixing 1.

Example 4 . 6 Figure 4 . 4 :

 4644 Let T be the rotation of Example 3.1. Let Q = {1, 2, 3} and let ϕ be the morphism from A * into the symmetric group on Q defined by ϕ(a) = (23) and ϕ(b) = (12). The transformation induced by the skew product of T and G on I × {1} corresponds to the bifix code X of Example 3.15. For example, we have U : (1α, 1) → (0, 2) → (α, 3) → (2α, 2) → (3α -1, 1) (see Figure 4.4) and the corresponding word of X is baab. The transformation U .


domain: info math

text:
Valérie Berthé

Clelia De Felice

Vincent Delecroix

Francesco Dolce

Julien Leroy

Dominique Perrin

Christophe Reutenauer

Giuseppina Rindone

à 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

We have studied in a series of papers initiated in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] the links between minimal sets, subgroups of free groups and bifix codes. In this paper, we continue this investigation in a situation which involves groups which are not free anymore. These groups, named here specular, are free products of a free group and of a finite number of cyclic groups of order two. These groups are close to free groups and, in particular, the notion of a basis in such groups is clearly defined. It follows from Kurosh's theorem that any subgroup of a specular group is specular. A specular set is a subset of such a group which generalizes the natural codings of linear involutions studied in [START_REF] Berthé | Return words of linear involutions and fundamental groups[END_REF].

The main results of this paper are Theorem 5.1, referred to as the Return Theorem and Theorem 5.2, referred to as the Finite Index Basis Theorem. The first one asserts that the set of return words to a given word in a uniformly recurrent specular set is a basis of a subgroup of index 2 called the even subgroup. The second one characterizes the monoidal bases of subgroups of finite index of specular groups contained in a specular set S as the finite S-maximal symmetric bifix codes contained in S. This generalizes the analogous results proved initially in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] for Sturmian sets and extended in [START_REF] Berthé | The finite index basis property[END_REF] to the class of tree sets (this class contains both Sturmian sets and interval exchange sets).

There are two interesting features of the subject of this paper.

In the first place, some of the statements concerning the natural codings of interval exchanges and of linear involutions can be proved using geometric methods, as shown in a separate paper [START_REF] Berthé | Return words of linear involutions and fundamental groups[END_REF]. This provides an interesting interpretation of the groups playing a role in these natural codings (these groups are generated either by return words or by maximal bifix codes) as fundamental groups of some surfaces. The methods used here are purely combinatorial.

In the second place, the abstract notion of a specular set gives rise to groups called here specular. These groups are natural generalizations of free groups, and are free products of Z and Z/2Z. They are called free-like in [START_REF] Bartholdi | Growth of groups and wreath products[END_REF] and appear at several places in [START_REF] De | Topics in geometric group theory[END_REF].

The idea of considering recurrent sets of reduced words invariant by taking inverses is connected, as we shall see, with the notion of G-rich words of [START_REF] Pelantová | Palindromic richness for languages invariant under more symmetries[END_REF].

The paper is organized as follows. In Section 2, we recall some notions concerning words, extension graphs and bifix codes. In Section 3, we introduce specular groups, which form a family with properties very close to free groups. We prove properties of these groups extending those of free groups, like a Schreier's Formula (Formula (3.1)). In Section 4, we introduce specular sets. This family contains the natural codings of linear involutions without connection studied in [START_REF] Valérie Berthé | Specular sets[END_REF]. We prove a result connecting specular sets with the family of tree sets introduced in [6] (Theorem 4.6). In Section 5, we prove several results concerning subgroups generated by subsets of specular groups. We first prove that the set of return words to a given word forms a basis of the even subgroup (Theorem 5.1 referred to as the Return Theorem). This is a subgroup defined in terms of particular letters, called even letters, that play a special role with respect to the extension graph of the empty word. We next prove the Finite Index Basis Theorem (Theorem 5.2).

Preliminaries

A set of words on the alphabet A and containing A is said to be factorial if it contains the factors of its elements. An internal factor of a word x is a word v such that x = uvw with u, w nonempty.

Let S be a set of words on the alphabet A. For w ∈ S, we denote

L S (w) = {a ∈ A | aw ∈ S}, R S (w) = {a ∈ A | wa ∈ S} and E S (w) = {(a, b) ∈ A × A | awb ∈ S}. Further ℓ S (w) = Card(L S (w)), r S (w) = Card(R S (w)
), e S (w) = Card(E S (w)). We omit the subscript S when it is clear from the context. A word w is right-extendable if r(w) > 0, left-extendable if ℓ(w) > 0 and biextendable if e(w) > 0. A factorial set S is called right-extendable (resp. left-extendable, resp. biextendable) if every word in S is right-extendable (resp. left-extendable, resp. biextendable).

A word

w is called right-special if r(w) ≥ 2. It is called left-special if ℓ(w) ≥ 2. It is called bispecial if it is both left-special and right-special.
For w ∈ S, we denote

m S (w) = e S (w) -ℓ S (w) -r S (w) + 1. The word w is called weak if m S (w) < 0, neutral if m S (w) = 0 and strong if m S (w) > 0.
We say that a factorial set S is neutral if every nonempty word in S is neutral. The characteristic of S is the integer 1 -m S (ε). Thus a neutral set of characteristic 1 is such that all words (including the empty word) are neutral. This is what is called a neutral set in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF].

A set of words S = {ε} is recurrent if it is factorial and if for any u, w ∈ S, there is a v ∈ S such that uvw ∈ S. An infinite factorial set is said to be uniformly recurrent if for any word u ∈ S there is an integer n ≥ 1 such that u is a factor of any word of S of length n. A uniformly recurrent set is recurrent.

The factor complexity of a factorial set S of words on an alphabet A is the sequence p n = Card(S ∩ A n ). Let s n = p n+1 -p n and b n = s n+1 -s n be respectively the first and second order differences sequences of the sequence p n .

The following result is from [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF] (see also [START_REF] Berthé | Combinatorics, automata and number theory[END_REF], Theorem 4.5.4).

Proposition 2.1 Let S be a factorial set on the alphabet A. One has b n =

w∈S∩A n m(w) and s n = w∈S∩A n (r(w) -1) for all n ≥ 0.

Let S be a biextendable set of words. For w ∈ S, we consider the set E(w) as an undirected graph on the set of vertices which is the disjoint union of L(w) and R(w) with edges the pairs (a, b) ∈ E(w). This graph is called the extension graph of w. We sometimes denote 1 ⊗ L(w) and R(w) ⊗ 1 the copies of L(w) and R(w) used to define the set of vertices of E(w).

If the extension graph E(w) is acyclic, then m(w) = 1 -c, where c is the number of connected components of the graph E(w). Thus w is weak or neutral.

A biextendable set S is called acyclic if for every w ∈ S, the graph E(w) is acyclic. A biextendable set S is called a tree set of characteristic c if for any nonempty w ∈ S, the graph E(w) is a tree and if E(ε) is a union of c trees (the definition of tree set in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] corresponds to a tree set of characteristic 1). Note that a tree set of characteristic c is a neutral set of characteristic c.

As an example, a Sturmian set is a tree set of characteristic 1 (by a Sturmian set, we mean the set of factors of a strict episturmian word, see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]).

Let S be a factorial set of words and x ∈ S. A return word to x in S is a nonempty word u such that the word xu is in S and ends with x, but has no internal factor equal to x. We denote by R S (x) the set of return words to x in S. The set of complete return words to x ∈ S is the set xR S (x).

Bifix codes. A prefix code is a set of nonempty words which does not contain any proper prefix of its elements. A suffix code is defined symmetrically. A bifix code is a set which is both a prefix code and a suffix code (see [START_REF] Berstel | Codes and Automata[END_REF] for a more detailed introduction).

Let S be a recurrent set. A prefix (resp. bifix) code X ⊂ S is S-maximal if it is not properly contained in a prefix (resp. bifix) code Y ⊂ S. Since S is recurrent, a finite S-maximal bifix code is also an S-maximal prefix code (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], Theorem 4.2.2). For example, for any n ≥ 1, the set X = S ∩A n is an S-maximal bifix code.

Let X be a bifix code. Let Q be the set of words without any suffix in X and let P be the set of words without any prefix in X. A parse of a word w with respect to a bifix code X is a triple (q, x, p) ∈ Q × X * × P such that w = qxp. We denote by d X (w) the number of parses of a word w with respect to X. The S-degree of X, denoted d X (S), is the maximal number of parses with respect to X of a word of S. For example, the set X = S ∩ A n has S-degree n.

Let S be a recurrent set and let X be a finite bifix code. By Theorem 4.2.8 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], X is S-maximal if and only if its S-degree is finite. Moreover, in this case, a word w ∈ S is such that d X (w) < d X (S) if and only if it is an internal factor of a word of X.

Specular groups

We consider an alphabet A with an involution θ : A → A, possibly with some fixed points. We also consider the group G θ generated by A with the relations aθ(a) = 1 for every

a ∈ A. Thus θ(a) = a -1 for a ∈ A. The set A is called a natural set of generators of G θ .
When θ has no fixed point, we can set A = B ∪ B -1 by choosing a set of representatives of the orbits of θ for the set B. The group G θ is then the free group on B. In general, the group G θ is a free product of a free group and a finite number of copies of Z/2Z, that is, G θ = Z * i * (Z/2Z) * j where i is the number of orbits of θ with two elements and j the number of its fixed points. Such a group will be called a specular group of type (i, j). These groups are very close to free groups, as we will see. The integer Card(A) = 2i + j is called the symmetric rank of the specular group Z * i * (Z/2Z) * j . Two specular groups are isomorphic if and only if they have the same type. Indeed, the commutative image of a group of type (i, j) is Z i × (Z/2Z) j and the uniqueness of i, j follows from the fundamental theorem of finitely generated Abelian groups. By Kurosh's Theorem, any subgroup of a free product

G 1 * G 2 * • • • * G n is itself
a free product of a free group and of groups conjugate to subgroups of the G i (see [START_REF] Magnus | Combinatorial group theory[END_REF]). Thus, we have, replacing the Nielsen-Schreier Theorem of free groups, the following result. Theorem 3.1. Any subgroup of a specular group is specular.

It also follows from Kurosh's theorem that the elements of order 2 in a specular group G θ are the conjugates of the j fixed points of θ and this number is thus the number of conjugacy classes of elements of order 2.

A word on the alphabet A is θ-reduced (or simply reduced) if it has no factor of the form aθ(a) for a ∈ A. It is clear that any element of a specular group is represented by a unique reduced word.

A subset of a group

G is called symmetric if it is closed under taking inverses. A set X in a specular group G is called a monoidal basis of G if it is symmetric, if the monoid that it generates is G and if any product x 1 x 2 • • • x m of elements of X such that x k x k+1 = 1 for 1 ≤ k ≤ m -1 is distinct of 1.
The alphabet A is a monoidal basis of G θ and the symmetric rank of a specular group is the cardinality of any monoidal basis (two monoidal bases have the same cardinality since the type is invariant by isomorphism).

If H is a subgroup of index n of a specular group G of symmetric rank r, the symmetric rank

s of H is s = n(r -2) + 2. (3.1)
This formula replaces Schreier's Formula (which corresponds to the case j = 0). It can be proved as follows. Let Q be a Schreier transversal for H, that is, a set of reduced words which is a prefix-closed set of representatives of the right cosets Hg of H. Let X be the corresponding Schreier basis, formed of the paq -1 for a ∈ A, p, q ∈ Q with pa ∈ Q and pa ∈ Hq. The number of elements of X is nr -2(n -1). Indeed, this is the number of pairs (p, a) ∈ Q × A minus the 2(n -1) pairs (p, a) such that pa ∈ Q with pa reduced or pa ∈ Q with pa not reduced. This gives Formula (3.1). Any specular group G = G θ has a free subgroup of index 2. Indeed, let H be the subgroup formed of the reduced words of even length. It has clearly index 2. It is free because it does not contain any element of order 2 (such an element is conjugate to a fixed point of θ and thus is of odd length).

A group G is called residually finite if for every element g = 1 of G, there is a morphism ϕ from G onto a finite group such that ϕ(g) = 1.

It follows easily by considering a free subgroup of index 2 of a specular group that any specular group is residually finite. A group G is said to be Hopfian if any surjective morphism from G onto G is also injective. By a result of Malcev, any finitely generated residually finite group is Hopfian (see [START_REF] Lyndon | Combinatorial Group Theory[END_REF], p. 197). Thus any specular group is Hopfian.

As a consequence, one has the following result, which can be obtained by considering the commutative image of a specular group. Proposition 3.2 Let G be a specular group of type (i, j) and let X ⊂ G be a symmetric set with 2i + j elements. If X generates G, it is a monoidal basis of G.

Specular sets

We assume given an involution θ on the alphabet A generating the specular group G θ . A specular set on A is a biextendable symmetric set of θ-reduced words on A which is a tree set of characteristic 2. Thus, in a specular set, the extension graph of every nonempty word is a tree and the extension graph of the empty word is a union of two disjoint trees.

The following is a very simple example of a specular set.

Example 4.1. Let A = {a, b} and let θ be the identity on A. Then the set of factors of (ab) ω is a specular set (we denote by x ω the word x infinitely repeated).

The following result shows in particular that in a specular set the two trees forming E(ε) are isomorphic since they are exchanged by the bijection (a, b) → (b -1 , a -1 ). Proposition 4.1 Let S be a specular set. Let T 0 , T 1 be the two trees such that

E(ε) = T 0 ∪ T 1 . For any a, b ∈ A and i = 0, 1, one has (1 ⊗ a, b ⊗ 1) ∈ T i if and only if (1 ⊗ b -1 , a -1 ⊗ 1) ∈ T 1-i
Proof. Assume that (1 ⊗ a, b ⊗ 1) and (1 ⊗ b -1 , a -1 ⊗ 1) are both in T 0 . Since T 0 is a tree, there is a path from 1 ⊗ a to a -1 ⊗ 1. We may assume that this path is reduced, that is, does not use consecutively twice the same edge. Since this path is of odd length, it has the form (u 0 , v 0 , u 1 , . . . , u p , v p ) with u 0 = 1 ⊗ a and v p = a -1 ⊗ 1. Since S is symmetric, we also have a reduced path

(v -1 p , u -1 p , • • • , u -1 1 , v -1 0 , u -1 0 ) which is in T 0 (for u i = 1 ⊗ a i , we denote u -1 i = a -1
i ⊗ 1 and similarly for v -1 i ). Since v -1 p = u 0 , these two paths have the same origin and end. But if a path of odd length is its own inverse, its central edge has the form (x, y) with x = y -1 a contradiction with the fact that the words of S are reduced. Thus the two paths are distinct. This implies that E(ε) has a cycle, a contradiction.

The next result follows easily from Proposition 2.1.

Proposition 4.2

The factor complexity of a specular set on the alphabet A is

p n = n(k -2) + 2 for n ≥ 1 with k = Card(A).
Doubling maps. We now introduce a construction which allows one to build specular sets.

A transducer is a graph on a set Q of vertices with edges labeled in Σ × A. The set Q is called the set of states, the set Σ is called the input alphabet and A is called the output alphabet. The graph obtained by erasing the ouput letters is called the input automaton (with an unspecified initial state). Similarly, the ouput automaton is obtained by erasing the input letters.

Let A be a transducer with set of states Q = {0, 1} on the input alphabet Σ and the output alphabet A. We assume that 1. the input automaton is a group automaton, that is, every letter of Σ acts on Q as a permutation, 2. the output labels of the edges are all distinct. We define two maps δ 0 , δ 1 : Σ * → A * corresponding to initial states 0 and 1 respectively. Thus δ 0 (u) = v (resp. δ 1 (u) = v) if the path starting at state 0 (resp. 1) with input label u has output label v. The pair δ = (δ 0 , δ 1 ) is called a doubling map on Σ × A and the transducer A a doubling transducer. The image of a set T on the alphabet Σ by the doubling map δ is the set S = δ 0 (T ) ∪ δ 1 (T ).

If A is a doubling transducer, we define an involution θ A as follows. For any a ∈ A, let (i, α, a, j) be the edge with input label α and output label a. We define θ A (a) as the output label of the edge starting at 1 -j with input label α. Thus,

θ A (a) = δ i (α) = a if i + j = 1 and θ A (a) = δ 1-i (α) = a if i = j. The reversal of a word w = a 1 a 2 • • • a n is the word w = a n • • • a 2 a 1 .
A set S of words is closed under reversal if w ∈ S implies w ∈ S for every w ∈ S. As is well known, any Sturmian set is closed under reversal (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]). The proof of the following result can found in [START_REF] Valérie Berthé | Specular sets[END_REF]. Proposition 4.3 For any tree set T of characteristic 1 on the alphabet Σ, closed under reversal and for any doubling map δ, the image of T by δ is a specular set relative to the involution θ A . We now give an example of a specular set obtained by a doubling map. Note that S is the set of factors of the fixed point g ω (a) of the morphism g : a → abcab, b → cda, c → cdacd, d → abc. The morphism g is obtained by applying the doubling map to the cube f 3 of the Fibonacci morphism f in such a way that g ω (a) = δ 0 (f ω (α)).

Odd and even words. We introduce a notion which plays, as we shall see, an important role in the study of specular sets. Let S be a specular set. Since a specular set is biextendable, any letter a ∈ A occurs exactly twice as a vertex of E(ε), one as an element of L(ε) and one as an element of R(ε). A letter a ∈ A is said to be even if its two occurrences appear in the same tree. Otherwise, it is said to be odd. Observe that if S is recurrent, there is at least one odd letter. A word w ∈ S is said to be even if it has an even number of odd letters. Otherwise it is said to be odd. The set of even words has the form X * ∩ S where X ⊂ S is a bifix code, called the even code. The set X is the set of even words without a nonempty even prefix (or suffix). Proposition 4.4 Let S be a recurrent specular set. The even code is an Smaximal bifix code of S-degree 2.

Proof. Let us verify that any w ∈ S is comparable for the prefix order with an element of the even code X. If w is even, it is in X * . Otherwise, since S is recurrent, there is a word u such that wuw ∈ S. If u is even, then wuw is even and thus wuw ∈ X * . Otherwise wu is even and thus wu ∈ X * . This shows that X is S-maximal. The fact that it has S-degree 2 follows from the fact that any product of two odd letters is a word of X which is not an internal factor of X and has two parses. Denote by T 0 , T 1 the two trees such that E(ε) = T 0 ∪ T 1 . We consider the directed graph G with vertices 0, 1 and edges all the triples (i, a, j) for 0 ≤ i, j ≤ 1 and a ∈ A such that (1 ⊗ b, a ⊗ 1) ∈ T i and (1 ⊗ a, c ⊗ 1) ∈ T j for some b, c ∈ A. The graph G is called the parity graph of S. Observe that for every letter a ∈ A there is exactly one edge labeled a because a appears exactly once as a left (resp. right) vertex in E(ε).

Note that, when S is a specular set obtained by a doubling map using a transducer A, the parity graph of S is the output automaton of A. The proof of the following result can be found in [START_REF] Valérie Berthé | Specular sets[END_REF]. Proposition 4.5 Let S be a specular set and let G be its parity graph. Let S i,j be the set of words in S which are the label of a path from i to j in the graph G.

(1) The family (S i,j \ {ε}) 0≤i,j≤1 is a partition of S \ {ε}.

(2) For u ∈ S i,j \ {ε} and v ∈ S k,ℓ \ {ε}, if uv ∈ S, then j = k.

(3) S 0,0 ∪ S 1,1 is the set of even words. (4) S -1 i,j = S 1-j,1-i .

A coding morphism for a prefix code X on the alphabet A is a morphism f : B * → A * which maps bijectively B onto X. Let S be a recurrent set and let f be a coding morphism for an S-maximal bifix code. The set f -1 (S) is called a maximal bifix decoding of S.

The following result is the counterpart for uniformly recurrent specular sets of the main result of [8, Theorem 6.1] asserting that the family of uniformly recurrent tree sets of characteristic 1 is closed under maximal bifix decoding. The proof can be found in [START_REF] Valérie Berthé | Specular sets[END_REF].

Theorem 4.6. The decoding of a uniformly recurrent specular set by the even code is a union of two uniformly recurrent tree sets of characteristic 1.

Palindromes. The notion of palindromic complexity originates in [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF] where it is proved that a word of length n has at most n + 1 palindrome factors. A word of length n is full if it has n + 1 palindrome factors and a factorial set is full (or rich) if all its elements are full. By a result of [START_REF] Glen | Palindromic richness[END_REF], a recurrent set S closed under reversal is full if and only if every complete return word to a palindrome in S is a palindrome. It is known that all Sturmian sets are full [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF] and also all natural codings of interval exchange defined by a symmetric permutation [START_REF] Baláži | Factor versus palindromic complexity of uniformly recurrent infinite words[END_REF]. In [START_REF] Pelantová | Palindromic richness for languages invariant under more symmetries[END_REF], this notion was extended to that of H-fullness, where H is a finite group of morphisms and antimorphisms of A * (an antimorphism is the composition of a morphism and reversal) containing at least one antimorphism. As one of the equivalent definitions of H-full, a set S closed under H is H-full if for every x ∈ S, every complete return word to the H-orbit of x is fixed by a nontrivial element of H (a complete return word to a set X is a word of S which has exactly two factors in X, one as a proper prefix and one as a proper suffix).

The following result connects these notions with ours. If δ is a doubling map, we denote by H the group generated by the antimorphism u → u -1 for u ∈ G θ and the morphism obtained by replacing each letter a ∈ A by τ (a) if there are edges (i, b, a, j) and (1 -i, b, τ (a), 1 -j) in the doubling transducer. Actually, we have H = Z/2Z × Z/2Z. The proof of the following result can be found in [START_REF] Valérie Berthé | Specular sets[END_REF]. The fact that T is full generalizes the results of [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF][START_REF] Baláži | Factor versus palindromic complexity of uniformly recurrent infinite words[END_REF]. Proposition 4.7 Let T be a recurrent tree set of characteristic 1 on the alphabet Σ, closed under reversal and let S be the image of T under a doubling map. Then T is full and S is H-full.

Example 4.6. Let S be the specular set of Example 4.2. Since it is a doubling of the Fibonacci set (which is Sturmian and thus full), it is H-full with respect to the group H generated by the map σ taking the inverse and the morphism τ which exchanges a, c and b, d respectively. The H-orbit of x = a is the set X = {a, c} and CR S (X) = {ac, abc, ca, cda}.

All four words are fixed by στ . As another example, consider x = ab. Then X = {ab, bc, cd, da} and CR S (X) = {abc, bcab, bcd, cda, dab, dacd}. Each of them is fixed by some nontrivial element of H.

Subgroup Theorems

In this section, we prove several results concerning the subgroups generated by subsets of a specular set.

The Return Theorem. By [START_REF] Berthé | Acyclic, connected and tree sets[END_REF]Theorem 4.5], the set of return words to a given word in a uniformly recurrent tree set of characteristic 1 containing the alphabet A is a basis of the free group on A. We will see a counterpart of this result for uniformly recurrent specular sets.

Let S be a specular set. The even subgroup is the group generated by the even code. It is a subgroup of index 2 of G θ with symmetric rank 2(Card(A) -1) by (3.1). Since no even word is its own inverse (see Proposition 4.5), it is a free group. Thus its rank is Card(A) -1. The proof can be found in [START_REF] Valérie Berthé | Specular sets[END_REF].

Theorem 5.1. Let S be a uniformly recurrent specular set on the alphabet A. For any w ∈ S, the set of return words to w is a basis of the even subgroup.

Note that this implies that Card(R S (x)) = Card(A) -1. Finite Index Basis Theorem. The following result is the counterpart for specular sets of the result holding for uniformly recurrent tree sets of characteristic 1 (see [START_REF] Berthé | The finite index basis property[END_REF]Theorem 4.4]). The proof can be found in [START_REF] Valérie Berthé | Specular sets[END_REF].

Theorem 5.2. Let S be a uniformly recurrent specular set and let X ⊂ S be a finite symmetric bifix code. Then X is an S-maximal bifix code of S-degree d if and only if it is a monoidal basis of a subgroup of index d.

Note that when X is not symmetric, the index of the subgroup generated by X may be different of d X (S).

Note also that Theorem 5.2 implies that for any uniformly recurrent specular set and for any finite symmetric S-maximal bifix code X, one has Card(X) = d X (S)(Card(A)-2)+ 2. This follows actually also (under more general hypotheses) from Theorem 2 in [START_REF] Dolce | Enumeration formulae in neutral sets[END_REF].

The proof of the Finite Index Basis Theorem needs preliminary results which involve concepts like that of incidence graph which are interesting in themselves.

Saturation Theorem. The incidence graph of a set X, is the undirected graph G X defined as follows. Let P be the set of proper prefixes of X and let Q be the set of its proper suffixes. Set P ′ = P \ {1} and Q ′ = Q \ {1}. The set of vertices of G X is the disjoint union of P ′ and Q ′ . The edges of G X are the pairs (p, q) for p ∈ P ′ and q ∈ Q ′ such that pq ∈ X. As for the extension graph, we sometimes denote 1 ⊗ P ′ , Q ′ ⊗ 1 the copies of P ′ , Q ′ used to define the set of vertices of G X .

Example 5.2. Let S be a factorial set and let X = S ∩ A 2 be the bifix code formed of the words of S of length 2. The incidence graph of X is identical with the extension graph E(ε).

Let X be a symmetric set. We use the incidence graph to define an equivalence relation γ X on the set P of proper prefixes of X, called the coset equivalence of X, as follows. It is the relation defined by p ≡ q mod γ X if there is a path (of even length) from 1 ⊗ p to 1 ⊗ q or a path (of odd length) from 1 ⊗ p to q -1 ⊗ 1 in the incidence graph G X . It is easy to verify that, since X is symmetric, γ X is indeed an equivalence. The class of the empty word ε is reduced to ε.

The following statement is the generalization to symmetric bifix codes of Proposition 6.3.5 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]. We denote by X the subgroup generated by X. Proposition 5.3 Let X be a symmetric bifix code and let P be the set of its proper prefixes. Let γ X be the coset equivalence of X and let H = X . For any p, q ∈ P , if p ≡ q mod γ X , then Hp = Hq.

We now use the coset equivalence γ X to define the coset automaton C X of a symmetric bifix code X as follows. The vertices of C X are the equivalence classes of γ X . We denote by p the class of p. There is an edge labeled a ∈ A from s to t if for some p ∈ s and q ∈ t (that is s = p and t = q), one of the following cases occurs (see Figure 5 (ii) or pa ∈ X and q = ε.

The proof of the following statement can be found in [START_REF] Valérie Berthé | Specular sets[END_REF].

Proposition 5.4 Let X be a symmetric bifix code, let P be its set of proper prefixes and let H = X . If for p, q ∈ P and a word w ∈ A * there is a path labeled w from the class p to the class q, then Hpw = Hq.

Let A be an alphabet with an involution θ. A directed graph with edges labeled in A is called symmetric if there is an edge from p to q labeled a if and only if there is an edge from q to p labeled a -1 . If G is a symmetric graph and v is a vertex of G, the set of reductions of the labels of paths from v to v is a subgroup of G θ called the subgroup described by G with respect to v.

A symmetric graph is called reversible if for every pair of edges of the form (v, a, w), (v, a, w ′ ), one has w = w ′ (and the symmetric implication since the graph is symmetric). Proposition 5.5 Let S be a specular set and let X ⊂ S be a finite symmetric bifix code. The coset automaton C X is reversible. Moreover the subgroup described by C X with respect to the class of the empty word is the group generated by X.

Prime words with respect to a subgroup. Let H be a subgroup of the specular group G θ and let S be a specular set on A relative to θ. The set of prime words in S with respect to H is the set of nonempty words in H ∩ S without a proper nonempty prefix in H ∩ S. Note that the set of prime words with respect to H is a symmetric bifix code. One may verify that it is actually the unique bifix code X such that X ⊂ S ∩ H ⊂ X * .

The following statement is a generalization of Theorem 5.2 in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] (Saturation Theorem). The proof can be found in [START_REF] Valérie Berthé | Specular sets[END_REF].

Theorem 5.6. Let S be a specular set. Any finite symmetric bifix code X ⊂ S is the set of prime words in S with respect to the subgroup X . Moreover X ∩ S = X * ∩ S.

A converse of the Finite Index Basis Theorem. The following is a converse of Theorem 5.2. For the proof, see [START_REF] Valérie Berthé | Specular sets[END_REF].

Theorem 5.7. Let S be a recurrent and symmetric set of reduced words of factor complexity p n = n(Card(A)-2)+2. If S ∩A n is a monoidal basis of the subgroup A n for all n ≥ 1, then S is a specular set.

Example 3 . 1 .

 31 Let A = {a, b, c, d} and let θ be the involution which exchanges b, d and fixes a, c. Then G θ = Z * (Z/2Z) 2 is a specular group of symmetric rank 4.

Example 4 . 2 .

 42 Let Σ = {α, β} and let T be the Fibonacci set, which is the Sturmian set formed of the factors of the fixed point of the morphism α → αβ, β → α. Let δ be the doubling map given by the transducer A of Figure4.1 on the left.

Fig. 4 . 1 .

 41 Fig. 4.1. A doubling transducer and the extension graph ES(ε).

Example 4 . 3 .

 43 Let S be the specular set of Example 4.2. The letters a, c are odd and b, d are even.

Example 4 . 4 .

 44 Let S be the specular set of Example 4.2. The even code is X = {abc, ac, b, ca, cda, d}.

Example 4 . 5 .

 45 The parity graph of the specular set of Example 4.2 is the output automaton of the doubling transducer of Figure 4.1.

Example 5 . 1 .

 51 Let S be the specular set of Example 4.2. The set of return words to a is R S (a) = {bca, bcda, cda}. It is a basis of the even subgroup.

  .

Fig. 5 . 1 .

 51 Fig. 5.1. The edges of the coset automaton.

Acknowledgments The authors thank Laurent Bartholdi and Pierre de la Harpe for useful indications. This work was supported by grants from Région Île-de-France and ANR project Eqinocs.