Gazdar Tahani
email: tahani.gazdar@alumni.univ-avignon.fr

Abderrezak Rachedi
email: rachedi@univ-mlv.fr

Abderrahim Benslimane
email: abderrahim.benslimane@univ-avignon.fr

Belghith

Tahani Gazdar

Abdelfettah Belghith
email: abdelfettah.belghith@hotmail.com

A distributed

come

I. INTRODUCTION

In vehicular environments, the time to react to a given situation is very critical and a vehicle must be able to accurately check the trust of the received information in real time. The trust and reputation models [START_REF] Govindan | Trust Computations and Trust Dynamics in Mobile Adhoc Networks[END_REF] are proposed as new approaches to circumvent with this constraint and to filter out inaccurate messages and malicious vehicles. Trust establishment is tagged in many existing research works for peer to peer, sensors, and mobile ad hoc networks [START_REF] Govindan | Trust Computations and Trust Dynamics in Mobile Adhoc Networks[END_REF] [START_REF] Marmol | LFTM, linguistic fuzzy trust mechanism for distributed networks[END_REF]. However, in vehicular environments it is facing tremendous specific challenges related to their characteristics. In general vehicular networks do not have any centralized third party. The only possible communications with infrastructures take place with Road Side Units (RSUs) which are not deployed along the roads. Therefore, centralized systems are not suitable to establish trust in vehicular environments. Furthermore, the vehicles are traveling with a high speed, consequently, the communications between the vehicles are short in time and it is difficult to form an experience history between peers. In addition, a trust model must be scalable providing the same achievement independently on the density of vehicles in the network.

The main existing trust models for VANETs are based on the verification of vehicles identities and their legitimacy in the network [START_REF] Huang | Situation-Aware Trust Architecture for Vehicular Networks[END_REF], [START_REF] Marmol | TRIP: a trust and reputation infrastructure-based proposal for vehicular ad hoc networks[END_REF], [START_REF] Tajeddine | A Privacy-Preserving Trust Model for VANETs[END_REF]. They are classified as entity oriented models such as identity-based systems where the trust metric is related to the vehicle credentials and its trustworthiness is static. Other existing trust models are based on a data-oriented approach. Indeed, in VANETs, when the vehicle introduces a new information in the network it will be responsible for the consequences of this information. In this paper, we propose a new hybrid dynamic trust model combining both approaches: entity and data oriented. We use a Markov Chain to formalize the proposed trust model. The goal of this modeling is to take into account different parameters related to the robustness, stability and flexibility of the trust model. Unlike static trust models, we propose a dynamic model based on the monitoring of the instantaneous vehicles behaviors in the network. The monitoring process considers the legitimacy of the information and the cooperation rate of the vehicles. We include also the constraints related to the efficiency of the monitoring process, particularly, the probability of false positives and negatives. Furthermore, our model is fully distributed, the assessment of vehicles behavior does not require any type of infrastructure.

The remainder of the paper is organized as follows. First, we discuss some existing trust models designed for VANETs. In section 2, we detail the proposed trust model. Section 3 exposes the simulation results and section 4 concludes the paper.

II. RELATED WORK

The trust models in VANETs can be classified into three main types: entity-oriented, data-oriented and hybrid models. In the entity-oriented trust models the evaluation of the legitimacy of an entity is required. In [START_REF] Tajeddine | A Privacy-Preserving Trust Model for VANETs[END_REF], the authors propose a reputation-based trust model where the vehicles are organized off-line into groups and each one has a reputation value. Each group reputation increases if the average of its members opinion is conform to the road state. It is obvious that this approach is not resilient against colluding vehicles which belong to the same group and they broadcast false information to make the reputation score of their group drive down. Another shortcoming is the absence of a reputation value for each vehicle to punish malicious ones. In our proposal, we remedy to this problem by an instantaneous evaluation of the vehicles behavior and a malicious vehicle is revoked whenever it is detected. In [START_REF] Marmol | TRIP: a trust and reputation infrastructure-based proposal for vehicular ad hoc networks[END_REF], the authors propose a fuzzy approach to decide whether to accept a warning message or not based on the trustworthiness of the issuer of the message. In this model, the authors assume that a vehicle requests from its neighbors information about the reputation of its peers which makes a supplementary overhead also this needs additional time. However, in our proposal each vehicle executes a standalone trust metric evaluation process using the already existing messages in the network. In the above exposed models, the trust establishment is related to the verification of the trustworthiness of the entities. However, inaccurate information cannot be detected without verifying the information itself.

Many research works propose instead, data-oriented trust models which require the evaluation of the trustworthiness of the information received in the messages. The authors in [START_REF] Raya | On Data-Centric Trust Establishment in Ephemeral Ad Hoc Networks[END_REF] propose a data trust model where the validity of the received reports about occurred events is inferred by a decision module [7] [8] to calculate the posteriori probability of the events. However, since inference module use the prior probability, it is not easy to derive it since the high speed. The authors in [START_REF] Ding | Reputation-based Trust Model in Vehicular Ad Hoc Networks[END_REF] proposed an event-based reputation model to filter out bogus messages. In order to decide about the legitimacy of the messages, the vehicle observes if the behavior of the reporter corresponds to the standard behavior result of that event. We notice that this solution is not realistic because a malicious vehicle can broadcast a message about an unreal event and it reacts correspondingly. Nevertheless, data oriented models seems to be efficient to filter out malicious data that is why we build our model on. Additionally, we combine it with a cooperation assessment parameter.

In order to circumvent the shortcoming of the two above mentioned approaches, the authors proposed in [START_REF] Dotzer | VARS: A vehicle Ad hoc network reputation System[END_REF], a hybrid approach using a piggybacking technique. In fact, a trustworthiness opinion is appended to each message reporting an event. The drawback of this proposal is that the first opinion appended to the message will affect other opinions since its computing is recursive; it is based on opinion received in the message. In [START_REF] Patwardhan | A Data Intensive Reputation Management Scheme for Vehicular Ad Hoc Networks[END_REF], the authors assume that in the network there is a set of trusted vehicles called anchors which broadcast reliable data. The data validation is ensured either by comparing the received data to other vehicles agreement or to the data of the anchors. The shortcoming of this model is that the validation process is accurate only if there is a sufficient number of reports from other vehicles. The trust model that we propose is a fully distributed and hybrid approach based on a monitoring process. We aim to conceive a flexible model combining many parameters relayed to the cooperativeness of vehicles in order to detect selfish ones, their ability to broadcast and forward legitimate information and the efficiency of the monitoring process.

III. THE ANALYTICAL TRUST MODEL

In this section, we describe our proposed trust model. We present the states transitions diagram for the Markov chain model. The model resolution, also the computation of different transition probabilities are detailed.

A. Trust Model Overview

In the network, we consider that when an event occurs on the road, all vehicles which are in the vicinity of that event must broadcast alerts messages reporting it. Furthermore, vehicles forward all received messages from their neighbors. We note that the arrival of alert messages to the transmission queue of vehicles is modeled in the following section. Our purpose is to establish a dynamic and distributed trust model where each vehicle called monitor affects a local trust metric T m to each vehicle from its neighbors called monitored vehicle. In fact, the evaluation of the behavior of the monitored vehicle by the monitor vehicle is based on two main aspects: the reliability of the message sent by the monitored vehicle and its cooperation ratio. Thus, according to the outcome of the monitoring process, the monitored vehicle will have its T m increased, decreased or unchanged. Additionally , the T m can change to null, and as presented in figure 1, this transition is weighted by a probability related to the honesty of the monitored vehicle when it broadcasts the alert messages, also it depends on the current state of the vehicle.

We model the update process of the T m at the monitor vehicle using a discrete-time Markov chain with N + 1 states and a transition matrix P = (P i,j (t)) 0≤i,j≤N as represented in figure 1. Consider a random variable (X t ) t≥0 which represents the current local T m corresponding to a given state of a monitored vehicle assigned by a monitor vehicle, the probability of transition from state i to state j is:

P i,j (t) = P r(X t = j|X t-1 = i) (1)
The T m has a value in [0, 1], state 0 is the non trusted state wherein T m = 0 and state N is the highest trusted state where T m = 1. Each vehicle has an initial trust metric T 0 in [0, 1].

The interval [0, 1] is divided into N + 1 states, each one represents a step of γ (1 mod γ = 0). The values of γ and N are determined based on the degree of accuracy assessment and severity towards the T m of vehicles that we want to achieve with our model. By using these two parameters we aim to make our model flexible in the context wherein it is used.

B. States Transition Probabilities 1)

One step increasing/decreasing of the T m : If the current state is i at time t (P r(X t = i) > 0) and the vehicle shows a positive behavior, its T m transits to the state i + 1 otherwise it transits to the state i -1. The positive behavior in our model is related to: the ability of the vehicle to correctly forward all received legitimate messages, and to the legitimacy of its own broadcasted messages. The transitions probabilities are expressed as follows:

P i,i+1 (t) = p i (t -1) * p c * p w 0 ≤ i < N P i,i-1 (t) = p i (t -1) * (1 -p c ) * p w 0 < i ≤ N (2)
Where p i (t) is the probability to be in state i at time t, given that the initial state is 1, p c is the probability to positively cooperate in the network, and p w is he probability to correctly evaluate the received messages. It is expressed as follows: In equation 3, p e is the probability of false positives and false negatives following the monitoring process [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF]. Using this parameter, we aim to take into account the constraints related to the nature of the network and to the monitoring in wireless environments. Indeed, this avoids the over and under estimation in the monitoring and consequently in the trust level evaluation. Particularly, p e includes the probability of collusion while transmitting warning messages and the failure of the monitored vehicle to access to the transmission channel.

p w = 1 -p e (3)
From the transition matrix P, it is possible to compute the probability to be in state i at time t, p i (t). In fact, given that the initial state of a vehicle is X 0 = 1, the probability for our Markovian process to be in state k at time

t k > 0 is p k (t k ) = P 1,k (t k ).
In addition, the probability to reach state i at time t > t k given that X t k = k is P k,i (t). Therefore, we can use the Chapman-Kolmogorov equation [START_REF] Hachtel | Markovian Analysis of Large Finite State Machines[END_REF] to compute the probability p i (t) that a vehicle is in state i at time t:

p i (t) = k in [1..N ] P 1,k (t k ) * P k,i (t) (4)
In order to evaluate the cooperation of a monitored vehicle, first, a monitor vehicle calculates a forwarding rate called F . The forwarding rate F is the number of messages forwarded by a monitored vehicle divided by the total number of messages transmitted by the monitor vehicle: F = the number of f orwarded messages the total number of transmitted messages

Secondly, the monitor vehicle calculates the probability that the monitored vehicle has a positive cooperation in the network denoted p c as follows:

p c = F * P m (6)
where P m is the probability that the monitored vehicle is not malicious. In fact we use this parameter in order to evaluate the honesty of the vehicle when transmitting or forwarding information. Tremendous works exist in the literature aiming to detect malicious nodes in MANETs [START_REF] Raya | Eviction of Misbehaving and Faulty Nodes in Vehicular Networkss[END_REF], [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF]and VANETs [START_REF] Marmol | TRIP: a trust and reputation infrastructure-based proposal for vehicular ad hoc networks[END_REF].

2) State sojourn probability : A vehicle can keep the same T m for a certain period of time because either it has no message in its buffer to forward or it has not detected events on the road. We consider that the application layer in the monitored vehicle generates alert messages according to a Poisson process with a rate λ 1 . In addition, the monitored vehicle receives alert messages from other vehicles according to a Poisson process with a rate λ 2 ≥ λ 1 . We suppose that a message needs the period t s to be treated in the higher layer before being sent, so we assume that the time required for the treatment of messages is exponential with a rate 1/t s . Then, according to [START_REF] Iyer | Secure V2V communications: Performance impact of computational overheads[END_REF], the probability P q that the transmission queue is empty is:

P q = 1 - 1 -(1 -θ)θ B 1 -θ (B+1) (7)
θ = (λ 1 + λ 2 ) * t s (8)
Where B is the size of the transmission queue and we assume that λ 1 ,λ 2 and t s have the same values for all vehicles. Thus, from equation 7 we deduce the probability that a node sojourns in state i, P i,i (i = N ):

P i,i (t) = p i (t -1) * P q (9)
3) Trusted state sojourn Probability: The vehicle keeps the trusted state N (T m = 1) either because it positively cooperates as discussed above or it has no messages in its transmission queue. We express P N,N the probability to sojourn in state N as follows:

P N,N (t) = p N (t -1) * (p c * p w + P q ) (10)
Yet, the trusted vehicles are also monitored by their neighbors in order to avoid that they benefit from the trusted state and behave maliciously or selfishly in the network. 4) Transition to the non trusted state: As we mentioned above, the monitor vehicle assesses both the cooperativeness of the monitored vehicle and the legitimacy of the information it broadcasts. Thus, according to the outcome of the monitoring process, the T m of the monitored vehicle can nullify with a given probability that reflects the legitimacy of its broadcasted messages. The probability of this transition is related to the current state of the vehicle and to its honesty represented by P m . Logically, if a vehicle reaches a high T m , this means that it is almost honest as expressed by equation ( 6). However, a malicious vehicle can behave honestly to reach the highest trust level and then it tries to benefit from its state and to broadcast false information. Thus, we consider this transition in order to detect such a malicious behavior known as camouflage attack. The probability that the vehicle transits to state 0 is calculated as follows:

p i,0 (t) = p i (t -1) * (1 -P m ) (11)

IV. PERFORMANCE EVALUATION

A. Analytical Results

In order to validate our trust model we consider a Markov chain as represented in figure 1 with N = 10 states. Each one represents a step γ = 0.1. The initial trust metric for each vehicle is T m = 0.1. We conducted a set of preliminary tests in order to investigate the convergence and the persistence of the proposed approach as function of different parameters. Furthermore, we study the resilience of the model against some misbehaving scenarios.

1) Convergence of the T m : We investigate the convergence of our model, particularly we are interested on the required time and the needed conditions for a vehicle to reach the trusted state where T m =1 and to remain in. To this end, we plot the probability to get T m = 1 that we call the trustworthiness of a vehicle, as function of the time, the forwarding rate F and P m . We set parameters p e to 0.20 as computed in [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF] and P q to 0.25. We notice from figures 2a and 2b that for time units less than 10, P (T m = 1) is equal to 0 because a vehicle starts from T m = 0.1 and it must pass by all states from 1 to N = 10, then the vehicle needs at least 10 time units to reach T m = 1. After, the P (T m = 1) incessantly grows until reaching a maximum in the 14 th time unit. Regarding the attenuation of P (T m = 1) after reaching the maximum in figure 2a, we explain this behavior by the cumulating effect of P m . If the vehicle does not improve its behavior related to P m , the probability to reach T m = 1 decreases. However, in figure 2b where P m = 1, when P (T m = 1) reaches 1 it does not attenuate as for the previous case where P m < 1. This result confirms our explanation for the attenuation in the previous plot, also this result points out the sensibility of the trustworthiness to the parameter P m . In addition, we remark in both plots that for small values of F (0.35 and 0.45) the drop of P (T m = 1) is less rapid compared to higher values of F (0.90 and 1.00), however it is obvious that P (T m = 1) is less important. Hence, if a vehicle reaches the trusted state with a legal behavior and a full cooperation, it keeps its trust state.

We conclude that the trustworthiness is getting higher for high values of the forwarding rate F. However, the persistence in the trusted state strongly depends on the behavior of the vehicle expressed by P m . The more positively the vehicle cooperates, the more chance it has to be trusted, and the longer it keeps its trusted state.

2) Impact of a disruptive behavior: Let us now study the ability of our trust model to handle dynamic behaviors of the vehicles. In general, a disruptive vehicle divides its behavior into two parts: in the first part it positively participates in the network in order to reach the highest trust level. However, in the second part it changes its positive behavior to negative one in order to benefit from the reached trust level to attack the network. In this study, we focus on two main scenarios.

Scenario 1: : When a vehicle reaches the highest trust level, it will act selfishly by reducing its forwarding rate F in order to keep its throughput only for its own data transmission. The vehicle shows a good behavior (P m =1 and F=1) for the first 20 time units to build up its T m . Then it proceeds with a disruptive behavior following a pattern of bad behavior where it degrades its forwarding rate for 10 time units followed by a good behavior for 10 time units and so on. From the plot of figure 3, we notice that P(T m =1) brutally decreases with the first misbehave time unit (21 th ). Along the period the vehicle does not cooperate, its trustworthiness grows slowly because it is not acting maliciously in the network and it continues to transmits its own messages (λ 1 = 0). Once the monitored vehicle restores its cooperation rate, its trustworthiness resumes to the old value. We remark also that when the degradation decreases, the vehicle finds its previous trustworthiness level more rapidly. The difference in the fall of the trustworthiness between the curves proves that the trustworthiness of the vehicles strongly depends on its cooperation quality (p c ). This result proves that our model reacts rapidly and accurately to the change in the behavior of vehicles. It points out that our trust model is dynamic unlike static models where the trustworthiness is not sensible to behavior changes.

Scenario 2: : We consider a disruptive vehicle which shows a good behavior (P m =1) for the first 20 times units to build up its T m and then it proceeds with a disruptive behavior with P m =0.45 as plotted in figure 4, giving a pattern of a bad behavior for 10 times units followed by a good behavior for 10 time units and so on. From the plot of figure 4, the trustworthiness decreases at the first misbehaving time unit. Once again, we notice the high sensibility of the proposed model to the parameter P m which reflects the honesty of the vehicles. When the vehicle resumes its good behavior (P m = 1), it doesn't restore its first trusted state and its trustworthiness increases slightly up to only 0.18 in figure 4. The same behavior of curves is repeated for the following steps until time unit 80. There are two conclusions that can be derived from analyzing the results. First, if a vehicle proves a malicious behavior even for a short period of time, this affects its trustworthiness on the network and it is difficult to restore the trusted state. Secondly, we deduce that the proposed model is incentive. Indeed, the vehicle must be neither selfish nor malicious not only to reach the trusted state but also to remain in.

B. Simulation Results

We study in this section, the feasibility of our trust model in high mobility environments. Specifically, we investigate the convergence of the trust metric in such environments and we focus on the followed reasoning to decide different parameters used in our proposed trust model particularly, the number of states N and transition step γ. To this end, we conducted a set of tests using the simulator Veins [START_REF] Sommer | Bidirectionally Coupled Network and Road Traffic Simulation for Improved IVC Analysis[END_REF] considering two vehicular models: a Urban model and a highway. Vehicles travel with a maximum speed of 15m/s and 25m/s for the urban model and the highway, respectively. In the highway model, all vehicles are traveling towards the same direction. However, in the urban model the vehicles passes by multiple crosses and they can change the direction at any time there are in a cross. The arrival of vehicles in the road is a Poisson process with a rate of 2 vehicles per one second. We plot in figures 5a and 5b the average number of vehicles encountered along a trip per one vehicle and the average encounter duration between two vehicles. From figure 5a, we remark that in the highway model, the average number of encountered vehicles is more important than the urban model. This is essentially due to the high speed of vehicles which makes the neighborhood change frequently in highway compared to the urban model. This is an important recommendation for our trust model. In fact, a vehicle will not travel isolated in the network and this augments the likelihood that its behavior is monitored.

According to the proposed model, the trust metric is evaluated each time the monitor receives a message from the monitored vehicle. Thus the time units expected in figures 2a and 2b correspond to the average time period between two evaluations of the trusted metric that we call iteration duration. It relies on the inter arrivals time of the messages from the monitored to the monitor and the average time required to assess F and p c by the monitor vehicle. Hence, if the vehicle proves a legitimate behavior (F = 1 and P m = 1), it needs only a time period of N*iteration duration to have its T m = 1. It is the minimal required convergence time of the trust metric. From figure 5b, the average encounter duration in the highway model is higher than urban model, it reaches 100s. However, in the urban model, the average encounter duration is less than 60s. We plot in figure 5c, the maximal and minimal time for the trust metric convergence for both urban and highway model. For the minimal convergence time we consider different iteration duration: 2s, 3s and 5s and N=10 states. The goal is to investigate if the average encounter duration guarantees the convergence of the trust metric to the trusted state. As depicted in figure 5c, we remark that the maximal encounter duration in the urban model insures the convergence for N=10, only for iteration duration < 5s. We deduce that in case where the network traffic is reduced in the urban model, the number of states N can be reduced to quickly reach the convergence to the trusted state. However, we remark that for the highway scenario, the encounter duration guarantees the convergence even for limited traffic of messages. Hence, in this model our trust model can be executed with N higher than 10 states. Thus, from the analysis of above results, we conclude that our model is highly adaptive to applications. Indeed, the different parameters values are constrained by the context where the trust model is processed, particularly the speed, the duration of encounter between vehicles and the network traffic.

