Thomas Peel

Valentin Emiya

Liva Ralaivola

Sandrine Anthoine

MATCHING PURSUIT WITH STOCHASTIC SELECTION

Keywords: Sparsity, Pursuit Algorithm, Stochastic Procedure

In this paper, we propose a Stochastic Selection strategy that accelerates the atom selection step of Matching Pursuit. This strategy consists of randomly selecting a subset of atoms and a subset of rows in the full dictionary at each step of the Matching Pursuit to obtain a sub-optimal but fast atom selection. We study the performance of the proposed algorithm in terms of approximation accuracy (decrease of the residual norm), of exact-sparse recovery and of audio declipping of real data. Numerical experiments show the relevance of the approach. The proposed Stochastic Selection strategy is presented with Matching Pursuit but applies to any pursuit algorithms provided that their selection step is based on the computation of correlations.

INTRODUCTION

We are interested in estimating the sparse representation x ∈ R K of a signal y ∈ R M in a so-called dictionary Φ ∈ R M ×K such that y ≈ Φx [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF] where M ≤ K, and where the number of non-zero elements x 0 in x is small ( x 0 ≪ M ). The columns of Φ are usually called atoms and x 0 is the sparsity of x.

Retrieving the sparsest representation from an observed signal and a known dictionary is NP-hard. The Matching Pursuit (MP) algorithm and its descendants [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF][START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF][START_REF] Blumensath | Gradient pursuits[END_REF] have been proposed to estimate such a sparse representation. Those greedy algorithms, which essentially iterate over two steps, a selection step and an update step, are known to perform well for exact sparse recovery and sparse approximation [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF].

Computational aspects of greedy algorithms have motivated a few works over the past years. Their goal is not only to propose fast algorithms but also to make it possible to deal with high-dimensional data, e.g. when the dictionary size is so large that it cannot be stored as a matrix in memory.

Accelerating the update stage is useful when high accuracy is targeted. Indeed, performance is better -regarding the decrease of the residual's norm per iteration-with Orthogonal Matching Pursuit (OMP) [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF][START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] than with MP, at the price of a computationallydemanding update stage. This has been thoroughly studied in [START_REF] Blumensath | Gradient pursuits[END_REF]: the authors propose a detailed analysis of the computational complexity of MP and OMP, together with fast implementations of the update stage in OMP; then, their gradient-based pursuit (GP) algorithms use new update stages and achieve better performance than MP with a lower computational cost than OMP.

Accelerating the selection stage consists in avoiding a full and naive matrix-vector product between the dictionary-matrix transpose and the current residual vector. It is particularly useful when a high-dimensional dictionary must be handled. For particular dictionaries, fast transforms [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF] can be used. However, they do not apply in general cases; instead, an approximate selection stage can be performed using an approximate nearest neighbor (ANN) search. An approximate search is motivated and supported by the theoretical study of so-called weak greedy algorithms [START_REF] Temlyakov | Weak greedy algorithms[END_REF][START_REF] Gribonval | Approximate weak greedy algorithms[END_REF], for which good convergence properties are guaranteed using a suboptimal selection [START_REF] Gribonval | On the exponential convergence of matching pursuits in quasi-incoherent dictionaries[END_REF]. ANN search for sparse representations have been developed using random projections in compressed sensing [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF], a tree structure [START_REF] Jost | Tree-based pursuit: Algorithm and properties[END_REF], a locality-sensitive hashing scheme [START_REF] Tjoa | Factorization of overlapping harmonic sounds using approximate matching pursuit[END_REF], or random selections of subsets of atoms [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF]. In this paper, we propose a new approach to accelerate the selection stage using a stochastic principle, generalizing a recent work proposed in [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF].

The main contributions of the paper are: i) a new family of algorithms that are stochastic variants of existing ones (including MP, OMP, GP); ii) numerical evidence of the accuracy -which is comparable to the accuracy of non-stochastic algorithms -and of the decrease in the computational complexity; iii) a discussion on the issues at stake regarding the proposed method, including the relation with compressed sensing and the analysis of the algorithm.

The rest of the paper is organized as follows. In Section 2, we motivate and present our Stochastic Selection procedure. Section 3 contains numerical experiments that show the relevance of our approach. This work leads to several theoretical questions discussed in Section 4.

ALGORITHM

Notations

Let y be a discrete signal living in R M ; y is a (possibly) noisy observation of a signal Φx sparsely coded in the dictionary Φ. By this, we mean that we consider the model y = Φx + n, where:

• Φ ∈ R M ×K is a dictionary composed by K atoms : Φ = [ϕ 1 . . . ϕ K ]
. Each ϕ j is in R M and has a unit l2-norm.

• x ∈ R K is sparse, its support is of length x 0 = K0.

• n ∈ R M denotes the noise in the measurements.

Note that we will also consider the non-noisy case y = Φx where y is exactly K0-sparse.

In this paper, we will randomly select m rows and k columns of the dictionary. Accordingly, M = {i1, . . . , im} denotes the set of selected rows and K = {j1, . . . , j k } the set of selected columns (i.e. atoms) of the dictionary. We denote by yM ∈ R M the restriction of the vector y to the coordinates indexed by M.

Motivations

Matching Pursuit [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF] is a greedy algorithm developed in the 90's that aims at approximately solving the NP-hard problem of finding the sparsest decomposition of the signal y with respect to the dictionary Φ. As depicted in Algorithm 1, Matching Pursuit computes an approximate solution to the problem arg min

x∈R K x 0 s.t. y -Φx 2 ≤ ǫ, (2)
where ǫ ≥ 0; ǫ = 0 in the exact sparse case and ǫ > 0 in the noisy case. Matching Pursuit is an iterative procedure that improves the estimation of the sparse coefficients vector x in a greedy fashion. At step t, the current coefficient vector x t yields the approximation Φx t of y. We call r t = y-Φx t the residual. At this step, Matching Pursuit selects the best atom that may be picked, i.e. the atom ϕ γ t+1 that minimizes the norm of the residual at the next step:

ϕ γ t+1 = arg min ϕ∈{ϕ 1 ,...,ϕ K } r t -r t , ϕ ϕ 2 .
The coefficients vector x t+1 and residual r t+1 are updated accordingly and one continues until a stopping criterion is met (see Algorithm 1 for the details). The usual criteria are to stop either when a predefined maximal number of iterations is reached (t = T ) or when the norm of the residual is below a predefined precision ( r t 2 ≤ ǫ).

Algorithm 1 Matching Pursuit

inputs: Φ ∈ R M ×K , y ∈ R M . outputs: x ∈ R K . initialization: x ← 0, r ← y. repeat Selection : j = arg max j∈{1,..,K} | < ϕ j , r > | Update : x j = x j + < ϕ j , r > r = r-< ϕ j , r > ϕ j until a stopping criterion is met.
Note that unless the dictionary has a particular structure, the complexity of the Matching Pursuit algorithm lies in the selection step, and more precisely the computation of the inner products | ϕ j , r |. Indeed, this step involves computing K inner products of signals of length M , which takes O(M K) operations, and sort them to extract the index of the selected atom (O(log K)), while the update step takes O(M ) operations.

