A Amouri
email: ali.amouri@ibisc.univ-evry.fr

F Ababsa
email: ababsa@ibisc.univ-evry.fr

Sliding Movement Platform for Mixed Reality Application

Keywords: Sliding movement, Virtual environment, Mixed reality, Mechanical design, Mechatronic synoptic diagram. 

This paper deals with the conception of a new 6 DoF (Degree of Freedom) platform to reproduce natural motion feeling when the human is completely merged in mixed reality environments. The proposed system is open and supposed to be flexible and adaptable to three different applications: sport, health and rescue. In this paper, we focus on the sport simulation domain, namely the ski sliding movement. We present the mechanical study of this platform, the 6 DOF motion modelling and some mechatronics aspects.

INTRODUCTION

3D Interactions in mixed reality environments and their integration in industry, have taken a major boom in recent years and many approaches have been developed. The combination between physical systems and virtual tools is the key issue to conceive and validate this kind of modern platforms. Besides, this type of mechatronic systems is closely depending on new technologies that emerge, namely in actuators and sensors domains. Last years, several simulator systems have been designed especially based on 6 DoF motion platforms. Thus, driving simulators are the most popular examples, they were used in various areas like entertainment, prototyping, research and advanced training (J.S. [START_REF] Freeman | The Iowa driving simulator: An implementation and application overview[END_REF]G.Reymond et al., 2000;[START_REF] Nehaoua | Review on single track vehicle and motorcycle simulators[END_REF]. The main research areas concern typically the driver behavior study (drugs and tiredness effects) (F.Colombet et al., 2008), the human machine interface (HMI) and the validation of new subsystems in vehicles. Nevertheless, motion platforms have been used in other domains as: flight simulators navigation (J.C.F.De [START_REF] De Winter | Training effectiveness of whole body flight simulator motion: A comprehensive meta-analysis[END_REF] and medical rehabilitation (J. [START_REF] Fung | Locomotors rehabilitation in a complex virtual environment[END_REF]. Moreover, most of these motion simulators use parallel Stewart-Gough platforms where the research works focused in particular on kinematics and dynamics analysis (D. [START_REF] Stewart | A platform with six degrees of freedom[END_REF]J.B. Sol et al., 2009). However, this kind of simulators has several known disadvantages and challenges, including: high cost, limited behavioural fidelity and discomfort. Furthermore, several researches proved that Virtual Environment techniques can be used to assess trainee's skills and improve their behaviour in real world while reducing training time, costs and errors (D. [START_REF] Kaufman | Teaching and Assessing Clinical Skills Using Virtual Reality[END_REF].

Indeed, virtual reality techniques provide an efficient way to enable people to interact efficiently with 3D objects in virtual environment using their natural senses. Several robust approaches on 3D tracking (F. Ababsa et al., 2006;[START_REF] Ababsa | Robust camera pose tracking for augmented reality using particle filtering framework[END_REF], and natural interaction (S. [START_REF] Ullah | Augmenting 3D interactions with haptic guide in a large scale virtual environment[END_REF] have been developed and evaluated on our Immersive Virtual Reality Evr@ platform.

The main contribution of this paper is the design of 6 DoF motion platform, which should reproduce a real sliding movement in a virtual environment, in particular for ski sport, without using snowy slopes and independently on weather conditions (figure 1).

Fig. 1. Sliding simulator

In order to enhance the perception of realism, our system must support the natural human motion and the real-time rendering of the stereoscopic view on large scale screen. The goal is to offer an accessible and cost-effective Virtual Environment that simulates sliding activities for training professional skier or amateur one who received little or no experiential practices in this sport. In our best knowledge, the most existing platforms for ski training have limited DoF number and could not reproduce a natural human sensation corresponding to the real motion. Our motivation is to extend the degree of freedom to make the simulation experiment more realistic.

The remaining of the paper is organized as follows: Section 2 gives a detailed description of the proposed sliding motion platform; a complete study of the mechanical design is presented with the mechatronic synoptic diagram of the principle blocs. Section 3 gives a modelling issue for the kinematics and the dynamics of the 6 DoF platform. Finally, a conclusion and further works are provided.

SLIDING PLATFORM

This project aims to provide the platform Evr@ with a 6 DoF motion simulator able to put a person in natural moving situation within mixed reality environment. The purpose is thus to study the human sensory behaviour in an immersive context, in particular, during a ski scenario. In this section, the platform specifications are presented in details.

Evr@

The EVR@ platform is a 3,20m 2,40m semi immersive platform with an active stereoscopy display (figure 2). There exists two tracking possibilities to interact with the virtual environment: the ART Track system which is very accurate and composed of two ARTTrack infrared cameras detecting position and orientation of objects with markers (as in figure 2). Our sliding platform should be integrated with Evr@ to simulate natural body movement in immersive scenarios. In this case, a person will be equipped by markers and tracked by ART track system in order to localize him in the workspace and hence allowing the feedback scenario -motion.

Evr@ platform uses the ART Tracking System to measure simultaneously the position and the orientation of the body. Indeed, the body is equipped by light reflecting markers (retroreflectors). Two ARTTrack cameras, disposed on both sides of the screen, scan the space work and detect the light that comes from the markers. Their images are processed to identify and calculate potential marker positions (in image coordinates) with high accuracy; a mean accuracy of 0.04 pixels is standard in ART tracking systems. These 2 DoF data are combined to compute the 6 DoF poses of a rigid arrangements of several markers. The result of each measurement are coordinates that describe the position of the markers, and hence the position and orientation of the body carrying the markers. Hence, the used ART Tracking System allows to track the body gesture when moving in front of the projection screen (up to 4.5 m wide).

Stereoscopy display Infrared camera

Fig. 2. Evr@ virtual reality platform with the 6 DoF mechanical system

Mechanical design

The mechanical structure is the interface between the slider and the simulation environment. It consists on a 6 DoF Gough-Stewart platform mounted on a 2 DoF x-y table. The x-y table carries both the 6 DoF platform and the slider. By means of a set of sliders assembled as shown in figure 3, the 6 DoF platform can move on a rail that is 1.60 m long.

Fig. 3. CAD figure of the x-y table

To this end, a hybrid Nanotec PD4 motors is fixed at a mechanical stand related to the platform's rails. The motor rotation is transformed into a longitudinal motion, which is due to a ball screw-up system. This platform achieves steady linear accelerations up to 0,66g.

To control the 6 DoF motion, six legs have been mounted in parallel between the lower base and the upper platform's chassis frame (figure 4). The various legs consist of two electro thrusts incorporating a high-quality ball screw drive. Each leg is connected on one side, to the lower frame of the simulator by a cylindrical joint, and on the other side by a spherical joint. The six electro thrusts are driven by a hybrid Nanotec PD4 servomotor. On the other side, the upper part of the Gough-Stewart platform is managed such that the slider can hold its equilibrium during the simulation of a given scenario. For this, a ski equipment (camber and boots) are installed on the upper 6 DoF platform with adequate fixations (figure 5). The ski equipment is provided with force sensors to measure the slider force, from his legs and feet, applied on the upper platform. This measurement will be used by the virtual slider dynamics and the platform's trajectories planning blocs.

Simulator architecture synoptic

The simulator architecture consists on various mechatronic components as it is shown in the synoptic of figure 6. These components are described below.

Visual environment: very common bloc in a simulation environment (driving simulation, flight simulation and others).

It provides the visual cues. It is intended for the construction of a 3D virtual environment based on saved database image.

Other tricks are added such wind effect, snowflakes and sound to improve the simulation rendering quality. On the other hands, the visual environment received information about slider gesture and posture to compensate for horizon and prevent the slider from the simulator sickness.

Platform's driver: this bloc includes all the embedded system for controlling, power supplying and managing the mechanical platform and sensors. In fact, the platform receives from the trajectories planning bloc only the reference trajectory to be achieved with a desired position, velocity and torque. In the other hands, sensors' signals are transmitted via bus data. No control is computed outside the servomotor drives. This is an important issue to minimize delays which are considered as the most problem for a worse simulation quality (S.K. [START_REF] Singhal | Exploiting position history for efficient remote rendering in networked virtual reality[END_REF]. As in driving simulation, the first objective is to create a sensation which should be interpreted as a good cue by the slider. The restitution of full-scale motion or a good reference tracking is not the primary objective in a dynamic simulation.

Fig. 6. Simulator mechatronics architecture

Virtual slider model: the slider moves with respect to the visual cues and follows a predefined ski trajectory. However, to achieve this task, we need a slider dynamic model to update the visual environment and mechanical platform position and orientation. In driving simulation, the driver interact with the virtual environment through an instrumented steering wheel and a set of various pedals. These information are used to simulate a virtual vehicle dynamics (H. [START_REF] Arioui | 2 DOF low cost platform for driving simulator: Modeling and control[END_REF]. However, in the present case, the slider acts with the virtual environment only through its space posture which creates efforts applied on the upper mobile part of the 6 DoF platform. For this, as described above, the ski equipment is provided with force sensors (under boots) where their signals can be merged with other gesture sensors. The gesture sensor are used to compute, in real time, the slider posture position and orientation by using a simple Kinect or more sophisticated home platform, Evr@. This solution is less computation consuming compared to the use of slider biomechanical model.

Platform's trajectories planning: to actuate the mechanical platform, a real time trajectory generation must be accomplished. The trajectory should be in concordance with the slider actions, the mechanical platform position and the projected visual scenario. Unless, the simulator sickness can be cause by the lack of coherence between these three entities.

In addition, since the platform has a limited kinematics workspace, a special algorithms like washout filters must be employed (S.F. [START_REF] Schmidt | Motion drive signals for piloted flight simulators[END_REF]H. Arioui et al., 2010;L. Nehaoua et al., 2008), the washout allows repositioning the platform at its neutral position, under the slider perception's threshold, to start a new acceleration-deceleration cycle.

Nevertheless, unlike the driving simulation, in ski, the slider is in direct contact with a very unevenness ground. This feature must be taken into account by the motion cueing algorithms used in the trajectory generation. More specifically, the x-y moving table will be used to generate longitudinal and lateral acceleration cueing. The 6 DoF, will be used to simulate road unevenness, the roll and the yaw motions.

MODELING ISSUES

In this section, the kinematics and dynamics modelling of the mechanical platform is discussed. In particular, the inverse geometric model is presented which allows to give the platform legs elongation with respect to the reference trajectory computed by the trajectories planning bloc. The dynamics model will help in the choice of the appropriate servomotor to be used for the platform actuation.

Inverse kinematics model

Inverse kinematics consists of defining the actuation joint coordinates, which are the legs' elongations, with respect to the Cartesian coordinates and orientation of the mobile platform.

The present simulator is based on a parallel 6 DoF platform. A base reference frame𝑅(𝑜, 𝑖, 𝑗, 𝑘) is defined at the centre of the platform's base. Next, a body reference frame 𝑅 𝑝 (𝑝, 𝑖 𝑝 , 𝑗 𝑝 , 𝑘 𝑝 ), is attached to the centre of the platform's upper part (figure 7). Each legs is attached to the base at point 𝑏 𝑖 and to the upper part at point 𝑐 𝑖 . The configuration of the body frame 𝑅 𝑝 is characterized by the position vector 𝑟 𝑜𝑝 = [𝑥, 𝑦, 𝑧] 𝑇 of its origin 𝑝 and three Euler orientation angles vector [𝜑, 𝜃, 𝜓] 𝑇 , corresponding to the roll, pitch, and yaw, respectively. Taking the ZYX convention, the rotation matrix is computed as follows:

ℛ = ℛ 𝜓 ℛ 𝜃 ℛ 𝜑 (1)
It is known that legs elongation can be computed by:

𝑙 𝑖 2 = 𝑟 𝑏 𝑖 𝑐 𝑖 𝑇 𝑟 𝑏 𝑖 𝑐 𝑖 (2)
Where 𝑟 𝑏 𝑖 𝑐 𝑖 is the position vector associated with each leg:

𝑟 𝑏 𝑖 𝑐 𝑖 = 𝑟 𝑏 𝑖 𝑜 + 𝑟 𝑜𝑝 + ℛ𝑟 𝑝𝑐 𝑖 (3)
Vectors 𝑟 𝑏 𝑖 𝑜 and 𝑟 𝑝𝑐 𝑖 are constant and expressed in their reference frames. The orientation of the reference frame 𝑅 𝑝 with respect to 𝑅 is given by the transformation matrix ℛ. The legs position rate are given by differentiating equation ( 2) with respect to time, which leads to the well-known equation:

𝑖 𝑖 = [𝑢 𝑖 𝑇 (ℛ𝑟 𝑝𝑐 𝑖 𝑥 𝑢 𝑖 ) 𝑇 ] [( 𝑟̇𝑜 𝑝 𝜔 𝑜𝑝 )] = 𝒥 -1 𝑞̇ (4)
Where 𝑞 is the upper platform configuration vector, 𝒥 -1 is the inverse Jacobean matrix and 𝜔 𝑜𝑝 is the body frame angular rate which can be expressed with respect to the roll-pitch-yaw angles vector as following:

𝜔 𝑜𝑝 = 𝛾𝑞̇𝑟 𝑞 𝑟 = [𝜑, 𝜃, 𝜓] 𝑇 (5)

Inverse dynamics model

In this section, a simple dynamics formulation of the 6 DoF platform will be demonstrated. The primary objective is to propose a control scheme adapted for our sliding application and to characterize the platform's capabilities. We suppose that the 6 DoF platform and the x-y table are completely decoupled. Also, the legs dynamics is assumed to be small with respect to the platform's upper part dynamics and slider dynamics. Hence, the system is composed by four bodies: the platform's upper part, the slider's bust and the two slider's legs. Finally, the slider motion is considered to be free with respect to the platform motion.

The inverse dynamics model is derived from the Jourdain's principle (G. [START_REF] Rill | Vehicle modelling for real time applications[END_REF] The ⋆ symbol means that the mass matrix is symmetric.

Next step is to compute the residual acceleration to evaluate 𝑄 𝑅 . Form (L. [START_REF] Nehaoua | Dynamic modeling of a two wheeled vehicle: Jourdain formalism[END_REF]

Where 𝑔 𝑝 , is the gravity vector expressed in the body reference frame 𝑅 𝑠 and 𝑔 𝑠 is the gravity vector expressed in the bust reference frame 𝑅 𝑠 (figure 8).

For thrust actuation forces along the legs elongation, the associated generalized effort can be found by expressing the virtual power done by these six forces, so:

CONCLUSIONS

In this paper we presented the design of 6 DOF cost platform which bring more realism to sliding movement.

This system could be adaptive to many other applications like rehabilitation for people with motor disabilities, rescue environments and educative issues. We have exposed the kinematics and dynamics modelling of the mechanical platform within the slider, but have not developed the parameters identification. Our mechanical structure (xy table combined with Stewart) is smaller comparing to the state of the art and can generate similar movement sensation.

Our future work will focus on control algorithms to validate the platform movement and integrate a visual feedback for haptic sensation. In order to enhance the immersive experience, a virtual reality Head-Mounted Display (HMD) could be used.

Fig. 4 .

 4 Fig. 4. CAD figure of the 6 DOF Gough-Stewart platform and its possible degrees of freedom

Fig. 5 .

 5 Fig. 5. CAD figure of the 6 DOF Gough-Stewart platform with ski equipment

Fig. 7 . 6

 76 Fig. 7. 6 DoF platform's kinematic

Fig

  Fig. 8. Slider kinematic

  The last step is to evaluate the generalized external effort 𝑄 𝑎 vector. External effort are mainly the gravity force and legs' thrust force. From the first equation of (7), the contribution of the gravity force is:𝑄 𝑎,𝑔 = [ (𝑚 𝑝 + ∑ 𝑚 𝑗𝑖 2 𝑖=1)𝑔 𝑝 + 𝑚 𝑠 𝑔 𝑠 -∑ 𝑚 𝑗𝑖 𝑟 ̃𝑝𝑗 𝑖 𝑔 𝑝 -𝑚 𝑠 𝑟 ̃𝑝𝑠 𝑔 𝑠 2 𝑖=1 ]

  𝑖 → 𝑄 𝑎,𝐹𝑠 = 𝑗 -1 𝐹 𝑠 (13) Finally, equations (7) to (13) define a first order differential equation 𝑀𝜗 ̇= 𝑄 which can be solved directly to find the platform's configuration 𝜗 or inversely to find the thrust forces 𝐹 𝑠 . A linearized version of this model can be used to tune the inner control loops of the platform's servomotors (L.[START_REF] Nehaoua | Parameters identification for motorcycle simulator's platform characterization[END_REF].

  . The equation of motion is expressed by: 𝑀𝑣 ̇= 𝑄. Here, 𝜗 = [𝑢 𝑜𝑝 𝑇 , 𝜔 𝑜𝑝 𝑇 ] 𝑢 𝑜𝑝 = [𝑢 𝑥 , 𝑦 , 𝑢 𝑧 ] 𝑇 and 𝜔 𝑜𝑝 = [𝑝, 𝑞, 𝑟] 𝑇 are the position and angular rates of the platform's upper part in its body reference frame.In the body reference frame Rp, the linear and angular velocity vectors of the slider's legs 𝜗 𝑜𝑗 𝑖 , 𝜔 𝑜𝑗 𝑖 and bust 𝜗 𝑜𝑠 , 𝜔 𝑜𝑠 are given by:

	The mass matrix M is given by:
	𝑀 = ∑ 𝑚 𝑖 ( 𝜕𝑣 𝑜𝑖 𝜕𝜗 ) 𝑇 𝜕𝑦 𝜕𝜗 + ( 𝜕𝑣 𝑜𝑖 𝜕𝜗 ) 𝑇 4 𝑖=1	Ι 𝑖	𝜕𝜔 𝑜𝑖 𝜕𝜗	(6)
	And the generalized effort vector Q is the sum of the
	generalized external effort Qa and the generalized residual
	accelerations effort QR given by:
	𝑄 𝑎 = ∑ ( 𝜕𝑣 𝑜𝑖 𝜕𝜗 ) 𝑇 𝑖 𝑄 𝑅 = ∑ 𝑚 𝑖 𝑖 ( 𝜕𝑣 𝑜𝑖 𝑇 𝑎 𝑅 + 𝜕𝜗 ) + ∑ 𝑚 𝑖 𝑖 ( 𝑇 𝜕𝑣𝜔 𝑜𝑖 𝜕𝜗 ) (Ι 𝑖∈𝑅 + 𝜔 𝑜𝑖 × Ι 𝑖 𝜔 𝑜𝑖 ) 𝐹 𝑖 + ( 𝜕𝜔 𝑜𝑖 𝑇 𝑀 𝑖 𝜕𝜗 )			(7)

𝑇

Where:

  , the linear and angular acceleration vectors of the slider's legs 𝑎 𝑜𝑗 𝑖 , 𝜖 𝑜𝑗 𝑖 and bust 𝑎 𝑜𝑠 , 𝜖 𝑜𝑠 are given by: 𝑎 𝑜𝑗 𝑖 = 𝜗 ̇𝑜𝑝 + 𝜔̇𝑜 𝑝 × 𝑟 𝑝𝑗 𝑖 + 𝑟̈𝑝 𝑗 𝑖 + 𝜔 𝑜𝑝 × (𝜗 𝑜𝑗 𝑖 + 𝑟̇𝑝 𝑗 𝑖 ) (10) Where: 𝑎 𝑅,𝑗 𝑖 = 𝑟̈𝑝 𝑗 𝑖 + 𝜔 𝑜𝑝 × (𝜗 𝑜𝑗 𝑖 + 𝑟̇𝑝 𝑗 𝑖 ) 𝑎 𝑜𝑠 = 𝜗 ̇𝑜𝑝 + 𝜔̇𝑜 𝑝 × 𝑟 𝑝𝑠 + 𝑟̈𝑝 𝑠 + 𝜔 𝑜𝑝 × (𝜗 𝑜𝑠 + 𝑟̇𝑝 𝑠 ) Where: 𝑎 𝑅,𝑠 = 𝑟̈𝑝 𝑠 + 𝜔 𝑜𝑝 × (𝜗 𝑜𝑠 + 𝑟̇𝑝 𝑠 ) 𝜖 𝑜𝑗 𝑖 = 𝜔̇𝑜 𝑝 + 𝜔 𝑜𝑝 × 𝜔 𝑝𝑗 𝑖 + 𝜔̇𝑝 𝑗 𝑖 Where: 𝜖 𝑅,𝑗 𝑖 = 𝜔 𝑜𝑝 × 𝜔 𝑝𝑗 𝑖 + 𝜔̇𝑝 𝑗 𝑖 𝜖 𝑜𝑠 = 𝜔̇𝑜 𝑝 + 𝜔 𝑜𝑝 × 𝜔 𝑝𝑠 + 𝜔̇𝑝 𝑠 Where: 𝜖 𝑅,𝑠 = 𝜔 𝑜𝑝 × 𝜔 𝑝𝑠 + 𝜔̇𝑝 𝑠 From these equations, some suppositions can be done to simplify the dynamics model which leads to: 𝑎 𝑅,𝑗 𝑖 = 𝜔 𝑜𝑝 × 𝜗 𝑜𝑗 𝑖 (11) 𝑎 𝑅,𝑠 = 𝜔 𝑜𝑝 × 𝜗 𝑜𝑠 𝜖 𝑅,𝑗 𝑖 = 0 𝜖 𝑅,𝑠 = 𝜔 𝑜𝑝 × 𝜔 𝑝𝑠


domain: info math

text:
Valérie Berthé

Clelia De Felice

Francesco Dolce

Julien Leroy

Dominique Perrin

Christophe Reutenauer

Giuseppina Rindone

The finite index basis property

Keywords: 19

We describe in this paper a connection between bifix codes, symbolic dynamical systems and free groups. This is in the spirit of the connection established previously for the symbolic systems corresponding to Sturmian words. We introduce a class of sets of factors of an infinite word with linear factor complexity containing Sturmian sets and regular interval exchange sets, namely the class of tree sets. We prove as a main result that for a uniformly recurrent tree set S, a finite bifix code X on the alphabet A is S-maximal of S-degree d if and only if it is the basis of a subgroup of index d of the free group on A.

4 Tree sets 15 4.1 Acyclic and tree sets . . . . . . . . .

Introduction

In this paper we study a relation between symbolic dynamical systems and bifix codes. The paper is a continuation of the paper with part of the present list of authors on bifix codes and Sturmian words [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]. We understand here by Sturmian words the generalization to arbitrary alphabets, often called strict episturmian words or Arnoux-Rauzy words (see the survey [START_REF] Glen | Episturmian words: a survey[END_REF]), of the classical Sturmian words on two letters.

As a main result, we prove that, under natural hypotheses satisfied by a Sturmian set S, a finite bifix code X on the alphabet A is S-maximal of Sdegree d if and only if it is the basis of a subgroup of index d of the free group on A (Theorem 4.4 called below the Finite Index Basis Theorem).

The proof uses the property, proved in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF], that the sets of first return words in a uniformly recurrent tree set containing the alphabet A form a basis of the free group on A (this result is referred to below as the Return Words Theorem).

We actually introduce several classes of uniformly recurrent sets of words on k + 1 letters having all kn + 1 elements of length n for all n ≥ 0.

The smallest class (BS) is formed of the Sturmian sets on a binary alphabet, that is, with k = 1 (see Figure 1.1). It is contained both in the class of regular interval exchange sets (denoted RIE) and of Sturmian sets (denoted S). Moreover, it can be shown that the intersection of RIE and S is reduced to BS. Indeed, Sturmian sets on more than two letters are not the set of factors of an interval exchange transformation with each interval labeled by a distinct letter (the construction in [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] allows one to obtain the Sturmian sets of 3 letters as an exchange of 7 intervals labeled by 3 letters).

The next one is the class of uniformly recurrent sets satisfying the tree condition (T ), which contains the previous ones. The class of uniformly recurrent sets satisfying the neutrality condition (N ) contains the class T . All these classes are contained in the class of uniformly recurrent sets of complexity kn + 1 on an alphabet with k + 1 letters.

We have tried in all the paper to use the weakest possible conditions to prove our results. As an example, we prove that, under the neutrality condition, any finite S-maximal bifix code of S-degree d has 1 + d(Card(A) -1) elements (Theorem 3.6 called below the Cardinality Theorem).

The class RIE is closed under decoding by a maximal bifix code (Theorem 3.13 in [START_REF] Berthé | Bifix codes and interval exchanges[END_REF] referred to as the Bifix Decoding Theorem) but it is not the case for Sturmian sets. In contrast, the uniformly recurrent tree sets form a class of sets containing the Sturmian sets and the regular interval exchange sets which is closed under decoding by a maximal bifix code (see [START_REF] Berthé | Maximal bifix decoding[END_REF]) and for which the Finite Index Basis Theorem is true. For each class, the array on the right of Figure 1.1 indicates whether it satisfies the Cardinality Theorem (CT ), the Return Words Theorem (RT ), the Finite Index Basis Theorem (BT ) or the Bifix Decoding Theorem (BD). All these classes are distinct.

BS

The paper is organized as follows.

In Section 3, we introduce strong, weak and neutral sets. We prove the Cardinality Theorem in neutral sets (Theorem 3.6). We also prove a converse in the sense that a uniformly recurrent set S containing the alphabet and such that the Cardinality Theorem holds for any finite S-maximal bifix code is neutral (Theorem 3.12).

In Section 4, we introduce acyclic and tree sets. The family of tree sets contains Sturmian sets and, as shown in [START_REF] Berthé | Bifix codes and interval exchanges[END_REF], regular interval exchange sets. We prove, as a main result, that in uniformly recurrent tree sets the Finite Index Basis Theorem holds (Theorem 4.4), a result which is proved in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] for a Sturmian set. The proof uses a result of [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] concerning bifix codes in acyclic sets (Theorem 4.2 referred to as the Saturation Theorem). It also uses the Return Words Theorem proved in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF]. We also prove a converse of Theorem 4.4, in the sense that a uniformly recurrent set which has the finite index basis property is a tree set (Corollary 4.11).

Ackowledgement This work was supported by grants from Région Île-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 warmly thank the referee for his useful remarks on the first version of the paper.

Preliminaries

In this section, we first recall some definitions concerning words, prefix codes and bifix codes. We give the definitions of recurrent and uniformly recurrent sets of words. We also give the definitions and basic properties of bifix codes (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] for a more detailed presentation).

Words

In this section, we give definitions concerning extensions of words. We define recurrent sets and sets of first return words. For all undefined notions, we refer to [START_REF] Berstel | Codes and Automata[END_REF].

Recurrent sets

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.

A set of words is said to be prefix-closed (resp. factorial ) if it contains the prefixes (resp. factors) of its elements.

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

L(w) = {a ∈ A | aw ∈ S}, R(w) = {a ∈ A | wa ∈ S}, E(w) = {(a, b) ∈ A × A | awb ∈ S} and further ℓ(w) = Card(L(w)), r(w) = Card(R(w)), e(w) = Card(E(w)).
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. leftextendable, 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 right and left-special.
A set of words S = {1} 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.

A set of words S 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, and thus biextendable.

A morphism f : A * → B * is a monoid morphism from A * into B * . If a ∈ A is such that the word f (a) begins with a and if |f n (a)| tends to infinity with n, there is a unique infinite word denoted f ω (a) which has all words f n (a) as prefixes. It is called a fixpoint of the morphism f . 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).

A morphism f :

A * → B * is trivial if f (a) = 1 for all a ∈ A.
The image of a uniformly recurrent set by a nontrivial morphism is uniformly recurrent (see [START_REF] Allouche | Automatic Sequences. Theory, Applications, Generalizations[END_REF], Theorem 10.8.6 and Exercise 10.11.38).

An infinite word is episturmian if the set of its factors is closed under reversal and contains for each n at most one word of length n which is right-special. It is a strict episturmian word if it has exactly one right-special word of each length and moreover each right-special factor u is such that r(u) = Card(A).

A Sturmian set is a set of words which is the set of factors of a strict episturmian word. Any Sturmian set is uniformly recurrent (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]). 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.2 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.

Bifix codes

In this section, we present basic definitions concerning prefix codes and bifix codes. For a more detailed presentation, see [START_REF] Berstel | Codes and Automata[END_REF]. We also describe an operation on bifix codes called internal transformation and prove a property of this transformation (Proposition 2.9). It will be used in Section 3.3.

Prefix 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.

We denote by X * the submonoid generated by X. A set X ⊂ S is right S-complete if any word of S is a prefix of a word in X * . Given a factorial set S, a prefix code is S-maximal if and only if it is right S-complete (Proposition 3.3.2 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]).

A parse of a word w with respect to a set 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. Let X be a prefix code. By Proposition 4.1.6 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], for any u ∈ A * and a ∈ A, one has

δ X (ua) = δ X (u) if ua ∈ A * X, δ X (u) + 1 otherwise.
(2.1)

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 [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], Theorem 4.2.2). 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.

