Gwenaël Richomme

Characterization of infinite LSP words and endomorphisms preserving the LSP property

Keywords: generalizations of Sturmian words, morphisms, S-adicity

Answering a question of G. Fici, we give an S-adic characterization of the family of infinite LSP words, that is, the family of infinite words having all their left special factors as prefixes. More precisely we provide a finite set of morphisms S and an automaton A such that an infinite word is LSP if and only if it is S-adic and one of its directive words is recognizable by A. Then we characterize the endomorphisms that preserve the property of being LSP for infinite words. This allows us to prove that there exists no set S of endomorphisms for which the set of infinite LSP words corresponds to the set of S -adic words. This implies that an automaton is required no matter which set of morphisms is used.

Introduction

Free monoid morphisms, also sometimes called substitutions, are basic tools to study finite and infinite words. They are used in various fields as Combinatorics on Words, Formal Languages or Dynamical Systems (see, e.g., [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF][START_REF]Handbook of Formal Languages[END_REF]). Literature contains many examples of interesting infinite words that are fixed points of endomorphisms. Their success and interest are mainly due to the simplicity of their definitions and the ability given by endomorphisms to prove their properties. Let w be such a fixed point of morphism and let f be a morphism such that w = f (w). This word w can be seen as the limit lim n→∞ f n (a) where a is the first letter of w (with some extra needed conditions on f to ensure that this limit exists and is an infinite word). This word w can also be considered as a word which can be recursively desubstituted by the morphism f : here desubstituted means the existence of a word w 1 such that w = f (w 1 ) and recursively desubstituted means that w 1 can be itself desubstituted by f and so on).

Paraphrasing [START_REF] Berthé | Beyond substitutive dynamical systems: S-adic expansions[END_REF], if one wants to go beyond the morphic case, and thus, get more flexibility in the hierarchical structure, one might want to change the morphism at each desubstitution step (the point of view in [START_REF] Berthé | Beyond substitutive dynamical systems: S-adic expansions[END_REF] is somewhat dual). Thus considering a set S of morphisms instead of a single morphism f , we may consider the S-adic words, that is, words that can be recursively desubstituted over S. A more precise definition is given in Section 3. For more information on S-adic words, readers can consult, e.g., papers [START_REF] Berthé | S-adic expansions related to continued fractions[END_REF][START_REF] Berthé | Beyond substitutive dynamical systems: S-adic expansions[END_REF], Chapter 12 in [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF] and their references. Note that we will sometimes write S-adic for substitutive-adic word without direct reference to a set S of morphisms.

S-adicity arises naturally in various studies as, for instance, those of Sturmian words [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]Chap.2][17, Chap. 5] or of Arnoux-Rauzy words [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF]. In [START_REF] Ferenczi | Rank and symbolic complexity[END_REF] (see also [START_REF] Leroy | Contribution à la résolution de la conjecture S-adique[END_REF][START_REF] Leroy | An S-adic characterization of minimal subshifts with first difference of complexity p(n + 1) -p(n) ≤ 2. Discrete Math[END_REF]) Ferenczi proved that any word with factor complexity bounded by some affine function is S-adic for some finite set S of morphisms that depends on the bound of the first difference of the factor complexity (remember that, for any word with factor complexity bounded by some affine function, the first difference of the factor complexity is bounded by a constant [START_REF] Cassaigne | Special factors of sequences with linear subword complexity[END_REF]). For each of the previous examples, the S-adic properties are not characteristic of the considered families. Episturmian words that generalize Sturmian and Arnoux-Rauzy words are the S Eadic words where S E is the finitely generated set of morphisms that preserve episturmian words [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF][START_REF] Justin | Episturmian words and episturmian morphisms[END_REF][START_REF] Richomme | Conjugacy and episturmian morphisms[END_REF]. Over the binary alphabet, it is an exercise to show that the set of balanced words (Sturmian words and ultimately periodic balanced words) are the S S -adic words where S S is the finitely generated set of morphisms that preserve Sturmian words. As far as the author knows it, the kind of characterizations of the two previous examples is very rare.

S-adic characterizations of families of words is generally twofold. In addition to the induced set S of morphisms, a characterization of allowed infinite sequences of desubstitutions is provided. For instance there exist two disjoint sets S a and S b of morphisms such that a word is Sturmian if and only it can be recursively decomposed over S a ∪ S b using infinitely often elements from S a and infinitely often elements from S b [START_REF] Berthé | Initial powers of Sturmian sequences[END_REF]. This condition can be described using infinite paths with prohibited segments in an automaton or a graph. These kinds of conditions are also used, for instance, in the characterization of words for which the first difference of factor complexity is bounded by 2 [START_REF] Leroy | Contribution à la résolution de la conjecture S-adique[END_REF][START_REF] Leroy | An S-adic characterization of minimal subshifts with first difference of complexity p(n + 1) -p(n) ≤ 2. Discrete Math[END_REF] or in the characterization of sequences arising from the study of the Arnoux-Rauzy-Poincaré multidimensional continued fraction algorithm [START_REF] Berthé | Factor complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré algorithm[END_REF]. For the last example, all infinite paths in the graphs are allowed.

Extending an initial work by M. Sciortino and L.Q. Zamboni [START_REF] Sciortino | Suffix automata and standard Sturmian words[END_REF], G. Fici investigated relations between the structure of the suffix automaton built from a finite word w and the combinatorics of this word [START_REF] Fici | Special factors and the combinatorics of suffix and factor automata[END_REF]. He proved that the words having their associated automaton with a minimal number of states (with respect to the length of w) are the words having all their left special factors as prefixes. G. Fici asked in the conclusion of his paper for a characterization of the set of words having the previous property, that he called the LSP property, both in the finite and the infinite case. In this paper, we provide an S bLSPadic characterization of LSP infinite words (for a suitable S bLSP set of morphisms) using an automaton recognizing allowed infinite desubstitutions over S bLSP . We prove that there exists no set of morphisms S such that the family of LSP words is the family of S-adic words.

Our S-adic characterization is a refinement of the one presented at Conference DLT 2017 [START_REF] Richomme | A characterization of infinite LSP words[END_REF]. Main ideas of Sections 2 to 7 were already presented and used in [START_REF] Richomme | A characterization of infinite LSP words[END_REF]. But the set of morphisms considered here allows to provide a smaller automaton (in particular it can be drawn for a three-letter alphabet while this was not possible in [START_REF] Richomme | A characterization of infinite LSP words[END_REF]) even if this set is larger as it is the set of morphisms considered in [START_REF] Richomme | A characterization of infinite LSP words[END_REF] plus their restrictions to smaller alphabets. The proof that one cannot have a characterization without restrictions on allowed desubstitutions (Section 8) is new.

The paper is organized as follows. After introducing in Section 2 our basis of morphisms S R-bLSP , in Section 3, we show that all infinite LSP words are S R-bLSP -adic. Section 4 introduces a property of infinite LSP words and a property of morphisms in S bLSP that together allow to explain why the LSP property is lost when applying an LSP morphism to an infinite LSP word. Section 5 allows to trace the origin of the previous property of infinite LSP words. Based on this information, Section 6 defines our automaton and Section 7 proves our characterization of infinite LSP words. In Section 8 we characterize endomorphisms preserving LSP words and deduce that the set of LSP words cannot be characterized as a set of S-adic words, whatever S is.

Some basic morphisms