To speed up Matching Pursuit, people have essentially focused on three directions. First, when the dictionary has a particular structure, for example when it corresponds to a fast transform such as a Gabor transform, the computation complexity of the dot products decreases from O(M K) to O(K log M ), and it makes sense to take advantage of such properties of the dictionary. However, in the general case, it might well be the case that the redundant dictionary at stake does not have such properties and it is necessary to envision other acceleration strategies. To this end, a second route has been to focus on the effectiveness of the update step: once the atom has been selected, the goal is to implement an update step such that the norm of the residual decreases faster than in the case of Matching Pursuit. This is the purpose of the Orthogonal Matching Pursuit algorithm (which was proposed along with Matching Pursuit), as well as many others. These updates are more effective to decrease the norm of the residual, i.e. the magnitude of the decrease induced by such updates is larger than that induced the Matching Pursuit update, while the cost of the refined update usually dominates that of the computations of the inner products. A third direction focuses on reducing the complexity of the selection step, while keeping the simple and efficient update step of Matching Pursuit. This is the strategy undertaken by [START_REF] Temlyakov | Weak greedy algorithms[END_REF][START_REF] Gribonval | Approximate weak greedy algorithms[END_REF][START_REF] Gribonval | On the exponential convergence of matching pursuits in quasi-incoherent dictionaries[END_REF][START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Jost | Tree-based pursuit: Algorithm and properties[END_REF][START_REF] Tjoa | Factorization of overlapping harmonic sounds using approximate matching pursuit[END_REF][START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF], and this is the strategy that we build our algorithm upon.

Note that we make no assumption on the properties of the dictionary at hand and our goal is to keep every step of this modified Matching Pursuit to a very low complexity, so that the computation of each iteration is fast. As we shall see, we propose an approximate selection step, which may result in sub-optimal selections of atoms. Our modified algorithm thus may be less efficient than Matching Pursuit in terms of the residual norm decrease per iteration. However, a gain in computation time per iteration, resulting in an overall faster algorithm, may be hoped for.

Before stating the algorithm, we want to stress out that although our Stochastic Selection procedure is here proposed in the framework of MP, it obviously carries over any other Pursuits algorithm with a selection step based on the computation of inner products, such as Orthogonal Matching Pursuit, Gradient Pursuits and so on.

Matching Pursuit with a stochastic selection

Our Matching Pursuit with a Stochastic Selection differs from the classical Matching Pursuit only in the selection step. The Stochastic Selection we propose here reduces the cost of the scalar products computations by proceeding to two dimension reductions:

1. Stochastic column selection. We consider only a sub-dictionary of Φ consisting of k atoms chosen uniformly at random among the K original ones. 2. Stochastic row selection. We consider an approximation of each scalar product ϕ j , r at stake using only m coordinates of the signals chosen uniformly at random among {1, .., M }. We select the atom in the sub-dictionary yielding the approximate scalar product with the current residual with the largest amplitude. The update step is exactly the same as in MP: once an atom ϕ j is selected we use the exact scalar product ϕ j , r to update the coefficients vector and the residual. The stopping criteria remain the same as in MP. The algorithm is described in details in Algorithm 2.

The algorithm proposed in [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF] is a particular case of our algorithm where only a subset of columns is randomly selected. When using only random subset of the atoms in Φ, one can not ensure to pick the best atom, however, one hopes to find one of the atoms involved in the representation of y. We add here the coordinate selection which implies that we do not at first have access to the correct values of the scalar products even for the selected sub-dictionary. Drawing a new random sub-dictionary and a new random set of coordinates at each iteration however allows us to explore all coordinates and all atoms, thus recover an accurate representation of y.

The selection step of Algorithm 2 takes O(mk) operations instead of the O(M K) operations needed in MP. The gain in computation time is thus of order M K/mk. This gain is to be balanced with Algorithm 2 Matching Pursuit with Stochastic Selection

inputs: Φ ∈ R M ×K , y ∈ R M , m ∈ {1, .., M }, k ∈ {1, .., K}. outputs: x ∈ R K . initialization: x ← 0, r ← y. repeat
Randomly pick a set M of m row indexes. Randomly pick a set K of k column indexes. Selection : j = arg max j∈K | < ϕ j M , rM > | Update : x j = x j + < ϕ j , r > r = r-< ϕ j , r > ϕ j until a stopping criterion is met.

the loss of accuracy due to the sub-optimality of the chosen atoms. We show in the numerical experiments section (Section 3) that overall, this Stochastic Selection procedure allows for faster computations time than MP.

NUMERICAL EXPERIMENTS

In this section, we present the results of numerical experiments in order to validate our approach. In a first experiment, we generate a random overcomplete dictionary and study the accuracy of our algorithm in terms of the residual energy decrease as a function of iterations and time. We compare our Matching Pursuit with Stochastic Selection approach (MP-S) to the standard Matching Pursuit (MP) algorithm. We then use a DCT dictionary in order to validate the capacity of the MP-S approach to recover the support of a signal (exact sparse recovery problem). Declipping of real audio data is performed in a third experiment using the stochastic selection in OMP.

Data generation

In the two following subsections, we use signals of length M = 128 and two types of dictionaries. We generate on the one hand random dictionaries Φ ∈ R M ×K : each entry is an i.i.d random variable drawn from a standard Gaussian distribution and normalized to have unit l2-norm atoms. On the other hand, we use standard DCT IV dictionaries. In sections 3.2 and 3.3he vector x is a K0-sparse vector where each nonzero entry is an i.i.d Gaussian random variable.

Residual energy decrease

In this experiment, we measure the energy of the residual as a function of the iterations of the algorithm and also as a function of runtime of the selection stage. We compare our approach with standard Matching Pursuit and a variant we called MP-S0 of our Matching Pursuit with Stochastic Selection approach. In this variant, a subdictionary is extracted at the beginning of the procedure (picking uniformly at random row and column subsets from the entire dictionary). The specificity lies in the fact that we use only this fixed sub-dictionary to identify the best atom at each iteration. Once an atom is selected, we do the same updates as in Algorithm 1 and 2 (i.e. using the entire information contained in the atom selected). This variant, which has the same runtime complexity as MP-S, plays the role of a baseline to demonstrate the usefulness of renewing at each iteration the subsets used for the selection step.

For the MP-S procedure, we denote by µ (resp. κ) the ratio m/M (resp. k/K). We ran experiments with a large set of configurations (µ, κ ∈ [0.2, 1.0]). Large values of these parameters imply a decrease per iteration close to MP while the gain in runtime is low. Small values imply a less efficient decrease per iteration but in general a larger gain in runtime of the algorithm. We only report in Figures 1 and 2 the results for the case µ × κ = 0.36 and K = 512. We used three configurations of MP-S with equal computational complexity: one with every atoms and a subset of dimensions of size m = 0.36 × M , one with every dimensions and only k = 0.36 × K atoms and the last one with µ = κ = √ µ × κ. Finally, for each experiment we average the performance of the Matching Pursuit with Stochastic Selection procedure over 20 runs.

The first result we want to emphasize here is the failure of the MP-S0 approach and, accordingly, the gain induced by our stochastic procedure. Clearly, MP-S0 is only able to decrease the residual energy in the first iterations and quickly reaches an asymptote. On the contrary, with the same runtime complexity, MP-S takes advantage of renewing the subsets at each iteration and does not suffer this lack of information.

Figure 1 shows the results of the experiment for a support of size K0 = 32. As one can see, with MP-S, the residual energy does not decrease as much as with MP at each iteration (top). This behavior can easily be explained because MP-S does not always find the best correlated atom at each iteration. However, since iterations of MP-S involve fewer operations than in MP, the residual energy decreases faster (in term of runtime) with MP-S (bottom). We can notice that MP-S outperforms MP whatever the configuration used, with an advantage for the setting µ = 1 and κ = 0.36 which performs the selection with the real dot products of a subset of atoms. In this configuration, a 120 dB decrease of the residual energy is reached more than twice faster than with MP. This improvement comes from the fact that we only do 36% of the calculations that MP does. Note that this is precisely the setting used in [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF].

The behavior is quite different in Figure 2. Here, we are in a case where the support is very sparse since K0 = 2. In this setting, the version of MP-S using every atom but looking only at 36% of the coordinates is the only one that beats MP. Surprisingly, computing the dot product with only 36% of the information seems to be sufficient to find, at each iteration, an atom as good as the one selected by MP. Moreover, MP-S seems to act exactly the same manner as MP in this setting and reaches again the same performance as MP more than twice faster. Here, the approach of [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF] (µ = 1 and κ = 0.36) experiences difficulties to decrease the residual energy. This configuration seems to be too sensitive to the fact that atoms of the support may often not be selected as candidates. The same behavior appears with the last configuration (µ = κ = 0.6).

Exact support recovery

In this section, we evaluate the capacity of our approach to recover the support of a signal and compare it to the standard Matching Pursuit approach. We only look at the exact sparse recovery problem i.e. we assume there is no noise: y = Φx. We use a DCT dictionary. Phase-transition diagrams are drawn in a standard way. The performance criterion is the normalized correlation between original and estimated vectors of coefficients. We consider that the support is recovered if this correlation is above 99%. We have run experiments for various configurations and plot the recovery success as a function of the redundancy δ = M/K and the sparsity ρ = K0/M . For each couple (δ, ρ), we ran the experiment 50 times and stop the procedure before adding the (K0 + 1)-th nonzero entry to the estimated vector of coefficients.

Figure 3 shows the phase-transition diagrams for various values of µ × κ. Recovery is displayed from white (recovery success for all 50 runs) to black (failure for all of them). Here, we do not tweak the parameters and only use the median configuration where µ = κ. First, the difference is very slight between MP and MP-S, when µ × κ = 0.81 (see (a) and (b)) i.e. with subsets of rows and columns close to the ones considered by MP. Second, as one decreases the size of the randomly selected subsets, one can notice that the redundancy of the dictionary seems to be a crucial parameter (see (c) and (d)). A theoretical analysis of the algorithm would be needed here to explain this sensitivity.

Audio declipping application

In order to assess the performance on real data, we have used the stochastic selection in OMP for audio declipping. We have reproduced the declipping experiments on speech sampled at 8kHz proposed in [START_REF] Adler | Audio inpainting[END_REF] using the code released by the authors. The exact same experimental conditions have been used and are not reported here due to space issues. We used the original OMP and its declipping version (see [START_REF] Adler | Audio inpainting[END_REF]). Their variants with stochastic selection have been used for µ = κ = 0.8 and µ = κ = 0.6.

Signal-to-noise ratio (SNR) performance is reported in Table 1 together with measured time complexity. Here, we measure the total time needed by the declipping algorithm (not the time for atom selections only). We observe a very low performance decrease but a significant time saving when using stochastic selections. As a consequence, we see that 1/ the proposed method can deal with real, noisy data; 2/ stochastic selection can be used with OMP; 3/ even with OMP, time saving is significant; and 4/ as SNR is computed on missing data, we measure a quantity that is akin to a generalization performance, as encountered in machine learning, while previous experiments assess the approximation and recovery performance.

DISCUSSION AND OUTLOOKS

In the present paper, we have proposed a stochastic sampling strategy to accelerate the atom selection step of Matching Pursuit. At each iteration, our approach consists in randomly selecting a set of rows and columns from the dictionary. The set of columns corresponds to the candidate atoms that will be considered for their addition in the signal representation. This means that instead of scanning through all available atoms, we propose to restrain the search to few stochastically selected atoms as in [START_REF] Moussallam | Matching pursuits with random sequential subdictionaries[END_REF]. We generalize this approach with an additional feature: in lieu of computing the correlations between the selected set of atoms and the current residual, we use an estimate of the correlations based on a stochastic downsampling of the atoms and of the residual. In essence, the procedure that we propose performs a random selection of columns and a random selection of rows from the dictionary and only uses the reduced dictionary to perform the selection step. Several numerical simulations illustrate the relevance of our approach both in terms of CPU time gained with respect to classical MP and in terms of the quality of the computed solution. We observe a very advantageous tradeoff between a limited performance decrease and a large time complexity reduction. Our approach raises a number of questions, which we plan to investigate in the near future.

First -more of an observation than a question-it is important to understand the wild applicability of our approach: even though we have presented it in the context of Matching Pursuit, it obviously

Fig. 1 .

 1 Fig. 1. Residual energy decrease (random dictionary, K0 = 32).

Fig. 2 .

 2 Fig. 2. Residual energy decrease (random dictionary, K0 = 2).

This work is partially supported by the French GIP ANR under contracts ANR-10-CORD-0003 Mtaphores Sonores-METASON and ANR Greediness: theory and algorithms-GRETA.

Table 1. Audio declipping performance (SNR in dB) for several clipping levels (rows) and for several algorithms (columns): OMP, declipping OMP (d-OMP) and their variants with stochastic selection (OMP-S * , d-OMP-S * ). Last row: average time for processing a sound. applies to many kinds of pursuit algorithms provided that their selection step is based on the computation of correlations. Second, there is the pressing question of bringing theoretical support to our algorithm. Fueled by the very positive empirical results presented here, we are now to devote our efforts to this aspect of our study. Among the questions that we want to address are the following. Is it possible to state conditions on the dictionary, such as coherence-related conditions, that guarantee i) the convergence of our algorithm and its connections to some form of weak-Matching Pursuit procedures, ii) the exponential decrease of the norm of the residual and iii) the retrieval of atoms that are indeed in the support of the signal considered (in case of exact-sparse recovery) ? Is it possible to devise non-uniform selection strategies that would accelerate even more? Answering these questions would require us to formally show that, in addition to (memory) space-related matters, there is a gain (or at least, no loss) in resampling different sets of coordinates at each iteration compared to sampling a random set of coordinates beforehand (as in MP-S0).

