Patrice Séébold
email: patrice.seebold@lirmm.fr

Sturmian images of non Sturmian words and standard morphisms §

Keywords: Sturmian words, Sturmian morphisms, standard morphisms, D0L systems, HD0L systems, Fibonacci word

We prove that if a Sturmian word is the image by a morphism of a word which is a fixed point of another morphism, then this latter word is mostly a Sturmian word, and the involved morphisms are Sturmian. This gives a characterization of Sturmian words that are generated by HD0L systems.

We also characterize the non Sturmian words which can be sent on Sturmian words by morphism, and the involved morphisms. We prove that the same Sturmian images can be obtained by using the standard morphisms of which the above morphisms are the conjugates, and we show how to obtain these Sturmian morphisms from their standard representatives.

Introduction

Sturmian words are infinite binary words of minimal complexity and Sturmian morphisms are those binary morphisms which preserve Sturmian words. These words and morphisms have been widely studied (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] for a general overview) and the Sturmian morphisms are very well known, especially those which generate Sturmian words (see, e.g., [START_REF] Séébold | On the conjugation of standard morphisms[END_REF]). However words generated by morphisms are only a particular case of words generated by D0L systems and, even more generally, by HD0L systems which are special subfamilies of Lindenmayer systems, a large class of mechanisms to produce infinite words which has been the object of hundreds of papers.

Surprisingly, it seems that Sturmian words and morphisms were not studied in the framework of Lindenmayer systems.

It is one of the aim of this paper to complete the knowledge of the links between Sturmian words and Sturmian morphisms when D0L systems are considered. First we shall characterize Sturmian words that are fixed points of morphisms (see Theorem 3.2 and Corollary 3.3). Except in the case of the identity morphism, these words are exactly the Sturmian words generated by morphisms (D0L systems where the starting word is a single letter). This complements Parvaix results [START_REF] Parvaix | Propriétés d'invariance des mots sturmiens[END_REF] about the action of morphisms on mechanical words.

The family of HD0L systems strictly contains that of D0L systems (roughly, an HD0L system needs two morphisms when a D0L system uses only one). One of the oldest examples is the Arshon word that Berstel [START_REF] Berstel | Mots sans carré et morphismes itérés[END_REF] proved to be generated by an HD0L system but not by a D0L system. However, as in the case § A preliminary version of this work was presented at "Journées annuelles SDA2" CNRS, Marseille, 2017 known examples use a very particular case of HD0L systems, namely the tag-systems introduced by Cobham [START_REF] Cobham | Uniform tag sequences[END_REF] (see also [START_REF] Allouche | Automatic Sequences[END_REF], Theorem 6.3.2).

Here, Theorem 4.3 and its Corollary 4.4 give an example of a wide family of words generated by HD0L systems which are not tag-systems (because a Sturmian morphism is never uniform), some of these words being not generated by D0L-systems (Proposition 4.5).

The other goal of this paper is to provide a sharp characterizion of the morphisms which transform non Sturmian words into Sturmian words. This is done with Theorems 5.2, 6.6 and 6.7.

After some definitions and basic results (Section 2) we study Sturmian fixed points of morphisms (Section 3). Then, in Section 4, we characterize the words whose images by a morphism are Sturmian (Section 4.1) and those which are an image by a morphism of a fixed point of another morphism (Section 4.2). Section 4 ends with an example of a Sturmian word generated by an HD0L system but not by a D0L system (Section 4.3). In Section 5 we detail the case of non Sturmian words whose images by morphisms are Sturmian words and we give a characterization of the morphisms which realize such a transformation. The last part of the paper (Section 6) is dedicated to evidence the link between these morphisms and the standard morphisms of which they are the conjugates, and to show how to directly obtain the former from the latter.

Preliminaries

We assume that the reader is familiar with basics of combinatorics on words (if necessary, see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]).

Let A = {a, b}. We will often consider a letter c ∈ A: the letter c is then defined by {c, c} = A. If u is a word over A and n a non-negative integer, u n is the power n of u, i.e., the word u • • • u made of n occurrences of u. We also use, as usual, the notation u * to denote the set {u n /n ∈ N} of all the powers of u.

A word x over

A is balanced if, for all u, v factors of x such that |u| = |v|, ||u| a -|v| a | ≤ 1 (since A is a two-letter alphabet, this implies ||u| b -|v| b | ≤ 1).
An infinite word x over A is ultimately periodic if there exist words y ∈ A * and z ∈ A + such that x = yz ω . Otherwise x is aperiodic.

Sturmian words are infinite words over A that are aperiodic and balanced.

We recall here a property of Sturmian words which is useful in the sequel.

Property 2.1 ([8], Proposition 2.1.3). If an aperiodic infinite word over A is not Sturmian, then it contains as factors both awa and bwb for some w ∈ A * .

A (endo)morphism on A is an application f from A * onto A * such that f (uv) = f (u)f (v) for every words u, v over A. The identity morphism on A is written Id A and in the whole paper, since there is no ambiguity, the composition of morphisms f • g will be denoted f g.

A morphism f on A is prolongable on the word u ∈ A + if f (u) begins with u and |f p+1 (u)| > |f p (u)| for every p ∈ N. In this case, f ω (u) = lim n→∞ f n (u) is a well defined infinite word which is called the infinite word generated by f . Here we remark that if f is not prolongable on u then |f (u)| u ≤ 1.

L systems

Words generated by morphisms are a particular case of a more general notion: words generated by Lindenmayer systems (see, e.g., [START_REF] Rozenberg | The Mathematical Theory of L systems[END_REF]). In the present paper, we only deal with two sorts of such systems (we use the definitions given in [START_REF] Honkala | The equality problem for purely substitutive words[END_REF]).

• A D0L system is a triple G = (A, σ, u) where σ : A * → A * is a morphism and u ∈ A + is a word. If σ is prolongable on u then G generates the infinite word σ ω (u).

• An HD0L system is a 4-tuple H = (A, σ, τ, u) where (A, σ, u) is a D0L system and τ is a morphism over A. If σ is prolongable on u then H generates the infinite word τ (σ ω (u)).

Sturmian morphisms

A morphism f on A is Sturmian if f (x) is a Sturmian word whenever x is a Sturmian word. For details about Sturmian words and morphisms, see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], Chapter 2.

In particular, it is a well-known fact that each Sturmian morphism can be obtained by composition from the three morphisms

E : a → b ϕ : a → ab φ : a → ba b → a b → a b → a Thus f is a Sturmian morphism if and only if f ∈ St = {E, ϕ, φ} * .
Writing convention. Let f be a Sturmian morphism. To a given decomposition of

f = f 1 f 2 • • • f n , f i ∈ {E, ϕ, φ}, is associated the word f 1 f 2 • • • f n over the alphabet {E, ϕ
, φ} (here E, ϕ, φ are considered as letters). We also denote this word f (f ∈ {E, ϕ, φ} * ) and we will use such an f either as the morphism or as the associated word, without noticing it when there is no ambiguity. Since E 2 = Id A , Sturmian morphisms can be obtained by an infinite number of compositions of E, ϕ and φ and are thus associated with an infinite number of words over the alphabet {E, ϕ, φ}. We sometimes use the terminology writing of f to indicate one particular word associated with the morphism f . For example, the morphism φEϕ has two writings containing no occurrence of E 2 : the words φEϕ and ϕE φ (because, as a morphism, φEϕ = ϕE φ).

We call length of a Sturmian morphism f the length of (one of) the shortest word associated with f . In particular, two Sturmian morphisms can be compared by their lengths.

To end, in Sections 4 and 6, we will use the notation |f | ϕ, φ to indicate the sum of the number of occurrences of ϕ and φ in a writing of a given morphism f (we will see that this value is the same for all the writings of a given f ). For example, |ϕ φEϕE φ| ϕ, φ = 4.

A characterization of non-trivial elements of St is the following (see [START_REF] Mignosi | Morphismes sturmiens et règles de Rauzy[END_REF]):

St \ {Id A , E} = {ϕ, Eϕ, ϕE, EϕE, φ, E φ, φE, E φE} + . (1)
It is aspecially clear with this decomposition that if f is a Sturmian morphism such that f (a) = a (resp.

f (b) = b) then f ∈ {ϕE, φE} * (resp. f ∈ {Eϕ, E φ} * ) (2)
and we have the following property. We give here two useful properties of the morphisms E, ϕ, and φ (the first one is an observation, originally made by Berstel [START_REF] Berstel | Mots de Fibonacci[END_REF]).

Lemma 2.3. For every u ∈ A * , a φ(u) = ϕ(u)a. For every infinite word x over A, a φ(x) = ϕ(x).

Lemma 2.4. Let x be an infinite word over A.

(i) If E(x) is Sturmian then x is Sturmian. (ii) If ϕ(x) is Sturmian then x is Sturmian. (iii) If φ(x)
is Sturmian and x starts with the letter a, then x is Sturmian.

(iv) If φ(x) is Sturmian and x starts with the letter b, then x = bx and x is Sturmian.

Proof. Item (i) is a direct consequence of the definition of Sturmian words, and items (ii) and (iii) are Proposition 2.3.2 of [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF].

We prove item (iv). Let x be an infinite word over A such that φ(x) is Sturmian. If x starts with the letter b, then x = bx and φ(x) = a φ(x ). Since a φ(x ) = ϕ(x ) (Lemma 2.3), x is Sturmian from (ii).

Sturmian fixed points of morphisms

