Fabien Durand

DECIDABILITY OF THE HD0L ULTIMATE PERIODICITY PROBLEM

In this paper we prove the decidability of the HD0L ultimate periodicity problem.

1. Introduction 1.1. The HD0L ultimate periodicity problem. In this paper we prove the decidability of the following problem :

Input: Two finite alphabets A and B, an endomorphism σ : A * → A * , a word w ∈ A * and a morphism φ : A * → B * . Question: Do there exist two words u and v in B * , with v non-empty, such that the sequence (φ(σ n (w))) n converges to uv ω (i.e., is ultimately periodic)?

(The convergence of the sequence (φ(σ n (w))) n meaning that (|φ(σ n (w))|) n goes to +∞ and that (φ(σ n (www • • • ))) n converges in B N endowed with the usual product topology.) We will refer to it as the HD0L ultimate periodicity problem. Observe that it is slightly more general than the classical statement where it is assumed in the input that the sequence (φ(σ n (w))) n converges.

Theorem 1. The HD0L ultimate periodicity problem is decidable.

This result was announced in [Durand 2012]. While we were ending the writing of this paper, I. Mitrofanov put on Arxiv [Mitrofanov preprint 2011] another solution of this problem.

This problem was open for about 30 years. In 1986, positive answers were given independently for D0L systems (or purely substitutive sequences) in both [Harju and Linna 1986] and [START_REF] Pansiot | Decidability of periodicity for infinite words[END_REF]], and, for automatic sequences (which are particular HD0L sequences) in [Honkala 1986]. Other proofs have been given for the D0L case in [Honkala 2008] and for automatic sequences in [Allouche, Rampersad and Shallit 2009]. Recently in [Durand 2012] the primitive case has been solved. In [Honkala and Rigo 2004] is given an equivalent statement of the HD0L ultimate periodicity problem in terms of recognizable sets of integers and abstract numeration systems. In fact, J. Honkala already gave a positive answer to this question in [Honkala 1986] but in the restricted case of the usual integer bases, i.e., for k-automatic sequences or constant length substitutive sequences. Recently, in [START_REF] Bell | [END_REF], a positive answer has been given for a (large) class of numeration systems including for instance the Fibonacci numeration system. Let us point out that the characterization of recognizable sets of integers for abstract numeration systems in terms of substitutions given in [START_REF] Maes | [END_REF] (see also [START_REF] Lecomte | [END_REF]), together with Theorem 1, provides a decision procedure to test whether a recognizable set of integers in some abstract numeration system is a finite union of arithmetic progressions.

1.2. Organization of the paper. In Section 2 are the classical definitions. In Section 3 we prove the HD0L ultimate periodicity problem for substitutive sequences. These sequences are such that (σ n (w)) n converges. This avoids to test the existence of the limit. Indeed, there are examples where (φ(σ n (w))) n converges and (σ n (w)) n does not: for σ and φ, defined by σ(a) = cb, σ(b) = ba, σ(c) = ab, φ(a) = φ(c) = 0 and φ(b) = 1, the sequence (σ n (a)) n does not converge but (φ(σ n (a))) n does (to the Thue-Morse sequence). Under these assumptions the proof could be sketched as follows. First we recall some primitivity arguments about matrices and substitutions. The "best or easiest situation" is when we deal with growing substitutions and codings (letter-to-letter morphisms). It is known that we can always consider we are working with codings (see [Cobham 1968[START_REF] Pansiot | Hiérarchie et fermeture de certaines classes de tag-systèmes[END_REF], Allouche and Shallit 2003[START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF]). In [Honkala 2009] it is shown this can be algorithmically realized. We propose a different algorithm using the proof of [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF] where we replace some (non-algorithmic) arguments (Lemma 2, Lemma 3 and Lemma 4 of this paper) by algorithmic ones. We treat separately growing and non-growing substitutions. For growing substitutions we look at their primitive components and we use the decidability result established in [Durand 2012] about periodicity for primitive substitutions. Indeed, these primitive components should generate periodic sequences. Hence, we check it is the case (if not, then the sequence is not ultimately periodic). From there, Lemma 11 allows us to conclude. For the non-growing case we use a result of Pansiot [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF]] saying that we can either consider we are in the growing case or there are longer and longer periodic words with the same period in the sequence. We again conclude with Lemma 11. In Section 4 we show how to use the substitutive case to solve the general HD0L case. This concludes the proof of Theorem 1.

1.3. Questions and comments. We did not compute the complexity of the algorithm provided by our proof of the HD0L ultimate periodicity problem. Looking at Proposition 4 and the results in [Durand 2012] we use here, our approach provides a high complexity.