V. CONCLUSION

In this paper, we propose a dynamic and distributed trust model aiming at establishing a trust relationship between vehicles and filtering out malicious and selfish vehicles. This trust model is formalized by Markov chain used to stress the trust evolution system, to introduce different parameters and to make it flexible. The monitoring process is based on the assessment of the cooperativeness of a vehicle also its honesty while broadcasting alert messages. In addition, the proposed model has a set of characteristics. It is incentive because it incites the vehicles to positively act in the network without adopting the selfish or the malicious behaviors in order to keep their reached trust level. It is robust because it is able to detect the different malicious behaviors. It is flexible because it presents different customized parameters like the trust interval and the number of transitions needed to reach the highest trust level. We conducted a set of simulations to investigate the performances of our trust model and to point out the reaction of our model to behavior changes. The obtained results illustrate the positive reaction of the model face to disruptive behaviors. In our future work, we are aiming at enhancing the performance evaluation of our trust model in real context of VANETs and we will extend our model in order to manage global trust metric where each vehicle has only one T m known by all its neighbors.

Fig. 1 .

 1 Fig. 1. States transitions diagram of the proposed approach

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. The trustworthiness of the vehicle versus the time with different Pm

Fig. 5 .

 5 Fig. 5. The average number of encountered vehicles, the average encounter duration and the convergence of the Tm in highway and urban models


Durand Fabien
email: fabien.durand@u-picardie.fr

Lamfa

Julien Leroy
email: j.leroy@ulg.ac.be

Towards a Statement of the S-adic Conjecture through Examples

The S-adic conjecture claims that there exists a condition C such that a sequence has a sub-linear complexity if and only if it is an S-adic sequence satisfying Condition C for some finite set S of morphisms. We present an overview of the factor complexity of S-adic sequences and we give some examples that either illustrate some interesting properties or that are counter-examples to what could be believed to be "a good Condition C".

Introduction

A usual tool in the study of a sequence (or an infinite word) w over a finite alphabet A is the complexity function p w (or simply p) that counts the number of factors of each length n occurring in the sequence, i.e., p w (n) = Card({u ∈ A * | |u| = n and ∃x ∈ A * , y ∈ A N : w = xuy}) (see Chapter 4 of [START_REF]Combinatorics, Automata and Number Theory[END_REF] for a survey on complexity function). The set of factors of length n of w is denoted by Fac n (w) and Fac(w) = n∈N Fac n (w). The complexity function p w is clearly bounded by (Card(A)) n , n ∈ N, but not any function can be a complexity function. As an example, it is well known (see [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]) that either the sequence is ultimately periodic (and then p w (n) is ultimately constant), or its complexity function grows at least like n + 1. Non-periodic sequences with minimal complexity p w (n) = n + 1 for all n exist. They are called Sturmian sequences and a large bibliography is devoted to them (see Chapter 2 of [START_REF] Lothaire | Algebraic combinatorics on words[END_REF] and Chapter 6 of [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF] for surveys on these sequences).

There is a huge literature about sequences with a low complexity. Indeed, see for instance [Abe03, AB07, All94, AR91, Cas96, Cas97, Fer95, Fer99, GJ09, [START_REF] Koskas | Complexités de suites de Toeplitz[END_REF][START_REF] Rote | Sequences with subword complexity 2n[END_REF]. By "low complexity" we usually mean that "the complexity is bounded by a linear function". Moreover, many well-known families of sequences can also be indefinitely desubstituted with a finite number of morphisms. Formally, an S-adic sequence is defined as follows. Let w be a sequence over a finite alphabet A. If S is a set of morphisms (possibly infinite), an S-adic representation of w is given by a sequence (σ n : A * n+1 → A * n ) n∈N of morphisms in S and a sequence (a n ) n∈N of letters, a i ∈ A i for all i, such that1 A 0 = A, w = lim n→+∞ σ 0 σ 1 • • • σ n (a ω n+1 ) and lim n→+∞ |σ 0 σ 1 • • • σ n (a n+1 )| = +∞, where a ω n+1 is the sequence only composed of occurrences of a n+1 . The sequence (σ n ) n∈N ∈ S N is the directive word of the representation. In the sequel, we will say that a sequence w is S-adic if there exists a set S of morphisms such that w admits an S-adic representation. Observe that in most cases, we deal with finite sets S of morphisms.

An open problem is to determine the link between being an S-adic sequence and having a sub-linear complexity (see [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF][START_REF] Ferenczi | Rank and symbolic complexity[END_REF][START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF]). This problem is called the S-adic conjecture.

Conjecture 1.1 (S-adic conjecture). There exists a condition C such that a sequence has a sub-linear complexity if and only if it is an S-adic sequence satisfying Condition C for some finite set S of morphisms.

It is clear that we cannot avoid considering a particular condition since there exist some purely substitutive sequences with a quadratic complexity.

In this paper, we present an overview of the factor complexity of S-adic sequences and we give some examples that either illustrate some interesting properties or that are counterexamples to what could be believed to be "a good Condition C".

In all what follows, we consider that alphabets are finite subsets of N and if σ : A * → B * is a morphism with A = {0, 1, . . . , k}, we write σ = [σ(0), . . . , σ(k)]. The following example is classical when considering S-adic sequences.

Example 1.2. Let us define the four morphisms R 0 , R 1 , L 0 and L 1 over {0, 1} by R 0 = [0, 10], R 1 = [01, 1], L 0 = [0, 01] and L 1 = [10, 1]. Since the work of Morse and Hedlund [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF], it is well known that for any Sturmian sequence w, there is a sequence (k n ) n∈N of integers such that

w = lim n→+∞ L k 0 0 R k 1 0 L k 2 1 R k 3 1 L k 4 0 R k 5 0 • • • L k 4n+2 1 R k 4n+3 1 (0 ω ). (1)
It is important to notice that, when we talk about an S-adic sequence, the corresponding directive word (σ n ) n∈N ∈ S N is always implicit (even when it is not unique). Indeed, for a given set S of morphisms, we will see that two distinct S-adic sequences can have different properties depending on their respective directive words.

Comparison between morphic and S-adic sequences

The aim of this section is to compare morphic sequences with S-adic sequences. In particular, we show that the factor complexity of morphic sequences is rather restricted and can be dependent on some combinatorial criteria although it is not the case at all for S-adic sequences.

Morphic and purely morphic sequences

Purely morphic sequences correspond to S-adic sequences with Card(S) = 1. If S = {σ}, we then have

σ 0 σ 1 σ 2 • • • = σσσ • • • = σ ω .
In that case, the complexity functions that can occur have been completely determined by Pansiot in [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF]. Indeed, he proved that for purely morphic sequences w = σ ω (a) = lim n→+∞ σ n (a ω ) with σ non-erasing (i.e., σ(b) is not the empty word for all letters b), the complexity function p w (n) can have only five asymptotic behaviors that are2 Θ(1), Θ(n), Θ(n log n), Θ(n log log n) and Θ(n 2 ). Moreover, when the sequence w is aperiodic, Morse and Hedlund proved that its complexity function cannot be Θ(1) (see [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]). Then, Pansiot proved that the class of complexity of the sequence only depends on the growth rate of the length of the images. Definition 2.1. Recall that a morphism σ : A * → A * is said to be everywhere growing if it does not admit bounded letter, i.e., letter b such that lim n→+∞ |σ n (b)| < +∞. We let A B,σ (or A B when no confusion is possible) denote the set of bounded letters of σ. By opposition, a non-bounded letter is called a growing letter. Since for all letters a, we have |σ n (a)| ∈ Θ(n αa β n a ) for some α a in N and β a ≥ 1 (see [START_REF] Rozenberg | The mathematical theory of L systems[END_REF]), any everywhere growing morphism satisfies exactly one of the following three definitions:

1. a morphism σ : A * → A * is quasi-uniform if there exists β ≥ 1 such that for all letters a ∈ A, |σ n (a)| ∈ Θ(β n );
2. a morphism σ : A * → A * is polynomially diverging if there exists β > 1 and a function α : A → N, α = 0, such that for all letters a ∈ A,

|σ n (a)| ∈ Θ(n α(a) β n ); 3. a morphism σ : A * → A * is exponentially diverging if there exist a 1 , a 2 ∈ A, α 1 , α 2 ∈ N and β 1 , β 2 > 1 with β 1 = β 2 such that for each i ∈ {1, 2}, |σ n (a i )| ∈ Θ(n α i β n i ).
Theorem 2.2 (Pansiot [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF]). Let w = σ ω (a) be a purely morphic sequence with σ nonerasing.

1. If σ is everywhere growing and i. quasi-uniform, then

3 p w (n) ∈ O(n);
ii. polynomially diverging, then p w (n) ∈ Θ(n log log n);

iii. exponentially diverging, then p w (n) ∈ Θ(n log n).

2. If σ is not everywhere growing and if there are infinitely many factors of

w in A * B , then p w (n) = Θ(n 2 ).
3. If σ is not everywhere growing and if there are only finitely many factors of w in A * B , then there exists a purely morphic sequence τ ω (b) with τ : B * → B * everywhere growing and a non-erasing morphism λ : B * → A * such that w = λ(τ ω (b)). In this case, we have

p w (n) ∈ Θ(p τ ω (b) (n)).
One could regret that Theorem 2.2 only holds for non-erasing morphisms. However, the following result states that when the morphism is erasing, one can see the obtained purely morphic sequence as a morphic sequence (i.e., an image under a morphism of a purely morphic sequence) with non-erasing morphisms. The result is due to Cobham [START_REF] Cobham | On the Hartmanis-Stearns problem for a class of tag machines[END_REF] and has been recovered later by Pansiot [START_REF] Pansiot | Hiérarchie et fermeture de certaines classes de tag-systèmes[END_REF]. It can also be found in Cassaigne and Nicolas's survey [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF].

Theorem 2.3 (Cobham [START_REF] Cobham | On the Hartmanis-Stearns problem for a class of tag machines[END_REF] and Pansiot [START_REF] Pansiot | Hiérarchie et fermeture de certaines classes de tag-systèmes[END_REF]). If w is a morphic sequence, it is the image under a letter-to-letter morphism of a purely morphic word σ ω (a) with σ a non-erasing morphism.

Theorems 2.2 and 2.3 show that to compute the complexity function of a purely morphic sequence, it is sometimes necessary to see it as a morphic sequence. It is therefore natural to be interested in the complexity function of such sequences. By definition, it is obvious that any purely morphic sequence is morphic. The converse is known to be false since at least 1980, when Berstel proved that the Arshon word is morphic but not purely morphic [START_REF] Berstel | Mots sans carré et morphismes itérés[END_REF] (other examples can be found in the litterature, as for instance, the result by Seebold showing that the unique, up to letter permutation, binary overlap-free word which is a fixed point of a morphism is the Thue-Morse word [START_REF] Séébold | Sequences generated by infinitely iterated morphisms[END_REF]).

Moreover, not only the class of morphic sequences strictly contains the class of purely morphic sequences, but also the asymptotic behaviors of the complexity functions are different. Indeed, Example 2.4 shows that the classes of complexity given by Pansiot are not sufficient anymore.

Example 2.4 (Deviatov [START_REF] Deviatov | On subword complexity of morphic sequences[END_REF]). Let w be the morphic sequence τ (σ ω (0)) where σ and τ are defined by σ :

         0 → 01 1 → 12 2 → 23 3 → 3 and σ :          0 → 0 1 → 1 2 → 2 3 → 2 We have p w ∈ Θ(n √ n).
Other examples can be found in [START_REF] Pansiot | Subword complexities and iteration[END_REF]. Indeed, for all k ≥ 1, Pansiot explicitly built a morphic sequence w whose complexity function satisfies p w (n) ∈ Θ(n k √ n). Consequently, the number of different asymptotic behaviors for the complexity function of morphic sequences is at least countably infinite. However, the behaviors Θ(n k √ n) seem to be the only new behaviors with respect to purely morphic sequences. Indeed, in [START_REF] Deviatov | On subword complexity of morphic sequences[END_REF] Deviatov proved the next result and conjectured an equivalent result of Pansiot's Theorem (Theorem 2.2) for morphic sequences.

Theorem 2.5 (Deviatov [Dev08]). Let w be a morphic sequence. Then, either p w (n

) ∈ Θ(n 1+ 1 k ) for some k ∈ N * , or p w (n) ∈ O(n log n).
Conjecture 2.6 (Deviatov [START_REF] Deviatov | On subword complexity of morphic sequences[END_REF]). The complexity function of any morphic sequence only adopts one of the following asymptotic behaviors: Θ(1), Θ(n), Θ(n log log n), Θ(n log n), Θ(n 1+ 1 k ) for some k ∈ N.

In particular, Theorem 2.5 implies that the highest complexity that one can get is the same for morphic sequences and for purely morphic sequences. This can be explained by the following result.

Proposition 2.7 (Cassaigne and Nicolas [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF]). Let w be a one-sided sequence over A and σ : A * → B * be a non-erasing morphism. If M = max a∈A |σ(a)|, for all n we have

p σ(w) (n) ≤ Mp w (n). Moreover, if w is purely morphic and σ is injective, then p σ(w) (n) ∈ Θ(p w (n)).
The previous discussion shows that the factor complexity of morphic sequences is rather constrained. To conclude this section, we give some examples of how some additional combinatorial criteria can even more restrict it.

A first well-known fact is that if a purely morphic sequence is k-power-free, i.e., it does not contains any factor of the form u k , then its factor complexity grows at least linearly and at most like n log n (see [START_REF] Ehrenfeucht | On the subword complexity of m-free D0L languages[END_REF]). We will consider a similar criterion on S-adic sequences in Section 3.5.

Another such criterion is the uniform recurrence of the sequence, i.e., any factor occurs infinitely often and with bounded gaps in w. For morphic sequences, this implies that the complexity is sub-linear (see [START_REF] Nicolas | On uniformly recurrent morphic sequences[END_REF]). Actually, the uniform recurrence of a morphic sequence is even equivalent to its linear recurrence, i.e., any factor u occurs infinitely often and with gaps bounded by K|u| (see [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF][START_REF] Durand | Decidability of uniform recurrence of morphic sequences[END_REF]). Furthermore, if w is a morphic and uniformly recurrent sequence over A, then w is a morphic sequence τ (σ ω (a)) with σ a primitive morphism (this result was already proved in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] in the particular case of morphic sequences ψ(ϕ ω (a)) with ψ non-erasing and ϕ everywhere growing). The following result also provides an algorithm to check whether a purely morphic sequence is uniformly recurrent.