We start our study by considering the case of a Sturmian word which is a fixed point of a morphism: we show that the morphism is Sturmian, and if it is different from Id A then the word is generated by this morphism.

The first step is given separately because it is interesting in itself. Proposition 3.1. Let x be an infinite word over A and f a morphism on

A. If f (x) is Sturmian then f ∈ St.
It is worth noticing that this proposition is an improvement of Theorem 2.3.7 of [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. Indeed Theorem 2.3.7 indicates that, to prove that a morphism is in St it is enough to verify that the image of one Sturmian word is a Sturmian word. The present proposition proves that the condition according to which the starting word has to be Sturmian is not even necessary: it is sufficient that the image is a Sturmian word.

Proof. Let x be an infinite word over A and f a morphism on A such that f (x) is Sturmian.

Before starting, we note that if f (x) is Sturmian then it is aperiodic and thus contains at least one occurrence of both f (ab) and f (ba), and

f (a) = ε, f (b) = ε.
From [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], Theorem 2.3.7, if x is a Sturmian word then f ∈ St. Consequently, we suppose in the following that x is not a Sturmian word (but x is aperiodic, otherwise f (x) is ultimately periodic thus non Sturmian). From Property 2.1, there exists a word w ∈ A * such that both awa and bwb are factors of x.

If This means that there exist words r, r 1 , r 2 , t, t 1 , t 2 such that f (a) = ryt 1 = r 1 y t and f (b) = rzt 2 = r 2 z t for {y, z} = {y , z } = {a, b}.

|f (a)| = |f (b)| then we first observe that |f (a)| a = |f (b)| a . For if not, ||f (awa)| a -|f (bwb)| a | ≥ 2; a contradiction with f (x) Sturmian. • Now, if f (a) = f (b) then f (x) is periodic; a contradiction with f (x) Sturmian. • But, if f (a) = f (b) then
• If y = y then z = z ( = y). In this case f (awa) contains the factor y tf (w)ry and f (bwb) contains the factor z tf (w)rz; a contradiction with f (x) Sturmian because ||y try| a -|z trz| a | = 2.

• If y = z then z = y ( = y). In this case f (ab) = r 1 y trzt 2 and f (ba) = r 2 z tryt 1 ; again a contradiction with f (x) Sturmian because ||y trz| a -|z try| a | = 2. Thus, if x is not a Sturmian word but f (x) is Sturmian then f (a) (resp. f (b)) is a proper prefix or a proper suffix of f (b) (resp. f (a)). We prove that f ∈ St by induction on f . Since f (a) is a proper prefix of f (b) one has f ≥ 3. If f = 3, since f (b) cannot be equal to aa or bb because f (x) is Sturmian, f ∈ {ϕE, EϕE} ⊂ St.
Now, suppose that f > 3 and, by induction, if g is such that g < f and g(y) is Sturmian for some infinite word y on A then g ∈ St.

Here we suppose that f (a) is a prefix of f (b) (the other cases are similar). Since f (a) is a proper prefix of f (b), there exists s ∈ A + such that f (b) = f (a)s. Let g be defined by g(a) = f (a) and g(b) = s. Since s = ε, g < f . Moreover f = gϕE thus g(y) is Sturmian for y = ϕE(x). Consequently g ∈ St by induction and, since St is closed under composition, f ∈ St.

From this we are able to show that if a Sturmian word is a fixed point of a morphism different from Id A then it is generated by this morphism which is Sturmian. Theorem 3.2. Let x be a Sturmian word over A. If x = g(x) for some morphism g on A then g ∈ St, and if g = Id A then there exists c ∈ A such that g is prolongable on c and x = g ω (c).

Remark. In [START_REF] Parvaix | Propriétés d'invariance des mots sturmiens[END_REF], B. Parvaix gives the value of g depending on x. His characterization is based on the notion of mechanical words which is out of the scope of the present paper.

Proof. Let x be a Sturmian word, c ∈ A the letter such that x begins with c, and g a morphism such that x = g(x).

Since x is Sturmian then, by Proposition 3.1, g ∈ St thus the first part of the result is proved. Now, suppose that g = Id A . Since x = g(x) and x begins with the letter c, g(c) starts with c thus either g(c) = c or g is prolongable on c. Indeed, if g(c) = c and g is not prolongable on c then |g(c

)| c ≤ 1 implies g(c) = cc k for some k ∈ N, k ≥ 1, and g(c) = ε; a contradiction with g ∈ St. • If g(c) = c then, since g = Id A , g(c) = c.
Let p = 0 such that x begins with c p c (such a p does exist because x is Sturmian thus x = c ω ). If g(c) begins with c then g(x) starts with c p+1 ; a contradiction. Consequently g(c) begins with c and, since g(c) = c, g is prolongable on c: g generates the Sturmian word

x such that x = c p x . Since g ∈ St and g(c) = c, g ∈ {ϕE, φE} + ∪ {Eϕ, E φ} + (cf (2), page 3).
But in this case, from Lemma 2.2, g does not generate any Sturmian infinite word; a contradiction.

• If g is prolongable on c then, for all n ∈ N, |g n+1 (c)| > |g n (c)| and, since x begins with c, the word g n (c) is a prefix of x. Consequently x = g ω (c).
This result admits three interesting corollaries.

Corollary 3.3. Let x be a Sturmian word over A. Are equivalent:

1. x is a fixed point of a morphism g = Id A 2.
x is generated by a D0L system G = (A, g, c) where g ∈ St is prolongable on the letter c ∈ A.

3.

x is generated by a D0L system G = (A, g, u) where g ∈ St is prolongable on the word u ∈ A + .

Proof. Equivalence between 1. and 2. is Theorem 3.2, and the implication 2. ⇒ 3. is straightforward. We prove 3. ⇒ 2.

Let us suppose that a Sturmian word x is generated by a D0L system (A, g, u) where g ∈ St is prolongable on the word u ∈ A + , |u| ≥ 2.

Let c be the first letter of u. Since f (u) begins with u, f (c) begins with c.

• If f (c) = c then, from Lemma 2.2, f does not generate a Sturmian word; a contradiction.

• Otherwise f is prolongable on c and x is generated by the D0L system (A, g, c), proving 2.

Corollary 3.4. If a Sturmian word x over A is a fixed point of a morphism g = Id A then g ∈ {ϕ, Eϕ, ϕE, EϕE, φ, E φ, φE, E φE} + \ ({ϕE, φE} + ∪ {Eϕ, E φ} + ) and there exists c ∈ A such that x = g ω (c).
Proof.

From Theorem 3.2 g ∈ St and, since g = Id A , one has g ∈ {ϕ, Eϕ, ϕE, EϕE, φ, E φ, φE, E φE} + (cf (1), page 3). Now, from Corollary 3.3, x is generated by g hence the result follows from Lemma 2.2.

Corollary 3.5. If a Sturmian word x over A is a fixed point of some morphism g = Id A then there exists a morphism h ∈ St such that g is a power of h (maybe g = h), and each morphism of which x is a fixed point is also a power of h. In other words, x is rigid.

Proof. Since x is generated by g, this is a direct consequence of [START_REF] Séébold | On the conjugation of standard morphisms[END_REF], Theorem 7 which states that all the Sturmian words generated by morphisms are rigid (see also [START_REF] Richomme | Completing a combinatorial proof of the rigidity of Sturmian words generated by morphisms[END_REF] for a complete proof of this theorem).

Sturmian images by morphisms

In this second part, we consider Sturmian words which are image by a morphism of an infinite fixed point of another morphism. Initially, this study needs to know the infinite words which can be transformed into Sturmian words by a morphism. After providing the main result in a second part, we end by proving that some words given here do not fulfill the conditions of Theorem 3.2.

Sturmian images by morphisms of infinite words

We start by giving a characterization of infinite words whose images under morphisms are Sturmian. It was originally proved by Parvaix [START_REF] Parvaix | Contribution à l'étude des mots sturmiens[END_REF]. The proof, given here in order to be self-contained, is based on the following important lemma.

Let c ∈ A and N S = {x infinite word over

A /x = c k cx with c ∈ A, k ≥ 1, cx non Sturmian}. Lemma 4.1. Let x ∈ N S and f ∈ St. Then f (x) ∈ N S.
Proof. Since every Sturmian morphism is a composition of E, ϕ and φ it is enough to prove the result for f = E, ϕ or φ. The case f = E is straightforward.

If c = a then ϕ(x) = (ab) k aϕ(x ) and φ(x) = (ba) k a φ(x ) = b(ab) k-1 aϕ(x ) (Lemma 2.3). Moreover, since bx is not Sturmian then aϕ(x ) = ϕ(bx ) is not Sturmian from Lemma 2.4(ii). Thus (ba) k ϕ(x ) and (ab) k-1 aϕ(x ) are not Sturmian If c = b then ϕ(x) = a k abϕ(x ) and φ(x) = a k ba φ(x ) = a k bϕ(x ) (Lemma 2.3).
But, since ax is not Sturmian, from Property 2.1, there exists a word v such that ava and bvb are factors of ax . This implies that bϕ(x ), which contains as factors both bϕ(v)ab and aϕ(v)aa, is not Sturmian.

In all the cases the words ϕ(x) and φ(x) are in N S. If x is ultimately periodic then f (x) is ultimately periodic (maybe empty) for any morphism f and consequently f (x) cannot be Sturmian. So x is aperiodic and there exists an infinite word x and an integer n ≥ 1 such that x = c n cx for some c ∈ A.

If cx is not Sturmian then x ∈ N S and, from Lemma 4.1, f (x) ∈ N S thus is not Sturmian; a contradiction. Consequently cx is Sturmian and the first implication is proved.

To prove the converse it is enough to observe that, from Lemma 2.3, for every infinite word x over A, ( φE

) n φ(b n+1 x) = a n+1 ( φE) n φ(x) = (ϕE) n ϕ(x) for every n ∈ N.
Thus, since from Lemma 2.4(i) and

(ii) (ϕE) n ϕ(x) is Sturmian whenever x is Sturmian, if x = b n+1 x , n ∈ N, with x Sturmian then ( φE) n φ(b n+1 x ) is also Sturmian. And so is ( φE) n φE(a n+1 E(x )).
Here it is worth noticing that, in the above proposition, n can be as large as needed because if x is any Sturmian word containing a 2 as a factor, the word b n x is not Sturmian for every n ≥ 2 but ( φE) n φ(b n+1 x) is Sturmian because (ϕE) n ϕ ∈ St. This also indicates that the two propositions 3.1 and 4.2 are not empty (i.e., apply for words that are not Sturmian) since there exist words x which are not Sturmian but for which f (x) is Sturmian for a morphism f on A. An example of such a word is given in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], page 84.