Our result is for one-dimensional sequences. What can be said about multidimensional sequences generated by substitution rules ? or self-similar tilings ? It seems hopeless to generalize our method to tilings, although the main and key result we use to solve the HD0L ultimate periodicity problem (that is, the main result in [Durand 1998], see [Durand 2012]) has been generalized to higher dimensions by N. Priebe in [Priebe 2000] (see also [Priebe and Solomyak 2001]). But observe that in [Leroux 2005] the author gives a polynomial time algorithm to know whether or not a Number Decision Diagram defines a Presburger definable set (see also [Muchnik 2003] where it was first proven but with a much higher complexity). From this result and [Cerný and Gruska 1986a, Salon 1986[START_REF] Salon | Suites automatiques à multi-indices et algébricité[END_REF] it is decidable to know whether a multidimensional automatic sequence (or fixed point of a multidimensional "uniform" substitution) has a certain type of periodicity (see [Leroux 2005, Muchnik 2003]). From [Durand and Rigo] this type of periodicity is equivalent to a block complexity condition.

Words, morphisms, substitutive and HD0L sequences

In this section we recall classical definitions and notation. Observe that the notion of substitution we use below could be slightly different from other definitions in the literature.

2.1. Words and sequences. An alphabet A is a finite set of elements called letters. Its cardinality is |A|. A word over A is an element of the free monoid generated by A, denoted by

A * . Let x = x 0 x 1 • • • x n-1 (with x i ∈ A, 0 ≤ i ≤ n -1)
be a word, its length is n and is denoted by |x|. The empty word is denoted by ǫ, |ǫ| = 0. The set of non-empty words over A is denoted by A + . The elements of A N are called sequences.

If x = x 0 x 1 • • • is a sequence (with x i ∈ A, i ∈ N) and I = [k, l] an interval of N we set x I = x k x k+1 • • • x l
and we say that x I is a factor of x. If k = 0, we say that x I is a prefix of x. The set of factors of length n of x is written L n (x) and the set of factors of x, or the language of x, is denoted by L(x). The occurrences in x of a word u are the integers i such that x [i,i+|u|-1] = u. If u has an occurrence in x, we also say that u appears in x. When x is a word, we use the same terminology with similar definitions. The sequence x is ultimately periodic if there exist a word u and a non-empty word v such that x = uv ω , where v ω = vvv • • • . In this case v is called a word period and |v| is called a length period of x. It is periodic if u is the empty word. A word u is recurrent in x if it appears in x infinitely many times. The sequence x is uniformly recurrent if all words in its language appear infinitely many times in x and with bounded gaps.

Morphisms and matrices.

Let A and B be two alphabets. Let σ be a morphism from A * to B * . When σ(A) ⊂ B, we say σ is a coding. We say σ is erasing if there exists b ∈ A such that σ(b) is the empty word. Such a letter is called erasing letter (w.r.t. σ). If σ(A) is included in B + , it induces by concatenation a map from A N to B N . This map is also denoted by σ. With the morphism σ is naturally associated its incidence matrix M σ = (m i,j ) i∈B,j∈A where m i,j is the number of occurrences of i in the word σ(j). Let σ be an endomorphism. We say it is primitive whenever its incidence matrix is primitive (i.e., when it has a power with positive coefficients). We denote by L(σ) the set of words having an occurrence in some image of σ n for some n ∈ N. We call it the language of σ.

2.3. Substitutions and substitutive sequences. We say that an endomorphism σ : A * → A * is prolongable on a ∈ A if there exists a word u ∈ A + such that σ(a) = au and, moreover, if lim n→+∞ |σ n (a)| = +∞. Prolongable endomorphisms are called substitutions. We say a letter b ∈ A is growing (w.r.t. σ) if lim n→+∞ |σ n (b)| = +∞. We say σ is growing whenever all letters of A are growing. Since for all n ∈ N, σ n (a) is a prefix of σ n+1 (a) and because (|σ n (a)|) n tends to infinity with n, the sequence (σ n (aaa • • • )) n converges (for the usual product topology on A N ) to a sequence denoted by σ ω (a). The endomorphism σ being continuous for the product topology, σ ω (a) is a fixed point of σ: σ(σ ω (a)) = σ ω (a). A sequence obtained in this way (by iterating a prolongable substitution) is said to be purely substitutive (w.r.t. σ). If x ∈ A N is purely substitutive and φ : A * → B * is a morphism then the sequence y = φ(x) is said to be a morphic sequence (w.r.t. (σ, φ)). When φ is a coding, we say y is substitutive (w.r.t. (σ, φ)). In these cases, when σ is primitive, y is uniformly recurrent (see [Queffèlec 1987]).

2.4. D0L and HD0L sequences. A D0L system is a triple G = (A, σ, u) where A is a finite alphabet, σ : A * → A * is an endomorphism and u is a word in A * . An HD0L system is a 5-tuple G = (A, B, σ, φ, u) where (A, σ, u) is a D0L system, B is a finite alphabet and φ : A * → B * is a morphism. If it converges, the limit of (φ(σ n (uuu

• • • )) n is called HD0L sequence.
It is clear that substitutive sequences are HD0L sequences. We will show in the last section that HD0L sequences are substitutive sequences. Nevertheless, as the initial data are not the same, it is not enough to solve the ultimate periodicity problem for substitutive sequences. Indeed, if (σ n (uuu • • • )) n does not converge it seems difficult to decide whether (φ(σ n (uuu • • • )) n converges. We leave this question as an open problem.

Ultimate periodicity of substitutive sequences

In this section we prove the decidability of the HD0L ultimate periodicity problem for substitutive sequences. In the sequel σ : A * → A * is a substitution prolongable on a, φ : A * → B * is a morphism, y = σ ω (a) and x = φ(y) is a sequence of B N . We have to find an algorithm deciding whether x is ultimately periodic or not.

3.1.

Primitivity assumption and sub-substitutions. We recall that the HD0L ultimate periodicity problem is already solved in the primitive case.

Theorem 2. [Durand 2012] The HD0L ultimate periodicity problem is decidable in the context of primitive substitutions. Moreover, a word period can be explicitly computed.

Proof. The first part is Theorem 26 in [Durand 2012]. The second part can be easily deduced from the proof of this theorem.

The following lemma shows that it is decidable to check that a nonnegative matrix is primitive.

Lemma 3. [Horn and Johnson 1990] The n × n nonnegative matrix M is primitive if and only if M n 2 -2n+2 has positive entries.

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

Proposition 4. Let M = (m i,j ) i,j∈A be a matrix with non-negative coefficients. There exist three positive integers p = 0, q, l, where q ≤ l -1, and a partition

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

The next three corollaries are consequences of Proposition 4.

The following corollary will be helpful to change the representation of x (in terms of (σ, φ)) to a more convenient representation.

Corollary 5. Let τ : A * → A * be an endomorphism whose incidence matrix has the form of M p in Proposition 4. Then, for all b ∈ A and all j ≥ 1, the letters having an occurrence in τ |A| j (b) or τ |A| j+1 (b) are the same.

Proof. Let us take the notation of Proposition 4. Let A (0) (resp. A (1) ) be the set of letters b belonging to some A i where M i is the null matrix (resp. is not the null matrix).

The conclusion is a consequence of the following two remarks. Let b ∈ A i . From the shape of the incidence matrix of τ we get:

• If b belongs to A (1) , then all letters occurring in τ (b) occur in τ n (b) for all n.

• If b belongs to A (0) , then all letters occurring in τ (b) belong to some A j with j > i. This achieves the proof. Corollary 6. It is decidable whether a given letter is growing for a given endomorphism.

Proof. Let τ be an endomorphism. Let us take the notation of Proposition 4. Let A (0) (resp. A (1) ) be the set of letters b belonging to some A i where M i is the null matrix (resp. the 1 × 1 matrix [1]). The letters belonging to A \ (A (0) ∪ A (1) ) are growing. Let b ∈ A i ∩ A (1) for some i. Then, from Corollary 5, b is non-growing (w.r.t. τ ) if and only if all letters occurring in τ p|A| (b), except b, are erasing with respect to τ p|A| . Let A ′ be the set of such non-growing letters. Let b ∈ A i ∩A (0) for some i. Then b is non-growing if and only if all letters occurring in τ p|A| (b) are erasing with respect to τ p|A| or belong to A ′ . Moreover, from Proposition 4 and Corollary 5 we can decide whether a letter is erasing w.r.t. τ p|A| . This achieves the proof.

In what follows we keep the notation of Proposition 4. We will say that {A i ; 1 ≤ i ≤ l} is a primitive component partition of A (with respect to M ), the A i being the primitive components. If i belongs to {q + 1, • • • , l} we will say that A i is a principal primitive component of A (with respect to M ). Let τ : A * → A * be a substitution whose incidence matrix has the form of M p in Proposition 4. Let i ∈ {q + 1, • • • , l}. We denote τ i the restriction τ /Ai :

A * i → A * of τ to A * i . Because τ i (A i ) is included in A *
i we can consider that τ i is an endomorphism of A * i whose incidence matrix is M i . When it defines a substitution, we say it is a sub-substitution of τ . Moreover the matrix M i has positive coefficients which implies that the substitution τ i is primitive. A non-trivial primitive endomorphism always has some power that is a substitution. For non-primitive endomorphisms we have the following corollary.

Corollary 7. Let τ : A * → A * be an endomorphism whose incidence matrix has the form of M p in Proposition 4. Then, with the notation of Proposition 4, there exists k ≤ |A| |A| satisfying : for all i ≥ q + 1 such that M i is neither a null matrix nor the 1 × 1 matrix [1], the endomorphism τ k i is a (primitive) substitution for some letter in A i .

Proof. We only have to check there exists k ≤ |A| |A| such that for all i ≥ q + 1 there exists a letter b ∈ A i satisfying τ k i (b) = bu for some non-empty word u. Let i ≥ q + 1 and c ∈ A i . There exist k i ≥ 1 and j ≥ 0, with k i + j ≤ |A|, such that τ j i (c) and τ ki+j i (c) start with the same letter b. That is to say, τ ki i (b) = bu for some u. To conclude, it suffices to take k

= k q+1 • • • k l .
The following lemma is easy to establish.

Lemma 8. Let x = φ(σ ω (a)). If x = uv ω , where v is not the empty word, then each sub-substitution σ ′ of σ such that L(σ ′ ) ⊂ L(σ ω (a)) verifies φ(L(σ ′ )) ⊂ L(v ω ).
Proof. Let σ ′ be a sub-substitution of σ. Its incidence matrix being primitive, there exists an uniformly recurrent sequence z such that L(σ ′ ) = L(z) (see [Queffèlec 1987]). Thus, the words of L(σ ′ ) appear infinitely many times in σ ω (a). Finally, for all w ∈ L(σ ′ ), φ(w) should occur in v ω .

3.2. Reduction of the problem. It may happen, as for σ defined by a → ab, b → a, c → c, that some letter of the alphabet, here the alphabet is {a, b, c}, does not appear in σ ω (a). It is preferable to avoid this situation. Corollary 5 enables us to avoid this algorithmically. We explain this below. Indeed, from Proposition 4, taking a power of σ (that can be algorithmically found) if needed, we can suppose (P1) the incidence matrix of σ has the form of M p in Proposition 4.

Then, consider σ |A| instead of σ. Hence, σ will continue to satisfy (P1) and, from Corollary, 5 we have (P2) for all b ∈ A and all j ≥ 1 the letters having an occurrence in σ j (b) or σ j+1 (b) are the same. Notice that, as σ is a substitution, taking a power of σ instead of σ will change neither y nor x. It will not be the case when we will deal with endomorphisms which are not substitutions. Let A ′ be the set of letters appearing in σ ω (a). From (P2) it can be checked that σ(A ′ ) is included in A ′ * and that the set of letters appearing in σ(a) is A ′ . Thus σ ′ , the restriction of σ to A ′ , defines a substitution prolongable on a satisfying σ ′ω (a) = σ ω (a) such that all letters of A ′ have an occurrence in σ ′ω (a) and all letters of A ′ occur in σ ′ (a). Hence we can always suppose σ and a satisfy the following condition.

(P3) The set of letters occurring in σ ω (a) is A.

When we work with morphic sequences it is much simpler to handle with non-erasing substitutions and even better to suppose that φ is a coding. Such a reduction is possible as shown in [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF].

Theorem 9. Let x be a morphic sequence. Then, x is substitutive with respect to a non-erasing substitution.

This result was previously proven in [Cobham 1968] and [START_REF] Pansiot | Hiérarchie et fermeture de certaines classes de tag-systèmes[END_REF]] (see also [Allouche and Shallit 2003] and [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF]). It was shown that it could be algorithmically done in [Honkala 2009]. In the sequel we give another algorithm. The proof of J. Cassaigne and F. Nicolas is short and inspired by [Durand 1998], in particular its second part which is clearly algorithmic. Whereas the first part (Lemma 2, Lemma 3 and Lemma 4 of [START_REF] Cassaigne | Quelques propriétés des mots substitutifs[END_REF]) is not because it uses the fact that from any sequence of integers, we can extract a subsequence that is either constant or strictly increasing. They use these lemmas to show the key point of their proof : we can always suppose that φ and σ fulfill the following : Below we show that this can be algorithmically realized. This provides another algorithm for Theorem 9. First let us show that σ can be supposed to be non-erasing. As we explained before, there is no restriction to suppose σ satisfies (P1), (P2) and (P3).

As σ satisfies (P2), each letter e is either erasing or, for all l, σ l (e) is not the empty word. Let A ′ be the set of non-erasing letters and A ′′ the set of erasing letters. Let ψ be the morphism that sends the elements of A ′′ to the empty word and that is the identity for the other letters. Then, we define σ ′ to be the unique endomorphism defined on A ′ satisfying ψ • σ = σ ′ • ψ. Observe that σ ′ is easily algorithmically definable and prolongable on a. Moreover we have σψ = σ. Let z = σ ′ω (a). Then, ψ(y) = z and σ(z) = y.

Notice that σ ′ is non-erasing. Indeed, if σ ′ (a ′ ) = ǫ for some a

′ ∈ A ′ , then ψ(σ(a ′ )) = σ ′ (a ′ ) = ǫ. Hence σ(a ′ ) = b 1 • • • b k where the b i 's belong to A ′′ . Then σ 2 (a ′ ) = ǫ.
But, from Property (P2), σ 2 (a ′ ) is not the empty word.

Thus we can also consider Proof. It can be easily algorithmically checked whether we are in the situation (2) of Lemma 16. Thus it is decidable to know whether we are in situation (1) of Lemma 16.

Theorem 18. The HD0L ultimate periodicity problem is decidable for substitutive sequences w.r.

(b) = σ n (v)buσ(u) • • • σ n (u). As the sequence (|σ n (u)|) n is bounded, there exist i and j, i < j, such that σ i (u) = σ j (u). Let u ′ = σ i (u)σ i+1 (u) • • • σ j-1 (u).
Then, we get L(u ′ω ) ⊂ L(σ). We conclude using Lemma 14 and Lemma 11.

This ends the proof of Theorem 1 for substitutive sequences.

Theorem 19. Suppose the sequence x is substitutive with respect to (σ, φ). Then, it is decidable whether x is ultimately periodic: x = uv ω for some u and non-empty v. Moreover, we can compute such u and v.

Ultimate periodicity of HD0L sequences

In this section we end the proof of the Theorem 1: We solve the HD0L ultimate periodicity problem. We use the notation introduced in the input of the problem. We recall that in the previous section we prove this theorem for a special case of HD0L sequences: the substitutive sequences. These sequences are very convenient as, by definition, there is no problem with the existence of the limit in the statement of the HD0L ultimate periodicity problem. We gave, in Section 1.2, an example of an HD0L sequence where the sequence (σ n (a)) n does not converge but (φ(σ n (a))) n does. Thus, in the general case, it would be convenient (but not necessary) to be able to decide the existence of the limit. As we did not succeed to solve this decidability problem, we leave this question as an open problem. We proceed in a different way.

Let us consider the input of the HD0L ultimate periodicity problem.

Lemma 20. Let a ∈ A. Suppose σ satisfies (P1) and (P2). Then, it is decidable whether:

(1) (|φ(σ n (a))|) n tends to 0, (2) (|φ(σ n (a))|) n tends to infinity. Moreover, if (|φ(σ n (a))|) n does not tend to infinity then it is bounded.

Proof. Let A ′ be the set of letters occurring in σ(a). We prove the decidability of (1). From (P2), for all n ≥ 1, the set of letters occurring in σ n (a) is A ′ . Then, (|φ(σ n (a))|) n tends to 0 if and only if φ(a ′ ) is the empty word for all a ′ ∈ A ′ . We prove the decidability of (2). Let us consider the notation of Proposition 4 for σ. As σ satisfies (P1) we can suppose p = 1. Suppose a belongs to A l . Then (|φ(σ n (a))|) n tends to infinity if and only if M l is neither the 1×1-matrix [1] nor the null matrix, and, there exists a letter b ∈ A l such that φ(b) is not the empty word. Thus for such a letter the problem is decidable. Moreover, if (|φ(σ n (a))|) n does not tend to infinity, then it is bounded.

  a))| > |φ(a)| > 0 and |φ(σ(b))| ≥ |φ(b)| for all b ∈ A.