We assume that readers are familiar with combinatorics on words; for omitted definitions (as for instance, factor, prefix, ...) see, e.g., [START_REF] Berthé | Combinatorics, Automata and Number Theory[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. Given an alphabet A, A * is the set of all finite words over A, including the empty word ε, and A ω is the set of all infinite words over A. For a non-empty word u, let first(u) denote its first letter, last(u) its last letter and alph(u) its set of letters. Notations first and alph are similarly defined for infinite words.

A finite word u is a left special factor of a finite or infinite word w if there exist at least two distinct letters a and b such that both words au and bu occur in w. Following G. Fici [START_REF] Fici | Special factors and the combinatorics of suffix and factor automata[END_REF], a finite or infinite word w is LSP if all its left special factors are prefixes of w. We also say say w has the LSP property. We study these words using morphisms.

Given two alphabets A and B, a morphism (endomorphism when A = B) f is a map from A * to B * such that for all words u and v over A, f (uv) = f (u)f (v). Morphisms are entirely defined by images of letters. Morphisms extend naturally to infinite words. We consider only nonerasing morphisms, that is, morphisms f such that f (x) = ε implies x = ε. When X and Y are two sets of morphisms, let XY denote the set of morphisms f

• g with f ∈ X, g ∈ Y such that if f is from A * to B * and g is from C * to D * then D ⊆ A.
We call basic LSP morphism on an alphabet A, or bLSP in short, any endomorphism f of A * verifying:

• there exists a letter α such that f (α) = α, and

• for all letters β = α, there exists a letter γ such that f

(β) = f (γ)β
From this definition one can naturally associate the rooted tree (all labels are on vertices and distinct vertices have distinct labels) whose vertices are elements of A, whose root is α and whose (oriented) edges are pairs (β, γ) of letters such that f (β) = f (γ)β. Conversely, given a labeled rooted tree T = (A, E), let f T be the morphism defined by: for all letters β, f T (β) is the word obtained concatenating vertices on the path in T from the root of T to β. This morphism is bLSP.

Let S bLSP (A) (or shortly S bLSP when A is clear) denote the set of all bLSP morphisms over the alphabet A. We have just seen that there is a bijection between this set and the set of labeled rooted trees with label in A. Thus, denoting by #X the cardinality of a set X, there are (#A) #A-1 elements in S bLSP (A) (see Sequence A000169 in The On-Line Encyclopedia of Integer Sequences: this sequence enumerates rooted trees; its first values are [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF][START_REF] Berthé | S-adic expansions related to continued fractions[END_REF][START_REF] Ferenczi | Rank and symbolic complexity[END_REF]64,625,7776,117649,2097152).

When f is a morphism defined on an ordered alphabet

A = {a 1 , . . . , a k }, we let [u 1 , u 2 , . . . , u k ] denote the morphism defined by a 1 → u 1 , a 2 → u 2 , . . . , a k → u k . For instance [a, ab, ac, acd, ace] defines the bLSP morphism f such that f (a) = a, f (b) = ab, f (c) = ac, f (d) = acd, f (e) = ace.
The rooted tree associated with f is given in Figure 1. Example 2.1. Some examples of bLSP morphisms are the standard episturmian morphisms L α defined, for α a letter, by: L α (α) = α and L α (β) = αβ for any letter β = α (see for instance [START_REF] Justin | Episturmian words and episturmian morphisms[END_REF][START_REF] Richomme | Conjugacy and episturmian morphisms[END_REF] for example of uses of these morphisms). The associated rooted tree has its root connected to all other vertices. Observe that S bLSP ({a, b}) = {L a , L b } = {[a, ab], [ba, b]}. These morphisms are well-known in the context of Sturmian words. They are denoted τ a and τ b in [START_REF] Berthé | Initial powers of Sturmian sequences[END_REF] from which it can be seen that standard Sturmian words are the non-periodic {τ a , τ b }-adic words (see also [START_REF] Levé | Quasiperiodic Sturmian words and morphisms[END_REF]).

Example 2.2. For any alphabet

A k = {a 1 , . . . , a k }, let λ a 1 •••a k be the morphism defined by λ a 1 •••a k (a i ) = a 1 • • • a i .
The associated rooted tree is a path. For instance λ acb = [a, acb, ac]. Note that S bLSP ({a, b, c}) = {L a , L b , L c , λ abc , λ acb , λ bac , λ bca , λ cab , λ cba }. Observe that these morphisms are the mirror morphisms of Arnoux-Rauzy and Poincaré morphisms (here f is a mirror morphism of g if f (a) is the mirror image or reversal of g(a) for all letters a) used by V. Berthé and S. Labbé [START_REF] Berthé | Factor complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré algorithm[END_REF].

Let A, B and A be three alphabets with A ⊆ A and let f be a morphism from A * to B * . The restriction of f to A is the morphism from A * to alph(f (A )) * denoted f |A or f |A and defined by f |A (α) = f (α) for each letter α of A . An R-bLSP morphism is any restriction to a subalphabet of a morphism in S bLSP . Let S R-bLSP (A) or simply S R-bLSP denote the set of R-bLSP morphisms. This means that if f belongs to S R-bLSP (A), there exists a subalphabet B of A and an element g of S bLSP such that f = g |B .

By construction of an R-bLSP morphism f , all images of letters by f begin with the same letter: let first(f ) denote it. Next properties are also direct consequences of the definition of R-bLSP morphisms. They will often be used without explicit mention. Property 2.3. Let f be an R-bLSP morphism over the alphabet A.

1. for all β ∈ A, last(f (β)) = β; 2. f (A) is a suffix code (no word of f (A) is a suffix of another word in f (A)); 3. f is injective both on the set of finite words and the set of infinite words;

Substitutive-adicity of infinite LSP words

Let S be a set of morphisms. Usually an infinite word w is said to be S-adic if there exist a sequence (f n ) n≥1 of morphisms in S ω and a sequence of letters (a n ) n≥1 such that lim

n→+∞ |f 1 f 2 • • • f n (a n+1 )| = +∞ and w = lim n→+∞ f 1 f 2 • • • f n (a n+1
). The sequence (f n ) n≥1 is called the directive word of w. We consider here S-adicity in a rather larger way: a word w is S-adic with directive word (f n ) n≥1 if there exists an infinite sequence of infinite words (w n ) n≥1 such that w 1 = w and w n = f n (w n+1 ) for all n ≥ 1. If the former definition is verified, the latter is also verified. This second definition may include degenerated cases as, for instance, the word a ω that is {Id}-adic with Id the identity morphism. To understand S-adicity, it may be better to see w n+1 as the inverse image of w n , rather than seing w n as the image of w n+1 . As morphisms are sometimes called substitutions, we say that w n+1 is a desubstituted word from w n and so saying that w is S-adic means that w can be recursively desubstituted (using elements of S). Sometimes f n can be defined on a larger alphabet than alph(w n+1 ). In this case f n can be replaced with its restriction to alph(w n+1 ). We will say that (f n ) n≥1 is a fitted directive word when for all n ≥ 1, f n is defined on alph(w n+1 ). Proposition 3.1. Any infinite LSP word is S R-bLSP -adic and so is S bLSP -adic. Moreover any LSP word has exactly one fitted directive word over S R-bLSP .

The proof of this proposition follows the following general scheme of proof and so is a direct consequence of the next two lemmas.

Given a set S of morphisms, in order to prove that infinite words verifying a property P are S-adic, it suffices to prove that for all infinite words w verifying P , 1. there exist f ∈ S and an infinite word w such that w = f (w ), and 2. if w = f (w ) with f ∈ S, then w verifies Property P .

To prove the uniqueness of directive words one has also to prove the uniqueness of f and w in the first item above. Lemma 3.2. Given any finite or infinite LSP word w, there exist a unique infinite word w and a unique morphism f in S R-bLSP (alph(w )) such that w = f (w ).

Proof. Let w be a non-empty finite or infinite LSP word and let α be its first letter. Let X be the set of words over alph(w) \ {α} such that w can be factorized over {α} ∪ X. Let G be the graph (alph(w), E) with E the set of edges (β, γ) such that βγ is a factor of a word αu with u ∈ X. By LSP Property of w, each letter occurring in a word of X is not left special in w. Hence G is a rooted tree with α as root, that is, for any letter β in alph(w), there exists a unique path from α to β. Let u β denote the word obtained by concatenating the letters occurring in the path. Let g be the morphism defined by g(β) = u β for all β in alph(w) \ {α}, and by g(α) = α. By construction, g is bLSP.

As α does not occur in words of X and as w begins with α, w has a unique decomposition over αX ∪ {α}. If this decomposition holds over αX, set Y = αX. Otherwise set Y = αX ∪ {α}. Observe that Y ⊆ {u β | β ∈ alph(w)}. Let f be the restriction of g to the set {β | u β ∈ Y }: f ∈ S R-bLSP . By construction w = f (w ) for a word w and f ∈ S R-bLSP (alph(w )).

Assume w = h(w ) with h an R-bLSP morphism and w an infinite word. Let A = alph(w ) and A = alph(w ). By the definition of R-bLSP morphisms, all images of letters by f or h begin with the same letter α (which is also the first letter of w). Still by the definition of LSP morphisms, this letter α occurs only once in each image of letters by f and h. Positions of the letter α in w determine the beginnings of images of letters by f and h. This implies that f (A ) = h(A ). By Property 2.3(1), for letters β and γ, last(f (β)) = γ or last(h(β)) = γ implies β = γ. Hence f = h and w = w . Lemma 3.3. For any R-bLSP morphism f and any infinite word w, if f (w) is LSP then w is LSP.

Proof. Assume by contradiction that w is not LSP. This means that w has (at least) one left special factor that is not one of its prefixes. Considering such a factor of minimal length, there exist a word u and letters a, b, β, γ such that a = b, β = γ, ua is a prefix of w, βub and γub are factors of w. As f is an R-bLSP morphism, there exists a unique letter α which is the first letter of all non-empty images by f . The word f (u)f (a)α is a prefix of f (w). Moreover by Property 2.3(1), the words βf (u)f (b)α and γf (u)f (b)α are factors of w (here the fact that w is infinite is useful: each factor is followed by a letter whose image begins with α). As f (a) = f (b) and as the letter α occurs only as a prefix in f (a) and f (b), f (a)α is not a prefix of f (b)α and, conversely, f (b)α is not a prefix of f (a)α. Hence there exist a word v and letters a , b such that a = b , va and vb are respectively prefixes of f (a)α and f (b)α. It follows that f (u)va is a prefix of f (w) while βf (u)vb and γf (u)vb are factors of f (w): f (w) is not LSP, a contradiction.

Observe that Lemma 3.3 does not hold for finite words. For instance the word baa is not LSP while its image abaa by the morphism [a, ab] is LSP.

Fragilities of infinite LSP words

The converse of Lemma 3.3 is false: there exist an infinite LSP word w and a bLSP morphism f such that f (w) is not LSP.

Example 4.1. Let F be the well-known Fibonacci word (the fixed point of the endomorphism [ab, a]), and let g = λ acb = [a, acb, ac]. The word g 2 (F) begins with the word g 2 (ab) = g(aacb) = aaacacb that contains the factor ac which is left special but not a prefix of the word. Hence the word g 2 (F) is not LSP while F is LSP and g is bLSP (actually one can prove, using Lemma 4.4 below, that g(F) is LSP).

In what follows, we introduce some properties of LSP words and morphisms that explain in which context a (breaking) R-bLSP morphism can map a (fragile) infinite LSP word on a non-LSP word. Definition 4.2. Let a, b, c be three pairwise distinct letters. An infinite word w is (a, b, c)-fragile if there exist a word u and distinct letters β and γ such that the word ua is a prefix of w and the words αub and βuc are factors of w. The word u is called an (a, b, c)-fragility of w. We will also say that, when we need letters α and β, w is (a, b, c, β, γ)-fragile and the word u is an (a, b, c, β, γ)-fragility of w.

For instance, the empty word ε is an (a, b, c, c, a)-fragility of g(F): εa is a prefix of g(F) = aacb • • • while cεb and aεc are factors of g(F). More generally any factor abc or acb in an infinite word produces an (a, b, c)-fragility. One can also observe that, by symmetry of the definition, any (a, b, c)-fragile word is also (a, c, b)-fragile. Finally let us note that no fragility exists in words over two letters (as the definition needs three pairwise different letters).

The main idea of introducing the previous notion is that for any (a, b, c)-fragile LSP word w, there exists a bLSP morphism such that f (w) is not LSP. For instance, if u, α, β, w are as in Definition 4.2 and if g = λ acb = [a, acb, ac], the word g(u)aa is a prefix of g(w) whereas the words αg(u)acb and βg(u)ac are factors of g(w), so that g(w) is not LSP since g(u)ac is left special but not a prefix of g(w). 3. There exist some pairwise distinct letters a, b, c in w such that w is (a, b, c)-fragile and f is LSP (a, b, c)-breaking.

Proof. 1 ⇒ 2. Assume first that f (w) is not LSP. There exists a left special factor V of f (w) which is not a prefix of f (w). Let v be the longest common prefix of V and f (w). Let a , b be the letters such that va is a prefix of f (w) and vb is a prefix of V : by construction a = b . Let also β, γ be distinct letters such that βV and γV are factors of f (w) (also βvb and γvb are factors of f (w)).

By the definition of R-bLSP morphisms, the letter α = first(f ) is the unique letter that can be left special in f (w). As α is the first letter of f (w), we have v = ε and first(v) = first(f ). As α occurs exactly at the first position in all images of letters, occurrences of α mark the beginning of images of letters in f (w). Considering the last occurrence of α in v, we can write v = f (u)αx with |x| α = 0. Let a, b, c be letters such that:

• ua is a prefix of w, and, va = f (u)αxa is a prefix of f (ua) when a = α or v = f (ua) when a = α;

• βub is a factor of w, and, βvb is a prefix of βf (ub) when b = α or v = f (ub) when b = α;

• γuc is a factor of w, and, γvb is a prefix of γf (uc

) when b = α or v = f (uc) when b = α.
As a = b , we have a = b and a = c. Observe that until now we did not use the fact that w is LSP. This implies b = c (and so b = α). Indeed otherwise ub would be a left special factor of w without being one of its prefixes: a contradiction with the fact that w is an LSP word. Thus w is (a, b, c)-fragile.

This ends the proof of Part 1 ⇒ 2 as αxb is a common prefix of f (b) and f (c) and αx is the longest common prefix of f (a) and f (b).

2 ⇒ 3. By hypothesis, f (a) = vδw 1 , f (b) = vγw 2 and f (c) = vγw 3 for letters δ, γ and words w 1 , w 2 and w 3 with δ = γ. Let w be any LSP (a, b, c)-fragile infinite word. Let u , β and γ be the word and letters such that u a is a prefix of w while β u b and γ u c are factors of w with β = γ . The word f (w ) has f (u )vδ as a prefix and words β f (u )vγ and γ f (u )vγ as factors. As δ = γ, the word f (w ) is not LSP. The morphism f is LSP (a, b, c)-breaking.

3 ⇒ 1. This follows the definition of (a, b, c)-fragile words and LSP (a, b, c)-breaking morphisms.

Observe that we have also proved the next result. To end this section let us mention that in the binary case the converses of Lemma 3.3 and Proposition 3.1 hold. Indeed as shown in Lemma 4.4, if w is LSP, f is an R-bLSP morphism and f (w) is not LSP, then w contains at least three distinct letters. Recall that the elements of S R-bLSP ({a, b}) are the morphisms L a , L b and their restrictions to alphabets {a} and {b}.

Corollary 4.6. If w is an LSP infinite word over {a, b} and if f is defined over alph(w) and belongs to the set S R-bLSP ({a, b} then f (w) is also LSP. Consequently an infinite word over {a, b} is LSP if and only if it is {L a , L b }-adic.

Origin of fragilities

Before characterizing infinite LSP words, we need to know how fragilities in an LSP word w can appear. We will see that this depends only on the morphisms in the fitted S R-bLSP -adic directive word of w (Theorem 7.1). At a first step, let f be an R-bLSP morphism from A * to B * with α = first(f ). We examine the fragilities occurring in the image by f of an LSP word.

New fragilities. Assume that for some letters b, c, β, γ with α = b = c = α and β = γ, the words βb and γc belong to f (A), that is, are factors of images of letters by f . Then for any word w containing all letters of A (or at least the letters whose images contain βb and γc), the empty word is an (α, b, c, β, γ)fragility of f (w). We say that ε is an (α, b, c, β, γ)-fragility (or simply an (α, b, c)-fragility) associated with f . For instance, (a, b, c) is a fragility associated with the morphism λ abc = [a, ab, abc].

Propagated fragilities. Assume now that an infinite word w over A contains an (a , b , c , β, γ)-fragility v. Observe that: f (va )α is a prefix of f (w); βf (vb )α and γf (vc )α are factors of f (w); the word f (v)α is a prefix of the three words f (va )α, f (vb )α and f (vc )α. Assume there exist a common prefix u of these words and pairwise distinct letters a, b and c such that ua is a prefix of f (va )α, βub is a prefix of βf (vb )α and γuc us a prefix of γf (vc )α. Then u is an (a, b, c, β, γ)-fragility in f (w). We say that this fragility is propagated by f from the (a , b , c , β, γ)-fragility v.

Note that |u| ≥ |f (v)α| and more precisely u = f (v)αu for some word u . Observe that αu a is a prefix of f (a )α, αu b is a prefix of f (b )α and αu c is a prefix of f (c )α. This is an important fact as it shows that letters a, b and c depend only on f and on letters a , b and c : if a word contains an (a , b , c )-fragility then f (w) contains an (a, b, c)-fragility. For instance, if A = {a, b, c} and w contains an (a, b, c)-fragility u, then this fragility is propagated by the morphism f = [a, ab, ac]. Note that |f (v)α| ≤ |u| implies |v| < |u|. Hence the propagation of a fragility makes it strictly longer.

Some fragilities can also be not propagated. For instance, the morphism [a, ab, abc] does not propagate the (b, a, c)-fragilities.

Lemma 5.1. Let w be an infinite word (not necessarily LSP) and let f be an R-bLSP morphism defined over alph(w). Fragilities of f (w) are exactly the fragilities associated with f and the fragilities of w propagated by f . Proof. From the definitions given before the lemma, the fragilities associated with f and the fragilities of w propagated by f are fragilities of f (w). Let u be an (a, b, c, β, γ)-fragility of f (w).

If u = ε, it follows from the definition of an (a, b, c, β, γ)-fragility that a = first(f (w)) and βb, γc are factors of f (w). Now observe that, still by the same definition, a ∈ {b, c}. Thus by the definition of R-bLSP morphisms, a = first(f ) and βb, γc belong to Fact(f (alph(w))). The fragility u is associated with f .

Assume from now on that u is not empty. Let α = first(f ). Considering the last occurrence of α in u, observe that the word u can be decomposed in a unique way as u = f (v)αx with v, x words such that |x| α = 0. As u is an (a, b, c, β, γ)-fragility of f (w), there exist words w 1 , w 2 and w 3 such that: By the definition of an R-bLSP morphism, there exist letters a , b , c such that f (a ) = αxw 1 , f (b ) = αxw 2 , f (c ) = αxw 3 . These letters a , b , c are pairwise distinct since letters a = first(w 1 α), b = first(w 2 α) and c = first(w 3 α) are pairwise distinct. Moreover va is a prefix of w and words βvb and γvc are factors of w (remember that α marks the beginning of letters in f (w) as f is an R-bLSP morphism and as, for letters x and y, last(f (x)) = y implies x = y). Hence the word v is an (a , b , c , β, γ)-fragility of w. This fragility is propagated by f .

• |w 1 | α = |w 2 | α = |w 3 | α = 0; • f (v)αxw 1 α is a prefix of f (w) and a = first(w 1 α); • βf (v)αxw

A first automaton

Lemma 5.1 shows that bLSP morphisms act locally on fragilities on the words. One can then construct an automaton to store the actions of these morphisms on fragilities of LSP words (one can do this for arbitrary words but this is not needed for our purpose). It is important to note that the exact alphabet on which a morphism is applied has a lot of importance. For instance, if w is an infinite word over {a, b, c} and if f = λ abc = [a, ab, abc], f (w) contains an (a, b, c)-fragility if and only if c occurs in alph(w). It is also important to note that the automaton will not follow the fragilities themselves but only the 3-tuples of letters (a, b, c) for which a fragility occurs. Given an infinite word w, let Frag(w) be the set of 3-tuples (a, b, c) of letters such that w contains an (a, b, c)-fragility.

Let A 1 = (S R-bLSP , Q 1 , ∆ 1 ) be the automaton without initial and final states defined by:

• The alphabet of A 1 is the set S R-bLSP of R-bLSP morphisms over the alphabet A.

• The set of states is the set {(alph(w), Frag(w)) | w LSP over A}.

• A 3-tuple ((A 1 , F 1 ), f, (A 2 , F 2 )
) is a transition of A 1 if and only if the following condition holds:

1. f |A 1 = f (f is exactly defined on A 1 ; this point is important as it prevents from having a morphism in the transition that creates a fragility which is not related to A 1 ; we need to control new and propagated fragilities); 2. A 2 = alph(f (A 1 )) (each letter of A 2 occurs in at least one image of a letter in A 1 ).

3. if (a, b, c) ∈ A 1 then f is not LSP (a, b, c)-breaking;

4. F 2 is the union of the set of 3-tuples (a, b, c) for which an (a, b, c)-fragility is associated with f and the set of 3-tuples (a, b, c) propagated by f from (a , b , c )-fragilities with (a , b , c ) in F 1 .

One can observe that for each state q of the automaton and each R-bLSP morphism f , there exists at most one state q such that (q, f, q ) is a transition. There is no transition when q = (B, F ), (a, b, c) ∈ F and f is (a, b, c)-breaking.

By the definition of the automaton, Lemma 5.1 has the following immediate corollary.

Corollary 6.1. Let w be an LSP word, let A 0 , A 1 , . . . , A k be alphabets and let f 1 , f 2 , . . . , f k be R-bLSP morphisms such that:

• A 0 = alph(w); • for all i, 1 ≤ i ≤ k, A i = alph(f i • • • • • f 1 (w)); • For all i, 1 ≤ i ≤ k, f i • • • • • f 1 (w) is LSP.
Then in A 1 there is a unique path labeled by On the alphabet {a, b}, as there is no fragility, the automaton A 1 has only three states (see Figure 2): one state for each of the alphabets {a}, {b}, {a, b}.

f 1 • • • f k from the state (alph(w), Frag(w)) to a state (A k , F ). Moreover F is the set of 3-tuples (a, b, c) for which there exist (a, b, c)-fragilities in f k • • • • • f 1 (w). {a}, ∅ a → a {b}, ∅ b → b {a, b}, ∅ L a , L b L b |{a} : a → ba L a |{b} : b → ab
The automaton for the alphabet {a, b, c} is provided in Figure 4. Here follow some explanations. We say that w has fragilities of type a (resp. of type b, of type c) if it has (a, b, c)-fragilities or (a, c, b)fragilities (resp. (b, a, c)-fragilities or (b, c, a)-fragilities; (c, a, b)-fragilities or (c, b, a)-fragilities). Figure 3 shows the action of R-bLSP morphisms on fragilities. One can observe that, for this ternary case, the type of a propagated fragility is the same then the type of the fragility from which it is propagated. The presentation of the automaton in Figure 4 is split into two parts. The first part contains the seven states corresponding to words without fragilities. The second part contains the three states corresponding to words with fragilities. In the first part, morphisms with entries "-" denote restrictions of endomorphisms: "-" means "not defined". In the second part, entries "*" denote any possibility of image (defined or not defined as this kind of entries correspond to restriction of λ . morphisms). There exist numerous transitions from the first part to the second one. The outgoing side of the transition is presented in the first part and the in-going side of the transition is presented in the second part. For instance there exists a transition from state ({b, c}, ∅) to state ({a, b, c}, type a) labeled by morphism [-, ab, abc].

For larger alphabets, the number of states explodes. This is due to the increasing number of subalphabets but also to the fact that the set of fragilities may contain more than one fragility. For instance, any LSP morphism f such that f (a) = abcd creates simultaneously several fragilities: in the image of an infinite word containing a, the empty word is an (a, b, c)-fragility, an (a, b, d)-fragility and an (a, c, d)fragility.

The S-adic Characterization of LSP words

Let w be an LSP word. By Proposition 3.1, w is S R-bLSP -adic. Let f = (f k ) k≥0 be its fitted directive word over S R-bLSP . Let also (w k ) k≥1 be the sequence of infinite words verifying: Let A R-bLSP (A), or simply A R-bLSP , be the automaton obtained by reversing transitions in A 1 and considering all states as initial. As f is fitted, an immediate consequence of Corollary 6.1 is that there exists an infinite path labeled by f in A R-bLSP starting on state (alph(w), Frag(w)). The next theorem states that conversely if such an infinite path exists for an S R-bLSP -adic word w, then w is LSP. If q = (X, F ) is a state of A R-bLSP , let alph(q) = X and Frag(q) = F . Theorem 7.1. A word w is LSP if and only if it is S R-bLSP -adic and there exists an infinite path in A R-bLSP labeled by the fitted directive word of w.

w 1 = w; for all k ≥ 1, w k = f k (w k+1 ). {a}, ∅ {b}, ∅ {c}, ∅ {a, b}, ∅ {a, c}, ∅ {b, c}, ∅ {a, b, c}, ∅ [a, -, -] [-, b, -] [-, -, c] [a, ab, -] [ba, b, -] [a, -, ac] [ca, -, c] [-, b, bc], [-, cb, c] [ca, cb, -] [ba, -, bc] [-, ab, ac] [ba, -, -] [ca, -, -] [-, ba, -] [-, bc, -] [-, -, ac] [-, -, bc] type a type b type c [-, ab, abc] [-, acb, ac] [-, b, bac] [-, cab, c] type a type b type c [a, acb, -] [bca, b, -] [ca, cab, -] [cba, cb, -] type a type b type c [a, -, abc] [ba, -, bca] [bca, -, bc] [cba, -, c]
Applying this theorem allows to provide particular examples of LSP words. For instance it can be verified that all standard episturmian words are LSP [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF][START_REF] Justin | Episturmian words and episturmian morphisms[END_REF]. These words are the S-adic words where S is the set of morphisms containing morphisms L α and their restrictions. In particular, if A = {a 1 , . . . , a k }, the k-bonacci word B a 1 ,...,a k (or Tribonacci word, also denoted T, when k = 3) which is the fixed point of the morphism

L a 1 • • • • • L a k is LSP.
Observe that B a 1 ,...,a k contains no fragility as its fitted directive word is recognized using only the state ({a 1 , . . . , a k }, ∅) in A R-bLSP . It may be observed that the fitted directive word of an LSP word can be recognized by several paths. For instance the fitted directive word of the Tribonacci word is the word (L a L b L c ) ω which is recognized by four paths starting respectively from states ({a, b, c}, ∅), ({a, b, c}, type a), ({a, b, c}, type b) and ({a, b, c}, type c).

Proof of Theorem 7.1. The only if part was already mentioned before the statement of the theorem. Assume, by contradiction, that there exists in A R-bLSP a path labeled by a directive word f of a word w which is S R-bLSP -adic but not LSP (for this part of the proof it is not needed that f is a fitted directive word). Such a word contains a left special factor u that is not a prefix of w. Among all possible 3-tuples (f , w, u), choose one such that |u| is minimal.

For n ≥ 1, we denote by f n the n th letter of f and w n the word directed by (f k ) k≥n (w 1 = w ; w 2 is the word directed by f 2 f 3 • • • ; w n = f n (w n+1 ) for all n ≥ 1).

The first three steps do not depend on the automaton.

Step 1: w 2 contains a fragility First observe that |u| ≥ 2. Indeed we have |u| = 0 as the empty word is a prefix of w. Moreover, by the structure of images of the R-bLSP morphism f 1 , only the letter first(f 1 ) can be left special, whence |u| = 1.

Let α = first(w) = first(f 1 ). Considering the last occurrence of α in u, the word u can be decomposed in a unique way u = f 1 (v)αx with v, x words such that |x| α = 0.

As u is left special, there exist distinct letters β and γ such that βu and γu are factors of w. As the letter α marks the beginning of images of letters in w and as for all letters δ, f 1 (δ) ends with δ, we deduce that βv and γv are factors of w 2 . As |v| < |u| and by the choice of the 3-tuple (f , w, u), the word v is a prefix of w 2 . Consequently f 1 (v)α is a prefix of w and so x = ε.

Assume there exists a unique letter b such that βvb is a factor of w 2 and u is a prefix of f (vb). Assume also that b is the unique letter c such that γvc is a factor of w 2 and u is a prefix of f (vc). As u is not a prefix of w = f 1 (w 2 ) and as u is a prefix of f 1 (vb), the word vb is not a prefix of w 2 . By the choice of the

3-tuple (f , w, u), |vb| ≥ |u|. As |v| < |u|, we get |vb| = |u| = |f 1 (v)αx|. As |f 1 (v)| ≥ |v|, it follows x = ε: a contradiction.
From what precedes, we deduce the existence of two distinct letters b and c such that βvb and γvc are factors of w 2 with u a prefix of f 1 (vb) and f 1 (vc). As u is not a prefix of w = f 1 (w 2 ), the letter a that follows the prefix v of w 2 is different from b and c. Hence the word w 2 is (a, b, c, β, γ)-fragile and v is such a fragility.

Step 2: f 1 is LSP (a, b, c)-breaking By the definition of letters b and c at Step 1, the word αx is a common prefix of f 1 (b) and f 1 (c). Also as u = f 1 (v)αx is not a prefix of w while f 1 (v)a is a prefix of w, the word αx is not a prefix of f 1 (a). By Corollary 4.5, f 1 is (a, b, c)-breaking.

Step 3: origin of fragilities of w 2 Applying iteratively Lemma 5.1, as the lengths of propagated fragilities decrease with the propagation, we deduce the existence of an integer n ≥ 2 and a sequence of 3-tuples of pairwise different letters

(a i , b i , c i ) i∈{2,••• ,n} , a sequence (v i ) i∈{2,••• ,n}
of words such that:

• v i is an (a i , b i , c i , β, γ)-fragility of w for all i ∈ {2, • • • , n}; • (a 2 , b 2 , c 2 ) = (a, b, c) and v 2 = v; • |v i+1 | < |v i | for all i ∈ {2, • • • , n -1} (v i is a fragility propagated by f i from v i+1 ); • v n = ε (origin of the fragilities); • the words v i a i , βv i b i , γv i c i are respectively prefixes of f i (v i+1 a i+1 )α i , βf i (v i+1 b i+1 )α i , γf i (v i+1 c i+1 )α i where α i = first(f i ) for i ∈ {2, • • • , n -1}
(by the definition of propagated fragilities);

• a n = first(f n );

• βb n , γc n belong to f n (alph(w n+1 )) (by the definition of new fragilities).

Step 4: conclusion. Let (q i ) i≥1 be the sequence of states along the path labeled by f : for all n ≥ 1, (q n , f n , q n+1 ) is a transition of A R-bLSP . At the end of Step 3, we learn that there exists an (a n , b n , c n )-fragility in f n (w n+1 ). Hence a n , b n , c n are pairwise distinct letters. Especially as a n = first(f n ) ∈ {b n , c n } by properties of R-bLSP morphisms, the words βb n and γc n are factors of images of some letters, say b n and c n . By the definition of the automaton A R-bLSP , alph(q n ) = alph(f n (alph(q n+1 ))) and f n is defined exactly on alph(q n+1 ). This implies that b n and c n belong to alph(q n+1 ) and a n , b n and c n belong to alph(q n ). Moreover, as βb n , γc n are factors of words in f n (alph(q n+1 )), we deduce that (a n , b n , c n ) ∈ Frag(q n ).

Using a backward induction and the definition of the automaton A R-bLSP , we can show that for all i, 2 ≤ i ≤ n, (a i , b i , c i ) ∈ Frag(q i ). Especially (a 2 , b 2 , c 2 ) ∈ Frag(q 2 ). As (q 1 , f 1 , q 2 ) is a transition of A R-bLSP , by the definition of transitions, f 1 is not LSP (a 2 , b 2 , c 2 )-breaking: a contradiction with Step 2 as (a, b, c) = (a 2 , b 2 , c 2 ).

Morphisms preserving LSP words

As explained at the end of [START_REF] Richomme | A characterization of infinite LSP words[END_REF], one can ask for a simpler characterization for LSP words. In the context of substitutive-adicity, the next theorem shows that this is not possible: given any set S of morphisms such that LSP words are S-adic, one needs a way to distinguish directive words of LSP words. Theorem 8.1. Let A be an alphabet containing at least three letters. There exists no set S of morphisms such that the set of LSP infinite words over A is the set of S-adic words.

The main idea of the proof lies on the fact that, given any set S of morphisms, these morphisms preserve the property of being an S-adic word: the image of any S-adic word by an element of S is still S-adic. Thus in this section, we first characterize the set of endomorphisms preserving the LSP property (the image of any LSP word is also LSP) and then show the existence of an LSP word that cannot be decomposed over this set of morphisms.

Some Morphisms

Let L(A) = {L a | a ∈ A}. When the context will be clear, we will just write L instead of L(A). Observe that, in the binary case, S bLSP = L. Lemma 8.2. A bLSP morphism preserves the LSP property if and only if it belongs to L.

Proof. Let f be a bLSP morphism that does not belong to L. There exist three pairwise distinct letters a, b and c such that f (a) = a, f (b) = ab, f (c) = abc. As previously mentioned (see Example 4.1) there exists an LSP word w that contains an (a, b, c)-fragility (see the beginning of Section 4). That is, for a word u and distinct letters β, γ, ua is a prefix of w while βub and γuc are factors of f (w). Then f (u)aa is a prefix of f (w) while βf (u)ab and γf (u)ab are factors of w: f (w) is not LSP and so f does not preserve the LSP property.

Conversely for any LSP word w and any letter α, let us prove that L α (w) is also LSP. Assume by contradiction that L α (w) is not LSP and consider a word u and two distinct letters a and b, such that ub is a left special factor of L α (w) while ua is a prefix of L α (w). Let β and γ be distinct letters such that βub and γub are factors of L α (w). Observe that at least one of the letters a and b is different from α, and also at least one of the letters β and γ is different from α. The structure of L α (any letter different from α is preceded by α in the image of any word) implies that u ends and begins with the letter α (in particular it is not empty) and so can be decomposed u = L α (v)α for a word v. One can deduce that va is a prefix of w while βvb and γvb are factors of w: a contradiction with w LSP.

Observe that Lemma 8.2 does not extend to R-bLSP morphisms. For instance [-, -, abc, ad] preserves the LSP property for words over {c, d}.

It is important also to observe that the first part of the proof of Lemma 8.2 also shows the next result.

Lemma 8.8. Let f be a nonerasing morphism that preserves the LSP property for infinite words. Assume there exist two distinct letters a and b such that f (a) = f (b). Then for all letters α, f (α) ∈ f (a) + , that is, f ∈ P LSP .

Proof. Assume by contradiction that there exists a third letter c such that f (c) = f (a) = f (b). Let u = f (a). Consider the Tribonacci word T over {a, b, c}. By induction, one can prove that, for all n ≥ 1, L n-1 a (T) begins with the prefix a n ba n ca and contains the word a n ba n+1 ba n . As L n-1 a (T) is an standard episturmian word, it is LSP.

Choose an integer n such that n ≥ 1 and |f (a n ba n c)u| ≤ |f (a n ba n+1 ba n )|-|u|. Let m, p be the integers such that f (a n ba n ) = u p and f (a n ba n+1 ba n ) = u m+1 . As f preserves the LSP property, f

(L n-1 a (T)) is LSP. As u m+1 is a factor of f (L n-1 a (T)) and u is a prefix of f (L n-1 a (T)), by Lemma 8.7, u m is a prefix of f (L n-1 a (T)). Also u p f (c)u is a prefix of f (L n-1 a (T)) and |u p f (c)u| ≤ |u m |. Thus f (c
) is a power of u or the last occurrence of u in u p f (c)u is an internal factor of u 2 (i.e. uu = pus with p and s non-empty). The former case is not possible as by hypothesis f (c) = u. The latter case contradicts the primitivity of u (as it implies u = ps = sp, a well-known equation which implies that u is not primitive -see, e.g., [START_REF] Lothaire | Combinatorics on Words[END_REF]). Lemma 8.8 implies that Proposition 8.6 is a corollary of the next result. Proposition 8.9. Let f : A * → B * be a nonerasing morphism that preserves the LSP property for infinite words. Assume that for all letters a and b, the words f (a) and f (b) do not have the same primitive root. Then f ∈ S * R-bLSP U.

Proof. We proceed by steps. Each step provides a stronger property on f .

Step 1. For all distinct letters a and b in A, f (a) is not a suffix of f (b).

Proof. Assume by contradiction that f (a) is a suffix of f (b) for two distinct letters a and b. Let ≥ 0 be the greatest integer such that f (a) is a prefix of f (b). The word f (a 3+ ) is a factor of f (baab). Let w be any LSP word containing the factor baab and having aba as a prefix (for instance the Fibonacci word). By Lemma 8.7, f (a) 2+ is a prefix of f (w). Also f (w) begins with f (aba). By the definition of , this is possible only if We observe that for any LSP word w containing a and b, the word u is a prefix of f (w) (remember that f preserves the LSP property, hence f (w) is LSP and its left special factors are prefixes of it). As w can be chosen with a as first letter or with b as first letter, this implies that u is a prefix of f (a) and of f (b).

f (b) = f (a) u 1 , f (a)
Let w be any LSP word beginning with aab and containing the word baaab (for instance the word L a (F) with F the Fibonacci word). Let be the greatest integer such that u is a prefix of f (a). Observe ≥ 1. The word αu +1 is a factor of f (aa) and the word βu +1 is a factor of f (ba). So u +1 is a left special factor of f (w) and so it is one of its prefixes. By the definition of , this implies that f (a) = (u 1 u 2 ) u 1 with u = u 1 u 2 and u 2 a prefix of f (a). Now using the fact that u +1 is a prefix of f (aa), we deduce that αu +2 and βu +2 are factors of f (baaa) and so of f (w): u +2 is a left special factor of f (w). Thus f (w) begins with u u 1 u 2 u 1 u 2 and with f (aa

) = u u 1 u 1 u 2 u -1 u 1 as ≥ 1. Hence u 1 u 2 = u 2 u 1 . By [15, Prop. 1.3.2], √ u 1 = √ u 2 which implies that f (a) = √ u.
Exchanging the roles of a and b, we deduce similarly that f (b) = √ u. Hence f (b) = f (a): a contradiction with our hypotheses.

From Step 2, we know that f = g • r for some renaming morphism r and some morphism g such that last(g(α)) = α for all letters α ∈ r(A). Observe that f preserves the LSP property for words over A if and only if g preserves the LSP property for words over r(A). Moreover the composition of any element of U with r is, when defined, an element of U. Thus if Proposition 8.9 holds for g, it also holds for f . Hence replacing f by g, from now on, we assume that last(f (α)) = α for all letters α.

Step 3. If the images of two distinct letters begin with the same letter, then all images of letters begin with the same letter.

Proof. Assume k = #A ≥ 3 and that for two distinct letters α, β, first(f (α)) = first(f (β)). Recall that we assumed after Step 2 that for all δ in A, last(f (δ)) = δ. Now consider the morphism g = λ a 1 ...a k (g(a i ) = a 1 . . . a i for all i = 1, . . . , k; a 1 , . . . , a k are pairwise distinct letters). This morphism is bLSP. As said just after Theorem 7.1 the k-bonacci word B a 1 ,a 2 ,a 3 ,...,a k contains no fragility. Hence g(B a 1 ,a 2 ,a 3 ,...,a k ) is LSP. As f preserves the LSP property, f (g(B a 1 ,a 2 ,a 3 ,...,a k )) is LSP: it begins with f (a 1 ) and contains the word f (a 1 a 2 a 3 ) (B a 1 ,a 2 ,a 3 ,...,a k begins with a 1 a 2 a 1 a 3 and g(a 3 ) = a 1 a 2 a 3 ). When a 2 = α and a 3 = β, denoting by a the first letter of f (α), we see that a 1 a and αa are factors of f (g(w)) showing that a is a left special factor of f (g(w)), and so a prefix of f (a 1 ). Consequently, a is the first letter of f (a 1 ) whatever a 1 ∈ A \ {α, β}.

Step 4. If a letter is left special in f (A), then all images of letters begin with the same letter.

Proof. Here we assume that for a letter α, there exist distinct letters β and γ such that βα and γα are both factors of images of letters. For any LSP word w containing two letters whose images contains βα and γα, these words are factors of f (w). As f preserves the LSP property, f (w) is LSP and so must begin with the letter α. As for any letter x, one can choose w in such a way that it begins with x, Thus all images of letters must begin with the same letter (the letter α).

Step 5. If there exists a letter a such that a letter occurs twice in f (a), then all images of letters begin with the same letter.

Proof. Let α be a letter occurring twice in f (a). Choose α such that its first occurrence is the leftmost as possible. Assume α is not the first letter of f (a). If α is left special in f (a), then the claim is clear by Step 4. So we can assume that all occurrences of α are preceded by the same letter β. Hence we should have chosen β instead of α: a contradiction. So α is the first letter of f (a). Let b be a letter in A different from a. By Step 3 we only have to consider the case where f (b) begins with a letter γ different from α.

There exists an infinite LSP word w beginning with a and containing the word aba (for instance the Fibonacci word). In f (aba), only the first letter α of f (w) can be left special. But there also exist infinite LSP words beginning with b and containing the word aba (exchange the roles of a and b in the Fibonacci word). As f (b) does not begin with α, this letter α cannot be left special in f (aba).

Let u be the word such that |u| α = 0 and αuα is a prefix of f (a). As no letter is left special in the factor f (ab)αuα of f (aba), each occurrence of α in f (ab)αuα is preceded by αu: αu is a period of f (ab). As αu is a prefix of f (a), f (ab) is a power of αu. For some words x and y and some integers k and with k ≥ 1, ≥ 0, we have u = xγy, f (a) = (αxγy) k αx, f (b) = γy(αxγy) .

Observe that f (ba) = (γyαx) k+ +1 . Consider an LSP word w beginning with babbabab (for instance the word obtained from the Fibonacci word exchanging the roles of a and b). The word f (w) contains (f (ba)) 2 = (γyαx) 2(k+ +1) and so by Lemma 8.7, (γyαx) 2k+2 +1 is a prefix of f (w): in particular as k ≥ 1, (γyαx) +1+k+ γyα is a prefix of f (w). But f (w) begins with f (babb) that begins with (γyαx) +1+k+ γyγ. This contradicts the fact that α = γ.

Step 6. If a letter occurs at least twice in f (A), then all images of letters begin with the same letter.

Proof. Assume α occurs twice in f (A). After Step 5, we can assume that α occurs in f (a) and f (b) for two distinct letters a and b. For any letter c (possibly a or b), there exists an LSP word w beginning with c and containing the word aba. Thus if α is left special in f (aba), α is the first letter of f (c) for all letters c.

Hence assume that α is not left special in f (aba) nor in f (bab). Thus all occurrences of α in f (aba) and in f (bab) are preceded by the same letter β. Possibly replacing iteratively α by β, we see that we can choose α as the first letter of f (a) or of f (b). Assume without loss of generality that it is the first letter of f (a). By Step 3, we can assume that α is not the first letter of f (b). As α is not left special in f (ba) and as f (b) ends with b (so bα is a factor of f (ba)), b has two occurrences in f (b). By Step 5 all images of letters begin with the same letter.

Step 7. End of the proof of Proposition 8.9.

The proof acts by induction on ||f || = a∈A |f (a)|. When ||f || = #A, by Step 2, f is a renaming morphism: it belongs to U. Assume ||f || > #A and that f does not belong to U. This means that a letter occurs at least twice in f (A). By Step 6, all images of letters begin with the same letter. Let a denote this letter. By Step 2, for all distinct letters x and y in A, last(f (x)) = last(f (y).

Observe that as f preserves the LSP property for infinite words, at one letter can be left special in f (A): this letter must be the letter a. Thus there exist an R-bLSP morphism g 1 and a morphism h, such that f = g 1 • h and g 1 is defined over alph(h(A)). Assume by contradiction that h does not preserve the LSP property for infinite words. This means there exists an infinite LSP word w such that h(w) is not LSP. By Lemma 3.3, f (w) = g(h(w)) is neither LSP: a contradiction. Hence h preserves the LSP property for infinite words. By the definition of R-bLSP morphisms, ||g 1 || ≥ #A + 1 and so ||h|| < ||f ||. By induction, h ∈ S * R-bLSP U: this also holds for f and Proposition 8.9 holds by induction.

Characterization of endomorphisms preserving LSP infinite words

Theorem 8.10. The set of nonerasing endomorphisms over an alphabet A that preserve the LSP property for infinite words over A is L * P erm ∪ P LSP Proof. Permutation morphisms (elements of P erm) and the elements of P LSP preserve the LSP property for infinite words. By Lemma 8.2, the elements of L also preserve this property. Hence any element of L * P erm ∪ P LSP preserves the LSP property for infinite words. Conversely let f be a nonerasing endomorphism over A * that preserves the LSP property for infinite words. Assume f ∈ P LSP . By Lemma 8.8 and the definition of P LSP , for all letters a and b, the words f (a) and f (b) do not have the same primitive root. By Proposition 8.9, there exist an integer n ≥ 0, n R-bLSP morphisms g 1 , g 2 , . . . , g n and an element ν of U such that f

= g 1 • • • • • g n • ν.
Let B = alph(ν(A)) and define the alphabets (A i ) i=n,n-1,...1 by A n = alph(g n (B)) and for i such that n -1 ≥ i ≥ 1, A i = alph(g i (A i+1 )). By Property 2.3(1), for any i in {n -1, . . . , 1}, A i+1 ⊆ A i and B ⊆ A n . Note that A 1 = A. Hence B ⊆ A. As ν belongs to U, #B ≥ #A. Hence A = B and ν is a permutation morphism. It follows that f preserves the LSP property for infinite words if and only if

g 1 • • • • • g n preserves it.
Thus from now on we assume that ν is the identity and

f = g 1 • • • • • g n . From
what precedes, we have A i = A for all i in {n, . . . , 1}. Hence all morphisms g i are endomorphisms. By definitions, the only R-bLSP morphisms that are endomorphisms are LSP morphisms.

To end we prove by induction that each endomorphism g i belongs to L. By Lemma 3.3, g n must preserve the LSP property for infinite words (otherwise morphisms g i • • • • • g n (1 ≤ i ≤ n) and so f would not preserve the LSP property for infinite words). By Lemma 8.2, it must belong to L. Assume we have already proved that g m+1 , . . . , g n ∈ L for some integer m, 1 ≤ m < n. By Lemma 8.3 if g m ∈ L, then g m is (a, b, c)-breaking for some pairwise distinct letters a, b and c. Let w be an (a, b, c)-fragile LSP word. By Lemma 8.4,

g m+1 • • • • • g n (w) is (a, b, c)-fragile and so g m • • • • • g n (w) is not LSP. By Lemma 3.3, we deduce that g 1 • • • • • g m • • • • g n (w) = f (w)
is not LSP: a contradiction with the fact that f preserves the LSP property for infinite words. Then for all pairwise distinct letters a, b and c, g m is not (a, b, c)-breaking: by Lemma 8.2 g m belongs to L. Hence by induction g i ∈ L for all i, 1 ≤ i ≤ n.

A particular word

To end the proof of Theorem 8.1, we need an LSP word defined on three letters that cannot be decomposed on two words. Let ξ a (resp. ξ b , ξ c ) be the fixed point of From Theorem 7.1, ξ a , ξ b and ξ c are LSP words as there exist infinite paths labeled by (λ abc λ bca λ cab ) ω , (λ bca λ cab λ abc ) ω and (λ cab λ abc λ bca ) ω in the automaton A bLSP . Lemma 8.11. There does not exist two words u and v such that ξ a can be decomposed on {u, v}, that is, for any choice of the words u and v, ξ ∈ {u, v} ω .

f a = λ abc • λ bca • λ cab = [ababcababca, ababcababcaab, ababc] (resp. f b = λ bca • λ cab • λ abc , f c = λ cab • λ abc • λ bca ). Considering the permutation π = [b, c, a], observe that π • λ abc = λ bca • π, π • λ bca = λ cab • π,
Proof. First observe that ξ a is not periodic (it has infinitely many left special factors). Then if X is a set of words such that ξ a ∈ X ω , the cardinality of X is at least two. Assume by contradiction that there exist two words u and v such that ξ a ∈ u{u, v} ω . Choose u and v such that |uv| is minimal. Observe also that u begins with the letter a as it is a prefix of ξ a . It is important to remark that for any word w beginning by a, there exists a word w such that w = λ abc (w ). We distinguish three cases depending on the first letter of v.

Case v begins with the letter a. Then u = λ abc (u ) and v = λ abc(v ) and ξ

b ∈ {u , v } ω . As abc occurs in u or v, |u v | ≤ |uv| -2. As ξ a = π(ξ b ), we get ξ a ∈ {π(u ), π(v )} ω with |π(u )π(v )| < |uv|.
This contradicts the choice of u and v.

Case v begins with the letter b. Let I be the set of integers such that uv i u occurs in ξ a : ξ a ∈ {uv i | i ∈ I} ω . Note that #I ≥ 2 since ξ a is not periodic. By the definition of λ abc , since uv occurs in ξ a = λ abc (ξ b ) and since v begins with b, u ends with the letter a. This is also the case for v if I = {0, 1}, that is, if vv occurs in ξ a .

Assume that vv occurs in ξ a (there exists j ∈ I with j ≥ 2). There exist words u 1 , v 1 such that u = λ abc (u 1 )a and av = λ abc (v 1 )a. As

ξ a = λ abc (ξ b ), ξ b ∈ {u 1 v i 1 a | i ∈ I} ω .
As aba and abca must occur at least once each in uv, |u 1 v 1 | ≤ |uv| -4. Both words u 1 and v 1 are not empty, otherwise ξ a ∈ {π(u 1 ), b} ω or ξ a ∈ {π(v 1 ), b} ω : a contradiction with the choice of u and v.

Remember that ξ b = λ bca (ξ c ). As v 1 v 1 a occurs in ξ b (j ≥ 2 belongs to I), the word v 1 ends with bc. and consequently the word v 1 begins with a or b.

Assume that v 1 begins with a. Then

ξ b ∈ {u 1 a(v 1 a) i | i ∈ I} ω where v 1 is the word such that v 1 = av 1 . Hence ξ a = π(ξ b ) ∈ {π(u 1 a)π(v 1 a) i | i ∈ I} ω . As |π(u 1 a)π(v 1 a)| = |u 1 av 1 | < |uv|, this contradicts the choice of u and v.
Thus v 1 begins with b. We still have 3 is not a factor of ξ b , I ⊆ {0, 1, 2}. Also 0 ∈ I implies that u 1 ends with bc and so (bc) 3 = bcv 2 1 is a factor of ξ b . Thus I = {1, 2} and ξ b ∈ {u 1 bca, u 1 bcbca} ω . As u 1 cannot ends with bc, it ends with b or bca. Then bbca or bcabca is a factor of ξ b which implies that ba or aa is a factor of ξ c . Both are impossible. Hence v 2 = ε. As v 2 1 a = (λ bca (v 2 )bc) 2 a is a factor of ξ b , the word v 2 cv 2 a is a factor of ξ c = λ cab (ξ a ). So v 2 must end with the letter c. As ccc is not a factor of ξ c , v 2 does not begin with c: its first letter is a. This implies that each occurrence of v 2 in ξ c = λ cab (ξ a ) is preceded by the letter c. Hence each occurrence of λ bca (v 2 ) in ξ b is preceded by bc. It follows that the word u 1 must end with bc. This word u 1 also begins with b as it is a prefix of ξ b . Then there exists a word u 2 such that u 1 = λ bca (u 2 )bc. We get ξ c ∈ {u 2 (cv 2 ) i a | i ∈ I} ω . Recall that v 2 begins with a and ends with c. There exists a word v 3 such that cv 2 = λ cab (v 3 )c. The word u 2 is not empty. Indeed otherwise ξ a = π 2 (ξ c ) ∈ {π 2 (cv 2 ), π 2 (a)} ω which contradicts the choice of u and v since |cv 2 | + |a| < |uv|.

ξ b = λ bca (ξ c ) ∈ {u 1 v i 1 a | i ∈ I} ω . Recall that v 1 ends with bc. There exists a word v 2 such that v 1 = λ bca (v 2 )bc. If v 2 = ε, as (bc)
• If 0 ∈ I, the factor u 2 a is a factor of ξ c and so the word u 2 ends with the letter c. As u 2 also begins with c as it is a prefix of ξ c , there exists a word u 3 such that u 2 = λ cab (u 3 )c. We get ξ a ∈ {u 3 (cv 3 ) i a | i ∈ I} ω .

• If 0 ∈ I, for a word u 3 , u 2 = λ cab (u 3 ) and ξ a ∈ {u 3 (v 3 c) i-1 v 3 a | i ∈ I} ω .

Assume v 3 = ε. Observe that 0 ∈ I since I contains an integer greater than or equals to 2 and cc is not a factor of ξ a Similarly I = {1, 2}. In this case, ξ a ∈ {u 3 a, u 3 ca} ω . As u 3 c is a factor of ξ a = λ abc (ξ b ), the word u 3 must end with ab implies that u 3 a ends with aba. As a is the first letter of u 3 , abaa is a factor of ξ a : a contradiction. Thus v 3 = ε. In both cases 0 ∈ I and 0 ∈ I, the factor u 3 v 3 c of ξ a ends with abc. As cv 3 a is a factor of ξ a , v 3 = b. Then v 3 ends with ab. Once again as u 3 begins with a, we get the factor abaa of ξ a : a contradiction that ends the study of the case "vv occurs in ξ a ".

To continue the study of the case "v begins with b", we have to study case I = {0, 1}. The word u begins with a and so there exist words u 1 and v 1 such that u = λ abc (u 1 )a, and either v = bλ abc (v 1 ) or v = bcλ abc (v 1 ). It follows that ξ b ∈ {u 1 a, u 1 bv 1 } ω or ξ b ∈ {u 1 a, u 1 cv 1 } ω . As ξ b = λ bca (ξ c ), the word u 1 ends with bc. As cc is not a factor of ξ b , necessarily ξ b ∈ {u 1 a, u 1 bv 1 } ω holds. Consequently there exist words u 2 and v 2 such that u 1 = λ bca (u 2 )bc and bv 1 = λ bca (v 2 ): ξ c ∈ {u 2 a, u 2 cv 2 } ω . Necessarily u 2 begins with c, the first letter of ξ c = λ cab (ξ a ). From the factor u 2 a we deduce that u 2 ends also with c: u 2 = λ cab (u 3 )c and cv 2 ∈ λ cab (v 3 ). It follows that ξ a ∈ {u 3 a, u 3 cv 3 } ω . From the factor u 3 c we deduce that u 3 ends with ab. Also u 3 must begin with a, the first letter of ξ a . Once again we find a factor abaa in ξ a : a contradiction. This ends the study of the case "v begins with b".

Case v begins with the letter c. Let I be defined as in the previous case: ξ a ∈ {uv i | i ∈ I} ω . Assume first that vv occurs in ξ a = λ abc (ξ b ). Then both words u and v ends with ab. There exist words u 1 and v 1 such that u = λ abc (u 1 )ab and v = cλ abc (v 1 )ab. Then ξ b ∈ {u 1 (cv 1 ) i b | i ∈ I} ω . As cv 1 c is a factor of ξ b = λ bca (ξ c ), the word v 1 is not empty and ends with b. The word u 1 c is a prefix of ξ b and so u 1 begins with b. As v 1 bu 1 is a factor of ξ b , bbb also occurs in ξ b : a contradiction. Hence vv does not occur in ξ a = λ abc . There exist words u 1 and v 1 such that u = λ abc (u 1 )ab and v = cλ abc (v 1 ). It follows that ξ b ∈ {u 1 b, u 1 cv 1 }. If u is empty, we find a contradiction with the choice of u and v as |bcv 1 | < |uv|. If u is not empty, it begins with b. The existence of the factor u 1 c shows that u 1 also ends with b. As u 1 bu 1 is a factor of ξ b , we deduce that bbb is a factor of ξ b : a final contradiction.

Proof of Theorem 8.1

Assume by contradiction that there exists a set S of morphisms such that the set of LSP infinite words is the set of S-adic words. Then all morphisms in S preserve the LSP property for infinite words over A.

Let ξ a be the word studied in Section 8.4. Recall that ξ a is LSP. So it is S-adic. By Lemma 8.11 ξ a cannot be decomposed on two words. It follows that any element f n occurring in a directive word (f n ) n≥1 ∈ S ω must be a morphism defined on at least three letters and cannot belong to P LSP . By Proposition 8.6, f n ∈ S * R-bLSP U. If f n is defined from the alphabet A n to the alphabet B n , then #A n ≤ #B n . As #B 1 = 3, by induction one can see that #A n = #B n = 3 for all n ≥ 1. This implies that f n = g n • π n with g n ∈ S * R-bLSP and π n a renaming morphism. As g n is an endomorphism over B n , g n ∈ S * bLSP . The fact that f n preserves the LSP property for infinite words (as all elements of S) implies that g n also preserves the LSP property. Hence g n ∈ L * P erm by Theorem 8.10 (ξ a is not periodic so g n cannot belong to P LSP ).

From what precedes ξ a = L α (w) for a letter α and an infinite word w. Indeed there must exist an integer k such that g k ∈ L + P erm and g i ∈ P erm for all 1 ≤ i ≤ k -1. As one can see that P ermP erm ⊆ P erm and P ermL ⊆ LP erm, relation ξ a = L α (w) follows. This is a contradiction with the fact that the word abca is a factor of ξ.

Final remarks

In [START_REF] Fici | Special factors and the combinatorics of suffix and factor automata[END_REF] G. Fici asked for a characterization of both finite and infinite words. As explained in [START_REF] Richomme | A characterization of infinite LSP words[END_REF], any finite LSP word can be extended to a longer LSP word and so: A finite word is LSP if and only if it is a prefix of an infinite LSP word. And thus any characterization of infinite LSP words provides naturally a characterization of finite LSP words (adding "is a prefix of" before the characterization of infinite LSP words).

A natural open question comes from the content of this paper. Does there exist an S-adic characterization of infinite words having at most one left special factor of each length (but not necessarily as a prefix)? Another question comes after Lemma 8.11. The proof of this result is rather technical while the result itself seems to be extendable. Let w be an infinite LSP word such that for all prefixes p, there exist at least three letters a, b and c such that ap, bp and cp are factors of w. Is it true that w cannot be decomposed on two words? More generally let w be an infinite word having infinitely many factors that have at least k left extensions (factors u such that there exist at least k distinct letters a 1 , . . . , a k with a i u factor of w for all i, 1 ≤ i ≤ k). Is it true that w cannot be decomposed on a set of k -1 or less words?

Figure 1 :

 1 Figure 1: Rooted tree associated with the morphism [a, ab, ac, acd, ace]

4 .

 4 for all β ∈ A, x, y ∈ A * , if |x| = |y| and if xβ and yβ are factors of words in f (A), then x = y; 5. for all letters β, γ, |f (β)| γ ≤ 1.

Definition 4 . 3 .Lemma 4 . 4 .

 4344 Let a, b, c be three pairwise distinct letters. A morphism f is LSP (a, b, c)-breaking, if for all (a, b, c)-fragile LSP word w, f (w) is not LSP.For instance, the morphism λ acb = [a, acb, ac] is (a, b, c)-breaking. Let w be an infinite LSP word and let f be an R-bLSP morphism defined on alph(w). The following assertions are equivalent:1. The word f (w) is not LSP; 2. There exist some pairwise distinct letters a, b, c such that w is (a, b, c)-fragile and the longest common prefix of f (b) and f (c) is strictly longer than the longest common prefix of f (a) and f (b);

Corollary 4 . 5 .

 45 An R-bLSP morphism is LSP (a, b, c)-breaking for pairwise distinct letters a, b and c if and only if the longest common prefix of f (b) and f (c) is strictly longer than the longest common prefix of f (a) and f (b).

  2 α and γf (v)αxw 3 α are factors of f (w) with b = first(w 2 α) and c = first(w 3 α).

Figure 2 :

 2 Figure 2: A 1 for the binary alphabet

Figure 3 :

 3 Figure 3: Ternary case: action of R-bLSP morphisms on fragilities

  , c}, type a {a, b, c}, type b {a, b, c}, type c * , abc] [ * , acb * ] [ * , * , bac] [bca, * , * ] [ * , cab, * ] [cba, * , * ]