Third, we are naturally brought to the question of the connections between our work and the contributions making use of random projections to reduce the sizes of the vectors and matrices they are based on. Randomly selecting coordinates (i.e. rows) of atoms might indeed be viewed as performing a random projection, and viewed this way, the uniform random selection strategy induces certain properties on the corresponding projections (regarding the orthogonality of the projection space): those have to be clearly stated. Down the road, it also leads us to compare our approach with compressed sensing-based Matching Pursuit [START_REF] Needell | Cosamp: Iterative signal recovery from incomplete and inaccurate samples[END_REF]. A critical difference is again how the random projections are computed: at each iteration for our procedure, and once for all in the latter approach.


Erwan Le

Merrer Technicolor

Gilles Trédan

Towards dynamic graph analysis: a p osition note

In this note, we elaborate on directions for efficient graph analysis, taking into account the dynamic nature of complex networks.

Introduction and problematic

Tailored network analysis is at the core of some of the most successful Internet stories, as Google search engine for instance [START_REF] Franceschet | Pagerank: standing on the shoulders of giants[END_REF]. Understanding complex networks is a challenge that receives a growing interest. Interestingly, this challenge is tackled not only by computer scientists, but also by biologists and physicists. Together, these efforts led to the definition of several important methodological tools to extract information from a complex network, such as centralities, sampling, or scale-free property analysis.

However, most of these tools have been defined in a static way, by only providing insights on crawled networks, at some fixed point in time [START_REF] Kermarrec | Second order centrality: Distributed assessment of nodes criticity in complex networks[END_REF]. This is notably counter intuitive, as the complex networks observed are by nature evolving constantly [START_REF] Leskovec | Graphs over time: densification laws, shrinking diameters and possible explanations[END_REF]; predictions are doomed to be inaccurate.

At the same time, researchers started to develop models that capture graphs over time. For instance the concept time varying graphs (TVGs) [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] which has been recently recognized as a suitable model to describe the evolution of a network in time, pushed by the development of delay-tolerant and opportunistic networks. The TVG model may then constitutes the next step of understanding complex networks, observing them on a dynamic time dimension.

Adapting the aforementioned static tools to TVGs may seem easy. A trivial solution is to simply take snapshots of the network at fixed intervals in time, and to run the analytical computation on each of these snapshots. This is of course cumbersome if the time interval is small, and even simply not computationally feasible if the observed network is large; this prohibits online use by number of resources limited devices or applications for instance.

Since the scale of each snapshot already forbids the use of expensive algorithms, it is clear to us that analyzing TVGs calls for developing methods to reduce the size of the input dataset 1 . The question we ask in this note is then the following one: "How to reduce the computational/memory costs when analyzing TVGs?".

Possible directions

We foresee 4 directions to reduce the global cost in computing characteristics of TVGs: i) observe a subset of relevant nodes over time, ii) concentrate on a subset of relevant snapshots, iii) observe the evolution over time of a set of graph measures and iv) develop/adapt graph measures to TVGs. We will hereafter briefly detail each approach.

Sample nodes Sampling has been extensively studied and provides accurate results in static contexts. This is probably a very efficient approach to gather the evolution of aggregate values, such as the evolution of the average age of social network users. However unbiased sampling is difficult, and adding the time dimension complexifies the problem.

The question of newcomers is pending: should we only sample nodes originally selected at random? Moreover, such an approach can not answer questions regarding the evolution of the graph structure itself.

Sample snapshots

Here, the objective is to reduce the analysis complexity by discarding snapshots that bring little information to concentrate on those conveying more meaning. However, selecting which snapshot is relevant to keep is a non trivial task.

The difficulty is precisely tied to the arbitrarily set interval at with a snapshot should be kept for analysis. If a snapshot is created at each topological change, i.e. appearance/disappearance of a node or edge (called graph centric evolution in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]), then the sampling rate of those snapshots should be related to their creation. It might as well be of a real interest to sample more snapshots when topological changes occur in the core of the network (or on nodes or edges that have been previously marked as important), than when events occur at the fringe.

Evolution of graph measures

The approach here is to run standard static graph analysis tools on each snapshot independently, and to interpret the obtained time serie. Reusing the static graph analysis toolbox is probably a very good starting strategy. Similarly to node sampling, this strategy has the drawback of only studying the evolution of static graph properties.

Keeping only an history of past analysis concerning a network may drastically reduce memory needed to track evolution in time, when compared to the snapshot-based approach. Starting from an initial network analysis, algorithms are providing outputs that are compared to previously observed results (one can for instance keep track of network diameter [START_REF] Leskovec | Graphs over time: densification laws, shrinking diameters and possible explanations[END_REF]). Only one network snapshot is then required in memory, for each evolution analysis, as compared to an array of snapshots as in the previous solution. The negative side being of course the loss of information when only conserving past measures instead of full network snapshots.

Adapted analytical tools

The approach here is to develop new algorithms suited to TVGs and their natural information redundancy. For instance, in many social networks, such as the co-authorship graph in DBLP, links are never removed. Each snapshot is thus a subset of the following one.

Recycling the results of previous snapshots to empower the current snapshot analysis could then lead to significant optimizations.

There is probably no generic solution for transforming static algorithms into their dynamicityaware counterparts. For most of known tools for graph analysis, even the slightest update of the initial graph might have unpredictable consequence on the algorithm.

Most of all, we believe that some very important TVG metrics are only definable in a dynamic context. Even very simple but interesting questions such as "how long does a link takes to be reciprocal, for a triangle to be closed?" can not be addressed by simply adapting our static toolbox to a dynamic setup.

When collecting data from evolving structures, researchers are often bound to the limitations of the API or available datasets. Thus, it is also important to think about the robustness of these complexity reduction techniques against incomplete datasets. For instance, time sampling is sometimes not under control because of crawling time and delays. It is sometimes hard to ensure the full graph is collected. Moreover, crawling times might lead us to question the association of one snapshot to one point in time.

We however believe that each of these directions could be valuable to be explored. It is still unclear which methods are above the others while considering costs, but probably all of them lead to the observation of different interesting phenomena. We yet have to understand their respective relevance to specific contexts.

Google+ graph has now more than 40e6u s e r s . A tt h et i m eo ft h i sw r i t i n g ,i t sm o s tf a m o u su s e rr e c e i v e sm o r et h a n 3000 followers each day.


Fabien Durand

DECIDABILITY OF UNIFORM RECURRENCE OF MORPHIC SEQUENCES

We prove that the uniform recurrence of morphic sequences is decidable. For this we show that the number of derived sequences of uniformly recurrent morphic sequences is bounded. As a corollary we obtain that uniformly recurrent morphic sequences are primitive substitutive sequences.

Introduction

In this paper we answer a question raised in [Nicolas and Pritykin 2009]. We prove the decidability of the following problem:

Input: Two finite alphabets A and B, an endomorphism σ : A * → A * prolongable on the letter a, a morphism φ : A * → B * . Question: Is φ(σ ∞ (a)) uniformly recurrent? Thus, the main result of the paper is the following.

Theorem 1. The uniform recurrence of morphic sequences is decidable.

During the writing process of this work, I. Mitrofanov put on arxiv another solution of this problem [Mitrofanov preprint 2011b]. Observe that Mitrofanov in [Mitrofanov preprint 2011a] and Durand in [Durand preprint 2011] also recently solved the HD0L ultimate periodicity problem. The proofs of Mitrofanov and Durand find their main arguments in [Kanel-Belov and Mitrofanov preprint 2011] and [Durand 1998], respectively. It seems (the first article is written in Russian) that these two articles share some common features that would be very interesting to understand. To prove the decidability of uniform recurrence for morphic sequences we proceed as in [Durand 2012] and [Durand preprint 2011], that is, we use the main result of [Durand 1998] that we extend to our setting.

Theorem 2. Let x be a uniformly recurrent sequence defined on a finite alphabet. Then, it is a morphic sequence if and only if the set of its derived sequences (on prefixes of x) is finite.

In fact we prove more giving effective bounds. As a consequence this shows that uniformly recurrent morphic sequences are primitive substitutive sequences.

Theorem 3. Uniformly recurrent morphic sequences are primitive substitutive sequences.

As we use derived sequences, we also use return words. Because we have to deal with some non necessarily uniformly recurrent sequences we need to introduce a notion of return words to sets of words. This paper is composed as follows. In Section 2 we recall some definitions and wellknown facts. Moreover, we introduce return words to sets of words and give some first properties. This construction is fundamental for our decidability algorithm. In Section 3 we prove Theorem 2 giving explicit bounds concerning this notion of return words in the context of morphic sequences. It is these bounds that make our problem decidable. In Section 4 we show the main result of this paper: Theorem 1. We end with Section 5 where Theorem 3 is proven and Theorem 2 is extended to descendant sequences (see [Holton and Zamboni 1999]). These results are interpreted in terms of dynamical systems, few words are given on the algorithmical complexity, and we add open decidability problems for morphic sequences to the list given in [Nicolas and Pritykin 2009].

2. Some background 2.1. Words and sequences. An alphabet A is a finite set of elements called letters. A word over A is an element of the free monoid generated by A, denoted by A * . Let x = x 0 x 1 • • • x n-1 (with x i ∈ A, 0 ≤ i ≤ n -1) be a word, its length is n and is denoted by |x|. The empty word is denoted by ǫ, |ǫ| = 0. The set of nonempty words over A is denoted by A + . The elements of A N are called sequences. If x = x 0 x 1 • • • is a sequence (with x i ∈ A, i ∈ N) and I = [k, l] an interval of N we set x I = x k x k+1 • • • x l and we say that x I is a factor of x. If k = 0, we say that x I is a prefix of x. The set of factors of length n of x is written L n (x) and the set of factors of x, or the language of x, is denoted by L(x). We set p x (n) = #L n (x). It is the word complexity (function) of x. The occurrences in x of a word u are the integers i such that x [i,i+|u|-1] = u. If u has an occurrence in x, we also say that u appears in x. When x is a word, we use the same terminology with similar definitions. The sequence x is ultimately periodic if there exist a word u and a non-empty word v such that x = uv ∞ , where v ∞ = vvv • • • . In this case |v| is called a length period of x. It is periodic if u is the empty word. A word u is recurrent in x if it appears in x infinitely many times. A sequence x is uniformly recurrent if every factor u of x appears infinitely often in x and the greatest difference of two successive occurrences of u is bounded. In the sequel A and B will always be finite alphabets.