Sturmian images by morphisms of fixed points of morphisms

Now, we synthesize the results of Sections 3 and 4.1 by studying the case of a Sturmian word which is the image of a fixed point of some morphism different from Id A . Theorem 4.3. Let y be a Sturmian word over A. If y = f (x) and x = g(x) for some morphisms f, g on A and a word x over A then:

• f ∈ St and g ∈ St;

• there exist n ∈ N and a Sturmian word x such that x = a n x or x = b n x ;

• if g = Id A then x is Sturmian and x is generated by g.

Proof. Let x, y be two infinite words over A and f , g two morphisms on A such that y = f (x) and x = g(x). This proves the first part of the result.

The second part comes from Proposition 4.2: there exist n ∈ N, c ∈ A, and a Sturmian word x such that x = c n x .

If n = 0 then x = x is a Sturmian word and the third part is proved thanks to Theorem 3.2. So, in the following, we will suppose that n ≥ 1. We also assume, by way of contradiction, that x is not Sturmian (but x is aperiodic because x is Sturmian, thus Property 2.1 applies).

The morphism g is not prolongable on c. Indeed if g is prolongable on c then, since x begins with c, g k (c) is a prefix of x = g k (x) = g k (c n x ) for every k ∈ N. Now, if x is not Sturmian then, from Property 2.1, it contains the two factors cwc and cwc for some w ∈ A * . For a sufficiently large k, these two words are factors of the prefix g k (c) of x, consequently g k (c) is not balanced. But, since x is aperiodic it contains infinitely many occurrences of c thus of g k (c), which implies that g k (c) is balanced; a contradiction. Since g(c) begins with c (because g(x) = g(c n x ) = x = c n x with n ≥ 1), the fact that g is not prolongable on c implies that g(c) = c. For if not, |g(c)| c ≤ 1 implies g(c) = cc k for some k ∈ N, k ≥ 1, and g not being prolongable on c means g(c) = ε; a contradiction with g ∈ St.

Moreover g(c) begins with c. Indeed let m ∈ N be such that x starts with c m c: if g(c) begins with c then g(c m c) begins with c m+1 ; a contradiction with x = g(x).

Let p < n be the integer such that c p x is Sturmian and c p+1 x is not Sturmian. Then, from Property 2.1, c p+1 x contains the two factors cwc and cwc for some w ∈ A * . Moreover, since c p x is Sturmian, the unique occurrence of cwc in x is as a prefix of c p+1 x thus wc is a prefix of c p x . But, since every Sturmian word is recurrent ([10], Proposition 6.1.2), wc appears as a factor of x in another position, which means that cwc is also a factor of x. Now, since g = Id A , g ∈ St implies that one of the two words g(c) or g(c) is a proper prefix or a proper suffix of the other one ( [START_REF] Séébold | On the conjugation of standard morphisms[END_REF], Lemma 3). But g(c) = c and g(c) begins with c, thus g(c) is a proper suffix of g(c) which means that g(c) ends with c.

This implies that g(cwc) ends with cg(wc). But c p+1 x begins with cwc thus x = c n-p-1 c p+1 x starts with c n-p-1 awa and g(x) = g(c n-p-1 c p+1 x ) = c n-p-1 c p+1 g(x ) = c n-p-1 cg(c p x ) starts with c n-p-1 cg(wc).

Thus, since x = g(x), one has that g(wc) begins with wc which implies that g(cwc) contains cwc. This is, in x, an occurrence of cwc in a different position than the prefix of c p+1 x ; a contradiction. Consequently, if g = Id A then x is Sturmian and it is generated by g from Theorem 3.2.

Another formulation of this result, joined with Corollary 3.3, is the following. 1. y is the image by a morphism f on A of a fixed point of a morphism g on A, g = Id A 2. y is generated by an HD0L system H = (A, g, f, c) where the morphisms f and g are Sturmian,

g ω (c) is the Sturmian word generated by the D0L system (A, g, c) where g is prolongable on the letter c ∈ A, and y = f (g ω (c)).

3. y is generated by an HD0L system H = (A, g, f, u) where the morphisms f and g are Sturmian, g ω (u) is the Sturmian word generated by the D0L system (A, g, u) where g is prolongable on the word u ∈ A + , and y = f (g ω (u)).

An example

We end this section with an example showing that the two families described in Theorems 3.2 and 4.3 are not equal, the first one being strictly included in the second.

Proposition 4.5. Let F be the Fibonacci word. The word φ(F ) fulfills the conditions of Theorem 4.3 but not those of Theorem 3.2 (with g = Id A in both cases).

Before proving this result, we recall from Séébold, 1985 [START_REF] Séébold | Sequences generated by infinitely iterated morphisms[END_REF] some properties of the elements of the monoid {ϕ, φ} * . We recall that |h| ϕ, φ is the number of elements of {ϕ, φ} implied in any decomposition of a morphism h on A (from 2. of Proposition 4.6 below, a given h may have several decompositions but all of them contain the same number of elements of {ϕ, φ}).

Property 4.6 ([16]).

Let h be a morphism on A.

1. If h generates an infinite word having the same set of factors than F then h ∈ {ϕ, φ} + .

2. The only non trivial relations between ϕ and φ are ϕ 2 φ = φ2 ϕ and its derivatives.

Morphisms sending non Sturmian words on Sturmian words

From Lemma 4.1 and Proposition 4.2, we deduce that the whole family of binary infinite words can be partitioned in three sets:

• the set of Sturmian words;

• the set of non Sturmian words which can be transformed into Sturmian words by applying a morphism, i.e., the words c n x with c ∈ A, n ∈ N \ {0}, x Sturmian and cx non Sturmian;

• the set N S of non Sturmian words which cannot be transformed into Sturmian words by applying a morphism.

In the following, we are interested in the second of these sets. The aim is to give a characterization of the morphisms which change non Sturmian words into Sturmian words, i.e., those morphisms involved in Proposition 4.2. This characterization needs an intermediate construction.

Let c ∈ A. For every n ∈ N we denote S c n the set of words S c n = {c n x, x Sturmian and cx non Sturmian}.

Of course, S a 0 ⊂ S and S b 0 ⊂ S where S is the set of Sturmian words, and for every n ∈ N, if y ∈ S c n then y is aperiodic.

The sets S c n , n ∈ N, have the following properties.

Lemma 5.1.

1. For every f ∈ St, f (S) ⊂ S and f (N S) ⊂ N S.

For every n ∈ N and c

∈ A, E(S c n ) = S c n . 3. For every n ∈ N \ {0}, ϕ(S b n ) ⊂ S a n and φ(S b n ) ⊂ S a n-1 .
4. For every n ∈ N \ {0}, ϕ(S a n ) ⊂ N S. 2. This second relation is straightforward. We prove the others. Since x is Sturmian, so is ϕ(x). Moreover, since bx is not Sturmian, aϕ(x) = ϕ(bx) is not Sturmian (Lemma 2.4(ii)). From this we deduce

For every n

∈ N \ {0, 1}, φ(S a n ) ⊂ N S.
-ϕ(y) = ϕ(b n x) = a n ϕ(x) ∈ S a n ; -φ(y) = φ(b n x) = a φ(b n-1 x) = (by Lemma 2.3) ϕ(b n-1 x) = a n-1 ϕ(x) ∈ S a n-1 .
4. Let n ∈ N, n ≥ 1, and y ∈ S a n : y = a n x with x Sturmian and ax non Sturmian.

From Lemma 2.3, bϕ(a n-1 x) = ba φ(a n-1 x) = φ(a n x) which is not Sturmian from Lemma 2.4(iii). Hence ϕ(y) = ϕ(a n x) = abϕ(a n-1 x) ∈ N S from Lemma 4.1.

5.

Let n ∈ N, n ≥ 2, and y ∈ S a n : y = aa n-1 x with x Sturmian and ax non Sturmian.

Since n -1 ≥ 1, ax non Sturmian implies a n-1 x non Sturmian thus a φ(a n-1 x) = φ(ba n-1 x) is not Sturmian from Lemma 2.4(iv). Hence φ(y) = φ(aa n-1 x) = ba φ(a n-1 x) ∈ N S from Lemma 4.1. These results are summarized in the following automaton