For S = A * , we use the term 'maximal bifix code' instead of A * -maximal bifix code and 'degree' instead of A * -degree. This is consistent with the terminology of [START_REF] Berstel | Codes and Automata[END_REF].

Let X be a bifix code. 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]).

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 set of words. A set X ⊂ S is said to be S-thin if there is a word of S which is not a factor of X. If S is biextendable any finite set X ⊂ S is S-thin. Indeed, any long enough word of S is not a factor of X. The converse is true if S is uniformly recurrent. Indeed, let w ∈ S be a word which is not a factor of X. Then any long enough word of S contains w as a factor, and thus is not itself a factor of X.

Let S be a recurrent set and let X be an S-thin and S-maximal bifix code of S-degree 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 [3]
). 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 2.3 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 [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], an S-thin and S-maximal bifix code is determined by its S-degree and its kernel. Moreover, by Theorem 4.3.12 of [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], we have the following result. The following proposition allows one to embed an S-maximal bifix code in a maximal one of the same degree.

Proposition 2.6 Let S be a recurrent set. For any S-thin and S-maximal bifix code X of S-degree d, there is a thin maximal bifix code X ′ of degree d such that X = X ′ ∩ S.

Proof. Let K be the kernel of X and let d be the S-degree of X. By Theorem 2.4, the set K is not S-maximal and δ K (y) ≤ d -1 for any y ∈ K. Thus, applying again Theorem 2.4 with S = A * , there is a maximal bifix code X ′ with kernel K and degree d. Then, by Theorem 4.2.11 of [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], the set X ′ ∩ S is an S-maximal bifix code.