Figure 4 :

 4 Figure 4: A 1 for the ternary alphabet

= u 1 u 2 Step 2 .

 22 for words u 1 and u 2 with u 2 = ε a prefix of f (a). But then, as f (a) is a suffix of f (b), we have ≥ 1 and f (a) = u 2 u 1 . Hence u 1 u 2 = u 2 u 1 . Thus u 1 = ε or the words u 1 and u 2 have the same primitive root by [15, Prop. 1.3.2]. It follows that f (a) and f (b) have also the same primitive root: a contradiction with our hypotheses. For all distinct letters a and b in A, last(f (a)) = last(f (b)). Proof. Assume by contradiction that last(f (a)) = last(f (b)) for two distinct letters a and b. By Step 1, f (a) is not a suffix of f (b) and f (b) is not a suffix of f (a). Hence there exist words u, u 1 , u 2 and distinct letters α, β such that f (a) = u 1 αu, f (b) = u 2 βu with u = ε.

  and π • λ cab = λ abc • π. Hence ξ a = π(ξ b ) and ξ b = π(ξ c ) and ξ c = a ).

 Lemma 8.3. If a bLSP morphism does not belong to L then it is (a, b, c)-breaking for some pairwise distinct letters a, b and c.

We will also need the following result. Lemma 8.4. Let α be a letter, a, b and c be three distinct letters and w be a word. The word w contains an (a, b, c)-fragility if and only if L α (w) contains an (a, b, c)-fragility.