&% '$ S a n ' ϕ ' E E C ϕ, φ &% '$ S b n n ≥ 3 % φ &% '$ S a 2 ' ϕ ' E E ' ϕ, φ &% '$ S b 2 A φ &% '$ S a ' ϕ ' E E E ϕ φ k &% '$ S b © φ &% '$ S T E, ϕ, φ &% '$ N S T E, ϕ, φ
From Lemma 5.1, we deduce that if f is a morphism on A and if an infinite word y on A is such that there exist c ∈ A and n ∈ N with y = c n x, x Sturmian and cx non Sturmian, then f (y) is Sturmian if and only if f = f g where f is any Sturmian morphism and g is the mirror image of the label, in the previous automaton, of a path starting at the state S c n and ending at the state S. Note that the if part can more or less be deduced from Chapter 5 of Parvaix, 1998 [12]. This (and Proposition 4.2) leads to the following characterization of morphisms which transform non Sturmian words into Sturmian words. Theorem 5.2. Let x be a Sturmian word and let f be a morphism on A.

• f (x) is Sturmian if and only if f ∈ St; • if bx is not Sturmian, f (bx) is Sturmian if and only if f = f φ, f ∈ St; • if ax is not Sturmian, f (ax) is Sturmian if and only if f = f g, f ∈ St and g ∈ φ{E, φ}; • if bx is not Sturmian, f (b n x) is Sturmian for some integer n ≥ 2 if and only if f = f g, f ∈ St and g ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * ; • if ax is not Sturmian, f (a n x) is Sturmian for some integer n ≥ 2 if and only if f = f g, f ∈ St and g ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * E.

A characterization with standard morphisms

In Séébold, 1998 [17] it is proved that each Sturmian morphism is a conjugate of a unique standard morphism obtained by replacing, in any writing of the morphism, all the occurrences of φ by ϕ. This construction is important because many properties of the morphism can be deduced from that of its standard representative. In this section we produce a new interesting property of the standard representatives of the morphisms described in Theorem 5.2. More precisely, we will prove that the morphisms g of Theorem 5.2 are conjugates of standard morphisms and we will indicate how to directly obtain such a morphism from its standard representative. This requires more information regarding Sturmian morphisms.

Standard morphisms and conjugacy

Standard morphisms are those Sturmian morphisms obtained by composition from E and ϕ only. They are representatives of the whole Sturmian morphisms thanks to the following conjugacy operation (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] and [START_REF] Séébold | On the conjugation of standard morphisms[END_REF]).

Let γ be the permutation over

A + defined by γ(cu) = uc, c ∈ A, u ∈ A * . Let f be a standard morphism and let ||f || = |f (a)| + |f (b)|. For 0 ≤ i ≤ ||f || -2, the i-th conjugate of f is the morphism f i defined by f i (ab) = γ i (f (ab)) and |f i (a)| = |f (a)|. Of course, f 0 = f . We call f ||f ||-2 the last conjugate of f .
In the following proposition we put together several results from [START_REF] Séébold | On the conjugation of standard morphisms[END_REF]. Proposition 6.1. Let f be a standard morphism.

• The ||f || -1 conjugates of f are Sturmian and are pairwise different.

• For 0 ≤ i ≤ ||f || -3, f i (a)
• For 0 ≤ i, j ≤ ||f || -2, |f i | ϕ, φ = |f j | ϕ, φ.
Let f be a Sturmian morphism. There exists a unique standard morphism g of which f is a conjugate and

• f = f 1 f 2 • • • f n , f i ∈ {E, ϕ, φ}, 1 ≤ i ≤ n; • g = g 1 g 2 • • • g n , g i ∈ {E, ϕ}, 1 ≤ i ≤ n; • if f i = E or f i = ϕ then g i = f i ; if f i = φ then g i = ϕ. Let R : St → St, the transformation defined by R(E) = E, R( φ) = R(ϕ) = ϕ. For every f ∈ St, R(f ) is called the standard representative of f : R(f ) is the standard morphism of which f is a conjugate.
Since φ = φEE, it is straightforward that, with each writing over {E, ϕ, φ} of any Sturmian morphism f , can be associated a writing of f over {E, ϕ, φE} : St = {E, ϕ, φ} * = {E, ϕ, φE} * . In Richomme, 2003 [START_REF] Richomme | Conjugacy and episturmian morphisms[END_REF] it is proved that the number, as a conjugate of its standard representative, of a Sturmian morphism f is obtained by searching the occurrences of φE in any writing of f over {E, ϕ, φE}. We give here a binary version of this result (see [START_REF] Levé | Conjugation of standard morphisms and a generalization of singular words[END_REF]).

Let us call

N C(f ) the conjugate number of a Sturmian morphism f : N C(f ) is such that f is the N C(f )-th conjugate of R(f ). Lemma 6.2 ([13], Proposition 6.2). Let f be a Sturmian morphism and n ∈ N such that f = f 0 . . . f n with f i ∈ {E, ϕ, φE}, 0 ≤ i ≤ n. Then N C(f ) = 0≤i≤n|fi= φE |f 0 . . . f i-1 (a)| (with |f 0 . . . f i-1 (a)| = 1 if i = 0).
This means that if f = g N C(f ) where g is a standard morphism, then N C(f ) is obtained from any decomposition of f over {E, ϕ, φE}, f = f 0 . . . f n , by summing the lengths of the words f 0 . . . f i-1 (a) for each i, 0 ≤ i ≤ n, such that f i = φE. Let f, f be morphisms on A such that f = f cd(E φ) t φ(E φ) s e for some c ∈ {ϕ, φ}, d ∈ {E, φ}, e ∈ {Id A , E}, and t, s ∈ N. We call seed of f the morphism s f = φd(E φ) t φ(E φ) s e.

It must be noticed that the value of the seed depends only on the letter d, i.e., the last letter of f cd. Moreover, from Theorem 5.2, if t = 0 and s = n -2 then s f is the shortest morphism such that s f (b n x) (or s f (a n x)) is Sturmian for a Sturmian word x with bx (or ax) non Sturmian.

We now prove that if a morphism f is as above, its seed is the last conjugate of R(f ) and we can give the value of N C(f ). • If d = E and t ≥ 1, then f = φEE( φE) t-1 φEE( φE) s φe. From 2. to 5. above, N C(f ) = 1 + 2 + 2(t -1) + 2(t -1) + 3 + s(2(t -1) + 3) = (2t + 1)(s + 2).

• If d = φ and t ≥ 1, then f = φEE( φE) t φEE( φE) s φe. From 2. to 5. above, N C(f

) = 1 + 2 + 2t + 2t + 3 + s(2t + 3) = (2t + 3)(s + 2).
In the four cases, N C(f ) = (2t + 1 + 2|d| φ)(s + 2) and, from 1. to 5. above, f (a) and f (b) start with different letters which implies, from Proposition 6.1, that f is the last conjugate of R(f ).

More about Sturmian morphisms

It is known (see, e.g., [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]) that the set St of Sturmian morphisms has the following presentation

E 2 = Id A (3) ϕ(ϕE) k E φ = φ( φE) k Eϕ. (4)
In particular, when k = 0 and k = 1, relation (4) gives ϕE φ = φEϕ and ϕϕ φ = φ φϕ.

Relations ( 3) and ( 4) indicate that a given Sturmian morphism may have several different writings. However it is important for what follows to notice that, from Proposition 6.1, if g 1 g 2 • • • g n and g 1 g 2 • • • g n are two writings of a given Sturmian morphism g (with g i , g i ∈ {E, ϕ, φ}, 1

≤ i ≤ n) then |g 1 g 2 • • • g n | ϕ, φ = |g 1 g 2 • • • g n | ϕ, φ.
The following lemma gives a set of relations induced by the presentation of St. Lemma 6.4. Let u ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * . Then uϕ = R(u) φ.

Proof. Let n ∈ N be such that u ∈ φ{E, φ}{E φ, ϕE, ϕ φ} n . The proof is by induction on n.

By [START_REF] Cobham | Uniform tag sequences[END_REF], φEϕ = ϕE φ and φ φϕ = ϕϕ φ thus the property is true if n = 0. Now we suppose that, for every n ≥ 0, the property is true for every non negative integer less than n, and we prove that it is also true for n + 1.

Let u ∈ {E φ, ϕE, ϕ φ} n . By induction, φEu ϕ = ϕER(u ) φ and φ φu ϕ = ϕϕR(u ) φ.

Moreover, {E φ, ϕE, ϕ φ} n+1 = {E φ, ϕE, ϕ φ}{E φ, ϕE, ϕ φ} n = E φ{E φ, ϕE, ϕ φ} n ∪ ϕE{E φ, ϕE, ϕ φ} n ∪ ϕ φ{E φ, ϕE, ϕ φ} n . • If u = φEE φu then uϕ = φEE φu ϕ = φ φu ϕ = ϕϕR(u ) φ (by induction) = ϕEEϕR(u ) φ.
• If u = φEϕEu then uϕ = φEϕEu ϕ = ϕE φEu ϕ = ϕEϕER(u ) φ (by induction).

• If u = φEϕ φu then uϕ = φEϕ φu ϕ = ϕE φ φu ϕ = ϕEϕϕR(u ) φ (by induction).

• If u = φ φϕEu then uϕ = φ φϕEu ϕ = ϕϕ φEu ϕ = ϕϕϕER(u ) φ (by induction).