Let us show that X ∪ X ′ is prefix. Suppose that x ∈ X and x ′ ∈ X ′ are comparable for the prefix order. We may assume that x is a prefix of x ′ (the other case works symmetrically). If x ∈ K, then x ∈ X ′ and thus x = x ′ . Otherwise, δ X (x) = d. Set x = pa with a ∈ A. Then, by Equation (2.1), δ X (x) = δ X (p) and thus δ X (p) = d. But since all the factors of p which are in X are in K, we have δ X (p) = δ K (p). Analogously, since all factors of p which are in X ′ are in K, we have δ

K (p) = δ X ′ (p). Therefore δ X ′ (p) = d. But, since X ′ has degree d, δ X ′ (x) ≤ d. Then, by Equation (2.1) again, we have δ X ′ (x) = d and x ∈ A * X ′ . Let z be the suffix of x which is in X ′ . If x = x ′ , then z = x or z ∈ K and in both cases z ∈ X. Since X ′ is prefix and X is suffix, this implies z = x = x ′ .
Since X and X ′ ∩ S are S-maximal prefix codes included in (X ∪ X ′ ) ∩ S, this implies that X = X ′ ∩ S.

Example 2.7 Let S be the Fibonacci set. Let X = {a, baab, bab} be the Smaximal bifix code of S-degree 2 with kernel {a}. Then X ′ = a ∪ ba * b is the maximal bifix code with kernel {a} of degree 2 such that X ′ ∩ S = X.