Theorem 2.8 (Damanik and Lenz [START_REF] Damanik | Substitution dynamical systems: characterization of linear repetitivity and applications[END_REF]). A purely morphic sequence w = σ ω (a) is uniformly recurrent if and only if there is a growing letter b ∈ A that occurs with bounded gaps in w and such that for all letters c ∈ A there is a power σ k such that c occurs in σ k (b).

S-adic sequences

The previous section shows that the factor complexity of morphic sequences are rather restricted (especially for purely morphic sequences). In particular, the class of uniformly recurrent morphic sequences is strictly contained in the class of morphic sequences with sublinear complexity. In this section, we show that, for S-adic sequences, things are strongly different. A first important result is the following. Proposition 2.9 (Cassaigne [Fog11]). Let A be an alphabet and l / ∈ A. There exists a finite set S of morphisms over A ′ = A ∪ {l} such that any sequence over A is S-adic.

In particular, this implies that one can get any high complexity with S-adic sequences (although for morphic sequences, the complexity is at most quadratic). Moreover, the following proposition implies that the set of possible asymptotic behaviors for the complexity function of S-adic sequences is uncountable (although it is finite for purely morphic sequences and conjectured to be countable for morphic ones). See also [START_REF] Mauduit | Complexity of infinite sequences with zero entropy[END_REF] for another approach to build sequences whose complexity is closed to a given function.

Proposition 2.10 (Cassaigne [START_REF] Cassaigne | Constructing infinite words of intermediate complexity[END_REF]). Let f : R + → R + be a function such that i. lim t→+∞

f (t) log t = +∞; ii. f is differentiable, except possibly at 0; iii. lim t→+∞ f ′ (t)t β = 0 for some β > 0; iv. f ′ is decreasing.
Then there exists a uniformly recurrent sequence w over {0, 1} such that4 log(p w (n)) ∼ f (n).

In particular, the function f (n) in the previous proposition can be taken equal to n α for any α with 0 < α < 1.

Another big difference is that the class of uniformly recurrent S-adic sequences with sublinear complexity is a very short part of the class of uniformly recurrent S-adic sequences. Indeed, recall that the topological entropy of a sequence over an alphabet A is the real number h with 0 ≤ h ≤ log(Card(A)) defined by

h = lim n→∞ log(p(n)) n .
A uniformly recurrent sequence w over an alphabet A with at least two letters a, b ∈ A cannot have maximal complexity (p w (n) = Card(A) n ): since all powers a n occur in w, there are unbounded gaps between two successive occurrences of b in w. However, together with Proposition 2.9, the following result shows that, except the maximal one p w (n) = Card(A) n , any high complexity can be reached by uniformly recurrent S-adic sequences.

Theorem 2.11 (Grillenberger [Gri73]). Let A be an alphabet with d = Card(A) ≥ 2 and h ∈ [0, log(d)[. There exists a uniformly recurrent one-sided sequence w over A with topological entropy h.

The following result provides an S-adic characterization of uniformly recurrent sequences. A sequence is said to be primitive S-adic (with constant s 0 ) if s 0 ∈ N is such that for all r ∈ N, all letters in A r occur in all images σ r • • • σ r+s 0 (a), a ∈ A r+s 0 +1 . It is said to be weakly primitive S-adic if for all r ∈ N, there exists s > 0 such that all letters in A r occur in all images σ r • • • σ r+s (a), a ∈ A r+s+1 . Any primitive S-adic sequence is weakly primitive and Durand [START_REF] Durand | Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF] proved that any weakly primitive S-adic sequence is uniformly recurrent. Following a construction based on return words (see Section 3.4 for definition), one can prove that the converse it true. More precisely, we got Theorem 2.12 (Durand [START_REF] Durand | Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF], Leroy [START_REF] Leroy | Contribution to the resolution of the S-adic conjecture[END_REF]). A sequence w is uniformly recurrent if and only if it is weakly primitive S-adic.

Moreover, the directive word can be chosen to be proper and if w does not have a sub-linear complexity, then S is infinite.

The proof is similar to the proof of the following result which gives an S-adic characterization of linearly recurrent sequences. Let recall that a sequence is said to be proper S-adic if all morphisms in its directive word are proper, i.e., for all n there are letters a, b ∈ A n such that σ n (A n+1 ) ⊂ aA * n b. Theorem 2.13 (Durand [Dur03]). A sequence w is linearly recurrent if and only if it is primitive and proper S-adic with Card(S) < +∞.

The next example shows that the linear recurrence is an even stronger condition that the primitivity for S-adic sequences (contrary to what holds in the morphic case).

Example 2.14 (Durand [Dur03]). Let S = {σ, τ } where σ and τ are defined by σ :

     0 → 021 1 → 101 2 → 212 and τ :      0 → 012 1 → 021 2 → 002
The sequence

w = lim n→+∞ στ σ 2 τ • • • σ n τ (0 ω )
is primitive S-adic but not linearly recurrent.

S-adicity and sub-linear complexity

The aim of this section is to explore some ideas that one could have about the S-adic conjecture. First, we present some sufficient conditions for S-adic sequences to have a sublinear complexity and we show that we cannot make them weaker. Then, we give some counter-examples to some conditions that one could naturally believe to be sufficient to have a sub-linear complexity.

The growth rate of the length have still some importance

Durand [START_REF] Durand | Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF][START_REF] Durand | Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF], gave some sufficient conditions for an S-adic sequence to have a sub-linear complexity. The main condition is the one given by the following result and is a generalization of what exists for purely morphic sequences (see Theorem 2.2). The other conditions are simply consequences of it.

Proposition 3.1 (Durand [Dur03]). Let w be an S-adic sequence with Card(S) < +∞ and whose directive word is Proposition 3.3 (Durand [Dur00]). If w is a primitive S-adic sequence with Card(S) < +∞ and constant s 0 directed by (σ n ) n∈N with σ n : A * n+1 → A * n and A 0 the alphabet of w, then there exists a constant D such that for all non-negative integers r,