Morphisms and matrices.

Let σ be a morphism from A * to B * . When σ(A) = B, we say σ is a coding. Thus, codings are onto. If σ(A) is included in B + , it induces by concatenation a map from A N to B N . These two maps are also called σ. To the morphism σ is naturally associated the matrix M σ = (m i,j ) i∈B,j∈A where m i,j is the number of occurrences of i in the word σ(j). We set |σ| = max a∈A |σ(a)| and σ = min a∈A |σ(a)|.

Morphic and substitutive sequences.

In the sequel we use the definition of substitution that is in [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]] and the notion of substitutive sequence defined in [Durand 1998]. Both are restrictive. For non restrictive context we will speak of (prolongable) endomorphisms and (purely) morphic sequences. The language of the endomorphism σ : A * → A * is the set L(σ) of words appearing in some σ n (a), a ∈ A. The number of words of length n in L(σ) is denoted by p σ (n).

If there exist a letter a ∈ A and a word u ∈ A + such that σ(a) = au and moreover, if lim n→+∞ |σ n (a)| = +∞, then σ is said to be prolongable on a. It is a substitution whenever it is prolongable and growing (that is, lim n σ n = +∞). Since for all n ∈ N, σ n (a) is a prefix of σ n+1 (a) and because |σ n (a)| tends to infinity with n, the sequence (σ n (aaa • • • )) n≥0 converges (for the usual product topology on A N ) to a sequence denoted by σ ∞ (a). The endomorphism σ being continuous for the product topology, σ ∞ (a) is a fixed point of σ: σ(σ ∞ (a)) = σ ∞ (a). A sequence obtained in this way by iterating a prolongable endomorphism is said to be purely morphic (w.r.t. σ) or purely substitutive when σ is a substitution. If x ∈ A N is purely morphic and φ : A * → B * is a morphism then the sequence y = φ(x) is said to be a morphic sequence (w.r.t. σ). When φ is a coding and σ a substitution, we say y is substitutive (w.r.t. σ). Whenever the matrix associated to σ is primitive (i.e., when it has a power with strictly positive coefficients) we say that σ is a primitive endomorphism. In this situation we easily check that L(σ) = L(σ ∞ (a)). A sequence is primitive substitutive if it is substitutive w.r.t. a primitive substitution. We say σ is erasing if there exists b ∈ A such that σ(b) is the empty word. Such a letter is called an erasing letter.

Iterated matrices.

For the sequel we need the following well-known results on iterated matrices.

Lemma 4. [Horn and Johnson 1990] If M is a primitive d × d matrix then there exists k ≤ d 2 -2d + 2 such that M k has strictly positive entries.

>From Lemma 4, Section 4.4 and Section 4.5 in [START_REF] Lind | [END_REF] we deduce following proposition.

Proposition 5. Let σ : A * → A * be an endomorphism. Then, there exist three positive integers r σ , q and l, where q ≤ l -1, and a partition

{A i |1 ≤ i ≤ l} of A such that M rσ σ =               A 1 A 2 • • • A q A q+1 A q+2 • • • A l A 1 M 1 0 • • • 0 0 0 • • • 0 A 2 M 1,2 M 2 • • • 0 0 0 • • • 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . A q M 1,q M 2,q • • • M q 0 0 • • • 0 A q+1 M 1,q+1 M 2,q+1 • • • M q,q+1 M q+1 0 • • • 0 A q+2 M 1,q+2 M 2,q+2 • • • M q,q+2 0 M q+2 • • • 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . A l M 1,l M 2,l • • • M q,l 0 0 • • • M l               ,
where the matrices M i have only positive entries or are equal to zero. Moreover, the partition and r σ can be algorithmically computed.

Using the terminology of the previous proposition we will say that M σ has l primitive components. When the substitution σ is primitive and defined on an alphabet with d letters, we get q = l = 1 and r σ = d 2 -2d + 2 (Lemma 4).

In order to introduce the next definition, we need the following well-known result.

Proposition 6. Let σ : A * → A * be a non-erasing endomorphism. There exists a computable integer p such that for τ = σ p and for all b ∈ A, there exist θ

(b) ≥ 1, d(b) ∈ N and c(b) ∈ R such that lim n→+∞ |τ n (b)| c(b) n d(b) θ(b) n = 1.
Moreover, for all b ∈ A and all integers d ′ ∈ [0, d(b)] there exists a letter b ′ , appearing in some σ k (b), such that lim n→+∞

|τ n (b ′ )| c(b ′ ) n d ′ θ(b ′ ) n = 1, i.e., d(b ′ ) = d ′ .
Proof. A proof can be found in [Durand and Rigo 2009] except that it is not indicated that p is computable. But from this proof it is clear that p can be chosen to be r σ (Proposition 5). This justifies the following definitions. a) θ(a) n = 1, for some constant c(a), then we say (d(a), θ(a)) is the growth type of a (w.r.t. σ), and, θ(a) is called the growth rate of a (w.r.t. σ). When the growth type of all the letters of a word w exists, we say that the growth type of w is the maximal growth type of its letters. If (d, θ) and (e, β) are two growth types we say that (d, θ) is less than (e, β) (or (d, θ) < (e, β)) whenever θ < β or, θ = β and d < e.

We say that a ∈ A is a growing letter if lim n→+∞ |σ n (a)| = +∞. Now suppose that all letters define a growth type. Notice that, taking a (computable) power a σ if needed, this is always possible (Proposition 6). We set α := max{θ(a) | a ∈ A}, D := max{d(a) | a ∈ A, θ(a) = α} and A max := {a ∈ A | θ(a) = α, d(a) = D}. We will say that the letters of A max are of maximal growth, (D, α) is the growth type of σ and α is the growth rate of σ. Observe that if α = 1, then in view of the last part of Proposition 6, there exists at least one non-growing letter (of growth type (0, 1)). Otherwise stated, if a letter has a polynomially bounded growth, then there exists at least one non-growing letter. Consequently σ is growing (i.e., all its letters are growing) if and only if θ(a) > 1 for all a ∈ A. We observe that for all k ≥ 1, the growth type of σ k is (D, α k ).

2.5. Return words. Let y ∈ A N and U be a finite set of words in L(y). We call return word to U any word

y [i,j-1] = y i y i+1 • • • y j-1 , where
(1) i is an occurrence of some word of U in y;

(2) j is an occurrence of some word of U in y;

(3) there is no other occurrence between i and j of any word in U . The set of return words to U is denoted by R y,U . When U consists of a single word then we recover the classical notion of return words (see [Durand 1996, Ferenczi, Mauduit, and Nogueira 1996, Durand 1998]). If y is uniformly recurrent then the set of return words to u is finite. For classical return words, we enumerate the elements of R y,U in the order of their first appearance in y. Here we should precise how we will proceed because it could happen that a return word is followed, for different occurrences, by different words of U . Thus in some sense this return word represents two different return words (because it returns to two different elements of U ). We set

Ry,U = {(w, u)|wu ∈ L(y), w ∈ R y,U , u ∈ U }.
We enumerate the elements (w, u) in Ry,U (resp. w ∈ R y,U ) in the order of the first appearance of wu in y (resp. of w in y). This defines a bijective map Θy,U : Ry,U → Ry,U (resp. Θ y,U : R y,U → R y,U )

where Ry,U = {1, 2, . . . } and # Ry,U = # Ry,U (resp. R y,U = {1, 2 . . . } and #R y,U = #R y,U ). The word Θy,U (i) = (w, u) is such that wu is the i-th such word occurring in y and Θ y,U (i) is the i-th return word to U occurring in y. Let δ U : R * y,U → A * be defined by δ U (w, u) = w.

Proposition 8. Suppose y ∈ A N has infinitely many occurrences of elements of U and has a prefix belonging to U . Then, (1) There exists a unique sequence

∆ U (y) = (w n , u n ) n ∈ RN y,U such that the word w 0 w 1 • • • w n u n is a prefix of y;
(2) There exists a unique sequence DU (y) ∈ RN y,U satisfying Θy,U ( DU (y)) = ∆ U (y);

(3) There exists a unique sequence

D U (y) ∈ R N y,U satisfying Θ y,U (D U (y)) = y; (4) δ U Θy,U ( DU (y)) = y.
Proof. The proof is left to the reader.

The case where y does not have any prefix in U is treated in the proof of Theorem 38. The sequence DU (y) is called the induced sequence on U of y and D U (y) is called the derived sequence on U of y. Observe that if y is uniformly recurrent then these sequences are also uniformly recurrent. When U = {u} we set (and we get)

δ u = δ U , R y,u = Ry,U = R y,U and D u (y) = DU (y) = D U (y).
Let y be uniformly recurrent and u a prefix of y. Then R y,u is finite. When u is the first letter of y, that is u = y 0 , then we set D(y) = D u (y) and D n (y) = D(D n-1 (y)) for all n ≥ 1.

Bounds for substitutions and derived sequences

For the purpose of this paper we need to generalize the results in [Durand 1998] (dealing with primitive substitution sequences) to uniformly recurrent morphic sequences.

3.1. Derived sequences. Here we recall some known properties of uniformly recurrent sequences and primitive substitutive sequences.

Proposition 9 ( [Durand 1998]). Let x be a uniformly recurrent sequence and u a non-empty prefix of x.

(1) The set R x,u is a code, i.e., Θ x,u : R *

x,u → Θ x,u (R * x,u ) is one-to-one. (2) If u and v are two prefixes of x such that u is a prefix of v then each return word to v belongs to Θ x,u (R * x,u ), i.e.
, it is a concatenation of return words to u.