Proof. The proof of the if part is similar to the converse part of the proof of Lemma 8.2 (if u is a word such that ua is a prefix of L α (w) and the words βub and γuc are factors of L α (w) with β = γ then u = L α (v)α for a word v such that va is a prefix of w and the words βwb and γwc are factors of w). The proof of the only if part is straightforward and is left to readers.

There exist morphisms that preserve the LSP property without being bLSP morphisms. We introduce some of them. First, we denote by U(A, B) (or simply U when the context is clear), the set of all nonerasing morphisms from A * to B * such that for each letter a in B, α∈A |f (α)| a ≤ 1 (each letter of B occurs at most once in the set of images of letters by f ). Here U stands for uniqueness. Renaming morphisms are nonerasing morphisms such that, for all a in A, |f (a)| = 1 and such that #{f (a) | a ∈ A} = A. Renaming morphisms are elements of U(A, B). Permutation morphisms (or simply permutations), that is, morphisms such that {f (a) | a ∈ A} = A, are particular renaming morphisms. Let P erm(A) (or simply P erm) denote the set of permutation morphisms.

Second, we denote by P LSP (A, B) (or simply P LSP when the context is clear), the set of all nonerasing morphisms from A * to B * for which there exists a word u over B with f (α) ⊆ u + for all letters α in A and u ω an LSP infinite word. Here P stands for periodic as any morphism in P LSP maps any infinite word to a periodic word. The proof of the next lemma follows quite immediately from the definitions and is left to the reader.