Internal transformation

We will use the following transformation which operates on bifix codes (see [START_REF] Berstel | Codes and Automata[END_REF]Chapter 6] for a more detailed presentation). For a set of words X and a word u, we denote u

-1 X = {v ∈ A * | uv ∈ X} and Xu -1 = {v ∈ A * | vu ∈ X}
the residuals of X with respect to u (one should not confuse this notation with that of the inverse in the free group). Let X ⊂ S be a set of words and w ∈ S a word. Let

G = Xw -1 , D = w -1 X, (2.2)
G 0 = (wD)w -1 D 0 = w -1 (Gw), (2.3)
G 1 = G \ G 0 , D 1 = D \ D 0 . (2.4) Note that Gw ∩ wD = G 0 w = wD 0 . Consequently G * 0 w = wD * 0 . The set Y = (X ∪ w ∪ (G 1 wD * 0 D 1 ∩ S)) \ (Gw ∪ wD) (2.5)
is said to be obtained from X by internal transformation with respect to w.

When Gw ∩ wD = ∅, the transformation takes the simpler form

Y = (X ∪ w ∪ (GwD ∩ S)) \ (Gw ∪ wD). (2.6)
It is this form which is used in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] to define the internal transformation.

Example 2.8 Let S be the Fibonacci set. Let X = S ∩ A 2 . The internal transformation applied to X with respect to b gives Y = {aa, aba, b}. The internal transformation applied to X with respect to a gives Y ′ = {a, baab, bab}.