(σ n ) n∈N with σ n : A * n+1 → A * n and A 0 the alphabet of w. If there is a constant D such that for all n, max a,b∈A n+1 |σ 0 • • • σ n (a)| |σ 0 • • • σ n (b)| ≤ D, (2)
max a,b∈A r+s 0 +1 |σ r • • • σ r+s 0 (a)| |σ r • • • σ r+s 0 (b)| ≤ D.
Corollary 3.4. Let S be a set of non-erasing morphisms and τ ∈ S be strongly primitive (i.e., for all letters a of τ (A), a occurs in all images τ (b) for b ∈ A). Any S-adic sequence for which τ occurs infinitely often with bounded gaps in the directive word is uniformly recurrent and has a sub-linear complexity.

The everywhere growing property can be naturally transposed to S-adic sequences. But, contrary to what holds in the purely morphic case, under that assumption, the condition given by Equation (2) is not equivalent to sub-linear complexity. Indeed, even some Sturmian sequences do not satisfy it (those with unbounded coefficient (k n ) n∈N in Example 1.2). One could therefore try to make that condition a little bit weaker.

We can observe in Example 1.2 that Condition (2) is still infinitely often satisfied. Indeed, let us consider the directive word (τ n ) n∈N defined by

τ 0 = L k 0 0 R k 1 0 L 1 , τ 2n = L k 4n -1 0 R k 4n+1 0 L 1 for n ≥ 1 and τ 2n+1 = L k 4n+2 -1 1 R k 4n+3 1
L 0 for n ≥ 0. For all n, there exist some integers i and j such that either τ n = [0 i 10 j+1 , 0 i 10 j ] or τ n = [1 i 01 j , 1 i 01 j+1 ]. With these morphisms, we have

τ 0 τ 1 • • • τ n • • • = L k 0 0 R k 1 0 L k 2 1 R k 3 1 • • • L k 4n+2 1 R k 4n+3 1 • • • (3)
and there is a constant K such that for all n, max a,b∈A n+1

|τ 0 •••τn(a)| |τ 0 •••τn(b)| ≤ K. The sequence (τ n ) n∈N is called a contraction of the directive word (L k 0 0 R k 1 0 • • • ).
Observe that the set S = {τ n | n ∈ N} of morphisms might be infinite (when (k n ) n∈N is unbounded). Consequently, it may be interesting to work either with infinite sets of morphisms or with contractions.

But, Example 3.5 below shows that Proposition 3.1 is not true anymore when Card(S) = ∞. Indeed, if we consider the contraction (σ n ) n∈N of the directive word of Proposition 3.6 defined for all n ≥ 0 by

σ n = γ kn µ, (4)
we have

|σ 0 • • • σ n (0)| = |σ 0 • • • σ n (1)
| for all n although the complexity is not sub-linear as soon as the sequence (k n ) n∈N is unbounded. Proposition 3.6. Let (k n ) n∈N be a sequence of non-negative integers. The sequence

w γ,µ = lim n→+∞ γ k 0 µγ k 1 µγ k 2 µ • • • γ kn µ(0 ω )
is uniformly recurrent. Moreover, w γ,µ has an at most linear complexity if and only if the sequence (k n ) n∈N is bounded. Finally, for all n we have

|γ k 0 µγ k 1 µγ k 2 µ • • • γ kn µ(0)| = |γ k 0 µγ k 1 µγ k 2 µ • • • γ kn µ(1)|,
and denoting

ℓ n = |γ k 0 µγ k 1 µγ k 2 µ • • • γ kn µ(0)|, we have p wγ,µ (ℓ n ) ≤ 4ℓ n -2.
Before proving the result, recall that a right (resp. left) special factor in a language L ⊂ A * is a factor such that there are at least two letters a, b ∈ A for which ua and ub (resp. au and bu) belong to L. A bispecial factor is a factor which is both left and right special. This definition can be extended to words and sequences w by replacing L by Fac(w). Let us recall the following result.

Theorem 3.7 (Cassaigne [START_REF] Cassaigne | Special factors of sequences with linear subword complexity[END_REF]). A sequence has a sub-linear complexity if and only if there is a constant K such that for all n, the number of right (resp. left) special factors of length n is less than K.

Proof of Proposition 3.6. First, as µ occurs infinitely often in the directive word, w γ,µ is weakly primitive {γ, µ}-adic and so, by Theorem 2.12, it is uniformly recurrent. Now let us study the complexity depending on the sequence (k n ) n∈N . The case of a bounded sequence is a direct consequence of Corollary 3.4. Hence let us consider that the sequence (k n ) n∈N is unbounded and let us show that the complexity is not at most linear. Due to Theorem 3.7, we only have to prove that the number of right special factors of length n of w γ,µ is unbounded.

As already mentioned in Example 3.5, the fixed point γ ω (0) has a quadratic complexity. Consequently the number of right special factors of γ ω (0) of a length n is unbounded.

We let readers check that bispecial factors of γ ω (0) are words ε, 0, 1 and words γ(1v) with v bispecial, and that other right special factors of γ ω (0) are the suffixes of words γ(v) for v right special. Thus, by induction, one can state that all right special factors of length n of γ ω (0) occur in γ n+1 (0). Now let us show that if u is a right special factor in γ k n+1 (0), then

γ k 0 µγ k 1 µ • • • γ kn µ(u)
is a right special factor of w of length |u|2 q with q = n i=0 (k i + 1). Indeed, as µ(0) and γ(0) start with 0 and µ(1) and γ(1) start with 1, the image of u is still a right special factor. Moreover, µ(u) contains exactly |u| occurrences of the letter 0 and n occurrences of the letter 1, and both γ and µ map a word with the same number of 0 and 1 to a word of double length with the same number of 0 and 1. Hence |γ k 0 µγ k 1 µ • • • γ kn µ(u)| = |u|2 q with q defined as previously. Now, if u and v are two distinct right special factors of length m of γ ω (0), then

γ k 0 µγ k 1 µ • • • γ kn µ(u) and γ k 0 µγ k 1 µ • • • γ kn µ(v)
are two distinct special factors of length m2 q of w. As the number of right special factors of a given length of γ ω (0) is unbounded, and as the sequence (k n ) n∈N is unbounded, the number of right special factors of a given length of w is also unbounded which concludes the first part of the proof.

The last step is to show that, for all integers ℓ n , we have p wγ,µ (ℓ n ) ≤ 4ℓ n . For all nonnegative integers n, we already know that

|γ k 0 µγ k 1 µ • • • γ kn µ(0)| = |γ k 0 µγ k 1 µ • • • γ kn µ(1)| = ℓ n = 2 q
with q as defined previously by n i=0 (k i + 1). Consequently, all factors u of length ℓ n are factors of |γ k 0 µγ k 1 µ • • • γ kn µ(v)| for some word v of length 2. As there are only 4 possible binary words of length 2 and as there are less than ℓ n + 1 distinct factors of length ℓ n in a word of length 2ℓ n , we obtain p wγ,µ (ℓ n ) ≤ 4ℓ n + 4. However, among the 4ℓ n + 4 words, both words

γ k 0 µγ k 1 µ • • • γ kn µ(0) and γ k 0 µγ k 1 µ • • • γ kn µ(1) have been counted 4 times, hence p wγ,µ (ℓ n ) ≤ 4ℓ n -2.
3.2 The condition C of the conjecture could not only concern the set S

Since it seems hard to make the condition of Equation (2) weaker, another idea is to determine new sufficient conditions that are independent from it. A first attempt in this direction was proposed by Boshernitzan, asking whether if S contains only morphisms for which the fixed points (if exists) of their powers have sub-linear complexity, then any S-adic sequence has a sub-linear complexity.

But, Boshernitzan eventually provided the following counter-example to that conjecture. Since we did not find any detailed proof of it, we provided it.

Example 3.8. Let γ and E be the morphisms over {0, 1} respectively defined by [001, 1] and [1, 0]. Observe that both morphisms γE and Eγ are primitive. Consequently, they admit a power whose fixed points have sub-linear complexity. We consider the sequence

w γ,E = lim n→+∞ γEγ 2 Eγ 3 E • • • γ n-1 Eγ n (0 ω ).
Proposition 3.9 (Boshernitzan). The sequence w γ,E is S-adic for S = {γE, Eγ}, is uniformly recurrent and does not have a sub-linear complexity.

Proof. First, by definition, w γ,E is indeed S-adic for S = {γE, Eγ}.

Next, the composition γ • E • γ is strongly primitive and occurs infinitely often in the directive word of w γ,E . It is therefore a consequence of Theorem 2.12 that w γ,E is uniformly recurrent.

To prove that w γ,E does not have a sub-linear complexity, by Theorem 3.7, it is sufficient to prove that the number of its right special factors of length n is unbounded. For this purpose, let us introduce notation. For all k ∈ N * , let us define the morphism

Γ k = γEγ 2 E • • • γ k-1
Eγ k E and, for all k ∈ N, the sequence

w (k) = lim n→+∞ γ k+1 Eγ k+2 E • • • γ k+n-1 Eγ k+n (0 ω ).
We then have w γ,E = w (0) = Γ k (w (k) ), for all k ≥ 1. For all i ≥ 1 we also consider the word u i = γ i (10) = 1γ i (0). As 100 and 101 are factors of E(w (k+1) ), and as 100 and 001 are factors of γ k-j γ(E(w (k+1) )) for all j with 1 ≤ j ≤ k (observe also that γ(100) = γ(10)001 and γ(001) = 00γ(10)1), we can deduce that u i is a right special factor of w (k) for all i with 1 ≤ i ≤ k + 1. As words Γ k (0) and Γ k (1) start with different letters, for all integers i such that 1 ≤ i ≤ k + 1, the word Γ k (u i ) is a right special factor of w γ,E , and so are all of its suffixes.

For 1 ≤ i ≤ k + 1, word u i end with 1001 i , so that the longest common suffix between u i and u i+1 is 1 i . It follows that the longest common suffix between Γ k (u i ) and Γ k (u i+1 ) is the word p k Γ k (1 i ) where p 0 = ε and for k ≥ 1,

p k = 1Γ 1 (1 2 )Γ 2 (1 3 ) • • • Γ k-1 (1 k ).
This is indeed a consequence of the fact (we let readers verify it) that for any word u containing at least one occurrence of 0 and 1, the word Γ k (u) ends with ap k where a is the last letter of u when k is even, and where a is the opposite letter to the last letter of u when k is odd.