(

  P4) σ is non-erasing. Consequently, from (P2), |φ • σ(σ(a))| > |φ(σ(a))| > |φ(a)|, otherwise φ(σ ω (a)) would not be an infinite sequence. Hence, replacing φ with φ • σ if needed, we can suppose φ and σ are such that |φ(σ(a))| > |φ(a)| > 0. Moreover, we claim that σ 2 (b) = σ(b) for all non-growing letters b ∈ A. Let b be a non-growing letter. As σ is non-erasing we necessarily have |σ 2 (b)| ≥ |σ(b)|. Suppose |σ 2 (b)| > |σ(b)|. Then, the letters occurring in σ 2 (b) and σ(b) being the same, we would have |σ n (b)| ≥ n + 1 for all n, and, b would not be growing. Consequently, |σ 2 (b)| = |σ(b)|. Let σ(b) = b 1 b 2 • • • b l . Then, |σ(b i )| = 1 for all i, and, from the shape of the incidence matrix of σ, σ(b i ) = b i for all i.

  t. non-erasing substitutions. Moreover, some u and v in the description of the problem can be computed.Proof. From Theorem 15, Lemma 16 and Lemma 17 it remains to consider that σ satisfies (2) in Lemma 16 : Let b be a letter occurring in σ ω (a) such that σ(b) = vbu (or ubv) with u ∈ C * \ {ǫ} where C is the set of non-growing letters. Then, for all n, σ n+1

Acknowledgements. The author thanks the referees for their valuable and relevant comments. He also thanks the ANR program SubTile for its financial support.

Hence, together with the argument of the proof of Theorem 9 we obtain the algorithm we are looking for. This is summarized in the following theorem (first proved in [Honkala 2009]).

Theorem 10. There exists an algorithm that given φ and σ compute a coding ϕ and a non-erasing substitution τ , prolongable on a, such that x = ϕ(z) where z = τ ω (a).

Thus, in the sequel we suppose φ is a coding and σ is a non-erasing substitution. We end this section with a technical lemma checking the ultimate periodicity.

Lemma 11. Let t ∈ A N , ϕ be a coding defined on A * , z = ϕ(t), and, u and v be non-empty words. Then, z = uv ω iff and only if for all recurrent words

, where the b i 's are letters, there exist r B ∈ {0, 1, 2}, s B and p B such that and, (2) for all recurrent words BB ′ ∈ L(t), where B ′ is a word of length 2|v|, p B s B ′ is equal to v or the empty word.

Proof. The proof is left to the reader.

3.3.

The case of substitutive sequences with respect to growing substitutions. In the sequel we suppose σ is a growing substitution. From Corollary 6 it is decidable to know whether we are in this situation. We recall that from the previous section we can suppose φ is a coding and that σ satisfies (P1), (P2), (P3) and (P4).

Lemma 12. Let u and v be two words. It is decidable to check whether or not L(u ω ) is equal to L(v ω ).

Lemma 13. The set of recurrent letters in σ ω (a) = c 0 c 1 • • • is algorithmically computable. Moreover there is a computable i such that all letters occurring in c i c i+1

Proof. Let n ∈ N. Let w 0 be the prefix of length n of σ n (a). Let w 1 , . . . , w j1 be the words of length n appearing in σ(w 0 ). Then we do the same for w 1 . We obtain some new words of length n: w j1+1 , . . . , w j2 . We proceed similarly with w 2 , w 3 and so on, until all the w i are handled and no new words appear. At this point, the set A ′ of all collected words is the set of all words of length n occurring in σ ω (a). It remains to find the words in A ′ that are recurrent in σ ω (a).

Consider A ′ as a new alphabet and σ n :

where

) and that

We achieve the proof using Lemma 13

Theorem 15. The HD0L ultimate periodicity problem is decidable for substitutive sequences w.r.t. growing substitutions. Moreover, some u and v in the description of the problem can be computed.

Proof. In this proof we suppose σ is growing. Let us use the notation of Proposition 4. From Corollary 7, taking a power of σ (less than |A| |A| ) if needed, we can suppose that for all i ≥ q + 1 the endomorphism σ i : A * i → A * i defines a primitive sub-substitution w.r.t. some letter a i ∈ A i . We recall that all sub-substitutions are primitive. We notice that, in the growing case, there is at least one sub-substitution.

Observe that for all i ≥ q + 1 and b ∈ A i , the word σ n (b) = σ n i (b) is recurrent in σ ω (a). Thus, to check the periodicity of x, we start checking with Theorem 2 that, for all i ≥ q + 1, the sequence φ(σ ω i (a i )) is periodic. We point out that when the language is periodic then a word period w(σ i ) can be computed. If for some σ i the sequence φ(σ ω i (a i )) is not periodic then x cannot be ultimately periodic. Indeed, suppose x = uv ω . As longer and longer words occurring in φ(σ ω i (a i )) occurs in x, the uniform recurrence would imply that φ(σ ω i (a i )) = v ω . Then, we check that all the languages L(w(σ i ) ω ) are equal using Lemma 12. From Lemma 8, if this checking fails, then x is not periodic. Hence we suppose it is the case : There exists a word v that is algorithmically given by Theorem 2 such that φ((w(σ i )) ω ) = L(v ω ) for all i. Consequently, we should check whether there exists u such that x = uv ω . We conclude using Lemma 14 and Lemma 11.

3.4. The case of substitutive sequences with respect to non-growing substitutions. In the sequel we suppose that σ is a non-growing substitution. From Corollary 6 it is decidable to know whether we are in this situation. We recall that from the previous section we can suppose φ is a coding and that σ satisfies (P1), (P2), ( P3) and (P4).

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

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

(2) There exists a growing letter b ∈ A, occurring in σ ω (a), such that σ(b) = vbu (or ubv) with u ∈ C * \ {ǫ} where C is the set of non-growing letters. Moreover, in the situation (1) the sequence σ ω (a) can be algorithmically defined as a substitutive sequence w.r.t. a growing substitution.

Lemma 17. It is decidable to know whether σ satisfies (1) or (2) of Lemma 16. Now we proceed by a finite induction. Suppose the problem is decidable for all letters in ∪ n+1≤j≤l A j . We show it is decidable for all letters in ∪ n≤j≤l A j . Suppose a belongs to A n . If M n is the null matrix, then we conclude with our induction hypothesis. Suppose M n is the 1 × 1-matrix [1]. Then, (|φ(σ n (a))|) n tends to infinity if and only if there is a letter a ′ in A ′ \ {a} such that (|φ(σ n (a ′ ))|) n does not tend to zero. Hence the decidability is deduced from (1). Moreover, if (|φ(σ n (a))|) n does not tend to infinity, then it is bounded. Suppose M n is neither the 1 × 1-matrix [1] nor the null matrix. Then, (|φ(σ n (a))|) n tends to infinity if and only if there exists a letter in A ′ such that φ(a ′ ) is not empty. Moreover, if (|φ(σ n (a))|) n does not tend to infinity, then it goes to 0 and thus is bounded.

Let us conclude with the HD0L ultimate periodicity problem. Let us first suppose that σ satisfies (P1) and (P2). Let w = w 0 • • • w |w|-1 where the w i 's belong to A. As we want to test the ultimate periodicity, from Lemma 20, we can suppose (|φ(σ n (w 0 ))|) n tends to infinity. Consequently we can suppose w = w 0 . We set a = w 0 . Let j 0 be the smallest integer less or equal to |A| + 1 such that σ j0 (a) and σ j0+n0 (a) start with the same first letter for some n 0 verifying j 0 + n 0 ≤ |A| + 1. Such integers exist from the pigeon hole principle. We also assume n 0 is the smallest such integer. Let a i be the first letter of σ j0+i (a), 0