The following result is proved in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] in the case G 0 = ∅ (Proposition 4.4.5).

Proposition 2.9 Let S be a uniformly recurrent set and let X ⊂ S be a finite S-maximal bifix code of S-degree d. Let w ∈ S be a nonempty word such that the sets G 1 , D 1 defined by Equation (2.4) are nonempty. Then the set Y obtained as in Equation (2.5) is a finite S-maximal bifix code with S-degree at most d.

Proof. By Proposition 2.6 there is a thin maximal bifix code X ′ of degree d such that X = X ′ ∩ S. Let Y ′ be the code obtained from X ′ by internal transformation with respect to w. Then

Y ′ = (X ′ ∪ w ∪ (G ′ 1 wD ′ 0 * D ′ 1 )) \ (G ′ w ∪ wD ′ ) with G ′ = X ′ w -1 , D ′ = w -1 X ′ , and G ′ 0 = (wD ′ )w -1 , D ′ 0 = w -1 (G ′ w), G ′ 1 = G ′ \ G ′ 0 , D ′ 1 = D ′ \ D ′ 0 . We have G = G ′ ∩ Sw -1 , D = D ′ ∩ w -1 S, and
D i = D ′ i ∩ w -1 S, G i = G ′ i ∩ Sw -1 for i = 0, 1. In particular G 1 ⊂ G ′ 1 , D 1 ⊂ D ′ 1 . Thus G ′ 1 , D ′ 1 = ∅.
This implies that Y ′ is a thin maximal bifix code of degree d (see Proposition 6.2.8 and its complement page 242 in [START_REF] Berstel | Codes and Automata[END_REF]).

Since w ∈ S, we have Y = Y ′ ∩ S. By Theorem 4.2.11 of [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], Y is an Smaximal bifix code of S-degree at most d. Since S is uniformly recurrent, this implies that Y is finite.

When G 0 = ∅, the bifix code Y has S-degree d (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]Proposition 4.4.5]). We will see in the proof of Theorem 3.12 another case where it is true. We have no example where it is not true.

Example 2.10 Let S be the Fibonacci set, as in Example 2.8. Let X = S ∩ A 2 and let w = a. Then Y = {a, baab, bab} is the S-maximal bifix code of S-degree 2 already considered in Example 2.8.

Strong, weak and neutral sets

In this section, we introduce strong, weak and neutral sets. We prove a theorem concerning the cardinality of an S-maximal bifix code in a neutral set S (Theorem 3.6).

Strong, weak and neutral words

Let S be a factorial set. For a word w ∈ S, let m(w) = e(w)ℓ(w)r(w) + 1.

We say that, with respect to S, w is strong if m(w) > 0, weak if m(w) < 0 and neutral if m(w) = 0.

A biextendable word w is called [START_REF]Combinatorics, automata and number theory[END_REF]Chapter 4]). If S is biextendable, any ordinary word is neutral. Indeed, one has We say that a set of words S is strong (resp. weak, resp. neutral ) if it is factorial and every word w ∈ S is strong or neutral (resp. weak or neutral, resp. neutral).

ordinary if E(w) ⊂ a × A ∪ A × b for some (a, b) ∈ E(w) (see
E(w) = (a × (R(w) \ b)) ∪ ((L(w) \ a) × b) ∪ (a, b
The sequence (p n ) n≥0 with p n = Card(S ∩ A n ) is called the complexity of S. Set k = Card(S ∩ A) -1.

Proposition 3.2

The complexity of a strong (resp. weak, resp. neutral) set S is at least (resp. at most, resp. exactly) equal to kn + 1.

Given a factorial set S with complexity p n , we denote s n = p n+1p n the first difference of the sequence p n and b n = s n+1s n its second difference. The following is from [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF] (it is also part of Theorem 4.5.4 in [START_REF]Combinatorics, automata and number theory[END_REF]Chapter 4] and also Lemma 3.3 in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF]). Proof. Assume that S is strong. Then m(w) ≥ 0 for all w ∈ S and thus, by Lemma 3.3, the sequence (s n ) is nondecreasing. Since s 0 = k, this implies s n ≥ k for all n. The proof of the other cases is similar. We now give an example of a set of complexity 2n + 1 on an alphabet with three letters which is not neutral.