(3) Let v be a non-empty prefix of D u (x) and w

= Θ x,u (v)u. Then • w is a prefix x, • Θ x,u Θ Du(x),v = Θ x,w and • D v (D u (x)) = D w (x).
Corollary 10. Let x ∈ A N be uniformly recurrent. For all n ≥ 1 there exists a prefix u n of x such that

D n (x) = D un (x) and u n+1 = Θ x,un (1)u n .
Corollary 11. Let x be a uniformly recurrent sequence and u a non-empty prefix of x. If u is a prefix of v and v is a prefix of x then there is a unique morphism

Θ satisfying Θ x,u Θ = Θ x,v .
The next lemma asserts that the derived sequences of purely primitive substitutive sequences are purely primitive substitutive sequences.

Proposition 12 ([Durand 1998]). Let x = σ ∞ (a) where σ : A * → A * is a primitive substitution prolongable on a, and, u be a non-empty prefix of x. The derived sequence D u (x) is the unique fixed point of the unique substitution, σ u , satisfying

Θ x,u σ u = σΘ x,u . Moreover, σ u is prolongable on the letter 1.
The substitution σ u is called the return substitution on u.

Lemma 13. [Durand 2012] Let x = σ ∞ (a) where σ : A * → A * is a primitive substitution prolongable on a. Let u be a non-empty prefix of x. Then, σ u and Θ x,u are algorithmically computable.

Computable bounds for linear recurrence of substitutive sequences.

In the sequel we give some computable bounds concerning the return substitutions and their linear recurrence constants. They will be important for the decidability problem we are interested in this paper. We will use the notation introduced in Proposition 5. In the sequel whenever M = (m i,j ) is a square matrix, m (n) i,j will denote the entry (i, j) of M n . We recall that, from Perron's theorem, the dominant eigenvalue α of a primitive matrix M is equal to the spectral radius ρ(M ) of M , and, the eigenvalue α has an eigenvector with strictly positive entries. Moreover, M has an eigenvector associated with α having positive entries. Lemma 14. Let M = (m i,j ) be a matrix with positive entries and x = (x i ) be its unique (right-)eigenvector with positive entries such that

x i = 1. Then, for all i,

(3.1) min j m i,j k m k,j ≤ x i ≤ max j m i,j k m k,j .
Proof. Perron's theorem implies that (see Proposition 5.8 in [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF])

lim n→∞ m (n) i,j k m (n) k,j = x i .
If we suppose that the left inequality in (3.1) does not hold then we can easily obtain the following contradiction:

lim sup n→∞ m (n) i,j k m (n) k,j > x i .
The right inequality can be treated in the same way.

Lemma 15 ([Horn and Johnson 1990]). Let M = (m i,j ) be a d × d-matrix with non-negative entries. If M has a positive eigenvector x, then for all n = 1, 2, . . . and all i = 1, . . . , d we have

min 1≤k≤d x k max 1≤k≤d x k ρ(M ) n ≤ d j=1 m (n) ij ≤ max 1≤k≤d x k min 1≤k≤d x k ρ(M ) n .
Lemma 16. Let M = (m i,j ) be a d× d-matrix and M ′ = (m ′ k,l ) be a d ′ × d ′ -matrix, both being primitive. Then, there exists a computable constant Q such that for all i, j, k, l, n one gets

(1/Q)m ′(n) i,j ≤ m (n) i,j ≤ Qm ′(n) i,j .
Proof. This comes from Perron's theorem, Lemma 14 and Lemma 15.

We recall that for each endomorphism σ we have, for all n,

|σ n | = max j i m (n) ij and σ n = min j i m (n) ij .
Lemma 17. Let σ be an endomorphism and α > 1 such that all letters of A has a growth type (0, α). There exists two computable constants P σ and Q σ such that, for all k, the following holds:

(3.2) (1/P σ )α k ≤ σ k ≤ |σ k | ≤ P σ α k and (3.3) |σ k | ≤ Q σ σ k .
Proof. It suffices to prove (3.2). Let M = (m i,j ) be the incidence matrix of σ.

When σ is primitive, we conclude with Perron's theorem, Lemma 15 and Lemma 14.

Let consider the non-primitive case. For all positive integer l, consider the following statement.

S(l)

If M has l primitive components, then there exists a computable constant P σ such that, for all k, (3.2) holds.

It suffices to prove S(l) for all l. We will proceed by induction. Notice that S(1) is true because it corresponds to the primitive case. We suppose S(l) is true. Let us prove S(l + 1) also holds.

Let {A k |1 ≤ k ≤ l + 1} be a partition of A that is organized as in Proposition 5. Consider the primitive matrices M ′ k = (m i,j ) i∈A k ,j∈A k . With the notation of Proposition 5 we get M ′ rσ k = M k . Let B = ∪ 2≤k≤l A k and N = (m i,j
) i∈B,j∈B . Remark that σ /B , the restriction of σ to B * , is an endomorphism whose incidence matrix is N . >From the hypothesis, the spectral radius of N is α. Observe that N has l primitive components and thus, from the induction hypothesis, there exists a computable constant P such that (3.2) holds. Let σ 1 be an endomorphism whose incidence matrix is M 1 . As M 1 is primitive, there exists a computable constant P 1 such that (3.2) holds for σ

1 . Let a ∈ A 1 . We set σ(a) = c 0 c 1 • • • c |σ(a)|-1
where the c i 's belong to A. We have:

|σ k (a)| = |σ k 1 (a)| + 0≤i≤|σ(a)|-1 |σ k-1 /B (c i )|.
This achieves the proof.

A sequence x is said to be linearly recurrent (for the constant K) if it is uniformly recurrent and the difference between two successive occurrences of any word u is bounded by K|u|.

In the sequel R σ will denote the maximal difference between two successive occurrences of a word of length 2 in any word on L(σ).

Lemma 18. If σ is a primitive substitution defined on an alphabet with d letters and prolongable on the letter a, then R σ is bounded by 2|σ 2d 2 |.

Proof. It is easy to check that for all k ≥ d 2 , any word σ k (a) has an occurrence of all words of length 2 appearing in σ ∞ (a). Therefore, from Lemma 4, R σ is bounded by 2|σ 2d 2 |.

Proposition 19

([Durand 1998]). Let x = σ ∞ (a)
, where σ is a primitive substitution prolongable on a. Then x is linearly recurrent for the constant

K σ = Q σ R σ |σ|.
Let σ be a substitution. >From Proposition 5 there always exists a sub-alphabet B ⊂ A such that σ(B) is a subset of B * and the incidence matrix of σ /B is primitive.

We say that σ /B is a primitive sub-morphism of σ. Observe that σ has finitely many primitive sub-morphisms.

Corollary 20. Let x = φ(σ ∞ (a)) be a uniformly recurrent sequence where φ is a coding and σ : A * → A * is a substitution prolongable on a. Then, x is linearly recurrent for the constant K where K is the infimum of the Q τ R τ |τ |, τ running over all primitive sub-morphisms of σ.

Proof. Let τ : B * → B * be a primitive sub-morphism of σ. Taking a power of τ if needed, we can suppose σ /B is prolongable on some letter b. Notice that, φ(σ ∞ (b)) being uniformly recurrent, we get L(φ(σ ∞ (b))) = L(x). We conclude with Proposition 19.

Theorem 21 ( [Durand, Host and Skau 1999]). Let x be a non-periodic linearly recurrent sequence for the constant K. For all words u of L(x),

(1) for all n, every word of L n (x) has an occurrence in each word of

L K(n+1) (x), (2) for all words v belonging to R x,u , 1 K |u| ≤ |v| ≤ K|u|, (3) #(R x,u ) ≤ 4K 3 , (4) p x (n) ≤ (K + 1)n for all n.
>From this theorem and the definition of σ u we deduce the following corollary.

Corollary 22. For all primitive substitutions σ, prolongable on a such that σ ∞ (a) is non-periodic, and all u such that u is a prefix of σ(u) we have

|σ u | ≤ |σ|K 2 σ .

Preimages of codings giving uniformly recurrent morphic sequences.

In this section φ is a coding and σ : A * → A * is a substitution prolongable on a such that all its letters have a growth type. From Proposition 6 there is no restriction to make such an assumption on the existence of the growth types. In addition we suppose the growth rate of σ is α and that x = φ(y) is uniformly recurrent and nonultimately periodic where y = σ ∞ (a). We also suppose that all letters of A occur in y. Observe that σ being a substitution (and thus being growing), α is strictly greater than 1. >From Corollary 20, x is linearly recurrent for some computable constant K.

The following two lemmas were proven in [Durand 2011].

Lemma 23 (Lemma 11 in [Durand 2011]). Let t be a non-periodic linearly recurrent sequence (with constant L). Then, for all u ∈ L(t) and all l ∈ N,

# ∪ 0≤n≤l R * t,u ∩ L n (t) ≤ 1 + 4L 3 lL |u| .
Lemma 24 (Lemma 15 in [Durand 2011]). All letters of A have the same growth rate (w.r.t σ).

Reading carefully the proof of this lemma in [Durand 2011] we can slightly improve it to obtain the following lemma.

Lemma 25. All letters of A have the same growth type (0, α) (w.r.t σ).

Proof. >From Lemma 24 we know that all letters have the same growth rate. We suppose that the growth type of σ is (d, α) with d ≥ 1.

There exists a letter whose growth type is (0, α) (Proposition 6). Hence, there necessarily exists a non-empty word bwc, appearing infinitely many times in y, where w has growth type (0, α), and, b and c are letters with d(b) ≥ 1 and d(c) ≥ 1.

Once we observe that for all letters γ with growth type (f, α), with f ≥ 1, there exist letters γ ′ and γ ′′ having growth type (f, α), such that σ(γ) = u ′ γ ′ u = vγ ′′ v ′ where u and v (being possibly the empty word) have growth types strictly less than (f, α), then, by a recurrence starting with bwc, it is easy to prove that there exist two sequences of letters (b n ) n and (c n ) n , and, two sequences of words (u n ) n and (v n ) n such that for all n ∈ N:

(1) b n u n σ(u n-1 ) • • • σ n-1 (u 1 )σ n (w)σ n-1 (v 1 ) • • • σ(v n-1 )v n c n appears infinitely many times in x; (2) b n has growth type (f, α); (3) c n has growth type (f, α); (4) u n has growth type (d n , α) with d n < f , |u n | < max c ′ ∈A |σ(c ′ )|; (5) v n has growth type (e n , α) with e n < f , |v n | < max c ′ ∈A |σ(c ′ )|.
Consequently, for all n and k the word >From Theorem 21 and Lemma 23 there exists some constant L such that: (P1) x is linearly recurrent for the constant L;

W (n, k) = σ k (b n )U (n, k)σ k (c n ), where U (n, k) = σ k (u n ) • • • σ k+n-1 (u 1 )σ k+n (w)σ k+n-1 (v 1 ) • • • σ k (v n ),
(P2) for all u ∈ L(x) and w ∈ R x,u ∩ L(x) we have |u| L ≤ |w| ≤ L|u|; (P3) for all u ∈ L(x) we have #R x,u ∩ L(x) ≤ L; (P4) for all u ∈ L(x) and all l ∈ N

# ∪ 0≤n≤l R * x,u ∩ L n (x) ≤ (1 + L) lL |u| .
(P5) for all n and k

|U (n, k)| ≤ L n i=0 (k + i) f -1 α k+i , 1 L k f α k ≤ |σ k (b ′′ )| ≤ Lk f α k and 1 L k f α k ≤ |σ k (c ′′ )| ≤ Lk f α k . >From (
|U (m i , k)| ≤ |σ k (c ′′ )| for all 1 ≤ i ≤ (1 + L) 2(L+3)(L+1)L + 1. (3.5)
>From (P1) and (P2), for all j, all words in L j (x) appear in all words of L (L+1)j (x). Let u be a prefix of φ(σ k (c ′′ )) such that

|σ k (c ′′ )| L + 1 -1 ≤ |u| ≤ |σ k (b ′′ )| L + 1 .
Then u is non-empty and occurs in φ(σ k (b ′′ )). We can decompose φ(σ k (b ′′ )) and φ(σ k (c ′′ )) in such a way that φ(σ k (b ′′ )) = G p uG s and φ(σ k (c ′′ )) = uH s with

|G s | ≤ (L + 1)|u|.
Observe that u, b ′′ , c ′′ and G s do not depend on i. Moreover, for all i belonging to [1, (1 + L) 2(L+3)(L+1)L + 1], the word uG s φ(U (m i , k)) belongs to L(x), is a concatenation of return words to u and satisfies

|uG s φ(U (m i , k))| ≤ (L + 3)|σ k (c ′′ )|. Moreover, from (P4) we get # (L+3)|σ k (c ′′ )| n=0 R * x,u ∩ L n (x) ≤ (1 + L) (L+3)|σ k (c ′′ )|L |u| ≤ (1 + L) 2(L+3)(L+1)L . (3.6) But observe that (|U (m i , k)|) 0≤i≤1+(1+L) 2(L+3)(L+1)L being strictly increasing, the words uG s φ(U (m i , k)), 0 ≤ i ≤ 1 + (1 + L) 2(L+3)(L+1)L are all distinct (and belong to ∪ 0≤n≤(L+3)|σ k (c ′′ )| R * x,u ∩ L n (x))
. This is in contradiction with (3.6).

We can now conclude with the number of preimages of φ.

Proposition 26. For all u ∈ L(x), we have: #φ -1 ({u}) ∩ L(y) ≤ p σ (K + 1)|σ|Q σ (K + 1) 2 .

Proof. Let u ∈ L(x) and n be such that σ n ≤ |u| ≤ σ n+1 . >From Theorem 21, all v ∈ φ -1 ({u}) ∩ L(y) occur in some σ n+1 (a 1 • • • a K+1 ) and in such a word occurs at most |σ n+1 (a 1 • • • a K+1 )|/(|u|/K) occurrences of elements belonging to φ -1 ({u}). Hence, using Lemma 25 and Lemma 17, one gets

|φ -1 ({u}) ∩ L(y)| ≤ p σ (K + 1) (K + 1)|σ n+1 | |u|/K ≤ p σ (K + 1)|σ|Q σ (K + 1) 2 .
3.4. Derived sequences of uniformly recurrent substitutive sequences. We keep the assumptions on x, y, σ and φ. Taking a power of σ if needed, we can suppose σ ≥ (K + 1) 2 . Let u be a non-empty prefix of y, v = φ(u) and U = φ -1 ({v}). >From Theorem 21, for each word w such that |w| ≥ (|u| + 1)/K, the word σ(w) has an occurrence of an element of U . Thus, for such w we set

σ(w) = p(w)m(w)s(w)
where m(w) belongs to U and p(w)m(w) has a unique occurrence of an element of U . Observe that p(u) is the empty word and m(u) = u. Now take (w, u ′ ) ∈ Ry,U . Then

σ(wu ′ ) = p(w)m(w)s(w)p(u ′ )m(u ′ )s(u ′ )
and there exists a unique finite sequence (w 1 , u 1 ), . . . , (w k , u k ) in Ry,U such that

(1) w 1 • • • w k = m(w)s(w)p(u ′ ) and (2) w 1 w 2 • • • w i u i is a prefix of m(w)s(w)p(u ′ )m(u ′ ) for all i. We set σU (w, u ′ ) = (w 1 , u 1 ) . . . (w k , u k ).
This defines an endomorphism of R * y,U . Then, we define σ U to be the unique endomorphism of R * y,U satisfying σU Θy,U = Θy,U σ U . (3.7)

Observe that the morphism Θy,U being a bijection from Ry,U onto Ry,U , we get |σ U (i)| = |σ U (w, u ′ )| for all i ∈ Ry,U and (w, u ′ ) ∈ Ry,U such that Θy,U (i) = (w, u ′ ). We recall that when y is a primitive substitutive sequence and U is a singleton {u} then σ U = σ u and it is the unique endomorphism satisfying σΘ y,u = Θ y,u σ u (Proposition 12). Unfortunately σ U does not satisfy such an equality (involving σ) in general. But we are not far from such a situation. This is explained by the following lemma which can be deduced from the above definitions.

Lemma 27. Let u be a non-empty prefix of y and U be the set φ -1 ({φ(u)}). Then, for all letters (w 1 , u 1 ), . . . ,

(w k , u k ) in Ry,U such that w 1 w 2 • • • w k u k belongs to L(y) and w 1 w 2 • • • w i u i is a prefix of w 1 w 2 • • • w k u k , for all i ≤ k, we have p(w 1 )δ U (σ U (w 1 , u 1 ) • • • σU (w k , u k )) m(w k )s(w k ) = σ(w 1 . . . w k u k ).
Moreover, for the unique element (w, u) ∈ Ry,U such that wu is a prefix of y, σ∞ U (w, u) is well-defined, σ∞ U (w, u) = ∆ U (y) and δ U (σ ∞ U (w, u)) = y. Proposition 28. For all prefixes u of y, with U = φ -1 ({φ(u)}), we get:

(1) The endomorphism σ U is a prolongable substitution on the letter 1;

(2) σ ∞ U (1) = DU (y); (3) φδ U Θy,U σ ∞ U (1) = x; (4) There exists a unique coding ψ u : R * y,U → R * x,u satisfying φδ U Θy,U = Θ u ψ u ;

(5) ψ u ( DU (y)) = D u (x).

Proof. Statement (1) follows from Lemma 27 and the definition of σ U in (3.7). Statement ( 3) is due to Lemma 27 and Proposition 8. Statement (2) also needs (3.7) to be proven. Statement ( 4) is easy to establish and Statement (5) follows from ( 2), ( 3), ( 4) and Proposition 8.

The following theorem extends the main result in [Durand 1998] and proves Theorem 2 (see Statement (4) below) for uniformly recurrent substitutive sequences, the necessary condition being already proven in [Durand 1998].

Theorem 29. We get:

(1) For all prefixes u of y, with

U = φ -1 ({φ(u)}), # Ry,U ≤ K 1 = 4K 3 p σ (K + 1)|σ|Q σ (K + 1) 2 ; (2) #{σ U |U = φ -1 ({φ(u)}), u is a prefix of x} ≤ K K1K2 1 , with K 2 = |σ|(K + 1)K; (3) #{ψ u |u prefix of x} ≤ K 2 1 ; (4) The cardinality of the set of derived sequences {D u (x)|u is a prefix of x} is bounded by K K1K2+2 1 .
Proof. Let u be a non-empty prefix of y. We set U = φ -1 ({φ(u)}). Let us first show that Ry,U is bounded independently of U . We have to bound the number of words wu ′ where (w, u ′ ) belongs to Ry,U . The sequence x being linearly recurrent for the constant K, from Proposition 26 and Proposition 21

# Ry,U ≤ K 1 = 4K 3 p σ (K + 1)|σ|Q σ (K + 1) 2 .
Now let us bound the length of σ U . Let i ∈ Ry,U and (w, u ′ ) = Θy,U (i). Thus, (w, u ′ ) belongs to Ry,U . >From the definition of σ U and Lemma 27 we get

|σ U (i)| = |σ U (w, u ′ )| ≤ |σ(wu ′ )| |u| K ≤ K 2 = |σ|K(K + 1). Hence #{σ U |U = φ -1 ({φ(u)}), u prefix of x} ≤ (K 1 + 1) K1K2 .
Let us show that #{ψ u |u prefix of x} is bounded. The morphism ψ u is a coding that necessarily verifies ψ u ( Ry,U ) = Rx,u . Thus, we obtain (3) using (1). The last statement follows from the two previous statements and Proposition 28. This achieves the proof.

Decidability of uniform recurrence of morphic sequences

In the sequel σ : A * → A * is an endomorphism prolongable on a, φ : A * → B * is a morphism, y = σ ∞ (a) and x = φ(y) is a sequence of B N . We have to find an algorithm telling if x is uniformly recurrent or not. >From Proposition 6 it is decidable to find an integer p such that all letters of A has a growth type w.r.t. σ p . Hence, taking such a power if needed, we suppose σ has this property. In this way we can freely use Theorem 29. In [Durand preprint 2011] it is shown that the ultimate periodicity of x is decidable. Hence we suppose x is non-periodic. As explained in Section 3.2 of [Durand preprint 2011] we can always suppose that all letters of A occur in y. When it is not the case, σ and φ can be algorithmically changed to fulfill this assumption. Hence we make such an assumption. An other reduction of the problem is given by the following result.

Theorem 30. [Honkala 2009, Durand preprint 2011] There exists an algorithm computing a coding ϕ and a non-erasing endomorphism τ , prolongable on a ′ , such that x = ϕ(z) where z = τ ∞ (a ′ ).

Consequently we can consider that φ is a coding and σ is non-erasing. >From Proposition 5 it is decidable whether σ is growing or not. Moreover we have the following lemma.

Lemma 31. [Pansiot 1984, Théorème 4.1] The endomorphism σ satisfies exactly one the following two statements.

(1) The length of words (occurring in σ ∞ (a)) consisting of non-growing letters is bounded.

(2) There exists a growing letter b ∈ A, occurring in σ ∞ (a), such that σ(b) = vbu (or ubv) with u ∈ C * \ {ǫ} where C is the set of non-growing letters. Moreover, in the situation (1) the sequence σ ∞ (a) can be algorithmically defined as a substitutive sequence. Suppose σ is not growing. >From Lemma 31 we can also suppose σ satisfies the Statement (2) of this lemma. Consequently it is classical to check there exists a word w, that can be algorithmically determined, such that w n belongs to L(y) for all n. Thus, to be uniformly recurrent, x should be periodic, more precisely we should have x = φ(w) ∞ . This can be verified using the main result in [Durand preprint 2011] or [Mitrofanov preprint 2011a], or, to use the following lemma.

Lemma 32. x = φ(w) ∞ if and only if (1) for all words B = b 1 b 2 • • • b 2|w| ∈ L(y), where the b i 's are letters, φ(B) = s B φ(w) rB p B where r B is a positive integer, s B is a suffix of φ(w) and p B a prefix of φ(w); (2) for all BB ′ ∈ L(y), where B and B ′ are words of length 2|w|, p B s B ′ = φ(w); (3) when B = φ(y 0 y 1 • • • y 2|w|-1 ), s B is the empty word.
Proof. The proof is left to the reader.

As the set of words of length 2|w| is algorithmically computable, it is decidable whether x is uniformly recurrent (in fact periodic) when σ is not growing.

Consequently we suppose σ is a substitution.

• m(u r2 )s(u r2 ) is a suffix σ(u 2 ).
All the w i should have a length less than K, otherwise x is not uniformly recurrent. Once we proceeded I steps we get: for 1 ≤ i ≤ I,

• σU (w i , u i ) = (w ri-1+1 , u ri-1+1 ) • • • (w ri , u ri ) where r i ≥ r i-1 + 1 and • σ(w 1 w 2 • • • w i u i ) = w 1 . . . w ri m(u ri )s(u ri )
and is a prefix of y, and, • m(u ri )s(u ri ) is a suffix σ(u i ).

We stop when I satisfies |w 1 . . . w rI | ≥ |σ K+1+#A 2 (wu 1 )|. Indeed, from Lemma 35, if x is uniformly recurrent then we can find all the elements of Ry,U1 looking at σ(w 1 w 2 • • • w I u I ). If we find more than K 1 elements then x is not uniformly recurrent. Then we check that for the step I + 1 no new elements of Ry,U1 appear. If some appears, then x is not uniformly recurrent. Otherwise, no new such element would appear in any steps i greater than I. Then, we continue computing R y,U1 , Ry,U1 , R y,U1 and Θy,U1 , and, σ U1 , δ U1 , Θ u1 and ψ u1 using their definition. We recall that when x is uniformly recurrent then, from Corollary 10, for all n we get (4.1)

D n (x) = D un (x) and u n+1 = Θ x,un (1)u n .
Thus we compute u 2 and U 2 = φ -1 ({u 2 }) and proceeding as previously we can algorithmically define σ U2 , δ U2 , Θ u2 and ψ u2 exiting the algorithm as it is described above. Continuing in this way we compute

{u n |1 ≤ n ≤ 1 + K K1K2+2 1 } and the set S = {(σ Un , ψ un )|U n = φ -1 ({u n }), 1 ≤ n ≤ 1 + K K1K2+2 1 }
exiting the algorithm when needed. If all the elements of S are different (which is algorithmically checkable) then, due to Theorem 29, x cannot be uniformly recurrent. Suppose there exist n and m, n < m

≤ 1 + K K1K2+2 1 , such that (σ Un , ψ un ) = (σ Um , ψ um ), then D n (x) = D m (x) ∈ R N where R = R x,un . Consequently D n (x) = D n+k(m-n) (x)
for all k. It remains to show that x is uniformly recurrent. We set z = D n (x). >From (4.1) the sequence (u n+k(m-n) ) k∈N is a strictly increasing sequence of prefixes of x and, consequently, there exists k such that for each return word w of R x,un , the word wu n has an occurrence in

u n+k(m-n) . As u n+k(m-n) is a prefix of w ′ u n+k(m-n) for all w ′ ∈ R x,u n+k(m-n) , we deduce that, for each (w, w ′ ) ∈ R x,un × R x,u n+k(m-n) , the word wu n occurs in w ′ u n+k(m-n) .
In other terms, for all letters i and j in R, i occurs in τ (j) where τ is the unique morphism satisfying

Θ x,un τ = Θ x,u n+k(m-n) .
This means that the incidence matrix of τ has positive entries. Moreover it can be easily checked that all images of τ start with the letter 1. Consequently, τ is a primitive substitution prolongable on the letter 1 whose unique fixed point is z. Hence z is uniformly recurrent. As x = Θ x,un (z), x is also uniformly recurrent and the uniform recurrence is finally decidable.

Remarks and conclusions

5.1. Morphic sequences versus substitutive sequences. In Section 4 we prove more than what we were searching. We incidently obtained Theorem 3. Let us sketch the proof. Taking the notation of Section 4, we got x = Θ x,un (z) and z = D m-n (z). Proposition 9 implies the existence of a prefix w of z such that Θ z,w (z) = z. There is no difficulty to check that Θ z,w is a primitive substitution. Thus, we conclude with Proposition 9 in [Durand 1998]. In fact, Theorem 3 was already known in [Durand 1998] (or [Durand 1996] where it is illustrated with the Chacon sequence) for non-erasing morphisms and growing substitutions (see also [Damanik and Lenz 2006]). Observe that if we do not assume uniform recurrence of the morphic sequence, then it is not necessarily a substitutive sequence. For example, let σ be the endomorphism defined on {0, 1} * by σ(0) = 001 and σ(1) = 1. The sequence x = σ ∞ (0) is not uniformly recurrent and is not substitutive (it can not be defined by a growing endomorphism). For more explanations, let us recall the main result in [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF]].