From what precedes w γ,E has at least n(k) right special words of length |p k Γ k (1 k )| + 1, where n(k) denotes the number of integers i between 1 and k + 1 such that |Γ(u

i )| > |p k Γ k (1 k )|. Next fact allows to estimate n(k). Fact: With f (k) = k 2 +k+2 2 , for all k ≥ 2, 1. for all 1 ≤ i ≤ k + 1, |Γ k (u i )| = 2 i 2 f (k) , 2. |p k Γ k (1 k )| ≤ k 2 2 f (k) .
Proof of the fact. 1. Let i be between 1 and k + 1. By induction, one can verify that

|γ i (0)| 0 = 2 i and |γ i (0)| 1 = 2 i -1. As u i = 1γ i (0), we have |u i | 0 = |u i | 1 = 2 i . Observe that for any word v such that |v| 0 = |v| 1 , we have |γ(v)| = 2|v| and |γ(v)| 0 = |γ(v)| 1 = |v| and |E(v)| 0 = |E(v)| 1 = |v| 0 . Thus, as Γ k = γEγ 2 E • • • γ k-1 Eγ k E, |Γ k (u i )| = 2 i+1 2 k j=1 j = 2 i+1 2 k(k+1) 2 = 2 i 2 f (k) . 2. Before estimating |p k Γ k (1 k )|, we need an estimate of |Γ k (1)|. |Γ k (1)| = γEγ 2 E • • • γ k E(1) = γ k (0) 0 γEγ 2 E • • • γ k-1 E(0) + γ k (0) 1 γEγ 2 E • • • γ k-1 E(1) = 2 k (|Γ k-1 (01)| -|Γ k-1 (1)|) + 2 k -1 |Γ k-1 (1)| = 2 k 2 +k+2 2 -|Γ k-1 (1)| < 2 f (k) . Observe that |Γ k (1 k )| = k|Γ k (1)|. One can verify that, for all j with 1 ≤ j ≤ k, Γ j-1 (1 j ) ≤ Γ k (1 k ). Moreover as k ≥ 2, |1Γ 1 (1 2 )| ≤ |Γ k (1 k )|. Hence |p k Γ k (1 k )| = |1Γ 1 (1 2 )| + k j=3 |Γ j-1 (1 j )| + |Γ k (1 k )| < k|Γ k (1 k )| < k 2 f (k).
To end the proof of proposition 3.9, it suffices to notice that for all i such that log

2 k 2 < i ≤ k + 1, |Γ k (u i )| > |p k Γ k (1 k )|, so that n(k) ≥ k + 1 -⌈log 2 k 2 ⌉.
In other words, the number of right special words of w γ,E of length |p k Γ k (1 k )| + 1 is unbounded, which shows by Theorem 3.7 that w γ,E does not have a sub-linear complexity.

Remark 3.10. The previous result is even stronger than just considering sets S of morphisms with fixed points of sub-linear complexity. Indeed, the sequence also has bounded partial quotients, i.e., all morphisms occur with bounded gaps in the directive word (over {γE, Eγ}).

An opposite question to the one previously answered is to ask whether S-adic sequences can have a sub-linear complexity when S contains a morphism that admits a fixed point that does not have a sub-linear complexity. Example 3.5 positively answers that question and we can prove even more. Indeed, the following example provides a uniformly recurrent S-adic sequence with sub-linear complexity such that a "bad morphism" occurs with arbitrary high powers in its directive word.

Example 3.11. Let us consider the morphisms

β :      0 → 010 1 → 1112 2 → 2 and M :      0 → 0 1 → 1 2 → 1
and the sequence

w β,M = lim n→+∞ MβMβ 2 Mβ 3 M • • • β n-1 Mβ n (0 ω ).
Note that β is not everywhere growing, its set of bounded letters is A B,β = {2} and all words in A * B,β are factors of β ω (0). Hence by Theorem 2.2(2), p β ω (0) is in θ(n 2 ). Proposition 3.12. The sequence w β,M defined just above has a sub-linear complexity. More precisely, for all n we have p(n + 1) -p(n) ∈ {1, 2}.

The proof of this proposition will use the link, proved by Cassaigne [Cas97] between bispecial factors and the first difference s of the complexity function. Given an infinite word w, we recall that the bilateral order of a word u is the value

m(u) = Card(Fac(w β,M ) ∩ AuA) -Card(Fac(w β,M ) ∩ Au) -Card(Fac(w β,M ) ∩ uA) + 1.
When m(u) > 0, u is a bispecial factor of w called a strong bispecial factor, and when m(u) < 0, u is also a bispecial factor of w called a weak bispecial factor.

Let s w (or simply s) be the function defined for n ≥ 0 by s(n) = p(n + 1) -p(n). We have s(0) = 1 and Cassaigne proved (see [START_REF] Cassaigne | Complexité et facteurs spéciaux[END_REF]) that

s(n + 1) -s(n) = u∈Facn(w) m(u) (5)
In next useful result, B 0 is the identity morphism and, for k > 0,

B k = MβMβ 2 • • • Mβ k . Lemma 3.13. A word u is a strong bispecial factor of w β,M if and only if u = B k Mβ i (1)
for some k ≥ 0 and some i in {0, . . . , k}.

A word u is a weak bispecial factor of w β,M if and only if u = B k Mβ i (101) for some k ≥ 0 and some i in {0, . . . , k}.

Proof. For all integers k ≥ 0, let w (k) be the sequence w (k) whose directive word is (M, β k+1 , M, β k+2 , . . . ). Note that, for k ≥ 0, w β,M = B k (w (k) ).

All words 010, 011, 110, 111 occur in w (k+1) and all words 010, 011, 120, 111 occur in β j (w (k+1) ) for j ≥ 1. Thus Mβ i (1) for i in {0, 1, . . . , k + 1} are strong bispecial factors of w (k+1) (observe Mβ i (120) = Mβ i (210) contains the factor 1Mβ i (1)0). As B k (0) starts and ends with 0, and as B k (1) starts and ends with 1, B k Mβ i (1) for i ∈ {0, 1, . . . , k} are strong bispecial factors of w β,M . Now let i ∈ {0, 1, . . . , k}. Words 0Mβ i (101)1 and 1Mβ i (101)0 are factors of w (k) (respectively factors of Mβ i+1 (01)1 and 1Mβ i+1 (10)). So 0B k (Mβ i (101))1 and 1B k (Mβ i (101))0 are factors of w β,M . One can verify that the existence of factor 0B k (Mβ i (101))0 in w β,M would imply the existence of factors M(0β j (101)0) in β (k+1-j) (w (k+1) ) for 0 ≤ j ≤ i, and of factor 01010 in β (k+1-i) (w (k+1) ) which is impossible. Similarly the existence of factor 1B k (Mβ i (101))1 in w β,M would imply the existence of 11011 in β (k+1-i) (w (k+1) ) which is impossible.

We now prove that there are no other strong and weak bispecial factors.

Let u be a bispecial factor of w β,M . If u contains no occurrence of the letter 0, u = 1 n for some n ≥ 0. As w β,M contains arbitrarily large powers of 1 and infinitely many occurrences of 0, words 11 n 1, 01 n 1, 11 n 0 are all factors of w β,M . When 01 n 0 is a factor of w β,M , one can verify that 1 n = B k Mβ i (1) for some k ≥ 0 and some integer i in {0, . . . , k}. Thus 1 n is a strong bispecial factor of w β,M if and only if 1 n = B k Mβ i (1) for some k ≥ 0 and some integer i in {0, . . . , k}.

Note that any factor of w β,M containing only one occurrence of 0 is on the form 01 n , 101 n , 1 n 0 or 1 n 01 for some n ≥ 0 and is not bispecial.

Thus assume u contains at least two occurrences of 0. From the shape of the morphisms B k , there is a unique integer k and a unique sequence of words v, p 0 , s 0 , p 1 , s 1 , . . . , p k-1 , s k-1 over {0, 1} such that

u = p 0 B 1 (p 1 )B 2 (p 2 ) • • • B k-1 (p k-1 )B k (v)B k-1 (s k-1 ) • • • B 2 (s 2 )B 1 (s 1 )s 0 ,
where v is a proper factor of Mβ k+1 (010) and for all i, 0 ≤ i ≤ k -1, the word p i (resp.

s i ) is a suffix (resp. prefix) of B i+1 (0) or of B i+1 (1) but is neither equal to B i+1 (0) nor to B i+1 (1).
Since for all i, B i (0) and B i (1) do not have any common prefix or suffix, the factor u is bispecial if and only if all words p 0 , s 0 , p 1 , s 1 , . . . , p k-1 , s k-1 are empty words and v is bispecial in w (k) . Moreover, v contains an occurrence of the letter 0. We also have that u is strongly (resp. weakly) bispecial if and only if so is v. Then, it is only a verification that the only bispecial factors in w (k) that contain an occurrence of 0 and that are factors of Mβ k+1 (010) are the words Mβ i (101) for i ∈ {0, 1, . . . , k}, which are weak bispecial factors.

Proof of Proposition 3.12. Let (u n ) n≥0 be the sequence of strong and weak bispecial factors of w β,M . Observe that for all k ≥ 0,

• B k Mβ k+1 (1) = B k+1 (1) = B k+1 Mβ 0 (1). • |B k (Mβ i (1))| < |B k (Mβ i (101))| < |B k (Mβ i+1 (1))|, for all i in {0, 1, . . . , k}.
Therefore by Lemma 3.13, u n is a strong bispecial factor of w β,M if n is even, and it is a weak bispecial factor of w β,M if n is odd. As, for any factor, m(u) = 1 if it is strong bispecial, m(u) = -1 if it is weak bispecial and m(u) = 0 otherwise, by Formula 5, for all n ≥ 0,

• s(|u n | + 1) -s(|u n |) = 1 if n is even, • s(|u n | + 1) -s(|u n |) = -1 if n is odd, • s(n + 1) -s(n) = 0 if n ∈ {|u m | | m ≥ 0}. Consequently, since s(0) = p(1) -p(0) = 1, for all n ≥ 0, we have p(n + 1) -p(n) = s(n) ∈ {1, 2}.

Another (easier?) version of the S-adic conjecture

A natural idea to try to understand the conjecture is to consider examples composed of well-known morphisms. For instance, one could consider the Fibonacci morphism ϕ = [01, 0] whose fixed point is a Sturmian sequence and the Thue-Morse morphism µ = [01, 10] whose fixed points both have a sub-linear complexity. We have Proposition 3.14. If S = {ϕ, µ} where ϕ and µ are defined above, any S-adic sequence is linearly recurrent.