The Cardinality Theorem

The following result, referred to as the Cardinality Theorem, is a generalization of a result proved in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] in the less general case of a Sturmian set. Since the set S ∩ A n is an S-maximal bifix code of S-degree n (see Example 2.3), it is also a generalization of Proposition 3.2. Theorem 3.6 Let S be a recurrent set containing the alphabet A and let X ⊂ S be a finite S-maximal bifix code. Set k = Card(A) -1 and d = d X (S). If S is strong (resp. weak), then Card(X) -1 ≥ dk (resp. Card(X) -1 ≤ dk). If S is neutral, then Card(X) -1 = dk.

Note that, for a recurrent neutral set S, a bifix code X ⊂ S may be infinite since this may happen for a Sturmian set S (see [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]Example 5.1.4]).

We consider rooted trees with the usual notions of root, node, child and parent. The following lemma is an application of a well-known lemma on trees relating the number of its leaves to the sum of the degrees of its internal nodes. Lemma 3.7 Let S be a prefix-closed set. Let X be a finite S-maximal prefix code and let P be the set of its proper prefixes. Then Card(X) = 1+ p∈P (r(p)-1).

We order the nodes of a tree from the parent to the child and thus we have m ≤ n if m is a descendant of n. We denote m < n if m ≤ n with m = n. Lemma 3.8 Let T be a finite tree with root r on a set N of nodes, let d ≥ 1, and let π, α be functions assigning to each node an integer such that (i) for each internal node n, π(n) ≤ π(m) where the sum runs over the children of n, (ii) for each leaf m of T , one has m≤n α(n) = d.

Then n∈N α(n)π(n) ≥ dπ(r).
Proof. We use an induction on the number of nodes of T . If T is reduced to its root, then d = α(r) implies α(r)π(r) = dπ(r) and the result is true. Assume that it holds for trees with less nodes than T . Since T is finite and not reduced to its root, there is an internal node such that all its children are leaves of T . Let m be such a node. Since x≤n α(n) = α(x) + m≤n α(n) has value d for each child x of m, the value v = α(x) is the same for all children of m. Let T ′ be the tree obtained from T by deleting all children of m. Let N ′ be the set of nodes of T ′ . Let π ′ be the restriction of π to N ′ and let α ′ be defined by

α ′ (n) = α(n) if n = m, α(m) + v otherwise.
It is easy to verify that T ′ , π ′ and α ′ satisfy the same hypotheses as T, π and α.

Then n∈N α(n)π(n) = n∈N ′ \m α(n)π(n) + α(m)π(m) + x<m vπ(x) = n∈N ′ \m α ′ (n)π ′ (n) + α(m)π(m) + v x<m π(x) ≥ n∈N ′ \m α ′ (n)π ′ (n) + (α(m) + v)π(m) = n∈N ′ \m α ′ (n)π ′ (n) + α ′ (m)π ′ (m) = n∈N ′ α ′ (n)π ′ (n),
whence the result by the induction hypothesis.

A symmetric statement holds replacing the inequality in condition (i) by π(n) ≥ π(m) and the conclusion by n∈N α(n)π(n) ≤ dπ(r).

Proof of Theorem 3.6. Assume first that S is strong. Let N be larger than the lengths of the words of X. Let U be the set of words of S of length at most N . By considering each word w as the father of aw for a ∈ A, the set U can be considered as a tree T with root the empty word ε. The leaves of T are the elements of S of length N .

For w ∈ U , set π(w) = r(w) -1 and let

α(n) = 1 if n is a proper prefix of X 0 otherwise.
Let us verify that the conditions of Lemma 3.8 are satisfied. Let u be in U with |u| < N . Then, since u is strong or neutral, a∈L(u) (r(au) -1) = e(u)ℓ(u) ≥ r(u) -1. This implies that au∈S π(au) ≥ π(u) showing that condition (i) is satisfied.

Let w be a leaf of T , that is, a word of S of length N . Since N is larger than the maximal length of the words of X, the word w is not an internal factor of X and thus it has d parses with respect to X. It implies that it has d suffixes which are proper prefixes of X (since X is right S-complete, this is the same as to have no prefix in X). Thus w≤u α(u) = d. Thus condition (ii) is also satisfied.

By Lemma 3.8, we have n∈U α(n)π(n) ≥ dπ(ε). Let P be the set of proper prefixes of X. By definition of α, we have n∈U α(n)π(n) = p∈P π(p) and thus by definition of π, dπ(ε) = dk ≤ p∈P (r(p) -1). Since S is recurrent, X is an S-maximal prefix code. Thus, by Lemma 3.7, we have Card(X) = 1 + p∈P (r(p) -1) and thus we obtain Card(X) ≥ 1 + dk which is the desired conclusion.

The proof that Card(X) -1 ≤ dk if S is weak is symmetric, using the symmetric version of Lemma 3.8. The case where S is neutral follows then directly.

We illustrate Theorem 3.6 in the following example. Example 3.9 Consider the set G of words on the alphabet B = {x, y, z, t} obtained as follows. Let S be the Fibonacci set and let X ⊂ S be the Smaximal bifix code of S-degree 3 defined by X = {a, baabaab, baabab, babaab}.

We consider the morphism f :

B * → A * defined by f (x) = a, f (y) = baabaab, f (z) = baabab, f (t) = babaab. We set G = f -1 (S).
The words of G of length at most 4 are represented in Figure 3.1 on the left. Since S is Sturmian, it is a uniformly recurrent tree set (see the definition in Section 4). By the main result of [START_REF] Berthé | Maximal bifix decoding[END_REF], the family of uniformly recurrent tree sets is closed under maximal bifix decoding. Thus G is a uniformly recurrent tree set.

The tree of right-special words is represented on the right in Figure 3. In agreement with Lemma 3.7, the sum of the values of r(p) -1 is 6 in both cases.

The following example illustrates the necessity of the hypotheses in Theorem 3.6.

Example 3.10 Consider again the Chacon set S of Example 3.5. Let X = S ∩ A 4 and let Y, Z be the S-maximal bifix codes of S-degree 4 represented in Figure 3.3. The first one is obtained from X by internal transformation with respect to abc . The second one with respect to bca. We have Card(Y ) = 10 and Card(Z) = 8 showing that Card(Y ) -1 > 8 and Card(Z) -1 < 8, illustrating the fact that S is neither strong nor weak.

The following example shows that the class of sets of factor complexity kn+1 is not closed by maximal bifix decoding.

A converse of the Cardinality Theorem

We end this section with a statement proving a converse of the Cardinality Theorem.

Theorem 3.12 Let S be a uniformly recurrent set containing the alphabet A.

If any finite S-maximal bifix code of S-degree d has d(Card(A)-1)+ 1 elements, then S is neutral.

Proof. We may assume that A has more than one element. We argue by contradiction. Let w ∈ S be a word which is not neutral. We cannot have w = ε since otherwise the S-maximal bifix code X = S ∩ A 2 has not the good cardinality.

Set n = |w| and X = S ∩ A n+1 . The set X is an S-maximal bifix code of S-degree n + 1. Let Y be the code obtained by internal transformation from X with respect to w and defined by Equation (2.5). Note that G = L(w) and D = R(w).

We distinguish two cases.

Case 1. Assume that Gw ∩ wD = ∅. The code Y is defined by Equation (2.6) and we have Card(GwD∩S) = e(w). Since D 0 = G 0 = ∅, the hypotheses of Proposition 2.9 are satisfied and Y has S-degree n + 1 (by Proposition 4.4.5 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]). This implies Card(X) = Card(Y ). On the other hand