• If u = φ φϕ φu then uϕ = φ φϕ φu ϕ = ϕϕ φ φu ϕ = ϕϕϕϕR(u ) φ (by induction).

• If u = φ φE φu and u does not contain any occurrence of ϕE or ϕ φ then u = φ φE φ(E φ) n (this includes the case n = 0).

Thus uϕ = φ φE φ(E φ) n ϕ = φ( φE) n+2 Eϕ = ϕ(ϕE) n+2 E φ (by (4)) = ϕϕEϕ(Eϕ) n φ.
• Otherwise u = φ φE φu and u contains at least one occurrence of ϕE or ϕ φ (this means in particular that n ≥ 1). There are two subcases If u = (E φ) p ϕEu , with u ∈ {E φ, ϕE, ϕ φ} n-p-1 for some p ∈ N then u = φ φ(E φ) p+1 ϕEu .

Thus uϕ = φ φ(E φ) p+1 ϕEu ϕ = φ( φE) p+2 EϕEu ϕ = ϕ(ϕE) p+2 E φEu ϕ (by (4)) = ϕϕ(Eϕ) p+1 φEu ϕ = ϕϕ(Eϕ) p+1 ϕER(u ) φ (by induction since n -p -1 < n). If u = (E φ) p ϕ φu , with u ∈ {E φ, ϕE, ϕ φ} n-p-1 for some p ∈ N then u = φ φ(E φ) p+1 ϕ φu . Thus uϕ = φ φ(E φ) p+1 ϕ φu ϕ = φ( φE) p+2 Eϕ φu ϕ = ϕ(ϕE) p+2 E φ φu ϕ (by (4)) = ϕϕ(Eϕ) p+1 φ φu ϕ = ϕϕ(Eϕ) p+1 ϕϕR(u ) φ (by induction since n -p -1 < n).
In all the cases, uϕ = R(u) φ.

Two characterizations

As seen above, standard morphisms are canonical representatives of Sturmian morphisms. We will show that this canonical representation extends to the computation of the words g(c n x), c ∈ A, described in Theorem 5.2 since, for each g, the application of its standard representative to the word x gives the same word as g(c n x).

In order to prove this, we need the following lemma which is a trivial generalization of Lemma 2.3. Lemma 6.5. Let x be an infinite word over A.

1. For any n ∈ N, E φ(b n+1 x) = b n Eϕ(x).

For any

n ∈ N, Eϕ(b n x) = b n Eϕ(x). 3. φ(b 2 x) = aϕ(x); ϕE(ax) = aϕE(x); ϕ φ(ax) = aϕ 2 (x); E φ(ax) = aEϕ(x).
4. φE(ax) = ϕE(x); φ2 (ax) = ϕ 2 (x).

Theorem 6.6. Let x be an infinite word over A and n ∈ N, n ≥ 2.

Let

g 1 ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * and g 2 ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * E. Then g 1 (b n x) = [R(g 1 )] (x) and g 2 (a n x) = [R(g 2 )] (x).
We remark that this provides an alternative proof of the if parts of Theorem 5.2. Indeed if f ∈ St and x is a Sturmian word, then R(f ) ∈ {E, ϕ} * thus R(f ) (x) is Sturmian by Lemma 2.4(i) and (ii).

Proof. Let x be an infinite word over A.

• Let n ∈ N, n ≥ 2, and let f 1 ∈ [(Eϕ) * E φ] n-2 (Eϕ) * : there exist non-negative integers p 1 , p 2 , • • • p n-2 , p n-1 such that f 1 = (Eϕ) p1 E φ(Eϕ) p2 E φ • • • (Eϕ) pn-2 E φ(Eϕ) pn-1 and, from 1. and 2. of Lemma 6.5, f 1 (b n x) = b 2 (Eϕ) r (x) with r = n -2 + p 1 + p 2 + • • • + p n-2 + p n-1 . • Let f 2 ∈ {E φ, ϕE, ϕ φ} * : there exist non-negative integers k, p 1 , q 1 , r 1 , p 2 , q 2 , r 2 , • • • p k , q k , r k such that f 2 = (E φ) p1 (ϕE) q1 (ϕ φ) r1 (E φ) p2 (ϕE) q2 (ϕ φ) r2 • • • (E φ) p k (ϕE) q k (ϕ φ) r k . From 3. of Lemma 6.5, f 2 φ(b 2 x) = f 2 [aϕ(x)] = a (Eϕ) p1 (ϕE) q1 (ϕ 2 ) r1 (Eϕ) p2 (ϕE) q2 (ϕ 2 ) r2 • • • (Eϕ) p k (ϕE) q k (ϕ 2 ) r k ϕ (x).
Applying 4. of Lemma 6.5, we calculate that if g ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * then g(b n x) = [R(g)] (x) and gE(a n x) = g(b n E(x)) = [R(g)] (E(x)) = [R(gE)] (x).

To end, we prove that there is a canonical writing (called normalized writing) of morphisms of Theorem 6.6 which can be obtained directly from the standard representatives by their conjugate number.

Let us call normalizable a Sturmian morphism f for which there exist f 1 ∈ {E, ϕ} * , f 2 ∈ {E, φ} * such that f = f 1 f 2 . We call this decomposition the normalized writing of f . Of course, there exist Sturmian morphisms which are not normalizable, as φϕ or ϕ φϕE φ for example. From Proposition 6.1 the normalized writing of a normalizable morphism is unique, up to occurrences of E 2 . In the following, we denote N (f ) the unique normalized writing without E 2 of a normalizable morphism f . In Theorem 6.7 below we prove that the morphisms g of Theorem 5.2 are all normalizable and we show how to obtain, from its standard representative, the normalized writing of such a morphism.

Notation.

In what follows, we will consider words of the set {E φ, ϕE, ϕ φ} * . Such a word should be written (E φ) p1 (ϕE) q1 (ϕ φ) r1 (E φ) p2 (ϕE) q2 (ϕ φ) r2 • • • (E φ) p k (ϕE) q k (ϕ φ) r k for non-negative integers k, p 1 , q 1 , r 1 , p 2 , q 2 , r 2 , • • • p k , q k , r k . But, since the precise values of k, p 1 , q 1 , r 1 , p 2 , q 2 , r 2 , • • • p k , q k , r k do not matter we will simplify, writing (E φ, ϕE, ϕ φ) p,q,r to indicate that, globally, there are p occurrences of E φ, q occurrences of ϕE, and r occurrences of ϕ φ. n-2 (Eϕ) * {Id A , E}. There exist p, q, r, t ∈ N, c ∈ {ϕ, φ}, d, d ∈ {E, φ}, a morphism f with f cd ∈ { φd, φd (E φ, ϕE, ϕ φ) p,q,r ϕd}, and e ∈ {Id A , E} such that • f = f cd(E φ) t φ(E φ) n-2 e (f is normalizable);

• f = N (f ) = R(f )s f ;
• f is the [(2t + 1 + 2|d| φ)n]-th conjugate of R(f ). This implies that φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * {Id A , E} = φ{E, φ}{E φ, ϕE, ϕ φ} * (ϕE) * φ(E φ) n-2 {Id A , E} = φ{E, φ}{E φ, ϕE, ϕ φ} * φ(E φ) n-2 {Id A , E}. Consequently, f ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ(E φ) n-2 {Id A , E} and there exist p, q, r, t ∈ N and c ∈ {ϕ, φ}, d, d ∈ {E, φ}, e ∈ {Id A , E} such that f = f cd(E φ) t φ(E φ) n-2 e for a morphism f with f cd ∈ { φd, φd (E φ, ϕE, ϕ φ) p,q,r ϕd}. This proves the first point. Now, if f cd = φd then f = ε thus R(f ) = ε and f = cd(E φ) t φ(E φ) n-2 e = φd(E φ) t φ(E φ) n-2 e = s f = R(f )s f .

Otherwise, from Lemma 6.4, f c = φd (E φ, ϕE, ϕ φ) p,q,r ϕ = R( φd (E φ, ϕE, ϕ φ) p,q,r ) φ = R(f ) φ. Consequently f = f cd(E φ) t φ(E φ) n-2 e = R(f ) φd(E φ) t φ(E φ) n-2 e = R(f )s f .

Since R(f ) ∈ {E, ϕ} * and s f ∈ {E, φ} * , the second point is established.

From Proposition 6.3, the conjugate number of s f is N C(s f ) = (2t + 1 + 2|d| φ)n. But since R(f ) ∈ {E, ϕ} * , from Lemma 6.2, N C(R(f )s f ) = N C(s f ) thus N C(s f ) is the conjugate number of N (f ), which completes the proof of the theorem.

As a conclusion we remark that Theorem 6.7 is, as we could hope, a generalization of the construction given at the end of the proof of Proposition 4.2. If a Sturmian word x is such that bx is not Sturmian, then a way to obtain a morphism f such that f (b n x) is Sturmian for some n ∈ N, n ≥ 2, is the following. Take any standard morphism g ending with (ϕE) n-1 ϕ: f = g n .