From Lemma 20 it is decidable to know whether (|φ(σ j0+i+kn0 (a i ))|) k tends to infinity. Let Λ be the set of such a i 's. Then, the set of accumulation points in B N of (φ(σ n (w))) n is computable: it is the set of the infinite sequences lim k→+∞ φ(σ j0+i+kn0 (a i )) where a i belongs to Λ. Consequently, (φ(σ n (w))) n converges to an ultimately periodic sequence if and only if there exist u, v ∈ B * such that for all 0 ≤ i ≤ n 0 -1, lim k→+∞ φ(σ j0+i+kn0 (a i )) = uv ω . Thus to decide whether (φ(σ n (w))) n converges to an ultimately periodic sequence, we first have to check (using Theorem 19) that for all 0 ≤ i ≤ n 0 -1, lim k→+∞ φ(σ j0+i+kn0 (a i )) = u i v ω i , for some computable u i , v i ∈ B * . Then, we check whether the sequences u i v ω i are equal (which can be algorithmically realized).

Let then σ be an arbitrary morphism. From Proposition 4 we can suppose that σ p satisfies (P1) and (P2) for some computable p > 0. Then, we proceed as before for the couples (σ p , φ • σ i ), 0 ≤ i ≤ p -1: We test their ultimate periodicity and then we compare the results to finally decide.


Thomas Hézard

Thomas Hélie

Boris Doval

Nathalie Henrich

Malte Kob

Non-invasive vocal-folds monitoring using electrical imaging methods

Many methods have been considered for human larynx imaging and especially vocalfolds monitoring. A widely-used non-invasive technology for vocal-folds monitoring is electroglottography (EGG), a technology based on impedance measurement of the larynx. Electrical impedance tomography (EIT) is another non-invasive electrical measurement method which attempts to reconstruct the conductivity map inside an object. It has been used in several human monitoring applications, and a theoretical study of EIT for vocal-folds monitoring has given promising results [8] but, to our knowledge, no device has been built. In our project, we aim at developing an innovative measurement system for vocal-folds monitoring using both EGG and EIT technologies. Two devices are currently under development. In this paper, we present a brief review of EGG and EIT technologies (section 1), the principles of the two new devices (section 2) and the perspectives they offer for both medical and research fields (section 3).

EGG and EIT in the context of vocal-folds monitoring 1.ElectroGlottoGraphy

The first electroglottograph was developed by Philippe Fabre, professor of biological physics at the University of Lille, in 1957 [START_REF] Fabre | Un procédé électrique percutané d'inscription de l'accolement glottique au cours de la phonation: glottographie de haute fréquence. Premiers résultats[END_REF]. This technology is based on impedance analysis of the larynx; two electrodes are placed on each side of the throat, a low-intensity high-frequency modulated current (commonly around 2 M Hz) is generated and applied to the laryngeal level, and the impedance between the two electodes is measured. This impedance is approximately proportionnal to the vocal-folds contact area. Unlike many imaging technologies (MRI, X-ray, echography) EGG has a frequency range sufficiently large for vocal-folds monitoring: from 0.2 Hz (for deglutition) to F max where F max is between 4 kHz (telephone bandwidth) and 20 kHz (audible bandwidth). However, the output of this measurement system is a time-domain one-dimensionnal signal, which does not reflect the spatial characteristics of vocal-folds vibratory movement.

EGG is used in both medical and research fields. It is commonly used to extract features of the vocal-folds vibration, such as the fundamental frequency, the glottal closure or opening instant, the glottal closed or open quotient [START_REF] Henrich | On the use of the derivative of electroglottographic signals for characterization of nonpathological phonation[END_REF] or to identify the laryngeal mechanism used by the speaker or singer [START_REF] Roubeau | Laryngeal vibratory mechanisms: the notion of vocal register revisited[END_REF]. The principle of an EGG device and the corresponding signals is schematically presented in Fig. 1.

As we said, the electroglottogram is a one-dimensionnal image of the complex laryngeal activity. Therefore, increasing the number of channels -electrodes-is an interesting way of improving

Electrical Impedance Tomography

Electrical impedance tomography (EIT) is a recent electrical imaging technology with a wide range of application, from medical monitoring to sismic activity recording. It has firstly been described by D.C. Barber and B.H. Brown in 1984 [START_REF] Barber | Applied potential tomography[END_REF], and it has raised much research interest since then. EIT consists in injecting a high-frequency current inside a body with two electrodes and measuring the resulting potential distribution (with other electrodes) at the bodys surface. The conductivity map inside the body is recovered using reconstruction algorithms. One can read [START_REF] Holder | Electrical Impedance Tomography: Methods, History and Applications[END_REF] for a complete review of theory, hardware and applications of EIT.

The relevance of EIT for vocal-folds monitoring was recently studied [START_REF] Seppänen | Electrical impedance tomography imaging of larynx[END_REF]. According to their preliminary results, EIT is sensitive to the vibration of vocal-folds. To our knowledge, no device using EIT for vocal-folds monitoring has been already built.

An innovative project of vocal-folds monitoring system

We started a project to conceive a non-invasive vocal-folds monitoring device based on EGG and EIT technologies. The aim of the project is to build a system able to measure precisely the shape and movement of vocal-folds during phonation. In the following, two new devices are described.

Frequency-division multiplexed multi-channel EGG

An improved version of [START_REF] Kob | A system for parallel measurement of glottis opening and larynx position[END_REF] is currently under development, with an aim to improve both the spatial and temporal resolution. Unlike M. Kob's device, which uses time-division multiplexing, our device is based on frequency-division multiplexing in order to be able to improve the temporal resolution without decreasing the spatial resolution. Thin electrode grids are used to improve the spatial resolution.

Fig. 2-(a) describes the general architecture of the system. Each transmitter T k generates a current at the frequency f k and measures the corresponding voltage. Each transmitter is connected to several electrodes through an analog router. On the other side, each receiver R n connects several electrodes to the ground through another analog router and measures the current for each receiving channel.

With such a system, the neck is equivalent to the complete impedances network presented in Fig. 2-(b). The value of each impedance can be computed from the measurement of the current at each receiver and the voltage at each transmitter for every frequencies when N ≤ K. The glottal activity should then be detected precisely, on the basis of a parametric of the conductivity distribution inside the neck which has yet to be defined.

T 1 T 2 T K-1 T K R 1 R 2 R N -1 R N neck router router ... ... T 1 T 2 T 3 R 1 R 2 R 3 (a) (b)

Orthogonal codes multiplexed multi-channel EIT

The second device is more inspired by the EIT technology. The general schematic is the same, presented in Fig. 2-(a). In this device, each transmitter T k generates a current at the unique carrier frequency f c , modulates this current by a command signal g t k (t) (a sum of orthogonal codes) and measures the corresponding voltage. Each receiver R n generates a voltage at the carrier frequency f c , modulates this voltage by a command signal g r n (t) (a sum of orthogonal codes) and measures the corresponding current. Moreover, potential measurements (high input impedance) modules are added and can be connected to electrodes through another analog router.

With this system, one code (orthogonal to the others) can be affected to each path (one path corresponds to one impedance in Fig. 2-(b)). The contribution of each path to the potential distribution is then measured simultaneously. Moreover, this system can be used as well as a classic EIT system (g t k 0 (t) = 1, {T k } k =k 0 disconnected, g r n 0 (t) = 0, {R n } n =n 0 disconnected), as an orthogonal codes multiplexed multichannel EGG ({g r n (t) = 0} n∈[1,N ] ) or as a device in between. Therefore this system will be a very interesting tool for research, this prototype and the relevancy of such a system will soon be tested.

This device is part of a mechatronic project conducted with students from Mines ParisTech. The project includes also robotic larynx with driven vocal-folds built with conductive materials. These larynx will be used to validate the devices before testing it on humans.

Further work and perspectives

These two devices aim at increasing both temporal and spatial resolution compared to existing larynx and vocal-folds monitoring systems. The ultimate goal of such a device would be to be able to reconstruct precisely vocal-folds shape with a sufficient temporal resolution (audible bandwidth). These devices raise technical challenges that need careful studies. At first, proper parametric con-ductivity map model will be needed. Next step is the reconstruction algorithms which has not been studied yet.

It was mentioned that we plan to use grids instead of independant electrodes. This gives us the opportunity to impose constraints on the electrodes' relative position and to use many electrodes on a small surface (several tens of electrodes on a few square centimeters), in other words, consider electrodes as pixels on the skin. Note that, for a given temporal resolution, the spatial resolution depends on the number of transmitters and receivers and on the number of electrodes. Nevertheless, another advantage of our devices is that time-division multiplexing is also possible thanks to the analog routers.

Such a device will have many possible applications in various field, including medical diagnosis, research about voice production and even vocal training.

Figure 1 :

 1 Figure 1: (a) Schematic description of an EGG device. (b) EGG signal (top) and its derivative (bottom). Glottal opening and closing instants are marked with vertical lines. From [2].

Figure 2 :

 2 Figure 2: (a) General schematic view of the multichannel EGG device (configuration and command signals in dotted red, measurement signals in dotted green, electrical components and wires in black, electrodes in blue). (b) Equivalent impedances network for K = N = 3.


We predict a photon Hall effect in the optical cross-section of atomic hydrogen, which is caused by the interference between an electric quadrupole transition and an electric dipole transition from the ground state to 3D 3/2 and 3P 3/2 . This induces a magneto-transverse acceleration comparable to a fraction of g. In atoms with a two level electric dipole transition, a much smaller transverse force is generated only when the atom is moving.

Light scattering exchanges momentum between matter and radiation, and thus induces a force on the matter. Classical light scattering is well known to be affected by a magnetic field. A specific feature, the photon Hall effect (PHE), was first predicted in multiple light scattering [1], and observed shortly afterwards [2] with typical changes in the magneto-transverse photon flux of order 10 -5 per Tesla of applied magnetic field. A Mie theory for the PHE [4] agreed quantitatively with the experiments. Given the wave number k of the incident photon flux and the magnetic field B , the PHE induces an exchange of momentum between scatterer and radiation in the magnetotransverse ("upward") direction along B×k. A light flux of 10 4 W/m 2 incident on a micron-sized particle with a relative PHE of 10 -5 per Tesla experiences a transverse force of 10 -19 N/T, roughly equivalent to the Lorentz force on a charge e moving with a velocity of 1 m/s. The magneto-transverse acceleration for a 10 µm TiO 2 particle would be as small as 10 -11 m/s 2 in a field of 10 Tesla.