Card(Y ) = Card(X) + 1 + e(w) -ℓ(w) -r(w) = Card(X) + m(w).
Since w is not neutral, we have m(w) = 0 and thus we obtain a contradiction. Case 2. Assume next that Gw ∩ wD = ∅. Then w = a n with n > 0 for some letter a and the sets G 0 , D 0 defined by Equation (2.3)

are G 0 = D 0 = {a}. Moreover a n+1 ∈ X.
Since w is not neutral, it is bispecial. Thus the sets G 1 , D 1 are nonempty and the hypotheses of Proposition 2.9 are satisfied. Since S is uniformly recurrent and since S = a * , the set a * ∩ S is finite. Set a * ∩ S = {1, a, . . . , a m }. Thus m ≥ n + 1.

Let b = a be a letter such that a m b ∈ S. Then, δ Y (a m ) = n since a m has n suffixes which are proper prefixes of Y . Moreover, a m b has no suffix in Y . Indeed, if a t b ∈ Y , we cannot have t ≥ n since a n ∈ Y . And since all words in Y except a n have length greater than n, t < n is also impossible. Thus by Equation (2.1), we have δ Y (a m b) = δ Y (a m ) + 1 and thus δ Y (a m b) = n + 1. This shows that the S-degree of Y is n + 1 and thus that Card(Y ) = Card(X) as in Case 1.

We may assume that n is chosen maximal such that a n is not neutral. This is always possible if a m is neutral. Otherwise, Case 1 applies to X = S ∩ A m+1 and w = a m .

For n ≤ i ≤ m -2 (there may be no such integer

i if n = m -1), since a i+1 is neutral, we have Card(G 1 a i D 1 ∩ S) = e(a i ) -ℓ(a i+1 ) -r(a i+1 ) + 1 = e(a i ) -e(a i+1 ). Moreover, Card(G 1 a m-1 D 1 ∩S) = e(a m-1 )-r(a m )-ℓ(a m ) = e(a m-1 )-e(a m )- 1 and Card(G 1 a m D 1 ∩ S) = e(a m ). Thus Card(G 1 a n a * D 1 ∩ S) = m-2 i=n (e(a i ) -e(a i+1 )) + e(a m-1 ) -e(a m ) -1 + e(a m ) = e(a n ) -1.
Thus Card(Y ) -Card(X) evaluates as

1 + Card(G 1 a n a * D 1 ∩ S) -Card(Ga n ) -Card(a n D) + 1 = 1 + e(a n ) -1 -ℓ(a n ) -r(a n ) + 1 = m(a n )
(the last +1 on the first line comes from the word a n+1 counted twice in Card(Gw) + Card(wD)). Since m(a n ) = 0, this contradicts the fact that X and Y have the same number of elements.

Tree sets

We introduce in this section the notions of acyclic and tree sets. We state and prove the main result of this paper (Theorem 4.4). The proof uses results from [START_REF] Berthé | Acyclic, connected and tree sets[END_REF].

Acyclic and tree sets

Let S be a set of words. For w ∈ S, the extension graph G(w) of w is the following undirected bipartite graph. Its set of vertices is the disjoint union of two copies of the sets L(w) and R(w). Next, its edges are the pairs (a, b) ∈ E(w). By definition of E(w), an edge goes from a ∈ L(w) to b ∈ R(w) if and only if awb ∈ S.

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 acyclic if for every word w ∈ S, the graph G(w) is acyclic. We say that S is a tree set if G(w) is a tree for all w ∈ S.

Clearly an acyclic set is weak and a tree set is neutral. Note that a biextendable set S is a tree set if and only if the graph G(w) is a tree for every bispecial non-ordinary word w. Indeed, if w is not bispecial or if it is ordinary, then G(w) is always a tree. Indeed, S is biextendable and every bispecial word is ordinary (see Example 3.1).

The following example shows that there are neutral sets which are not tree sets. In the last example, the set is not recurrent. We present now an example, due to Julien Cassaigne [10] of a uniformly recurrent set which is neutral but is not a tree set (it is actually not even acyclic).

Finite index basis property

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 the free group on A.

We will prove the following result, referred to as the Finite Index Basis Theorem.

Theorem 4.4 Any uniformly recurrent tree set S containing the alphabet A has the finite index basis property.

Note that the Cardinality Theorem (Theorem 3.6) holds for a set S satisfying the finite index basis property. Indeed, by Schreier's formula a basis of a subgroup of index d of a free group on s generators has (s -1)d + 1 elements (actually we use Theorem 3.6 in the proof of Theorem 4.4).

We denote by X the subgroup of the free group on A generated by a set of words X. A submonoid M of A * is called saturated in S if M ∩S = M ∩S. We recall the following result from [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] (Theorem 6.2 referred to as the Saturation Theorem). Theorem 4.5 Let S be an acyclic set. The submonoid generated by a bifix code included in S is saturated in S.

Actually, by a second result of [START_REF] Berthé | Acyclic, connected and tree sets[END_REF] (Theorem 6.1 referred to as the Freeness Theorem), if S is acyclic, any bifix code X ⊂ S is free, which means that it is a basis of the subgroup X . We will not use this result here and thus we will prove directly that if S is a uniformly recurrent tree set, any finite S-maximal bifix code is free.

Before proving Theorem 4.4, we list some related results. The first one is the main result of [START_REF] Berstel | Bifix codes and Sturmian words[END_REF]. The following examples shows that Theorem 4.4 may be false for a set S which does not satisfy some of the hypotheses.

The first example is a uniformly recurrent set which is not neutral.

Example 4.7 Let S be the Chacon set (see Example 3.5). We have seen that S is not neutral and thus not a tree set. The set S ∩ A 2 = {aa, ab, bc, ca, cb} is an S-maximal bifix code of S-degree 2. It is not a basis since ca(aa) -1 ab = cb. Thus S does not satisfy the finite index basis property.

In the second example, the set is neutral but not a tree set and is not uniformly recurrent.

Example 4.8 Let S be the set of Example 4.2. It is not a tree set (and it is not either uniformly recurrent). The set S ∩ A 2 is the same as in the Chacon set. Thus S does not satisfy the finite index basis property.

In the last example we have a uniformly recurrent set which is neutral but not a tree set. Example 4.9 Let S be the set on the alphabet B = {1, 2, 3} of Example 4.3. We have seen that S is neutral but not a tree set.

Let X = S ∩ B 2 . We have X = {12, 13, 22, 23, 31}. The set X is not a basis since 13 = 12(22) -1 23. Thus S does not satisfy the finite index basis property.

We close this section with a converse of Theorem 4.4. Proposition 4.10 A biextendable set S such that S ∩ A n is a basis of the subgroup A n for all n ≥ 1 is a tree set.

Proof. Set k = Card(A) -1. Since A n generates a subgroup of index n, the hypothesis implies that Card(A n ∩ S) = kn + 1 for all n ≥ 1. Consider w ∈ S and set m

= |w|. The set X = AwA ∩ S is included in Y = S ∩ A m+2 . Since Y is a basis of a subgroup, X ⊂ Y is a basis of the subgroup X .
This implies that the graph G(w) is acyclic. Indeed, assume that (a

1 , b 1 , . . . , a p , b p , a 1 ) is a cycle in G(w) with p ≥ 2, a i ∈ L(w), b i ∈ R(w) for 1 ≤ i ≤ p and a 1 = a p . Then a 1 wb 1 , a 2 wb 1 , . . . , a p wb p , a 1 wb p ∈ X. But a 1 wb 1 (a 2 wb 1 ) -1 a 2 wb 2 • • • a p wb p (a 1 wb p ) -1 = 1,
contradicting the fact that X is a basis.