Lemma 2 . 2 (

 22 [START_REF] Mignosi | Morphismes sturmiens et règles de Rauzy[END_REF]). The word generated by a Sturmian morphism f is a Sturmian word if and only if f ∈ {ϕE, φE} * ∪ {Eϕ, E φ} * ) (i.e., if f (a) = a and f (b) = b).

  there exist words r, t, t over A such that f (a) = rat and f (b) = rbt . Moreover, since |f (a)| a = |f (b)| a , one has |t | a = |t| a + 1 and, since |f (a)| = |f (b)|, |t | = |t|. But in this case, f (ab) = ratrbt and f (ba) = rbt rat thus f (x) contains the two factors trb and t ra which are such that |trb| = |t ra| and |trb| a = |t ra| a -2; again a contradiction with f (x) Sturmian. Thus if f (x) is Sturmian then |f (a)| = |f (b)|. Now, suppose that f (a) (resp. f (b)) is neither a prefix nor a suffix of f (b) (resp. f (a)).

Proposition 4 . 2 .

 42 Let x be an infinite word over A. Are equivalent:1. there exists a morphism f on A such that f (x) is Sturmian; 2. there exist n ∈ N, a letter c ∈ A, and a Sturmian word x such that x = c n x .Proof. Assume that f (x) is Sturmian for a morphism f on A. From Proposition 3.1, f ∈ St.

  If y is Sturmian then, from Proposition 3.1, f ∈ St. Moreover, since x = g(x), one has y = f g(x) thus, again from Proposition 3.1, f g ∈ St. Now, since St is left unitary ([4] Corollary 2.3.9), f ∈ St and f g ∈ St imply g ∈ St.

Corollary 4 . 4 .

 44 Let y be a Sturmian word over A. Are equivalent:

3 .

 3 If h 1 , h 2 are two morphisms in {ϕ, φ} * such that |h 1 | ϕ, φ = |h 2 | ϕ, φ then |h 1 (a)| = |h 2 (a)| and |h 1 (b)| = |h 2 (b)|.Proof of Proposition 4.5. The Sturmian word F is defined as F = ϕ ω (a) thus F is generated by the D0L system (A, ϕ, a) and, consequently, φ(F ) = φ(ϕ ω (a)) is generated by the HD0L system (A, ϕ, φ, a). Now, we prove that φ(F ) is not generated by a morphism.Assume, contrary to what we want to prove, that there exists a morphism f on A such that φ(F ) = f ω (b) (the starting letter of φ(F ) is b).From Lemma 2.3, a φ(F ) = ϕ(F ) = F thus φ(F ) and F have the same set of factors, which implies f ∈ {ϕ, φ} + from 1. of Property 4.6.Letp = |f | ϕ, φ. Of course, since φ(F ) = f ω (b), f = Id A thus p = 0.Since ϕ p (F ) = F , one has φϕ p (F ) = φ(F ). On the other hand, since φ(F ) is generated by f , f φ(F ) = φ(F ).Consequently φϕ p (F ) = f φ(F ) and, since | φϕ p | ϕ, φ = |f φ| ϕ, φ, one has φϕ p = f φ from 3. of Property 4.6; a contradiction with 2. of Property 4.6 because p = 0.

6 .

 6 φ(S a ) ⊂ S b . Proof. The first part of relation 1. is the definition of St and the second part is Lemma 4.1.

3 .

 3 Let n ∈ N, n ≥ 1, and y ∈ S b n : y = b n x with x Sturmian and bx non Sturmian.

6 .

 6 Let y ∈ S a : y = ax with x Sturmian and y = ax non Sturmian. From Lemma 2.4(iii), φ(y) is not Sturmian. But φ(y) = φ(ax) = ba φ(x) = bϕ(x) (Lemma 2.3) and, since x is Sturmian, ϕ(x) is Sturmian from Lemma 2.4(ii), thus φ(y) ∈ S b .

  and f i (b) start with the same letter. • f ||f ||-2 (a) and f ||f ||-2 (b) start with different letters.

Example.

  Let f = φϕE φ φ = φEEϕE φEE φEE. Then, N C(f ) = 1+| φEEϕE(a)|+| φEEϕE φEE(a)| = 1 + 2 + 5 = 8. Indeed, f = g 8 with g = ϕϕEϕϕ.

Proposition 6 . 3 .•

 63 Let f = φd(E φ) t φ(E φ) s e for some d ∈ {E, φ}, e ∈ {Id A , E}, and t, s ∈ N. Then f is the last conjugate of R(f) and N C(f ) = (2t + 1 + 2|d| φ)(s + 2).Proof. Let n, p ∈ N. Since φEE = φ, and φE(a) = a, φE(b) = ba, one has:1. ( φE) n (a) = a, ( φE) n (b) = ba n : |( φE) n (a)| = 1 2. φEE(a) = ba, φEE(b) = a: | φEE(a)| = 2 3. φEE( φE) n (a) = ba, φEE( φE) n (b) = a(ba) n : | φEE( φE) n (a)| = 2 4. φEE( φE) n φEE(a) = a(ba) n+1 , φEE( φE) n φEE(b) = ba: | φEE( φE) n φEE(a)| = 2n + 3 5. φEE( φE) n φEE( φE) p (a) = a(ba) n+1 , φEE( φE) n φEE( φE) p (b) = ba(a(ba) n+1) p : | φEE( φE) n φEE( φE) p (a)| = 2n + 3. Now, let f = φd(E φ) t φ(E φ) s e for some d ∈ {E, φ}, e ∈ {Id A , E}, and t, s ∈ N. • If d = E and t = 0, then f = ( φE) s+1 φe. From 1. above, | φE(a)| = • • • = |( φE) s+1 (a)| = 1 thus N C(f ) = 1 + (s + 1) = s + 2. If d = φ and t = 0, then f = φEE φEE( φE) s φe. From 2. and 5. above, | φEE(a)| = 2 and | φEE φEE(a)| = | φEE φEE( φE)(a)| = • • • = | φEE φEE( φE) s (a)| = 3. Consequently N C(f ) = 1 + 2 + 3(s + 1) = 3(s + 2).

Theorem 6 . 7 .

 67 Let n ∈ N, n ≥ 2, and f ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ]

Proof.

  Let f ∈ φ{E, φ}{E φ, ϕE, ϕ φ} * φ [(Eϕ) * E φ] n-2 (Eϕ) * {Id A , E}, n ≥ 2. From (5), φ [(Eϕ) * E φ] n-2 (Eϕ) * {Id A , E} = (ϕE) * φ(E φ) n-2 {Id A , E}.

Acknowledgments

I would like to thank Christophe Reutenauer for suggesting the study of these questions to me and for his helpful comments on the first version of this paper. I am greatly indebted to Gwenaël Richomme for correcting many mistakes and proposing several improvements.


Violaine Prince

An Empirical Study for a Machine Aided Translation of French Prepositions 'à', 'de' and 'en' into English

This paper presents a study about ambiguous French prepositions, stressing out their roles as dependencies introducers, in order to derive some translation heuristics into English, based on a French-English set of parallel texts. These heuristics are formulated out of statistical observations and use some up-to-date results in Machine Translation (MT). Their originality mostly relies upon the importance given to syntax and dependency relations, along with lexicons, the latter being well browsed by the present literature in the domain. An experiment has been run on corpora in both languages, using a dependency parser in the source language, and results looked to be encouraging for a "step by step approach" for MT improvement.

Introduction