Atoms are strong light scatterers that can achieve elastic optical cross-sections as large as the maximum unitary limit λ 2 near optical transitions, and with promising applications in mesoscopic physics [3]. When the typical Zeeman splitting 1 2 ω c (ω c = eB/m e = 17.5 MHz/Gauss is the cyclotron circular frequency) equals the atomic line width (typically γ ≈ 100 MHz), the optical cross-section is significantly altered by the magnetic field, typically true for a few Gauss. Since atoms have small mass, the magneto-transverse recoil would be much larger than for Mie particles. The magneto-cross-section of an atomic resonance with width γ and Zeeman splitting ω c can be estimated as 1 2 (ω c /γ)λ 2 /π 2 . If we would assume the Hall cross-section to be of this order the magneto-transverse acceleration would be as large as 4 km/s 2 per Gauss when tuned the 1S-2P transition in Strontium exposed to a small flux of 100 W/m 2 . Unfortunately, no PHE can occur for pure electric-dipole (ED) transitions, since the ED imposes a symmetry between forward and backward scattering, as well as between upward and downward directions in the magneto-cross-section [4]. The PHE induced by the scattering from pairs of atoms in a cold 88 Sr gaz, is estimated to be a few percent [5].

Can the PHE of a single atom exist at all, and how large will the magneto-transverse momentum transfer to the atom be? Two striking differences exist between classical Mie scattering and light-atom scattering. First, given a monochromatic incident laser beam, the atom is usually subject to inelastic transitions to levels that are no longer excited by the same beam, thus preventing a stationary scattering process. Secondly, given the small mass of atoms, one must anticipate significant velocity recoils that change the resonant frequency via the Doppler effect, and finally reduce the light scattering.

The optical cross-section of an atom is expressed by the Kramers-Heisenberg formula [START_REF] Loudon | The Quantum Theory of Light[END_REF],

dσ dΩ (ωkε → ω s k s ε s ) = α 2 ω 3 s ω 3 |f ED (ω, ε, ε s ) +f EQ (ω, ε, ε s , k, k s ) + • • • | 2
Here, α is the fine structure constant, ω and ω s < ω are incident and scattered frequency, ε and ε s are the polarization vectors of incident and scattered radiation; f (ω) is the complex scattering amplitude associated with transitions in the atom, that can be either elastic or inelastic, and driven by either electric dipole (ED) or quadrupole (EQ). The above expression does not take into account stimulated emission (SE). For this to be true we require that W (ω s , k s , ε s ) < W 0 (ω s ), with W the radiation density per steradian, per bandwidth, per polarization, and W 0 = ω 3 s /(2πc 0 ) 3 its value for the quantum vacuum. We will first focus on the simplest atom, atomic hydrogen, whose physics in a magnetic field has been studied in great detail [6,7]. This atom has the unique property that the fine-structure levels 3P 3/2 and 3D 3/2 strongly overlap, despite their hyperfine structure (HF), The anomalous Zeeman effect of the latter is shown in Fig. 1. For not too large magnetic fields all levels are en-ergetically close and can thus interfere constructively. It is instructive to first simply ignore the spin of both electron and proton, and to adopt a simple 1S ground state and excited levels 3P and 3D separated by the (finestructure energy) of 18 radHz (= 2πs -1 ). The electronic transitions 1S → 3P → 1S and 1S → 3D → 1S are now both elastic. The 1S -3D transition, however, is ED forbidden and requires an EQ transition. The ED transition between the ground state 1S and the 3P level reads

f ED (ω) = ω 2 c 0 m=0,±1 { 1S|r|3P m • ε s }{ 3P m |r|1S • ε} ω -ω P m (B) + iγ P ≡ ω 2 r 2 3P c 0 [P 0 (ε s • ε) + [P 1 -P 0 ](ε s • ẑ)(ε • ẑ) + P 2 (ω)iε s • (ε × ẑ)] (1)
Here i| r |j is the ED matrix element between states i and j. It depends on orbital momentum but has constant radial part r 3P = 0.517a 0 . The second expression is obtained by inserting the orbital eigenfunctions, and by putting P i = 1/(ω -ω m (i, B) + iγ P ). In our simplified picture, the Zeeman effect behaves normally (mω c /2).

We choose k = x, B = ẑ and let B × k = ŷ be the Hall direction. For the elastic EQ transition via the 3D level we find,

f EQ (ω) = ω 2 c 0 m=0,±1,±2 {k s • 1S| 1 2 rr|3D m • ε s } {k • 3D m | 1 2 rr|1S • ε} ω -ω D m (B) + iγ D
with γ D = 32 radMHz the natural line width of the 3D level. This expression can again be developed by inserting the orbital eigenfunctions associated with the 3D level, at fixed radial matrix element q 3D = 0.867a 2 0 . The differential cross-section for incident unpolarized, broadband light is obtained from the interference between the two transitions, averaged over incident polarization, and summed over outgoing polarization. The Hall terms are defined by the difference in flux up and down along the vector ŷ, and are all characterized by a factor i( ks • ŷ) that emerges in the cross-product of the two scattering amplitudes. We shall write this as

dσ dΩ = α 2 1 ∆ ∆ dω ε,εs Re f * ED f EQ = dσ 0 dΩ + α 2 ω 6 ∆c 4 0 r 2 3P q 2 3D Re i( ks • ŷ) m,m ′ Fn (ω, B)A mm ′ (k, ks , B) (2)
The Hall cross-section is a sum over 3 × 5 = 15 cross-products among the magnetic sublevels. The factor Fmm ′ is the frequency-averaged cross-product of the complex line profiles. If the bandwidth ∆ largely exceeds the line widths then

Fmm ′ (ω) = ∞ -∞ dω 1 ω -ω P (m) -iγ P 1 ω -ω D (m ′ ) + iγ D = 2πi ω P (m) -ω D (m ′ ) + i(γ D + γ P ) (3)
It can be seen that only 6 functions A mm ′ actually generate a PHE, with

A 0,m ′ =±1 = m ′ [1 -2( ks • ẑ) 2 ]/60 and A m=±1,m ′ =±2 = [m + 1 2 m ′ + (-2m + 1 2 m ′ )( ks • x) 2 - 1 2 m ′ 1 2 ( ks • ŷ) 2 ]
/60. Note that this simplified picture highlights the PHE as a "which-way" event inside the hydrogen atom. It is straightforward to calculate from Eq. ( 2) the total magneto-transverse recoil force (black line in Fig. 2).

The present picture poses three problems. First we know that excited 3P atoms will have a significant probability to decay inelastically to the meta-stable state 2S so FIG. 2: Three different broadband laser beams are necessary to generate a stationary process with magneto-transverse recoil. Laser 1 induces the transition to 3P 3/2 and 3D 3/2 levels that generate the PHE. Laser 2 reassures that the inelastic decay to 2S 1/2 is pumped back to 3P 3/2 . Finally, beam 3, propagating opposite to the beam 1 , compensates the longitudinal photon recoil produced by laser 1.

that the PHE process would rapidly come to an end. Secondly, absorbed photons will transfer momentum to the atom that will rapidly become Doppler detuned from the incident laser. Finally, the inclusion of hyperfine structure (HF) considerably complicates the above picture.

The longitudinal photon recoil to the atom of the first laser can be compensated by a second laser beam (intensity I 2 ) opposite to the first, and exciting the atom to the 2P transition. If I 2 ≈ 3I 1 the average recoil rate is equal to zero (see Figure 2). The occurrence of inelastic decay to 2S must be compensated by a third laser beam (intensity I 3 ) that pumps 2S atoms back to 3P . A straightforward analysis shows that detailed balance results in N 2S /N 1S = (ω 23 /ω 13 ) 3 I 3 /I 1 . If the two laser intensities are roughly equal we infer that N 2S ≪ N 1S , so that the PHE with 1S as initial state is maintained. Note that the 2S -(3P, 3D) transitions also induce a PHE which we will not discuss in view of its much smaller transverse recoil.

The inclusion of HF structure is a straightforward process that we shall not discuss in detail. The HF eigenfunctions 3P (D) j= 3 2 , f = 1, 2, m = -f, .., f can be constructed from the product states of orbital momentum, electron and proton spin with appropriate Clebsch-Gordan coefficients. In the presence of a magnetic field the magnetic sublevels m = 0, ±1 of the HF levels f = 1, 2 mix, thus giving the 8 sublevels whose Zeeman effect is shown in Fig. 1. The 1S 1/2 ground state splits into one singlet and a triplet at 8.9 radGHz higher in energy. The PHE can be determined by collecting all cross products among the transitions from the 4 1S 1/2 to the 8 3D 3/2 and 3P 3/2 levels. The result of this cumbersome task is shown as the red line in Figure 3. The HF splitting decreases the recoil because the overlap between the We finally show that a PHE can be induced by an ED transition once the atom is moving. Let K ′ be the frame that moves with the atom, and K the one in which the atom moves with velocity v. The ED magneto-transverse scattering cross-section for a two-level atom in frame K ′ follows from the interference between first and third term in Eq. ( 1),

dσ ′ dΩ ′ (ω ′ k ′ → ω ′ s k ′ s ) = 1 9 ω ′ 3 s ω ′ α 2 r 4 01 c 2 0 Im(P 0 P * 2 ) ×[ k′ s • k′ ][ k′ s • ( B × k′ )] (4)
This cross-section exhibits no net PHE since forward and backward contribution cancel the flux along k × B. However, this cancelation is perturbed by the Doppler effect. The cross-section dσ relates an incident flux ρ(ω, k)/c 0 to an outgoing current ρ s (ω s , k s )dΩr 2 /c 0 at a distance r in the far field. Since r is unaffected by a Lorentz transformation to order v/c 0 , and since the radiation density ρ transforms as ρ ′ = (ω ′3 /ω 3 )ρ [START_REF] Milonni | The Quantum Vacuum[END_REF], the cross-section in frame K is

dσ dΩ (ωk → ω s k s ) ≈ ω ′ ω s ωω ′ s 3 dσ ′ dΩ ′ (ω ′ k ′ → ω ′ s k ′ s )
We insert k′