Theorem 36. Let σ be a non-erasing endomorphism prolongable on the letter a. Let x = σ ∞ (a). Then,

• If σ is growing then (p x (n)) n increases like 1, n, n log log n or n log n; • If σ is non-growing such that the words consisting of non-growing letters have bounded length, then x is a morphic sequence w.r.t. a substitution and its word complexity grows like in the previous case; • If σ is non-growing such that the words consisting of non-growing letters have unbounded length, then (p x (n)) n increases like n 2 .

Therefore the word complexity p x is quadratic. If x was substitutive, then the underlying endomorphism would be growing and thus its word complexity would increase at most like n log n. This is not possible.

In [Nicolas and Pritykin 2009] it is observed that uniformly recurrent morphic sequences x have subaffine word complexity. This result is a straightforward corollary of Theorem 3 but it has a direct and short proof. Suppose that x is not periodic, then from a result of Pansiot (Lemma 31) we can suppose x is morphic w.r.t. a growing substitution σ. As σ has a primitive sub-morphism τ , by uniform recurrence we have that L(x) is the morphic image of the language of a primitive substitution. As primitive substitutions have sub-affine complexity, so has x.

5.2. Derived sequences with respect to words that are not prefixes. In [Holton and Zamboni 1999] the authors studied the notion of derived sequences not only on prefixes but on all words of the uniformly recurrent sequence x considered. Let us call these sequences descendant of x as they did. They are defined as follows.

Let u ∈ L(x) and w be such that x = wuy where wu has a unique occurrence of u.

The sequence D u (uy) is called descendant of x with respect to u. We denote it by D u (x). They improved the main result in [Durand 1998] showing the following.

Theorem 37. Let x be a uniformly recurrent sequence. Then, x is a primitive substitutive sequence if and only if the set of its descendants is finite.

A similar result was recently stated in [Kanel-Belov and Mitrofanov preprint 2011] by means of Rauzy graphs. We think it is important and interesting to recall that C. Holton and L. Zamboni presented this result as "a symbolic counterpart to a theorem of M. [START_REF] Boshernitzan | An extension of Lagrange's theorem to interval exchange transformations over quadratic fields[END_REF] which states that an interval exchange transformation with lengths in a quadratic field has only finitely many descendants". Moreover, this last result is presented as an extension of the classical Lagrange's theorem asserting that the continued fraction expansion of a quadratic irrational is eventually periodic. Due to Theorem 3, Theorem 37 also holds for uniformly recurrent morphic sequences (instead of primitive substitutive sequences).

Theorem 38. Let x be a uniformly recurrent sequence. Then, x is a morphic sequence if and only if the set of its descendants is finite.

Proof. If x is periodic then it is a morphic sequence and it has finitely many descendants. Thus we suppose x is non-periodic.

Let us sketch the proof. >From Theorem 37 (or the main result in [Durand 1998]) we only have to prove that morphic sequences have finitely many descendants. Let x = φ(y) where y = σ ∞ (a) and σ is an endomorphism on A * prolongable on the letter a. Let us first make some remarks. Let u ∈ L(x) and w be such that x = wuz where wu has a unique occurrence of u.