Researchers in in Computational Linguistics (CL) and Natural Language Processing (NLP) have been working on the role of prepositions and the issues they raise for an automated processing of language [START_REF] Litkowski | The preposition project[END_REF]. When addressing the pair English-French, the impact of prepositions is a bit underestimated in the literature, when compared to the overwhelming importance given to nouns, noun phrases and adjectival phrases in lexical semantics. Electronic resources such as WordNet still assign to prepositions a secondary role, and mostly restricted to syntax, within multiword expressions. In Machine Translation (MT), a huge project such as ARTFL (American and French Research on the Treasury of the French Language), led by the University of Chicago and the French ATILF association for Machine Translation, provides an electronic bilingual resource of 75, 000 entries. Though, this resource seems to discard prepositional noun phrases acting as technical (and sometimes usual) multiword expressions. Although ontologies and web semantics have shed light on multiword expressions, several of which containing prepositions, as the lexical impersonation of some of their concepts, it seems that the real importance of prepositions is still left aside, whereas their role is quite crucial in the semantic interpretation of the fragment. In this pair of languages, the preposition gives the direction in interpretation in a prepositional noun phrase. For instance a set of pairs greatly differs in meaning from a pair of sets. The non commutativity of natural language is here typically demonstrated by the existence and/or position of prepositions [START_REF] Yeh | Some properties of preposition and subordinate conjunction attachments[END_REF]. Second, the preposition semantics greatly modify the verb meaning in a phrasal verb, especially in English. Whole sets of new verbs are created by combining verbs with a strong polysemous potential such as do, put, make, take, get, etc. with prepositions (B. [START_REF] Trawinski | Combinatorial aspects of collocational prepositional phrases[END_REF]. Third, prepositions are not univocal terms. They behave like nouns, adjectives and verbs by being as ambiguous as the latter (J. Taylor, 1993). For instance, if the preposition at seems to indicate a projection from a source towards a target in phrasal verbs such as to look at, a sense it shares with the preposition to, at seems a locative tag, with stability and immobility characteristics in 'he is at home', shar-ing the latter with the preposition in [START_REF] Japkowicz | A system for translating locative prepositions from english into french[END_REF]. So characteristics such as polysemy and synonymy, common in nouns and verbs, also apply to prepositions. The issue we try to address in this paper is the role and transformation of prepositions in a machine translation (MT) application in a restricted environment. The main items that we need to tackle are the following : -Prepositions are often ambiguous in the source language (SL), but also their candidate equivalencies are ambiguous in the target language (TL). How can a task like MT disambiguate and choose the appropriate candidate? -What is the syntactic role of the preposition? Does it introduce a particular complement? If yes, what is the influence of its semantics in SL on its representation in TL? -Some prepositions belong to idiomatic multiword expressions and do not need to be examined as such. The recognition of their ineffectiveness as syntactic agents belongs to the existence (or the improvement) of existing translation memories and databases.

All these questions are naturally very broad in their scope. Since languages greatly vary in their use of linguistic dimensions, and in spite of an asymptotic aim at generalization, we have restricted their impact on the pair we address and all results will be considered as locally grounded in our English-French environment. They might possibly have an echo in other pairs of languages, and asserting the generality would be another very interesting issue that we cannot undertake in this paper.

Machine Translation and Prepositions :

Is There a Most Appropriate Approach ?

The ground hypothesis is that MT, a very large field with several paradigms and software that contribute to its evolution, should be enhanced with tools able to detect as automatically as possible the nature of the dependency introduced by the preposition in SL, as a requirement for discriminating the proper equivalent in TL, provided that the preposition is not an element of an idiomatic multiword expression. Idiomatic expressions, as multiword colocations, can be stored in extensive lexicons, or translation memories. Their enhancement has been long studied in MT, and any survey, however extensive, will not capture all the achievements in this domain. A few works are still more dedicated to prepositions (e.g., [START_REF] Wehrli | The preposition project[END_REF], [START_REF] Villavicencio | A multilingual database of idioms[END_REF])) or tend to stress them out (e.g, The Ultralingua dictionary at htttp://www.ultralingua.net/ provides human readable cross-lingual idiomatic expressions containing prepositions. The problem is that is not machine operable as such). Others (e.g. (V. [START_REF] Seretan | Multi-word collocation extraction by syntactic composition of collocation bigrams[END_REF]) have focused on the requirements for candidate idiomatic expressions in order to enhance existing resources. Several works have thoroughly contributed to the domain, but those we cite here have been the most inspiring to us, or the closest to our specific issue. If the fragment to be translated is not idiomatic, then two approaches might compete: -One that would browse aligned corpora and automatically learn translations and storing them in translation memories thus 'lexicalising' as much as possible the translation process. This is the actual main trend in MT. It needs important resources but few manpower. Another that would undergo the same browsing, but would try to semi-automatically extract patterns to be rewritten into transformation rules. A more costly approach in terms of human effort, but since prepositions seem to deal with hidden construction aspects (e.g. syntax, dependencies) and less with apparent lexical data, it seems that a more rule based approach would not be totally out of scope, in such a case. We have chosen to explore the second (and less used) path for which we have particular opportunities. If statistical MT was all successful in properly translating prepositions in the selected pair of languages , the issue would have dropped. However, the rationale is not "to beat" statistical MT. but to contemplate a hybrid method (both statistical and rule-based) seen as a task-properties oriented approach (if the local syntactic properties of prepositions provide a true added-value to their translation then a local rule-based tool within a statistical overall frame could be envisaged). Our research team has access to a dependency parser for French [START_REF] Chauché | Un analyseur du franc ¸ais en constituents et dépendances[END_REF], our source language, and to a French to English translation prototype that would implement, as a proof of concepts, some ideas about transformation rules as a formal rewriting of regular translation patterns. This prototype is compatible with the parser. But in order to do so, we needed to produce a study of prepositions behavior in both SL and TL, and this is what this paper is about. As computational linguists, we tried the most automatic approach, by parsing an SL corpus for which we had a TL aligned equivalent, we tagged parsed chunks with dependency tags, and studied the regularity (or not) of the prepositions translation according to their role.

Looking for Translation Patterns: An Experimental Framework

For a POC (Proof of Concepts) result, we have restricted the study to three prepositions widely used, which are à, de and en. The three could be seen as locative ((Japkowicz and Wiebe, 1991)) but are highly ambiguous, and might present a distributional similarity close to that described in [START_REF] Baldwin | Distributional similarity and preposition semantics[END_REF]. We have a pair of aligned French-English corpora of about 54, 000 words (in French) about stock exchange and economics, extracted from com-panies reports. The present corpus is specialized, "clean" and its quality is sufficient to ensure a reliable study. Moreover, it is naturally rich in prepositions. It is a good candidate "to begin with". We also used bilingual economics dictionaries1 and an access to French and English Wordnet. First subsection states the issue, the second gives the general methods we have tried to follow and the third provides the obtained results.

A brief Overview of The Issue

This section describes the characteristics of the studied prepositions and their linguistic properties and the subsequent issues raised for computational representation. A particular light will be shed on the role of these prepositions as dependency triggers. As a consequence, we will address the particular problem of modeling translating actions for these prepositions.

Source Language Morphological Variation

Table 1 refer to lexical variability of prepositions 'de' and '`a' in SL, whereas 'en' is invariant. The two variants correspond to the contraction of a determinant (i.e. le, les) and the preposition and plays both the role of a preposition and a determinant. Some linguists consider only the determinant tag, some others insist on the dual role invoking the substitution theory (i.e, if one substitutes the singular feminine form of the determinant to the contracted token, it expands into two tokens, the preposition + the determinant. Thus, theoretically, aux should expand into à les , du should expand into de le, etc.). With substitution, one has to read "tag 1" and "tag 2" in table 2 not as mutually excluded tags, but as conjugated tags. The ambiguity here is not to be solved but is intrinsic to the contracted form, whereas with en, it is a classical mutually exclusive ambiguity. The different dependency roles of these prepositions are the following: -in a noun phrase introducing a noun complement (NC) -in a verb phrase introducing an indirect noun phrase object complement for verbs either transitive of intransitive (OC) -in a verb phrase introducing an infinitive proposition acting as an object complement (OCP) -in a verb phrase introducing a noun phrase location complement (LC) Table 3 gives a few examples of translations with the three prepositions.

Canonic

Multiple Equivalencies in Target Language

The ambiguity of the three studied prepositions is revealed and enhanced by the multiplicity of their equivalencies in the target language. Table 3 has already hinted at the fact that more than one equivalent is available for each of the prepositions. Table 4 shows what the bilingual dictionary we use suggests.

Modeling Prepositions Translation

One of the main items is the following question: Are prepositions part of a multiword expression? Do they already belong to a bilingual dictionary? If not, could they be possible candidates for domain-oriented translation lexicon?

The second question rises if prepositions are not part of Prep.

Translations à at, to, in, with, by, upon, about de of, out of, off, from,with, by, about en in, into, to, of, thereof, at, during 3 show that translation sometimes deletes them. For instance, the NC (noun complement) dependency role seems to favor deletion of the preposition in TL (cf table 3). Could it be a transformation rule at the dependency level? Could it be flattened back at the pure component level in which the French Noun Phrase pattern N1 Prep N2 (where N1 and N2 are nouns) , respectively NP1 Prep NP2 (where NP1 and NP2 are noun phrases) would be translated in English into TN2 ('s) TN1, respectively TNP2 TNP1 (where Tx is the translation of x)? Another way to look at it is to consider the impact of dependency role on the translation. Does it reduce the translation ambiguity for a given preposition? If in the NC role, prepositions are deleted, in the LC (locative complement) role, is à always translated by to, de by from, and en by by? An experiment is interesting to conduct on such an issue. Object complements (both OC and OCP roles) are more difficult to stress down. Here, a more thorough empirical study might lead to a better view of the subject.

Experimental Setup

We ran an experiment by parsing the SL corpus (54,000 words) with our morphosyntactic parser, which provides an deep syntactic analysis (with a syntactic tree) and assigns dependency roles to subtrees. The experiment was divided into three parts. It needed to answer the 'lexical or not lexical' question. Is the preposition an element of a multiword expression belonging or not to a lexical resource? For that we first checked that the parser was able to recognize lexical prepositional noun phrases. A second step aimed at tracking domain oriented multiword expressions by retrieving the most frequent subtrees containing any of our studied prepositions, in order to see if we can enhance a translation lexicon. The third investigated the remaining occurrences, focusing on dependency tags whenever they appeared.

Experiment Results

Checking the Parser

In our system, if the morphosyntactic parser recognizes the candidate as an idiomatic expression it transforms its pattern by adding '_%20' tags in the lexical string to replace the blanks. For instance, the idiomatic 'pomme de terre' meaning potato is transformed into 'pomme_%20de_%20terre'. The bilingual lexicon must contain it as a single entry. Other adjectival and verbal locutions exist in our dictionary, such as 'Beaucoup_%20de' (many), 'A_%20partir_%20de' (from... on) 'en_%20dépit_"%20de' (in spite of, despite). We created the machine readable bilingual lexicon out of our bilingual resources in such a format. We ran the parser on the SL corpus and obtained the results in table 5 according to the type of multiword expression. Two usual measures have been used: recall and precision. Recall is calculated as following: ρ = nc nc+nf , Where nc stands for the number of candidates correctly extracted and nf the number of candidates forgotten. Precision is calculated as: π = nc np , where np is the number of candidates extracted by the parser. Table 5 showing that idiomatic verbal locutions being less recognized by the parser, the latter was fed with this information and its abilities were thus enhanced.

Extracting the Most Frequent Noun Phrases with Prepositions

The second step was quite important in the sense that we needed to isolate sentence fragments containing prepositions that had proper syntactic roles, that were properly constituted and to which dependencies roles have been assigned. This meant that the corpus needed to be totally parsed. The parser performances are not perfect: if POS tagging is over 98% in precision and recall [START_REF] Chauché | Un analyseur du franc ¸ais en constituents et dépendances[END_REF]), syntactic analysis and dependency assignment, although quite successful compared to the on-going state-of-the-art, are closer to a 70% value. We had to run a tedious checking on the results and then, for well parsed subtrees, we re-run an automatic counting on the corpus. As a first approach, we were interested into enhancing our bilingual lexicon with domain oriented expressions, and most of these are known to be noun phrases, so we extracted the 20 most frequent prepositional noun phrases.

Since we had a TL corpus that was a translation of our SL corpus, we associated the TL equivalent and obtained the results given in table 6. The first observation was that the deletion of the preposition in the noun complement dependency role was quite regular, except in item 19 of table 6, so it was not a negligible clue for our future transformation rules. Second, it seems that the pattern N1 Prep N2 in French is not always transformed into TN2 TN1. For instance, item 8 in table 6 gives birth to four English nouns, whereas items 12 pr 14 drop down to only one. Moreover,TN2 (respectively TN1) is not always the translation of French N2 (respectively French N1). 13 out of 20 expressions in table 6 do not follow such a pattern. So, in our opinion, Domain Idiomatic Noun Phrases would be those prepositional noun phrases in which nouns in TL are not translations of nouns in SL and should be candidate entries to the bilingual lexicon. Thus, we incorporated items 5,6,7,8,9,10,12,13,14,15,17,18,19 to our lexicon. Other noun phrases were extracted, and we noticed that there was a distribution, for the pattern N1 de N2 (value "de" for the preposition) between TN2 TN1 and TN1 of TN2, the latter being a word to word translation. These noun phrases were not specific to the domain.

Comparing Translations of Prepositions

according to their Dependency Roles If the NC role seems to lead to preposition deletion in quite an important number of cases and could be used as a rule if the expression is not idiomatic or domain specific, and if the preposition is not de, we tried to investigate other roles and the variation in translation within a given role. From the parsed corpus, we extracted all sub-trees (chunks) in which prepositions à, de and en had one of the other dependency roles (within verb phrases). It is to be noticed that not all sentences were completely parsed, but all of them had at least a partial parsing (local subtrees formed). We had, at that point, two solutions: Either we checked all occurrences of those prepositions in a window of words (with an n-gram approach) on the aligned corpora (the SL and its translation), then assigned by hand dependency roles to our prepositional phrases, or we had to rely on the parsed SL corpus with its shortcomings. We chose to examine the well-formed verbal subtrees of the parsed SL corpus, containing our prepositions. Out of 1305 verbal phrases containing any of these prepositions, 962 were correctly parsed and the subtrees having the proper information in terms of dependency role tag2 . Some of the reasons for such a recall value ( i.e 0.73) were issued of a bad recall and precision on verbal locutions (cf table 5) or adverbial ones. The comparison of translations was made semiautomatically (with sentence numbers as usual in aligned corpora). The results are given in table 7. What is quite interesting is the regularity of translations in the case of the locative complement (LC). à is translated as much by at as by to. The distribution has a semantic grounding: at is more static, pointing at the present place, whereas to is projective and points at the place to reach. In our corpus de is always translated by from, and en by by. Thus, the relationship with the semantic aspects is quite obvious: en designates the mean with which the movement is performed, and de the source. 1), then to, respectively -(i.e, the deletion of the preposition), are quite dominant, as well as some, an unlikely translation for de. It is also true for en : as a preposition, it is widely translated by by, whereas as a pronoun, it differs according to the nature of the object it refers to.