Since G(w) is an acyclic graph with ℓ(w) + r(w) vertices and e(w) edges, we have e(w) ≤ ℓ(w) + r(w) -1. But then

Card(A m+2 ∩ S) = w∈A m ∩S e(w) ≤ w∈A m ∩S (ℓ(w) + r(w) -1) ≤ 2 Card(A m+1 ∩ S) -Card(A m ∩ S) ≤ k(m + 2) + 1.
Since Card(A m+2 ∩ S) = k(m + 2) + 1, we have e(w) = ℓ(w) + r(w) -1 for all w ∈ A m . This implies that G(w) is a tree for all w ∈ S. Thus S is a tree set.

Corollary 4.11 A uniformly recurrent set which has the finite index basis property is a tree set.

Proof. Let S be a uniformly recurrent set having the finite index basis property. For any n ≥ 1, the set S ∩ A n is an S-maximal bifix code of S-degree n (Example 2.3). Thus it is a basis of a subgroup of index n. Since it is included in the subgroup generated by A n , which has index n, it is a basis of this subgroup. This implies that S is a tree set by Proposition 4.10. Theorem 4.12 Let S be a uniformly recurrent tree set containing the alphabet A. For any w ∈ S, the set R S (w) is a basis of the free group on A.

Proof of the Finite Index Basis Theorem

Proof of Theorem 4.4. Assume first that X is a finite S-maximal bifix code of S-degree d. Let P be the set of proper prefixes of X. Let H be the subgroup generated by X.

Let u ∈ S be a word such that δ X (u) = d, or, equivalently, which is not an internal factor of X. Let Q be the set formed of the d suffixes of u which are in P .

Let us first show that the cosets Hq for q ∈ Q are disjoint. Indeed, assume that Hp ∩ Hq = ∅. It implies Hp = Hq. But any p, q ∈ Q are comparable for the suffix order. Assuming that q is longer than p, we have q = tp for some u u y q r Denote by F A the free group on A. Let

V = {v ∈ F A | Qv ⊂ HQ} .
For any v ∈ V the map p → q from Q into itself defined by pv ∈ Hq is a permutation of Q. Indeed, suppose that for p, p ′ ∈ Q, one has pv, p ′ v ∈ Hq for some q ∈ Q. Then qv -1 is in Hp ∩ Hp ′ and thus p = p ′ by the above argument.

The set V is a subgroup of F 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 S (u) is contained in V . Indeed, let q ∈ Q and y ∈ R S (u). Since q is a suffix of u, qy is a suffix of uy, and since uy is in S (by definition of R S (u)), also qy is in S. Since X is an S-maximal bifix code, it is an S-maximal prefix code and thus it is right S-complete. This implies that qy is a prefix of a word in X * and thus 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 S (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 the set I(X) of internal factors of X, and this is not the case. Thus we have r ∈ Q (see Figure 4.3). Since X * ⊂ H and r ∈ Q, we have qy ∈ HQ. Thus y ∈ V .

By Theorem 4.12, the group generated by R S (u) is the free group on A. Since R S (u) ⊂ V , and since V is a subgroup of F A , we have V = F A . Thus Qw ⊂ HQ for any w ∈ F A . Since 1 ∈ Q, we have in particular w ∈ HQ. Thus F 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. Since S is acyclic and recurrent, by Theorem 3.6, we have Card(X) ≤ d(Card(A) -1) + 1. But since X generates H, it contains a basis of H. In view of Schreier's Formula, this implies that X is a basis of H.

Assume conversely that the finite bifix code X ⊂ S is a basis of the group H = X and that H has index d. Since X is a basis of H, 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 in [START_REF] Berstel | Bifix codes and Sturmian words[END_REF], if S is a uniformly recurrent set, any finite bifix code contained in S is contained in a finite S-maximal bifix code. Thus there is a finite S-maximal bifix code Y containing X. Let e be the S-degree of Y . By the first part of the proof, Y is a basis of a subgroup K of index e of the free group on A. In particular, it has

Example 2 . 1

 21 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.

Theorem 2 . 4

 24 Let S be a recurrent set. A bifix code Y ⊂ S is the kernel of some S-thin S-maximal bifix code of S-degree d if and only if Y is not S-maximal and δ Y (y) ≤ d -1 for all y ∈ Y .Example 2.5 Let S be the Fibonacci set. The set Y = {a} is a bifix code which is not S-maximal and δ Y (a) = 1. 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).

Example 3 . 1

 31 ) and thus e(w) = ℓ(w) + r(w) -1. In a Sturmian set, any word is ordinary. Indeed, for any bispecial word w, there is a unique letter a such that aw is right-special and a unique letter b such that wb is left-special. Then awb ∈ S and E(w) = a × A ∪ A × b.

Lemma 3 . 3

 33 We have b n = w∈A n ∩S m(w) and s n = w∈A n ∩S (r(w) -1) for all n ≥ 0. Proposition 3.2 follows easily from the following lemma. Lemma 3.4 If S is strong (resp. weak, resp. neutral), then s n ≥ k (resp. s n ≤ k, resp. s n = k) for all n ≥ 0.

Example 3 . 5

 35 Let A = {a, b, c}. The Chacon word on three letters is the fixpoint x = f ω (a) of the morphism f from A * into itself defined by f (a) = aabc, f (b) = bc and f (c) = abc. Thus x = aabcaabcbcabc • • • . The Chacon set is the set S of factors of x. It is of complexity 2n + 1 (see [11, Section 5.5.2]). It contains strong, neutral and weak words. Indeed, S∩A 2 = {aa, ab, bc, ca, cb} and thus m(ε) = 0 showing that the empty word is neutral. Next E(abc) = {(a, a), (c, a), (a, b), (c, b)} shows that m(abc) = 1 and thus abc is strong. Finally, E(bca) = {(a, a), (c, b)} and thus m(bca) = -1 showing that bca is weak.

Figure 3 . 1 :

 31 Figure 3.1: The words of length at most 4 of a neutral set G and the tree of right-special words.

Figure 3 . 2 :

 32 Figure 3.2: Two G-maximal bifix codes of G-degree 2. indicated in black in Figure 3.2 with the value of r(p) -1 indicated for each one. In agreement with Lemma 3.7, the sum of the values of r(p) -1 is 6 in both cases.

Example 3 .Figure 3 . 3 :

 333 Figure 3.3: Two S-maximal bifix codes of S-degree 4.

Proposition 4 . 1 A

 41 Sturmian set S is a tree set.

Example 4 . 2 Figure 4 . 1 :

 4241 Figure 4.1: The graph G(ε) for the set S.

Example 4 . 3 Figure 4 . 2 :

 4342 Figure 4.2: The words of length at most 4 of the set S.

Corollary 4 . 6 A

 46 Sturmian set has the finite index basis property.Proof. This follows from Theorem 4.4 since a Sturmian set is a uniformly recurrent tree set (Proposition 4.1).

Let

  S be a set of words. For w ∈ S, let Γ S (w) = {x ∈ S | wx ∈ S ∩ A + w} be the set of right return words to w. When S is recurrent, the set Γ S (w) is nonempty. Let R S (w) = Γ S (w) \ Γ S (w)A + be the set of first right return words. The proof of Theorem 4.4 uses several other results, among which Theorem 4.5 and the following result from [5] (Theorem 5.6).

Figure 4 . 3 :

 43 Figure 4.3: A word y ∈ R S (u).

(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 .