Proof. Let S = {µ, ϕ}. Let w be an S-adic sequence directed by (σ n ) n∈N and, for all k ∈ N, let w (k) be the S-adic sequence directed by (σ n ) n≥k .

By definition of ϕ and µ, as w (k) ∈ {ϕ(w (k+1) ), µ(w (k+1) )}, word 111 does not occur in w (k) for all k ≥ 1. Note also that 000 does not occur in µ({0, 1} * ), and 0000 does not occur in ϕ(w (k+1) ) since otherwise 111 should occur in w (k+1) . Thus both words 0000 and 111 does not occur in w (k) for all k ≥ 0. This implies that the gap between two occurrences of 01 and 10 is at most 5 (7 is the maximal length of a shortest word on the form 10u10 or on the form 01u01). Now observe that 11 occurs in w (k) only in the image of σ k (10) (and only if σ k = µ). This implies that the gap between two occurrences of 11 is at most 12.

Finally observe that 00 occurs in w (k) only in the image of σ 1 (10) or in the image of σ k (11) (when σ k = ϕ). As factors of w (k) that start with 10 or 11, end with 10 or 11 and do not contain any other occurrences of 10 or 11 have length at most 7, the gap between two consecutive occurrences of 00 is at most 12.

We have just proved that the length of the largest gap between two occurrences of a word of length 2 in all words w (k) is bounded. By choice of S, w is primitive S-adic. Hence by a result of Durand [START_REF] Durand | Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF], w is linearly recurrent.

Let us say that a set of morphisms S is good-adic if all S-adic sequences have a sub-linear complexity. Proposition 3.14 provides an example of such a set. Many other examples are known as:

• any singleton {f } with f a morphism with fixed points of linear complexity;

• the set of Sturmian morphisms {[01, 1], [10, 1], [0, 01], [0, 10]};

• the set of episturmian morphisms over an alphabet

A: S = {L a , R a | a ∈ A} with for all a ∈ A, L a (a) = R a (a) = a, L a (b) = ab and R a (b) = ab for b = a;
• any finite set S that contains only uniform morphisms (see Corollary 3.2);

• any finite set S that contains only strongly primitive morphisms (see Corollary 3.4).

Note that if S is good-adic then, for any morphism f in S admitting an infinite fixed point, this fixed point must have a sub-linear complexity. But this necessary condition is certainly not the only one.

Question 3.15. What are good-adic sets of morphisms?

About return words

If u is a factor of a sequence w, a return word to u is a word r such that ru is a factor of w that admits u as a prefix and that contains only two occurrences of u. Return words to u in w actually correspond to the gaps between two occurrences of u in w.

Durand [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] proved that primitive morphic sequences, i.e., sequences defined as the image, under a morphism, of a fixed point of a primitive morphism can be characterised using return words. Hence, it is quite natural to ask whether such a result exists for S-adic sequences with sub-linear complexity.

There exist many examples of S-adic sequences w with sub-linear complexity for which there exists an integer K, such that all factors of w have at most K return words. For instance, Vuillon [START_REF] Vuillon | A characterization of Sturmian words by return words[END_REF] proved that Sturmian sequences are exactly sequences whose factors have exactly two return words. Justin and Vuillon [START_REF] Justin | Return words in Sturmian and episturmian words[END_REF] extended this result to the family of Arnoux-Rauzy sequences (also called strict episturmian sequences) whose factors have exactly m return words with m the cardinality of the alphabet. Balková, Pelantová and Steiner [START_REF] Balková | Sequences with constant number of return words[END_REF] characterized sequences whose factors have all the same number of return words showing they have all a sub-linear complexity. Improving a result by Ferenczi [START_REF] Ferenczi | Rank and symbolic complexity[END_REF], Leroy [START_REF] Leroy | Contribution to the resolution of the S-adic conjecture[END_REF] proved that sequences whose complexity verify ultimately 1 ≤ p(n+1)-p(n) ≤ 2 are S-adic and infinitely many of their factors admit two or three return words.

Despite of previous example, next proposition show that there exist S-adic sequences with sub-linear complexity such that any long factor has many return words ("many" depending on "long").

Example 3.16. Let us consider the three morphisms p, σ and s defined by p :

         a 1 → 0 a 2 → 1 b 1 → 1 b 2 → 0 σ :          a 1 → a 1 a 2 a 1 a 2 → a 2 a 2 a 2 b 1 → b 1 b 2 b 1 b 2 → b 2 b 2 b 2 s : 0 → a 1 1 → b 1
For all n ≥ 1 we let π n denote the morphism pσ n s; we have

w π = lim n→+∞ π 1 π 2 • • • π n (0 ω ).
Proposition 3.17. The sequence w π defined above is uniformly recurrent, has a sub-linear complexity and for all integers k, there is a length ℓ k such that all factors of w π of length at least ℓ k have at least k return words in w π .

Proof. The uniform recurrence is a direct consequence of Theorem 2.12. Since w is S-adic with S = {p, σ, s}, it is a consequence of Corollary 3.2 that w π has a sub-linear complexity.

Let us prove that all sufficiently long factors of w π have many return words. For all k ≥ 1, we let w (k) denote the sequence

w (k) = lim n→∞ π k π k+1 • • • π n (0 ω ).
We obviously have w (1) = w π and for all k ≥ 1, k+1) ). We also have |π k (0)| = |π k (1)| = 3 k for all k and we let ℓ k denote the length