Then there exists a morphism χ u : R * x,wu → R * uz,u such that χ u (D wu (x)) = D u (uz). Moreover, it can be shown that the set {χ u |u ∈ L(x)} is finite using Theorem 3 and Theorem 21. Thus, applying the main result in [Durand 1998] (or Theorem 37) achieves the proof. 5.3. Dynamical interpretation. Let us reformulate Theorem 38 and Proposition 26. Below K will stand for either N or Z. We refer to [START_REF] Queffélec | Substitution dynamical systems-spectral analysis[END_REF]] for more details on subshifts. A (topological) dynamical system is a couple (X, S) where S is a continuous map from X to X and X is a S-invariant compact metric space. It is a subshift when X is a closed S-invariant subset of A K and S is the shift map (S : A K → A K , (x n ) n∈K → (x n+1 ) n∈K ). In the sequel even if the alphabet changes, S we will always denote the shift map. We say that a dynamical system (X, S) is minimal whenever the only S-invariant subsets of X are X and ∅. Let x be a sequence on the alphabet A. Consider the set Ω(x) = {y ∈ A K |L(y) ⊂ L(x)}. Then, (Ω(x), S) is a subshift. Let (X, T ) and (Y, R) be two dynamical systems. We say that (Y, R) is a factor of (X, T ) if there is a continuous and onto map φ :

X → Y such that φ • T = R • φ.
If, moreover, φ is one-to-one we say φ is a conjugacy. Then, Proposition 26 can be interpreted by means of subshifts and factors.

Proposition 39. Let x be a morphic sequence. There exists a constant K such that for any minimal factor (Y, S), with #Y = +∞, given by φ : (Ω(x), S) → (Y, S), for all y ∈ Y , #φ -1 ({y}) ≤ K.

Let (X, S) be a minimal subshift and U ⊂ X be a clopen set (closed and open set). We recall that X being a Cantor space, a basis of its topology consists of clopen sets. For example the family of cylinder sets is such a family. A cylinder is a set of the form

[u.v] X = {x ∈ X | x -|u| • • • x -1 x 0 • • • x |v|-1 = uv}. Let S U : U → U be the induced map, i.e. if y ∈ U then S U (y) = S rU (y) (y)
, where r U (y) = inf{n > 0 | S n (y) ∈ U }. As (X, S) is minimal, the map r U is well-defined and continuous. It is called the return map to U . The pair (U, S U ) is a minimal dynamical system. We say (U, S U ) is the induced dynamical system of (X, S) with respect to U . >From Theorem 38 we obtain the following result.

Theorem 40. Let x be a uniformly recurrent morphic sequence. Then, (Ω(x), S) has finitely many induced dynamical systems on cylinders up to conjugacy. This could also be directly deduced from [Holton and Zamboni 1999] using the arguments at the end of Section 5.1. 5.4. Algorithmical complexity. In [Nicolas and Pritykin 2009] is shown the decidability of the uniform recurrence for purely morphic sequences and automatic sequences by presenting a polynomial time algorithm. >From the present work, and for purely morphic sequence, we can deduce a polynomial algorithm as a direct consequence of Lemma 4 and Proposition 5. But for the general case the algorithm having a high complexity we did not find interesting to compute it precisely. 5.5. Other decidability problems for morphisms. In the conclusion of the work [Nicolas and Pritykin 2009] is mentioned some open problems of decidability concerning morphic sequences. Let us recall them and add some. The inputs will always be the morphism φ and the endomorphism σ defining the morphic sequence or pairs of such couples (φ, σ).

Periodicity. The decidability of the ultimate periodicity has been recently solved in both [Mitrofanov preprint 2011a] and [Durand preprint 2011]. It was previously shown in the primitive case in [Durand 2012] and for purely morphic sequences in [START_REF] Pansiot | Decidability of periodicity for infinite words[END_REF]] and [Harju and Linna 1986].

Recurrence. The decidability problem concerning different notions of recurrence such as recurrence or almost periodicity remains open (see [Maes 1998, Maes 2000], [Muchnik, Semenov and Ushakov 2003] and [START_REF] Pritykin | Almost periodicity, finite-automaton transformations, and efficiency aspects[END_REF]).

Language. Given two morphic sequences, is it decidable whether that they have the same language? In [Fagnot 1997b] is given some answers to this question for purely morphic sequences generated by primitive substitutions under some mild assumptions. In [Fagnot 1997a] I. Fagnot solves this decidability problem for automatic sequences. She considers two cases : the multiplicative dependence and independence of the dominant eigenvalues p and q (which are integers in these settings) of the underlying substitutions, that is whether log p/ log q belongs or not to Q. She managed to treat the multiplicatively independent case using the extension of Cobham's theorem for automatic languages she obtained in the same paper, then testing the ultimate periodicity of the languages and to see if they are equal. For the dependent case she used the logical framework of Presburger arithmetic associated to automatic sequences. Thus, this problem remains open.

Equality. Given two morphic sequences x and y, is it decidable whether x = y? This was shown to be true in [Durand 2012] in the primitive case. For purely morphic sequences, this problem (called the D0L ω-equivalence problem) was solved in 1984 by K. Culik II and T. Harju [Culik and Harju 1984]. More is shown for this problem in [Durand 2012] in the primitive case: the two primitive substitutions have powers that coincide on some cylinders.

Factor and conjugacy. Let (X, S) and (Y, S) be two subshifts generated by two morphic sequences. Could we decide whether one is a factor of the other, or, whether they are conjugate. In [START_REF] Coven | [END_REF]] some elements of answers can be found for the Morse subshift.

Orbit equivalence. With the same settings as before we can ask for the decidability of the orbit equivalence of the subshifts. That is, does there exist a continuous bijective map φ sending orbits to orbits: φ({S n (x)|n ∈ Z}) = {S n (φ(x))|n ∈ Z}) for all x ∈ X. Thanks to the characterization of orbit equivalence by means of dimension groups, a stronger notion of orbit equivalence (called the strong orbit equivalence) is decidable. This comes from [Bratteli, Jorgensen, Kim and Roush 2001] and the fact that the dimension groups of minimal substitution system are stationary (see [Forrest 1997] or [Durand, Host and Skau 1999]). We refer the interested reader to [Giordano, Putnam and Skau 1995] for more details on (strong) orbit equivalence. The decidability of orbit equivalence remains open for substitution subshifts. 5.6. For tilings. All these questions could also be asked for self-similar tilings or multidimensional substitutions. The more tractable problems would certainly concern "square multidimensional substitutions" (see for example the references [ Černý and Gruska 1986, Salon 1986[START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF][START_REF] Salon | Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels)[END_REF]] or, in an interesting logical context, the nice survey [Bruyère, Hansel, Michaux, and Villemaire 1994]).

Moreover, the striking papers [Mozes 1989] and [Goodman-Strauss 1998] should also be mentioned as they show that in higher dimension the situation is not as "simple" as it is in dimension 1.

Definition 7 .

 7 Let σ : A * → A * be a non-erasing endomorphism. For all a ∈ A, if there exists a couple (d(a), θ(a)) satisfying lim n→+∞ |σ n (a)| c(a) n d(

  appears infinitely many times in x. There exist a strictly increasing sequence (m i ) and two letters b ′′ and c ′′ such that (3.4) b mi = b ′′ and c mi = c ′′ for all i.

  3.4) and the previous inequalities, there exists k such that |σ k (c ′′ )| ≤ |σ k (b ′′ )| (the other case can be treated in the same way), 2(1 + L) ≤ |σ k (c ′′ )| and

Let K be the infimum of the Q τ R τ |τ |, τ running over all primitive sub-morphisms of σ. If x is uniformly recurrent, then, from Corollary 20, x should be linearly recurrent for the constant K. In this case, K being fixed with respect to the linear recurrence of x, we can take a power of σ instead of σ: this will change neither x nor K. Consequently, we can suppose that σ ≥ (K + 1) 2 and the constants of Section 3.4 can be freely used whenever we suppose x uniformly recurrent. The algorithm we now present is based on the fact (proven incidently below) that x is uniformly recurrent if and only if in the set {D n (x)|1 ≤ n ≤ 1 + K K1K2+2 1 } there are two identical sequences, where K 1 and K 2 are the computable constants given by Theorem 29. Let u 1 = y 0 . We start the algorithm computing σ U1 and ψ u1 . There are several intermediate objects that have to be determined. Let us remind the order in which we should proceed (see Section 3.4):

(1)

(2) Ry,U1 , R y,U1 , Ry,U1 and R y,U1 , (3) Θy,U1 , (4) σU1 and σ U1 , (5) δ U1 , Θ u1 and ψ u1 . Let us explain how to compute Ry,U1 , R y,U1 , Ry,U1 and R y,U1 . It suffices to compute Ry,U1 . In fact we will directly compute σU1 . We will need the following lemmas.

Lemma 33. All words in L 2 (x) have an occurrence in σ #A 2 (x 0 x 1 ).

Proof. The proof is left to the reader.

As a consequence we obtain the following lemma.

Lemma 34. For all n, all words in L n (x) have an occurrence in σ n+#A 2 (x 0 x 1 ).

Proof. The proof is left to the reader. Lemma 35. Suppose x is uniformly recurrent. For all (w ′ , u ′ ) ∈ Ry,U1 , the word w ′ u ′ has an occurrence in the word σ K+1+#A 2 (wu 1 ).

Proof. >From Lemma 34, all words of length K + 1 have an occurrence in the word σ K+1+#A 2 (wu 1 ). We achieve the proof observing that, x being uniformly recurrent, for all (w ′ , u ′ ) ∈ Ry,U1 we get |w ′ u ′ | ≤ K + 1.

In y [0,K] there should be at least two occurrences of u 1 : 0 and some other. If this is not the case, then x is not uniformly recurrent. Let j be the second occurrence of u 1 is y. Then, (w 1 , u 1 ) = (y [0,j-1] , u 1 ) is an element of Ry,U1 . (In what follows we use the notations of Section 3.4.) Below, all the (w i , u i ) will be elements of Ry,U1 . We have:

•

) and is a prefix of y, and,

• m(u r1 )s(u r1 ) is a suffix σ(u 1 ). Observe that r 1 is necessarily greater than or equal to 2. All the w i should have a length less than K, otherwise x is not uniformly recurrent. We continue with (w 2 , u 2 ):

• σU (w 2 , u 2 ) = (w r1+1 , u r1+1 ) • • • (w r2 , u r2 ) where r 2 ≥ r 1 + 1 and • σ(w 1 w 2 u 2 ) = w 1 . . . w r2 m(u r2 )s(u r2 ) and is a prefix of y, and,