(s) ≈ k(s) (1 + k(s) • v/c 0 ) -v/c 0 and ω ′ (s) ≈ ω (s) (1 -v • k(s) /c 0 )
and assume for simplicity that the atom moves either parallel or opposite to the incident wave vector k. Note that transformation factors involving ω ′ s in the formula above cancel and do not contribute to the PHE. The only contribution is the Lorentz transform of the angle-dependent factor in Eq. ( 4) that generates -

[1 -2( ks • k) 2 ](k s • (v × B)/c 0 .
The momentum transfer to the atom exhibits a magneto-transverse force,

F = - 1 ω I(k) dΩ s k s dσ dΩ (ωk → ω s k s ) = I(k) 4π 45
α 2 ω 4 r 4 01 c 3 0 Im(P 0 P * 2 )(ω ∓ vω c 0 , B) v c 0 × B (5)
with I the incident flux in W/m 2 . Apart from the Doppler shift ∓v/c 0 of the incident frequency, this force is equal for motion parallel (-) or opposite to the incident beam. This is useful since the normal scattering of the light beam also induces a longitudinal acceleration. The presence of two opposite beams with properly chosen intensities allows to induce a magneto-transverse recoil and at the same time select a specific constant velocity. For typical parameters in a total flux of 100 W/m 2 (small enough for stimulated emission to be small) applied to 88 Sr we find the stable velocity v = 4.4 m/s and a magneto-transverse acceleration a = 43 µm /s 2 (Fig. 5). This is much smaller than what we found for hydrogen, since 88 Sr is heavier and v/c 0 ≪ α 2 , but is still measurable.

In conclusion, we have quantified the magnetotransverse scattering of light from unpolarized atomic Gauss. The beam parallel to the speed is 50% more intense so that a stable velocity v = 4.4 m/s is selected (acceleration a = 0).

hydrogen. It is caused by the interference of en electric dipole transition and a electric quadrupole transition. A transverse recoil of several m/s 2 is predicted, i.e. a fraction of g. The generalization to other atoms seems difficult since one needs overlapping transitions with different (orbital) symmetry. these are often excluded by (hyper)fine splitting. Maybe the application of high magnetic fields may induce level-crossing of remote transitions, this causing a PHE. An electric dipole alone is found to induce a magneto-transverse scattering only when the atom is moving, though with much smaller accelerations of order µm/s 2 It could be interesting to study the atomic spin-Hall effect in the spin-polarized S-state of atomic hydrogen [7], and to make a link with previous predictions [START_REF] Xiong-Jun Liu1 | [END_REF] This work was supported by the ANR contract PHO-TONIMPULS ANR-09-BLAN-0088-01.

FIG. 1 :

 1 FIG. 1: Hyperfine structure of the 3P 3/2 (left) and 3D 3/2 (right) level of atomic hydrogen, as a function of magnetic field. Equal colors indicate equal values for the hyperfine magnetic quantum number m. The height of the vertical bar on the right indicates the line width γ. The zero in frequency is chosen at the fine structure level of 3P 3/2 . The one of 3D 3/2 is 21.07 radMHz lower.

FIG. 3 :

 3 FIG. 3: Magneto transverse recoil acceleration of the hydrogen atom in the presence of a broadband laser beam with flux I = 10 kW/m 2 and bandwidth ∆ = 10 radGHz (thus resolving the HF ground state). The black curve follows from the model with neglect of (hyper)fine structure, the red curve takes into account the full hyperfine structure of the 1S 1/2 ground state and the 3D 3/2 and 3P 3/2 levels, which results in a smaller PHE recoil though with same sign.

FIG. 5 :

 5 FIG. 5: Longitudinal acceleration of 88 Sr by two opposite beams with total flux (I = 100 W/m 2 ), as a function of atom velocity. The atomic transition is taken red-tuned by one line width (γ = 101 MHz) in a transverse magnetic field of B = 1Gauss. The beam parallel to the speed is 50% more intense so that a stable velocity v = 4.4 m/s is selected (acceleration a = 0).

  Transverse Momentum Transfer in Atom-Light Scattering B.A. van Tiggelen, 1 A. Nussle, 1 and G.L.J.A. Rikken 2 1 Université Grenoble 1/CNRS, LPMMC UMR 5493, B.P. 166, 38042 Grenoble, France 2 LNCMI, UPR 3228 CNRS/INSA/UJF Grenoble 1/UPS, Toulouse & Grenoble, France (Dated: January 2, 2013)


Marie Candito
email: marie.candito@linguist.jussieu.fr

Djamé Seddah
email: djame.seddah@paris-sorbonne.fr

Effectively long-distance dependencies in French : annotation and parsing evaluation

We describe the annotation of cases of extraction in French, whose previous annotations in the available French treebanks were insufficient to recover the correct predicate-argument dependency between the extracted element and its head. These cases are special cases of LDDs, that we call effectively longdistance dependencies (eLDDs), in which the extracted element is indeed separated from its head by one or more intervening heads (instead of zero, one or more for the general case). We found that extraction of adep en d en t of a finite verb is very rarely an eLDD (one case out of 420 000 tokens), but eLDDs corresponding to extraction out of infinitival phrase is more frequent (one third of all occurrences of accusative relative pronoun que), and eLDDs with extraction out of NPs are quite common (2/3oftheoccurrences of relative pronoun dont). We also use the annotated data in statistical dependency parsing experiments, and compare several parsing architectures able to recover non-local governors for extracted elements.

Introduction

While statistical parsers obtain high overall performance, they exhibit very different performance across linguistic phenomena. In particular, most statistical parsers perform poorly on long-distance dependencies (LDDs), which, thoughr a r e ,a r e important to fully recover predicate-argument structures, which are in turn needed for semantic applications of parsing. Poor performance on LDDs is known of English statistical parsers, even though the training data does contain information for resolving unbounded dependencies (the Penn Treebank, or the specific dataset evaluated by Rimell et al. [START_REF] Rimell | Unbounded dependency recovery for parser evaluation[END_REF]). For French, the situation is worse, since the usual training data, the French Treebank (Abeillé and Barrier [START_REF] Abeillé | Enriching a french treebank[END_REF]), is a surface syntagmatic treebank that does not contain indications of LDDs : extracted elements bear a grammatical function, but no annotation indicates their embedded head. Hence syntagmatic stochastic French parsers cannot capture LDDs. Concerning dependency parsing, French dependency parsers can be learnt on the DEPFTB, resulting from the automatic conversion of the FTB into projective dependency trees (Candito et al. [START_REF] Candito | Statistical french dependency parsing : Treebank conversion and first results[END_REF]). But we will show that this automatic conversion leads to wrong dependencies for particular cases of LDDs -cases we call effectively-long-distance dependencies (eLDDs), in which the fronted element is extracted from an actually embedded phrase -, and thus statistical parsers learnt on the DEPFTB are unable to recover such cases correctly.

In this paper, we describe the manual annotation, performed on the FTB and the Sequoia treebank (Candito and Seddah [START_REF] Candito | Le corpus sequoia : annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical[END_REF]), of the correct dependencies in eLDDs, leading to non-projective dependency treebanks. We then evaluate several dependency parsing architectures able to recover eLDDs.

Target linguistic phenomena

Extraction is a syntactic phenomena, broadly attested across languages, in which a word or phrase (the extracted element) appears in a non-canonical position with respect to its head. For a given language, there are well-defined contexts that involve and licence an extraction. In English or French, the non-canonical position corresponds to a fronting of the extracted element.

A first type of extraction concerns the fronting of the dependent of a verb, as in the four major types topicalization (1), relativization (2), questioning (3), it-clefts (4), in which the fronted element (in italics) depends on a verb (in bold):

( Since transformational grammar times, any major linguistic theory has its own account of these phenomena, with a vocabulary generally bound to the theory. In the following we will use 'extracted element' for the word or phrase that appears fronted, in non canonical position. One particularity of extraction is 'unboundedness': stated in phrase-structure terms, within the clause containing the extraction, there is no limit to the depth of the phrase the extracted element comes from. In dependency syntax terms, for a fronted element f appears either directly to the left of the domain of its governor g, or to the left of the domain of an ancestor of g. We focus in this paper on the latter case, that we call effectively long-distance dependencies (eLDD). In examples (1) to (4), only the versions with the material in brackets are eLDDs.

In French, another case of eLDD is when a PP is extracted from a predicative complement either nominal or adjectival: [START_REF] Candito | Le corpus sequoia : annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical[END_REF] la the mélancolie melancholy à to laquelle which il he est is enclin prone ('the melancholy he is prone to') Other cases of eLDDs arise for some PPs with preposition de, which under some well-studied conditions (see for instance Godard [START_REF] Godard | Extraction out of NP in French[END_REF]) can be extracted from subject or direct object NPs, as in [START_REF] Chrupaa | Morfette: A tool for supervised learning of morphology[END_REF] 3 Target French Treebanks

French treebank and Sequoia treebank

Our objective is to obtain a dependency treebank for French with correct governors for extracted elements. This treebank will thus contain non-projective links.W e perform our annotation of cases of extraction on two treebanks :

• the French Treebank (Abeillé and Barrier [START_REF] Abeillé | Enriching a french treebank[END_REF]) (hereafter FTB), a constituency treebank made of 12351 sentences2 from the national newspaper Le Monde

• the Sequoia treebank (Candito and Seddah [START_REF] Candito | Le corpus sequoia : annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical[END_REF]), an out-of-domain corpus annotated following the FTB's annotation scheme. It contains roughly 1000 sentences from the French wikipedia, 1000 sentences from the medical domain (from medicines' marketing authorization reports from the European Medecine Agency), 500 sentences from Europarl and 500 sentencesf r o m the regional newspaper L'Est Républicain.

These are constituency treebanks, in which the dependents of verbs are labeled with a grammatical function, since a given structural position may correspond to different grammatical relations. Candito et al. [START_REF] Candito | Statistical french dependency parsing : Treebank conversion and first results[END_REF] describe a tool for the automatic conversion of such constituency trees into surface dependency trees. 3 We briefly describe below this procedure, and detail the incorrect result obtained for eLDDs.

Automatic conversion to surface dependencies

The conversion procedure is based on the classic technique of head propagation rules, proposed for English by Magerman [START_REF] David | Statistical decision-tree models for parsing[END_REF], and outputs projective surface dependency trees (each token has exactly one governor, except the root) : (i) Nodes in phrase-structure trees are annotated with their lexical head, using head-propagation rules, that state how to find the syntactic head in the right-hand side of a CFG rule;

(ii) Using the lexical heads, bilexical dependencies are extracted. If the constituent node for the dependent bears a functional label, it is used as the label of the dependency; (iii) Remaining unlabeled dependencies are labeled using heuristics.

With that technique, output dependency trees are necessarily projective, and non-local dependents are wrongly attached to the local lexical head, as exemplified in Figure 1 in which the accusative relative pronoun que is wrongly attached to the local head semblaient (seemed) instead of its actual syntactic head partager (to share). A crucial point here is that a wrong dependency arises only for LDDs that are eLDDs. For instance from a simplified version of tree (a), without the raising verb, we would obtain the correct dependency between que and the verb partager.

Manual annotation 4.1 Selection of occurrences to annotate

One major difficulty to annotate extractions is that though ubiquitous in the linguistic literature, they are quite rare in actual texts. Further, some cases like topicalization (cf. example (1) above), involve structural clues only, and no lexical clue, namely no wh-words. Topicalization does exist in French, but is much rarer than relativization, it-clefts or questioning, and is restricted to the extraction of prepositional phrases. Hence, because we could not afford to scan the whole treebank to look for extractions, and also because it is unclear whether such dependencies can be recovered with current parsing techniques, we chose as a first step to focus on words known to be likely to involve an extraction, namely the clitic en and wh-words (relative and interrogative pronouns and determiners). This allows to capture the cases exemplified in section 2, except topicalization. We examined each occurrence of wh-word and of the clitic en, and annotated the correct dependency in case of non-local dependency.

Annotation scheme and methodology

Functional paths

We chose to annotate non-locality using functional paths, made of sequences of dependency labels, as proposed in the LFG framework. We were inspired by Schluter and van Genabith [START_REF] Schluter | Preparing, restructuring, and augmenting a French Treebank: Lexicalised parsers or coherent treebanks?[END_REF], who have used them to annotate a manually modified version of half the French Treebank. 5 Before formalizing this notion, let us take as example the automatically-derived dependency tree in Figure 1, in which the relative pronoun que is wrongly attached to the local governor semblaient. The non-local governor is partager. We define the functional path for que to be the sequence of labels appearing on the path between que and its correct governor, namely OBJ.AT S, which can be read as "'que' should be the OBJ of the ATS of its local governor".

More generally, let d be a lexical item that should depend on a non-local governor nlg.L e tADT be the dependency tree obtained by automatic conversion from the source constituency tree, and CDT the correct dependency tree that we target.

Since nlg is non-local, the tree ADT contains a wrong dependency lg l 0 → d, while CDT contains nlg l 0 → d (we suppose here that the label l 0 is correct is ADT ). For such cases, we define a functional path as the sequence of labels l 0 .l 1 ....l n that appear, in the incorrect tree ADT , on the path between the dependent d and its non-local governor nlg.

The manual annotation consists in making functional paths explicit : in the previous formalization, it amounts to modifying ADT into ADT ′ , by labeling the dependency lg l 0 -→ d with the functional path as label : lg l 0 .l 1 ...l n -→ d. Note that eLDDs are exactly the cases involving a functional path of length > 1 instead of a simple functional tag (which can be regarded as a functional path of length 1).

Automatic interpretation of functional paths

This kind of annotation can be used in a straightforward way to recover the correct governor of extracted elements. We give in figure 2 the algorithm used to interpret functional paths as the indication of non-local dependencies : it changes a tree containing functional paths into a corresponding tree, in which dependents that are non-local, are attached to their non-local governors.

0 • ADT ′ ← ADT 1 • while ADT ′ contains a dependency a of the form lg l 0 .l 1 ...l n -→ d,withn > 0, do 2 • i ← n, g i ← lg 3 • while i > 0do 4 • G ← nodes x such as g i l i -→ x and x = d 5 • if G = / 0,choosetheleft-mostmostappropriatenodex,andsetg i-1 ← x 6
• else, continues to next element in while 1 7

• i ← i -1 8

• replace in ADT ′ the dependency a by g 0 If we go back to the example of Figure 1, the manual annotation applied to tree (b) is given in tree (c) in Figure 3. The interpretation of the sole functional path in tree (c) outputs the tree (d), which is non-projective.

l 0 -→ d
The functional paths can be inconsistent with respect to the tree they appear in. This results in obtaining an empty set at line 4 in Figure 2. During the manual annotation phase, such cases can be used as warnings for a wrong functional path. When using the procedure in the parsing phase (see section 5), such functional paths are simply discarded and the label l 0 .l 1 ...l n is replaced by l 0 .

Further, the functional paths can be ambiguous. This is the case when the set G obtained at line 4 contains more than one element, at any point in the functional path. In these cases, the procedure prefers verbal governors over any other POS, and leftmost governor in case of remaining ambiguity.

This procedure is similar to the deprojectivization procedure defined by Nivre and Nilsson [START_REF] Nivre | Pseudo-projective dependency parsing[END_REF], when these authors use the encoding scheme they called 'Head'. More precisely, both procedures are equivalent in case of a functional path of length 2. We needed to define a procedure able to cope with paths of arbitrary length, in order to interpret any manually annotated functional path.

Annotation methodology

Because the original treebanks we use have been annotated in constituency format, we chose to annotate the above-mentioned functional paths in the constituency trees, in order to retain the property that the dependency treebank can be automatically converted from the constituency trees. So, for the example of Figure 1, we annotate the functional path OBJ.AT S on the NP node that dominates the relative pronoun : NP-OBJ is replaced by NP-OBJ.ATS, then the usual constituency-todependency conversion produces the left tree of Figure 3, and the functional path interpretation procedure produces the right tree of Figure 3. 6We performed manual annotation of functional paths on a bracketed version of the French Treebank (called the FTB-UC by (Candito et al. [START_REF] Candito | Statistical french dependency parsing : Treebank conversion and first results[END_REF])), and on the bracketed version of the Sequoia Treebank, using the WordFreak tool (Morton and LaCivita [START_REF] Morton | Wordfreak: an open tool for linguistic annotation[END_REF]), customized to handle the relevant sets of POS, non terminals and functional labels. The annotation for the words en and dont were performed independently by two annotators using WordFreak, and adjudicated by an expert annotator. The annotation for all the other wh-words were directly performed by a single expert annotator, because they potentially involve longer dependencies than for the word en, hence requiring to define more difficult (longer) functional paths. Then we applied the functional path interpretation algorithm (Figure 2), to obtain dependency versions of the FTB and the SEQTB with correct governors in case of eLDD. The resulting annotations are freely available. 7

Quantitative characteristics

The resulting annotation provides a picture of the prevalence of extraction phenomena for a corpus of journalistic text (FTB) and for a corpus with mixed genres (the Sequoia corpus). We give various numbers of tokens for the annotated data in table 1, for the FTB, the SEQTB, and for the concatenation of both corpora.

The first observation is that the cases of extraction leading to eLDDs are very rare : for the whole FTB +SEQTB corpus, 0.16% of the tokens received a non-local governor (i.e. a functional path of length > 1). Further, more than 80% of eLDDs have a functional path of length 2, namely are "not-so-long" distance dependencies.

Focusing on projectivity, we see that only around two thirds of the eLDDs are non-projective (359 out of 618 dependencies). This is because most eLDDs are extractions from a subject NP, as in (6) (noted with functional path 'DEP.SUJ' : the extracted element is the dependent of the subject of the local (wrong) head). In general, no dependent of the local verbal head intervenes between the subject and the extracted element (en or dont) as in [START_REF] Chrupaa | Morfette: A tool for supervised learning of morphology[END_REF], projectivity is preserved. If we focus on the top three lexical items that exhibit eLDDs, we obtain the accusative relative pronoun que, the genitive relative pronoun dont and the anaphoric clitic en. As can be seen in table 2, these three lemmas totalize 570 out of the 618 cases of annotated eLDD in the FTB +SEQTB treebanks. 9 Note that though we saw eLDDs are very rare, these particular three lemmas have a substantial proportion of eLDD occurrences, especially dont (65.7% of its occurrences).

The most frequent element extracted from a verbal phrase is the relative pronoun que. A striking observation is that for all the 152 eLDD cases involving que, the embedded phrase que originates from is infinitival (as in the example Figure 3), and none is a finite clause. 10 However, though the relative pronoun dont and the clitic en can either depend on verbs, nouns or adjectives, the majority of eLDDs are cases of extraction out of NPs. More precisely, out of subject NPs for dont (251 cases of functional paths DEP.SUJ out of 329) and out of object NPs for en (51 cases of functional paths DEP.OBJ, out of 89). The other prevalent case for clitic en is the extraction out of predicative complement (24 cases of functional paths DEP.ATS).

Parsing experiments

In this section we list and evaluate various parsing strategies able to output eLDDs. Though the overall parsing performance is unlikely to be affected by this parameter (given the very small amount of annotated eLDDs), it seems interesting to focus on attachment scores for the specific tokens that do often trigger eLDDs.

We relate experiments both using the "local" dependency trees, namely trees automatically converted from constituency trees without functional paths, and us- 8 Non projectivity also arises when extracting a more deeply embedded dependent within the subject NP, as in "une entreprise dont la moyenne d'âge des salariés dépasse 40 ans" (acompany of-which the average of age of the employees is over 40). 9 Other cases concern (i) extractions of prepositional phrases (pied-piping), such as in example 3, for which the token that will bear the eLDD is the head preposition of the PP (à in example 3) or (ii) rare cases of extraction of NPs with wh-determiner, for which the noun bears the eLDD. 10 We found no extraction out of an embedded finite clause in the FTB, and one in the SEQTB, in which the extracted element is a PP. 11 In all our experiments the predicted parses are evaluated against the non local (pseudo-)gold dependency trees (while for training, we sometimes use the local dependency trees). We provide unlabeled and labeled attachment scores for all tokens except punctuation, and for the three lexical items that have a non local governor most frequently (the three lemma+POS pairs of Table 2).

We use MaltParser (Nivre et al. [START_REF] Nivre | Maltparser: A data-driven parser-generator for dependency parsing[END_REF]), version 1.7 and MSTParser (McDonald [START_REF] Mcdonald | Online learning of approximate dependency parsing algorithms[END_REF]), version 0.5.0.12 For the features, we use the best ones from a benchmarking of dependency parsers for French (Candito et al. [4]), except we removed unsupervised word clusters as features. 13 For MaltParser, we always use the arc-eager parsing algorithm, that can provide projective trees only. 14 For MSTParser, we either use order 1 factors and the Chu-Liu-Edmonds algorithm, that can output non projective trees, or order 2 factors, with the Eisner algorithm, restricted to projective trees. We also test pseudo-projective parsing (Nivre and Nilsson [START_REF] Nivre | Pseudo-projective dependency parsing[END_REF]), where non projective trees are transformed into projective ones, with label marking to allow the reverse the graph transformation: we use MaltParser to obtain projectivized versions of the non local trees, then either MaltParser or MSTParser to train a (projective) parser on these, and MaltParser again to de-projectivize the obtained predicted parses. 15 If we look at the overall performance, we observe, as usual, that MSTParser order 2 performs better than MaltParser. Further, training on the local, non local or projectivized trees has practically no impact (differences are not significant). When focusing on the lexical items that are likely to exhibit a non local dependency, the picture is quite different. First, it can be noted that using the non projective decoding for MSTParser, because it implies using order 1 factors, is not worth: the gain obtained for the eLDDs is too small to counterbalance the drop in performance when using order 1 instead of order 2 factors. Second, when comparing performance across the various training trees types, we note that pseudo-projectivization performs best on eLDDs. Moreover performance on eLDDs with training on projectivized data is comparable for MaltParser and MSTParser. The best strategy both overall and for eLDDs seems to be to use pseudo-projectivization with MSTParser and projective decoding, in order to use higher order factors.

SEQTB

Related Work

The Penn Treebank's annotation style of all types of long distance dependencies considerably eases the extraction of wide coverage grammars, and the building of high performing deep syntax parsers, as long as their underlying linguistic framework is able to cope with those complex phenomena (Hockenmaier et al. [START_REF] Hockenmaier | Data and models for statistical parsing with Combinatory Categorial Grammar[END_REF] for CCG; Cahill et al, [START_REF] Cahill | Long-Distance Dependency Resolution in Automatically Acquired Wide-Coverage PCFG-Based LFG Approximations[END_REF] for LFG based parsing; Miyao et al. [START_REF] Miyao | Probabilistic disambiguation models for wide-coverage hpsg parsing[END_REF] for HPSG). Dependency parsers, when trained on a non projective dependency version of the PTB, and with the use of post-parsing heuristics, exhibit a similar range of performance than the parsers cited above (Nivre et al. [START_REF] Nivre | Evaluation of dependency parsers on unbounded dependencies[END_REF]). For French, as noted in introduction, non local dependencies were not natively annotated in the FTB. This complicates of-course direct comparison of our work. Schluter and van Genabith [START_REF] Schluter | Dependency parsing resources for french: Converting acquired lexical functional grammar f-structure annotations and parsing f-structures directly[END_REF] focus on producing treebank based LFG approximations for French, using for this a modified version of part of the FTB, where they annotated functional paths for a few cases. Clergerie [START_REF] De | Convertir des dérivations TAG en dépendances[END_REF] proposes a deep symbolic parser for French, which can recover LDDs directly (including eLDDs), but currently quantitative evaluation of LDDs for this parser remains to be performed. More generally, works on LDDs do not focus specifically on eLDDs, though they are the most difficult type of LDDs. For example, Rimell et al. [START_REF] Rimell | Unbounded dependency recovery for parser evaluation[END_REF] describe a 800 English sentences corpus used for the evaluation of wide coverage parsers on unbounded dependencies, but over all eight types of unbounded dependencies only one is exclusively of eLDD type.

Conclusion

We have annotated cases of effectively long distance dependencies for two French treebanks, totalizing over 15000 sentences. We could verify that non local dependencies are very rare in actual French texts: we annotated a non local governor for 513 tokens only out of over 420000 tokens. Yet, they are massive within the occurrences of the relative pronoun dont, and to a lesser extent que, and also frequent for the clitic en. We noted that extraction out of finite verbal clause is totally absent from the corpora we've annotated (one case only for over 15000 sentences), but extraction out of infinitival clause accounts for one third of the occurrences of the relative pronoun que. Further only 2 thirds of annotated eLDDs give rise to non projective links. As far as parsing is concerned, the best results, both overall and on eLDDs, are obtained when combining pseudo-projectivization and MSTParser with order 2 factors and projective decoding.

4

 4

Figure 1 :

 1 Figure1: Left: An NP as annotated in the original French Treebank scheme (for a feeling that (they) all seemed (to) share). Right: corresponding automatically derived dependency tree, with wrong governor for the wh-word que.

Figure 2 :

 2 Figure 2: Algorithm to interpret functional paths : find the non-local governors and change the dependency tree accordingly

Figure 3 :

 3 Figure 3: Left: Tree (c) is a modification of tree (b), with (manually) annotated functional path for the extracted element que. Right: Tree (d) is the output (nonprojective) tree after using the algorithm Figure 2 to interpret functional paths.

  .

	(6)	un	échec		dont		(Léo	me	dit	que)	les	causes	sont	bien	connues
		a	failure	of-whom	(Léo	to-me	says	that)	the	causes	are	well	known
		'a failure whose causes (Leo tells me) are well known'
	Those de-phrases are precisely the ones that can be cliticized, with the anaphoric
	clitic en (of-it) appearing on the verb governing the NP, as in (7). 1
	(7)	Tu		en	connais	bien	les		raisons
		you	of-it	know	well	the	reasons 'You know well the reasons for it'
	To sum up, eLDDs comprise any case of extraction out of predicative comple-
	ments, nominal subjects or objects (examples (5) to (7)), and cases of extraction of
	a dependent of a verb (examples (1) to (4)) only when involving intervening heads,
	(such as to think in these examples).

Table 1 :

 1 8 For the FTB and the SEQTB, total number of tokens, tokens with non-local dependency, i.e. with length of functional path (fpl) > 1, tokens with fpl=2, fpl=3, fpl > 3; Number of tokens with fpl>1 that have a non projective dependency.

			Number of tokens
	Treebank	total with eLDD (%) fpl=2 fpl=3 fpl>3 non projective
	FTB	350931 555 (0.16 %) 466	69	20	317
	SEQTB	69238	63 (0.09 %)	47	13	3	42
	FTB +SEQTB 420169 618 (0.15%)	513	82	23	359

Table 2 :

 2 Statistics for the three lexical items having a non-local governor most frequently: total number of occurrences, number with and without local governor, and top-three most frequently-annotated functional paths. ing the "non local" dependency trees, which have corrected dependencies for eL-DDs (obtained via the procedure described in section 3.1). The local trees are projective, whereas the non local trees contain a few non projective links (two thirds of the eLDDs are non projective, cf. section 4.3).We use the usual split for the 2007 version of the FTB (1235, 1235 and 9881 sentences for test, development and training sets respectively). For evaluation, we use as test sets the whole SEQTB on top of the usual FTB development and test sets.

				Number of occurrences in FTB +SEQTB
	Lemma	POS	total local gov non-local gov Top-3 most frequent fct paths
	que	relative	616	464	152 (32,8%)	OBJ.OBJ	77
		pronoun				OBJ.OBJ.OBJ	22
						OBJ.OBJ.DE_OBJ	19
	dont	relative	501	172	329 (65.7%)	DEP.SUJ	251
		pronoun				DEP.OBJ	29
						DEP.ATS	27
	en	accusative 411	322	89 (21,7%)	DEP.OBJ	51
		clitic				DEP.ATS	24
						DEP.SUJ	11

Table 3 :

 3 Parsing performance for malt or mst, with training on either local, non local, or projectivized (pproj) trees.

Note that in that case, the dependency between the clitic and the noun is bounded, but we still consider it a eLDD, because the clitic appears locally to the head (the verb) of the NP it depends on.

As distributed in 2007. The current release has around 4000 additional sentences.

Included in the BONSAI toolkit (http://alpage.inria.fr/statgram/frdep/fr_stat_dep_parsing.html).

Note that the anaphoric relation between the pronoun and its antecedent is then trivial to recover, provided the relative clause is correctly attached.

But these authors obtain only

cases in total, suggesting the linguistic constructions covered are few. Note we chose to use reverse functional paths, for easier reading.

We are aware that such an annotation task supposes a very good understanding of both the linguistic phenomena at play, and of the ad-hoc conversion to dependency procedure. Yet this has the advantage, over more traditional annotation using coindexed traces, that annotation on bracketed constituency trees is easier than on dependency structure.

The SEQTB with correctly annotated eLDDs is available at https://www.rocq.inria.fr/alpagewiki/tiki-index.php?page=CorpusSequoia. The FTB with non-local dependencies is available on request, provided you have the license for the FTB.

As we did no parameter tuning, we did not reserve a test set for final test.

Available at http://www.maltparser.org and http://sourceforge.net/projects/mstparser.

POS are predicted using MORFETTE (Chrupaa et al.[START_REF] Chrupaa | Morfette: A tool for supervised learning of morphology[END_REF]), and lemmas and morphological features are predicted using the BONSAI toolkit.

Experiments with the swap algorithms showed degraded performance, supposedly due to the feeble amount of non-projective links.

We report results with the 'head' marking strategy of Nivre and Nilsson, performing very slightly better than the other two strategies (the difference not being significant).