w π = π 1 • • • π k (w (
|π 1 π 2 • • • π k (0)| = |π 1 π 2 • • • π k (1)| = 3 k(k+1) 2 .
Due to the shape of morphisms π 1 , any factor u of w π of length at least equal to 24 can be uniquely decomposed into images π 1 (0) and π 1 (1), i.e., there is a unique word v in w (2) such that u ∈ Fac(π 1 (v)) and such that if u ∈ Fac(π 1 (v ′ )), then v ∈ Fac(v ′ ). Indeed, given such a factor u, either it contains an occurrence of 00 or of 11 (which uniquely determine how to decompose the factor), or it is equal to π 1 (10101010) or to π 1 (01010101) (neither 101010101, nor 010101010 occur in w (2) ).

Similarly, we see that, for all k ≥ 2, any factor of w (k) of length at least equal to 7 can be uniquely decomposed into π k (0) and π k (1).

Let n be a positive integer (suppose it is large). The sequence (l k ) k≥1 is increasing so there is a unique positive integer k such that l k-1 ≤ n < l k . Consequently, all factors of length n of w π belong to Fac (π 1 • • • π k ({0, 1} 2 )). From what precedes, there is a unique word v in Fac (π k ({0, 1} 2 )) ⊂ Fac w (k) such that u ∈ Fac(π 1 • • • π k-1 (v)) and any word v ′ over {0, 1} such that u ∈ Fac (π 1 • • • π k-1 (v ′ )) contains v as a factor.

By unicity of v, the number of return words to u in w π is at least equal to the number of return words to v in w (k) (some return words could also occur in π 1 • • • π k-1 (v)) so we only have to show that the number of return words to v in w k is at least linear in k. This will prove the result since k increases with n.

First, if |v| ≥ 7, we have seen that there is a unique word x ∈ {0, 1, 00, 01, 10, 11} such that v ∈ Fac(π k (x)) and such that if v ∈ Fac(π k (y)), then x ∈ Fac(y). The number of return words to v in w (k) is at least equal to the number of return words to x in w (k+1) and we let the reader check that it is at least linear in k.

Let us suppose that |v| is less than 7 and that the factor 000 occurs in v (the case 111 ∈ Fac(v) is similar). Then, from the shape of π k , v only occurs in w (k) as factor of π k (1). The number of return words to v in w (k) is then at least equal to the number of return words to 1 in w (k+1) and we let the reader check that it is at least linear in k. Now suppose that neither 000 nor 111 occur in v (still with |v| < 7). Since the number of return words to a factor is the same as the number of return words to the smallest bispecial factor containing it, we only have to count the number of return words to bispecial factors of w (k) that are smaller than 7 and that do not contain 000 neither 111 as factors. We let the reader check that these factors are exactly {0, 1, 00, 01, 10, 11, 010, 101, 0101, 1010, 01010, 01011, 11010, 10101, 010101, 101010} .

The bispecial factors 01010, 10101, 010101 and 101010 only occur in w (k) as factors of π k (01) and π k (01) but are not factor of π k (0) neither of π k (1). Since the number of words filling the gaps between occurrences of 01 and 10 in w (k+1) is linear in k, these bispecial factors have a number of return words which is linear in k too.

We let the reader check that the other bispecial factors have a number of return words in w (k) which is linear in k (each return word containing a different highest power of 0 or of 1 depending on the bispecial factor). This completes the proof.

To end with return words, let us observe that it is possible to build sequences whose complexity is not sub-linear and in which infinitely many factors have a bounded number of return words. Indeed, for instance, the sequence γ ω (0) (see Example 3.5) has a quadratic complexity and any factor γ n (1) admits two return words. After last observation it seems difficult to characterize sequences with a sub-linear complexity using return words. Nevertheless next interesting question is open. Question 3.18. Let w be a sequence such that, for some integer K, all factors of w has at most K return words. Is it true that w is S-adic for some suitable set S and has linear complexity?

What about the number of distinct powers?

As already mentioned, it is known that the factor complexity of k-power-free morphic purely sequences grows at most like n log n. In this section, we explore links between bounding the number of distinct exponents of factors instead of the maximal exponent of factors and the factor complexity.

Let us introduce the following notation: given a language L and a word u = u 1 • • • u |u| ∈ L, Pow(u, L) is the set of all non-negative integers i such that there are some words p and s such that pu i s belongs to L, |p| ≤ |u|, |s| ≤ |u|, p is not a suffix of u and s is not a prefix of u. With the notation of previous section, we have Pow(π 1 • • • π n (0), Fac(w π )) = {3 1 , 3 2 , . . . , 3 n }, which shows the existence of an S-adic sequence with an at most linear complexity that have factors with an unbounded number of distinct exponents.

The previous phenomenon also holds for S-adic sequences that do not have a sub-linear complexity. Indeed this is the case of the S-adic sequence considered in Proposition 3.6 when the sequence (k n ) n∈N is unbounded, as one can observe that

Pow(γ k 0 µγ k 1 µγ k 2 µ • • • γ kn µ(1), Fac(w γ,µ )) = {1, 2, . . . , k n+1 + 2}.
If it seems difficult from previous discussion to get an S-adic characterization of sequences with sub-linear complexity using the number of distinct powers of their factors, next proposition inspired by word w γ,µ shows that the number of distinct powers can be used to prove that a sequence does not have a sub-linear complexity. Recall that a word u is primitive if it is not a power of a smaller word v, i.e., there is no integer k ≥ 2 such that u = v k . Proposition 3.19. Let w be a recurrent sequence over A. If there is a constant C > 1, a sequence (u n ) n∈N of primitive words in Fac(w) and an increasing sequence (k n ) n∈N of positive integers such that (|u n |) n∈N is increasing and such that for all n, all integers i with kn C ≤ i ≤ k n belong to Pow(u n , Fac(w)), then w does not have a sub-linear complexity.

Before proving the result, let us recall the classical following result (see for instance Proposition 3.1.2 in [START_REF] Lothaire | Combinatorics on words[END_REF]). Proposition 3.20. If x and y are two non-empty words such that xy = yx, then there is a word v smaller than x and y such that x = v n and y = v m for some positive integers n and m.

Proof. Let us give a lower bound on the number of factors of length k n |u n | of w. When C is at least equal to 2, the property is also true with 2 -ε instead of C for all ε > 0, thus, without loss of generality, we assume C < 2.

Let n be a positive integer and let i in {0, 1, . . . , k n -kn C }. By hypothesis the word u kn-i n is a factor of w. Let us study the return words to u kn-i n . Since u n is a primitive word, a return word r to u kn-i n is either u n or has length |r| > (k n -i)|u n |. Indeed, if not, one of the following holds true:

1. |r| = j|u n | with 2 ≤ j ≤ k n -i; in this case, we have r = u j n which is not a return word to u n ; 2. |r| < (k n -i)|u n | and |r| is not a multiple of |u n |; in this case, there is a non-empty word u ′ smaller than u n such that u ′ u n = u n u ′ and, by Proposition 3.20, u n is not a primitive word. Now, since k n -i belongs to Pow(u n , Fac(w)) and w is recurrent, there are two words p i and s i such that p i u kn-i

p w (k n |u n |) ≥ 1 + kn-⌈ kn C ⌉ i=1 i|u n | ≥ |u n | C-1 C kn-1 i=1 i ≥ |u n | 2 C -1 C k n C -1 C k n -1
and we deduce that the complexity is not sub-linear.

Example 4.3. Let β be the morphism ϑ :

     0 → 0120 1 → 11 2 → 222
and consider its fixed point w = ϑ ω (a). It can be seen as an expansive {ϑ}-adic sequence and we know from Theorem 2.2 that p w (n) = Θ(n log n).

  then p w (n) ≤ D max σn∈S,a∈A n+1 |σ n (a)|(Card(A)) 2 n with A = ∪ n∈N A n . Corollary 3.2 (Durand [Dur03]). If w is S-adic with Card(S) < ∞ and all morphisms in S are uniform, then we have p w (n) ≤ l(Card(A)) 2 n with A = ∪ n∈N A n and l = max σ∈S,a∈A(σ) |σ(a)|.

Example 3. 5 .

 5 Let µ be the Thue-Morse morphism [01, 10] and let γ be the morphism [001, 1]. From Theorem 2.2 we know that the sequence γ ω (0) = 001001 2 001001 3 001001 2 001001 4 • • • has a quadratic complexity.

0 →

 0 01 e 0 01 e 1 01 e 2 • • • = 2 n-1 -1 i=0 01 e i 0 1 → 10 e 0 10 e 1 10 e 2 • • • = 2 n-1 -1 i=0 10 e i 1 ,where e is the fixed point of the morphism Exp defined over the infinite alphabet{3 n | n ∈ N} by ∀n ∈ N, Exp(3 n ) =13 n+1 , i.e., e = 1313 2 1313 3 1313 2 1313 4 1313 2 1313 3 1313 2 13 • • • . Now let us consider the sequence

n

  s i belongs to Fac(w), |p i | ≤ |u n |, |s i | ≤ |u n | and u n does not admit p i as a suffix neither s i as a prefix. Thus, from what precedes, p i is a suffix of a return word r i to u kn-i n with |r i | > (k n -i)|u n | and such that r i u kn-i n s i is a factor of the recurrent word w.By hypothesis, we have C < 2 and k n -i ≥ kn C so it comes|r i u kn-i n | > 2 k n C |u n | > k n |u n |. Let v i denote the suffix of length k n |u n | of r i u kn-i nand, when i ≥ 1, let x i denote a factor of w of length (k n + i)|u n | that admits v i s i as a prefix. Let also x 0 = u kn n ). For a given wordw = w 1 • • • w |w| , we let w[r : s] denote its factor w r • • • w s-1. By definition of return words, the word u kn-i n occurs only once in v i . Thus all the wordsx i [ℓ : ℓ + k n |u n |], ℓ ∈ {1, 2, . . . , i|u n |}, are different.Let us show that if i and j belong to {1, . . . , k n -kn C }, i < j, then all wordsx i [ℓ : ℓ + k n |u n |], ℓ ∈ {1, 2, . . . , i|u n |} x j [m : m + k n |u n |], m ∈ {1, 2, . . . , j|u n |}are also distinct (by construction they are not equal to x 0 ). Suppose by contrary that there are some integers ℓ ∈ {1, 2, . . . , i|u n |} and m ∈ {1, 2, . . . , j|u n |} such thatx i [ℓ : ℓ + k n |u n |] = x j [m : m + k n |u n |] = X.Since ℓ ≤ i|u n | and m ≤ j|u n |, there are some words α, β, γ and δ such thatX = αu kn-i n β = γu kn-j n δ.We have |α| > |γ| otherwise u kn-j n would occur twice in v j . Let us show that we also have|α| < |γ| + (k n -j)|u n | -|u n |. As k n -i > k n -j ≥ kn C > kn 2 , we have (k n -i)|u n | ≥ (k n -j + 1)|u n | > k n |u n | 2 + |u n |. Thus, if |α| ≥ |γ| + (k n -j)|u n | -|u n |, we have |α| + (k n -i)|u n | ≥ |γ| + (k n -j)|u n | -|u n | + (k n -j + 1)|u n | > |γ| + k n |u n |,which is a contradiction because |αu kn-i β| = k n |u n |. We have just proved that |γ| < |α| < |γ| + (k n -j)|u n | -|u n | = |γu kn-j n | -|u n |. This implies that, if p is the prefix of length (|α| -|γ|) mod |u n | of u n , we have u n p = pu n . Since |α| -|γ| = 0 mod |u n | (otherwise s j would be a prefix of u n ), Proposition 3.20 implies that u n is not primitive, hence a contradiction. Now we can conclude the proof: since all words x i [ℓ : ℓ + k n |u n |], i ∈ {1, . . . , k n -kn C }, ℓ ∈ {1, 2, . . . , i|u n |}, are distinct and different from x 0 , we have

The topology over A N is the classical product topology of the discrete topology over A.

f (n) ∈ Θ(g(n)) if ∃C 1 , C 2 > 0, n 0 ∀n ≥ n 0 |C 1 g(n)| ≤ |f (n)| ≤ |C 2 g(n)|.

f (n) ∈ O(g(n)) if ∃C > 0, n 0 ∀n ≥ n 0 |f (n)| ≤ |Cg(n)|.

f (n) ∼ g(n) if ∀ε > 0 ∃n 0 ∀n > n 0 |f (n)/g(n) -1| < ε.

Beyond linearity

Until now, we have provided several examples showing that various natural approaches to characterize S-adic sequences that have a sub-linear complexity does not appear to be promising. To conclude this paper, we raise a new problem related to S-adicity and, more precisely, to everywhere growing S-adic sequences.

For purely morphic sequences, the complexity function can have only 5 asymptotic behaviours and only depends on the growth rate of images (see Theorem 2.2). For S-adic sequences we have seen in Section 2.2 that things are highly more complicated. However, it has been proved in [START_REF] Ferenczi | Rank and symbolic complexity[END_REF] (see also [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF][START_REF] Leroy | A combinatorial proof of S-adicity for sequences with sub-affine complexity[END_REF]) that any uniformly recurrent sequence with sub-linear complexity is everywhere growing S-adic with Card(S) < +∞. This is a kind of generalization of the third point of Theorem 2.2. Moreover, one can check that all examples considered in previous sections (and more generally all S-adic representations of well-known families of sequences such as codings of rotations, codings of interval exchanges, etc.) are everywhere growing. It is also interesting to note that for purely morphic sequences, the class of highest complexity Θ(n 2 ) can be reached only by morphisms with bounded letters (still Theorem 2.2). Furthermore, up to now, Cassaigne's constructions (Proposition 2.9) are the only ones that allow to build S-adic sequences with arbitrarily high complexity and they admit several bounded letters. Consequently, the fact that the length of all images tends to infinity with n seems to be important to get a reasonably low complexity.

Observe that, given an S-adic sequence w, the everywhere growing property is not a necessary condition for w to have a low complexity. Indeed, Cassaigne's constructions also hold for sequences with low complexity. One can also think to the Chacon substitution ̺ defined by ̺(0) = 0010 and ̺(1) = 1 whose fixed point ̺ ω (0) has complexity p(n) = 2n+1 for all n (see [START_REF] Ferenczi | Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1[END_REF]). However, the existence of an everywhere growing S ′ -adic representation of w could be necessary (this is the case for the Chacon substitution and for any uniformly recurrent sequence with sub-linear complexity).

That property is neither a sufficient condition since the sequence w γ,E of Example 3.5 satisfies it and does not always have a sub-linear complexity. However the following question seems to be natural. Question 4.1. Is it possible to reach any high complexity with everywhere growing S-adic sequences?

This question seems to be a new non-trivial problem. Proposition 4.2 below provides a partial answer to that question. Indeed, it deals with expansive S-adic sequences, i.e., with S-adic sequences such that for all morphisms σ in S and all letters a, we have |σ(a)| ≥ 2. The proof can be found in [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF] and involves techniques similar to those used in [START_REF] Ehrenfeucht | Subword complexities of various classes of deterministic developmental languages without interactions[END_REF] for D0L systems. Example 4.3 shows that this bound is the best one we can obtain.