A first necessary condition

Proposition 8.6. Any nonerasing morphism f that preserves the LSP property for infinite words belongs to S R-bLSP (B) * U(A, B) ∪ P LSP (A, B).

The converse of this proposition is false as some R-bLSP morphisms do not preserve the LSP property (see the notion of LSP breaking morphisms).

The rest of the section is devoted to the proof of Proposition 8.6. We first need a technical lemma on factors of LSP infinite words. Lemma 8.7. Let w be an LSP word, u be a prefix of w and n ≥ 1 be an integer. If u n+1 is a factor of w, then u n is a prefix of w.

Proof. Let us consider an occurrence of the word u n+1 . Observing its extension on the left, we deduce that u = u 1 u 2 for two words u 1 and u 2 such that one of the following two possibilities hold:

• αu 2 (u 1 u 2 ) n+1 is a factor of w with α a letter different from last(u 2 u 1 ).

In the second case, the word (u 2 u 1 ) n is a left special factor of w. As w is LSP, (u 2 u 1 ) n is a prefix of w. This also holds in the first case. By hypothesis, u is a prefix of w. As n ≥ 1, both u and u 2 u 1 are prefixes of w: u = u 2 u 1 and consequently u n is a prefix of w.

For a non-empty finite word w, let √ w denote its primitive root, that is, the shortest word u such that w = u k for some integer k. We now show when the second condition of Proposition 8.6 happens.