Last, a very interesting track has been suggested to us: Considering a 'verb/preposition' pair as a multiword expression per se and studying its semantic properties and the dependency roles attached to it. For this, one has to discard the classical tree building of Chauche's great parser for French and possibly 're-work' the corpus looking for POS tags bi-grams and thus producing patterns and asso-ciative rules that could be statistically exploited. This is a quite enjoyable research perspective and a work to be undertaken as a possible alternative to our present framework.

Conclusion

This first semi-automatic study on a corpus seemed to show the emergence of a few regular patterns, strongly related to the dependency role in case of noun and locative complements, and better discriminated when the appropriate POS tag is included in the case of noun phrases object complements to verbal phrases. The case of a verbal complement seems to indicate a preferred translation (see OCP line in table 7). This tends to mean that preposition translation obey to rules, and are far from being pure custom based (a case which would have favored a pure statistical approach). It also asserts that semantics have an important position (J. Taylor, 1993): Locative complements hint a spatial semantics, the behavior of en as a temporal complement appears in both noun phrases and OCP role and is translated by in or during, whereas its behavior as an instrument case indicates the use of by.

There is a very clear frame that appears if a precious resource such as a semantic parser, able to assign casual roles to chunks in SL, is available as a pre-processor for machine aided translation. In our case, semantic roles were assigned in almost 90% of the correctly parsed OC and OCP, and all LC roles were correctly assigned. This gave us a valuable setting to produce transformation rules for our prototype, in which they were implemented (unfortunately, we have no room here to detail all the further work that has been undertaken and its results).

As an answer to the question concerning a possible generalization to either other prepositions or to another pair of languages, a broader experiment is currently being set up in order to investigate the prepositions behavior: 1) Outside the original corpus, extended to other corpora (focusing on the generic capacity of our results in a specific domain), 2) Compared to results returned by statistical MT devices (stressing out, or not the possible added value of semantic patterns), 3) Including other prepositions that would have similar properties in the same pair of languages, 4) Extending the framework to at least another pair (and relying upon the state-of-the art in such a pair). This is a huge research program and we just wanted to reach a reasonable outcome on the first item. Thus we intend to pursue the experiment by running the modified prototype on another corpus, and examining its success rate in properly translating

Table 3 :

 3 Equivalencies for each preposition multiword expressions. Some of the examples in table

Table 5 :

 5 Extracted Candidates For Parser Checking

	Role	Example in SL	Translation
	NC	médecin de famille	family doctor
		moulin à café	Coffeemill
		pot en terre cuite	terracotta pot
	OC	Je pense à lui	I think of him
		Je parle de lui	I am talking about him
		Je pense en Franais	I think in French
	OCP	Je viens de manger	I have just eaten
		Je refuse de parler	I refuse to talk
		Il parle en dormant	He talks in his sleep
	LC	Je pars en avion	I am going by plane
		Je pars à Londres	I am going to London
		Je viens de New York I am coming from New York
		Table 4: Dependency Roles Examples
	Type		Typical Example	Recall Precision
	Idiomatic NP	Hôtel de ville (Town Hall)	0.88	0.92
	Idiomatic Nominal Locutions	En raison de ( because of )	0.75	0.87
	Idiomatic Verbal Locutions	A partir de (from ... on)	0.56	0.52
	Idiomatic Adjectival Locutions	A peu près (circa)	0.90	0.88

Table 6 :

 6 The only ambiguity is about the location, either present or future. The Most Frequent Prepositional Noun Phrases in the corpus (NC dependency role)

	Rank	Contents	Translation		Frequency
	1	Economie de marché	market economy		45
	2	Taux d'intérêt	Interest rate		42
	3	Taux de croissance	growth rate		41
	4	Taux d'inflation	inflation rate		39
	5	Chiffre d'affaires	Sales turnover		39
	6	Marché à terme	Futures exchange		37
	7	Indice de référence	Benchmark		39
	8	Indice de satisfaction	Customer Satisfaction Value Index	32
	9	Consommation des ménages	Private Consumption		28
	10	Marchés des devises	Exchange market		25
	11	Augmentation de capital	Capital growth		23
	12	Option d'achat	Call		19
	13	jour de liquidation	Winding-up date		12
	14	jour de valeur	Overnight		12
	15	Obligations à haut rendement	Junk Bonds		7
	16	Frais de souscription	Subscription charges		5
	17	Frais de rachat	back-end load		5
	18	Ecart de suivi	tracking error		4
	19	Teneur de marché	mark to market		4
	20	Facturation d'entreprise	Enterprise billing		3
	Role	à	de		en
	OC	at (22, 8%), to (20, 2%),	of (37, 2%), -(33, 5%)	by (40, 3%), in (24, 5%)
		-( 18, 1%), of(16, 2%),	some (17, 9%) by (11, 4%)	with (10, 4%), -(9, 8%)
	with (11, 3%), by (6, 6%), about (4, 8%)		about(9, 5%), into (5%)
	OCP	to (71, 2%), -( 28, 8%)	-(85, 3%), to (10%)	in (45, 1%) during (32%)
			about (3, 1%), of (1, 6%)	while (20, 3%), into (3, 4%)
	LC	at ( 50, 9% ) to (49, 1%)	from		by

Table 7 :

 7 Prepositions translations (through alignment) and their percentages in the well parsed verbal phrases OCP role, or the verb or proposition acting as an object complement, is more ambiguous for all prepositions, with a deletion case (represented by '-' in table7) quite present. Let us note that preposition en is quite often translated in the meaning of a duration (while, during), especially with a present progressive verbal form. The widest distribution is for the OC (object complement) role assigned to a noun phrase. Here, it seems that the POS tag of the preposition (ambiguous as shown in table 2) has a role to play. When the tag is that of a determinant (case of au, aux, du, des as shown in table

URL :http://www.e-anglais.com/ressources/glossary.html, developed by Kevin Halion. Mostly human readable, but machine operability was easy.

The parser developer has created a semi-automatic counting tool which allows him to check the parser abilities in terms of recall and precision.