IRMAR Matthieu Calvez
email: matthieu.calvez@univ-rennes1.fr

IRMAR Bert Wiest
email: bertold.wiest@univ-rennes1.fr

FAST ALGORITHMIC NIELSEN-THURSTON CLASSIFICATION OF FOUR-STRAND BRAIDS

We give an algorithm which decides the Nielsen-Thurston type of a given four-strand braid. The complexity of our algorithm is quadratic with respect to word length. The proof of its validity is based on a result which states that for a reducible 4-braid which is as short as possible within its conjugacy class (short in the sense of Garside), reducing curves surrounding three punctures must be round or almost round. As an application, we give a polynomial time solution to the conjugacy problem for non-pseudo-Anosov four-strand braids.

During the 1990's, algorithms which decide the type (called the Nielsen-Thurston type) of a given mapping-class were constructed via the theory of train-tracks ( [START_REF] Bestvina | Train-tracks for surface homeomorphisms[END_REF], [START_REF] Los | Pseudo-Anosov maps and invariant train tracks in the disc: a finite algorithm[END_REF]). Unfortunately, the complexity of these algorithms remains unknown. Even in the particular case of the n-strand braid group B n (i.e. the mapping class group of an n-times punctured disk) the problem of deciding whether a given braid is reducible or not (which we call reducibility problem) has currently no known polynomial time solution.

An alternative algorithm in this particular case, using Garside theory, is given in the paper [START_REF] González-Meneses | Reducible braids and Garside theory[END_REF] (which builds on [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF]). However, the complexity of the algorithm in [START_REF] González-Meneses | Reducible braids and Garside theory[END_REF], while conjectured to be polynomial, strongly depends on an open question. In the present paper we give a polynomial solution to the reducibility problem in the particular case of 4-braids. More precisely we establish the following result: Theorem 1.1. There is an algorithm which decides the Nielsen-Thurston type of any given 4-braid x, and whose running time is O(l 2 ), where l denotes the length of x in the classical Artin generators σ i .

Corollary 1.2.

There is a polynomial time solution to the conjugacy search problem for 4-strand braids in the non-pseudo-Anosov case, i.e. deciding whether two braids, at least one of which is not pA, are conjugate, and if they are, finding a conjugating element.

Together with Theorem 2 of [START_REF] Ito | Braid ordering and the geometry of closed braids[END_REF] we also obtain the following:

2010 Mathematics Subject Classification. 20F36, 20F10, 20F65.

Corollary 1.3.

There is an algorithm with the following properties. It takes as its input a 4-strand braid x whose Dehornoy floor is at least 3, and whose closure is a knot K; and it outputs, after a calculation in time O((length(x)) 2 ), whether K is • a torus knot • a satellite knot (and in this case it also outputs the reducing torus)

• a hyperbolic knot.

The plan of the paper is as follows. In this first section we recall some facts about reducible braids and Garside theory; the second section is devoted to the proof of Theorem 1.1 and Corollary 1.2, modulo the key technical result (Proposition 1.10) whose proof is deferred to the third section. Finally in the fourth section we give some examples and conjectures related to the reducibility problem in braid groups.

1.2. Reducible braids. Let D n be the closed disk in C with diameter [0, n + 1] and with the points {1, • • • , n} removed. It is known [START_REF] Farb | A primer on mapping class groups[END_REF][START_REF] González-Meneses | Basic results on braid groups[END_REF] that the n-strand braid group B n is identified with the mapping class group of D n .

Hence there is a (right) action of the braid group on the set of isotopy classes of simple closed curves in D n . By abuse of notation we do not distinguish between a simple closed curve and its isotopy class. We denote the curve resulting from the action of the braid x on the curve C by C * x. A simple closed curve is said to be nondegenerate if it surrounds more than one puncture and less than n.

A braid x is said to be reducible if it preserves setwise a family of nondegenerate simple closed curves; such a curve is then called a reduction curve for x. A reduction curve of x is said to be essential if it does not cross any other reduction curve. The set of all essential reduction curves of x is called the canonical reduction system of x and denoted by CRS(x). It is known that the set CRS(x) is non-empty if and only if x is reducible nonperiodic (see [START_REF] Birman | Abelian and solvable subgroups of the mapping class groups[END_REF]).

A braid x is said to be periodic if some power of x is a power of the full twist ∆ 2 . Pure periodic braids are known to be powers of ∆ 2 (where ∆ is the half-twist of all strands, defined in Artin's generators by the formula ∆ = (σ 1 . . . σ n-1 )(σ 1 . . . σ n-2 ) . . .

(σ 1 σ 2 )σ 1 .)
In what follows we will take "reducible" to mean "reducible nonperiodic". Note that a braid x is reducible if and only if every power x t (with t = 0) of x is reducible. Note also that reducibility is a property invariant under conjugation.

The following definition, which comes from [START_REF] Wiest | How to read the length of a braid from its curve diagram, Groups[END_REF], uses the notion of canonical length of a braid, which will be recalled in the next subsection. Definition 1.4. We say that a simple closed curve in D n is round if it is homotopic to a geometric circle. The complexity of a simple closed curve C in D n is defined to be the smallest canonical length of a positive braid which sends C to a round curve. (Note that if some positive braid sends C to a round curve, then there is another positive braid of the same canonical length sending the round curve back to C.)

Hence the curves of complexity 0 are the round curves; we shall call almost-round the curves of complexity 1. In Figure 1 are represented three simple closed curves in D 4 : the first is round, the second is almost-round and is sent to a round curve by the permutation braid σ 1 σ 3 , the third is of complexity 2 and is obtained from the first by applying σ -2 2 .

(c) (a) (b)

Let us introduce a notion which is closely related to Definition 1.4 (see [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF]): the minimal standardizer of a family C of disjoint simple closed curves in D n is defined to be the smallest positive braid (for the prefix order on B n ) which sends C to a family of round curves. Hence the complexity of a curve C coincides with the canonical length of its minimal standardizer. In particular, we may consider the minimal standardizer of the canonical reduction system of a reducible braid.

1.3. Garside theory. For an introduction to the classical Garside structure on braid groups, the reader is referred to the papers [START_REF] Garside | The braid group and other groups[END_REF] and [START_REF] Elrifai | Algorithms for positive braids[END_REF] where the notion of left normal form is defined. The second one also introduces the notions of inf, sup and canonical length. Recall that if a braid x = ∆ p x 1 • • • x r is in left normal form (where the x i 's are positive permutation braids) then sup(x) = p + r, inf(x) = p and the canonical length of x, denoted by ℓ(x), is defined by ℓ(x) = r.

We also recall that the super summit set SSS(x) of a braid x is the (finite, nonempty) subset of the conjugacy class of x containing all those elements which have both minimal sup and maximal inf (or equivalently minimal canonical length) within their conjugacy class [START_REF] Elrifai | Algorithms for positive braids[END_REF]. The minimal value of ℓ within the conjugacy class of a braid x is called summit canonical length of x and is denoted ℓ s (x).

In order to be able to construct at least one element of SSS(x) for any given braid x, let us recall a special kind of conjugation, the so-called cyclic sliding [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF]. Let us denote by τ the conjugation by the half-twist ∆, by ∧ the gcd associated to the prefix order and, for a simple element z of B n , by ∂(z) the right complement to ∆, that is ∂(z) = z -1 ∆.

Definition 1.5 ([12]). Let x = ∆ p x 1 • • • x r be a braid in left normal form, with r > 0; one defines the cyclic sliding, denoted s, by the following conjugation:

s(x) = p(x) -1 xp(x) where p(x) = τ -p (x 1 ) ∧ ∂(x r ).
The simple braid p(x) is called the preferred prefix of x. (If ℓ(x) = 0, one also can define cyclic sliding: in this case x is some power of ∆ and s is the trivial conjugation).

In [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] it was shown that, starting from x and iteratively applying the cyclic sliding operation (ℓ(x) -1) • ( n(n-1)

2

-1) times yields an element of SSS(x). (This is analogue to previous results of [START_REF] Elrifai | Algorithms for positive braids[END_REF] and [START_REF] Birman | The infimum, supremum, and geodesic length of a braid conjugacy class[END_REF] concerning the so-called cycling and decycling operations.) This leads to the following result:

Theorem 1.6 ([12]

). There is an algorithm which takes as its input a braid x with n strands, runs for time O ℓ(x) 2 n 2 , and outputs an element x ′ of SSS(x) which is of the form x ′ = s k (x) for some k ∈ N.

The cyclic sliding operation behaves well with respect to the reducibility problem: Proposition 1.7 ( [START_REF] González-Meneses | On reduction curves and Garside properties of braids[END_REF]). Let x = ∆ p x 1 • • • x r be a braid in left normal form and let C be a round simple closed curve such that C * x = C. Then the curve C * p(x) is also round. In particular, the braid s(x) also preserves a round curve. Now every reducible braid has some conjugate with round essential reduction curves. Thus Proposition 1.7 together with Theorem 1.6 yields:

Corollary 1.8 ([1]
). For any reducible braid x there exists an element of SSS(x) with a round essential reduction curve.

We shall also need the following result which essentially comes from [START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF].

Proposition 1.9. Let x = ∆ p x 1 • • • x r be the left normal form of a reducible braid which preserves a simple closed curve C of complexity s. Then the complexity of the curve C * ∆ p x 1 • • • x i is bounded above by s for every i with 1 i k.

Proof. Notice that the case s = 0 in the proposition is proved in Theorem 5.7 in [START_REF] Benardete | Braids and the Nielsen-Thurston classification[END_REF]. Let P be the minimal standardizer of CRS(x). By Theorem 4.9 in [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF], we have: inf(P -1 xP ) inf(x) and sup(P -1 xP ) sup(x). Under some minor changes, Proposition 2.1 and Corollary 2.2 in [START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF] assert the existence of positive braids P 0 = τ p (P ), P 1 , . . . , P r such that P -1 xP has left normal ∆ p (P -1 0 x 1 P 1 ) . . . (P -1 r-1 x r P r ) (with possibly some indices 0 i ′ < i ′′ r -1 such that u -1 i x i+1 u i+1 = ∆ for i i ′ and u -1 i x i+1 u i+1 = 1 for i i ′′ ) and inf(P i ) inf(P ), sup(P i ) sup(P ) for i = 1 . . . r.

The case s = 0 of the current Proposition yields the roundness of the curves (C * P ) * (∆ p (P -1 0 x 1 P 1 ) . . . (P -1 i-1 x i P i )) for all i = 1, . . . , r. The latter can now be rewritten as (C * (∆ p x 1 . . . x i )) * P i . The complexity of the curve C * ∆ p x 1 . . . x i is thus at most ℓ(P i ) ℓ(P ) = s. This shows Proposition 1.9. The special case s = 0 of Proposition 1.9 together with Corollary 1.8, means that for some (but not necessarily every) element of the SSS of a reducible braid, reducibility is easy to detect. However this is not sufficient in order to obtain a polynomial-time algorithm for detecting reducibility since the size of the SSS may grow exponentially with both word length and braid index (see [START_REF] Birman | Conjugacy in Garside groups III: Periodic braids[END_REF]). This difficulty does not yet appear in the case n = 3, as will be shown in Proposition 1.14. Our strategy for proving Theorem 1.1 is to show that also in the case of four strand braids, the reducibility is easy to see for every element in the SSS. The following is our main technical result: Proposition 1.10. Let x be a reducible 4-braid such that x ∈ SSS(x). Suppose that x has an essential reduction curve surrounding 3 punctures. Then this curve is round or almost round.

Notice that an essential reduction curve of a 4-braid x surrounding three punctures is fixed by x (not sent to another reduction curve). Now, let us recall from [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] a last Garside-theoretical notion: Definition 1.11 ([12]). Let x = ∆ p x 1 • • • x r be a braid in left normal form. We say that x is rigid if its preferred prefix is trivial, i.e. if the equality p(x) = 1 holds. That means that the pair x r τ -p (x 1 ) is left-weighted.

We end this section with some results specifically concerning 3-braids. We start by recalling that in this case there are only four simple braids other than 1 and ∆ (i.e. nontrivial strict prefixes of ∆), namely σ 1 , σ 2 , σ 1 σ 2 and σ 2 σ 1 .

Proposition 1.12. Let x be a 3-braid with inf(x) = p and ℓ(x) = r. Let x 1 , . . . , x r ∈ B + 3 be non-trivial simple elements different from ∆.

If x = ∆ p x 1 • • • x r , then this is the left normal form of x.
Proof. If it was not, making the pair x i x i+1 left-weighted (for some 1 i r -1) either would create one factor ∆ (contradicting inf(x) = p) or would decrease the number of factors (contradicting sup(x) = r + p), or both. Proposition 1.13. Let x be a 3-braid with ℓ s (x) > 1. Then SSS(x) is the set of rigid conjugates of x.

Proof. Let y be an element of SSS(x), written y = ∆ p y 1 . . . y r in left normal form, and suppose that y is not rigid. Consider the conjugate z = (τ -p (y 1 )) -1 yτ -p (y 1 ) = ∆ p y 2 . . . y r τ -p (y 1 ) of y. As in the proof of Proposition 1.12, the non left-weightedness of the pair y r τ -p (y 1 ) implies that z has smaller canonical length than y. This is a contradiction because y ∈ SSS(x).

Conversely, according to Theorem 1.6, a rigid braid y conjugate to x belongs to SSS(x) since s(y) = y.

Proposition 1.14. The reducibility problem as well as the conjugacy search problem can be solved in polynomial time for three-strands braids.

Proof. We claim that in the particular case of 3-strand braids, the size of the Super Summit Set of a braid x is bounded above by 2 • ℓ s (x). Thus computing the whole Super Summit Set of any 3-braid is doable in polynomial time according to Proposition 6.2 in [START_REF] Franco | Conjugacy problem for braid groups and Garside groups[END_REF] and consequently, the reducibility problem and the conjugacy search problem can be solved quickly.

Let us prove the claim we made. First, the SSS of elements of canonical length 0 (i.e. powers of ∆) contain only one element. Then, any braid of canonical length 1 is an element of its Super Summit Set since it is not conjugate to a power of ∆ and thus the canonical length is already minimal within the conjugacy class. Thus as both letters σ 1 and σ 2 are conjugate to each other (by ∆) and because inf has constant value in the Super Summit Set one has

SSS(∆ k σ 1 ) = {∆ k σ 1 , ∆ k σ 2 }, SSS(∆ k σ 1 σ 2 ) = {∆ k σ 1 σ 2 , ∆ k σ 2 σ 1 },
for any k ∈ Z. This proves the claim for braids of canonical length 1.

Suppose then that we are given a 3-braid x of summit canonical length ℓ > 1 together with an element y = ∆ p y 1 . . . y ℓ (in left normal form) of SSS(x). Recall the cycling operation, which consists, for a general braid u = ∆ p u 1 . . . u r in left normal form, of the conjugation c(u) = (τ -p (u 1 )) -1 uτ -p (u 1 ) [START_REF] Elrifai | Algorithms for positive braids[END_REF]. Applied to our braid y, we have c(y) = ∆ p y 2 . . . y ℓ τ -p (y 1 ), and since y is rigid (by Proposition 1.13), c(y) is in left normal form as written and rigid. Notice that τ (y) as well belongs to SSS(x). Now consider the first ℓ cyclings of both y and τ (y). This produces at most 2.ℓ elements of SSS(x). More precisely we have c ℓ (y) = τ -p (y), which is y if p is even and τ (y) if p is odd (recall that ∆ 2 is central). Thus we have just computed either two closed orbits under cycling, conjugate to each other by ∆, or one closed orbit under cycling, self conjugated by ∆. We thus have a subset O of SSS(x) closed by cycling and conjugation by ∆. By Proposition 4.14 in [START_REF] Franco | Conjugacy problem for braid groups and Garside groups[END_REF], if the inclusion O ⊂ SSS(x) is strict, then there must exist another element v ∈ SSS(x) which can be obtained by conjugation of some z = ∆ p z 1 . . . z ℓ ∈ O by a minimal conjugator s. This minimal conjugator is a simple, and is shown in in the proof of Corollary 2.7 in [START_REF] Birman | Conjugacy in Garside groups II: Structure of the Ultra Summit Set, Groups[END_REF] to be either a prefix of τ -p (z 1 ) or of ∂(z r ). However, for the rigid 3-braid z, conjugating by a strict prefix of either τ -p (z 1 ) or of ∂(z ℓ ) would increase the canonical length. Thus s must actually be the whole factor: either

s = τ -p (z 1 ) (in which case v = c(z)) or s = ∂(z ℓ ). In the latter case, ∂(z ℓ ) -1 z∂(z ℓ ) = ∆ p τ p+1 (z ℓ )τ (z 1 ) . . . τ (z ℓ-1 ) = c ℓ-1 (τ p+1 (z)).
This shows that we already had all the elements of SSS(x) in O. Since O has at most 2.ℓ elements, the claim is proven.

Proposition 1.10 implies Theorem 1.1

In this section we prove Theorem 1.1 with the aid of Proposition 1.10. The first observation is that there are only 2 round curves and 4 almost-round curves surrounding 3 punctures in D 4 (see Figure 2).

Lemma 2.1.

There is an algorithm which decides in time O(l 2 ) whether a 4-braid x given as a word of length l in Artin's generators, is reducible with an essential reduction curve surrounding 3 punctures.

Proof. We recall that ℓ(x) l(x) 6ℓ(x). Now according to Theorem 1.6, an element y of SSS(x) can be computed in time O(l 2 ). According to Proposition 1.10, x admits an essential reduction curve surrounding 3 punctures if and only if y preserves one of the six curves in Figure 2. The check whether this is the case can be performed in time O(l): according to Proposition 1.9, it is sufficient to test whether the images of these curves under each successive Garside factor of y are still round or almost round. In order to overcome the fact that we don't have any analogue of Proposition 1.10 for curves surrounding 2 punctures, we will consider 4-braids as mapping classes of a 5-punctured sphere by collapsing the boundary of D 4 . The five punctures lie on the equator and we shall number them from 1 to 5, the fifth being the new puncture, on the far side of the sphere.

In the following construction x will be supposed to be pure; this assumption is fullfilled up to taking a power 2, 3 or 4. Then for j = 1, . . . , 4, blowing up the jth puncture to become the boundary of a new 4-punctured disk D 4 yields from x a new 4-braid which we will denote by xj . Lemma 2.2. For j = 1, . . . , 4, the length l(x j ) of xj in Artin's generators is bounded above by 3l(x).

Proof. We show that each letter of x gives rise to no more than 3 letters. Let us describe in detail how the first letter of x is transformed. In order to identify the jth puncture with the new boundary we make a rotation of the equator bringing the jth puncture behind the sphere at the place of the fifth, and then we renumber the punctures following the rule:

i ; i -j + 5 if i j, i ; i -j if i > j.
If the first letter of x is σ i , for 1 i j -2 or for j + 1 i n -1, then its image in xj is easy to compute: it is σ i-j+5 or σ i-j , respectively. If j 2 and the first letter of x is σ j-1 , then this corresponds to a move of the puncture numbered j -1 which goes to the right above the puncture numbered j. After our rotation the corresponding move involves the fourth puncture which goes above the other punctures to the first position. This corresponds to the braid σ -1

3 σ -1 2 σ -1 1 .
In a similar way we can compute the images of all Artin's generators:

σ ±1 i ; σ ±1 i-j+5 if i < j -1, σ ±1 i ; σ ±1 i-j if i > j, σ ±1 j-1 ; σ ∓1 3 σ ∓1 2 σ ∓1 1 (for j 2), σ ±1 j ; σ ∓1 1 σ ∓1 2 σ ∓1 3 (for j 3).
Notice that the first letter of x induces a permutation of the punctures which possibly sends the puncture numbered j to another position. Thus computing the image of the second letter of x with the aid of the above formulae requires a renumbering of the punctures, according to the permutation involved. The images of the following letters of x are computed in the same way.

Lemma 2.3. Let x be a reducible braid without any essential reduction curve surrounding 3 punctures. Then there exists j between 1 and 4 such that xj is reducible with an essential reduction curve surrounding 3 punctures.

Proof. Note that the reducibility of x is equivalent to the reducibility of each xj for j = 1, . . . , 4. Now under the assumption of the lemma, x admits an essential reduction curve surrounding 2 punctures. After collapsing the boundary of D 4 this curve divides the sphere into two connected components, one with 2 punctures, the other with 3 punctures. Blowing up one of the first two to the new boundary achieves the proof of the lemma.

To conclude the proof of Theorem 1.1, we can give the algorithm which solves the reducibility problem in B 4 .

0 INPUT: A braid word x in the letters σ ±1 i . 1 Compute a pure power x t of x and do x := x t . 2 Compute the left normal form of x. 3 Test whether x is periodic (that is test if x is a power of ∆ 2 ). If yes, then RETURN "x periodic" and STOP. Else go to 4. 4 Apply iterated cyclic sliding to x until the canonical length has not decreased during the last five iterations. 5 For the element of SSS(x) obtained at the previous step, test whether it has a round or almost round essential reduction curve surrounding 3 punctures. If yes, RETURN "x reducible" and STOP. If not go to the following step. 6 For j = 1, . . . , 4, compute xj , apply to it steps 2 and 4. Test whether the element of SSS(x j ) thus obtained has a round or almost round essential reduction curve surrounding 3 punctures; if the answer is positive for some j, RETURN "x reducible" and STOP. If the answer is negative for all j, RETURN "x pseudo-Anosov" and STOP.

Proof. We now prove Corollary 1.2. Given two braid words x (1) and x (2) of length l in the generators σ ±1 i (i = 1, 2, 3), we want to test whether they are conjugate, and we want to do so in time O(P (l)), where P is a polynomial. In order to achieve this, we first check whether they are periodic. If one of them is and the other one isn't, then they are not conjugate; if they both are, we are able to solve the conjugacy search problem for them in polynomial time, see [START_REF] Birman | Conjugacy in Garside groups III: Periodic braids[END_REF].

Next we want to check whether both braids admit a reducing curve surrounding three punctures. In order to do so, we calculate (using iterated cyclic sliding) braids P 1 and P 2 such that P -1 i x (i) P i ∈ SSS(x (i) ) (see Theorem 1.6). For each of these conjugated braids we can decide whether they admit a round or almost round reducing curve surrounding 3 punctures (see Lemma 2.1). If one of them has and the other one has not then they are not conjugate. If they both have then, possibly after adding one factor to P i , we can even assume that P -1 i x (i) P i (for i = 1, 2) both have round reducing curves. These two braids are now conjugate if and only if two conditions are satisfied. Firstly the winding numbers of the outer strand with the three inner strands must coincide, and secondly the inner 3-braids must be conjugate. Both of these conditions can be checked very quickly (see Proposition 1.14).

The most difficult case occurs when neither of the braids admits a reducing curve surrounding three punctures, and we have to check for reducing curves surrounding two punctures. If a braid x (i) has a canonical reducing curve surrounding two punctures, then a conjugate of x (i) in which the reducing curve is round can be found as follows. We consider the twelfth power 12 which is guaranteed to be pure and which has the same canonical reduction curves as x (i) . One of the braids ỹ(i) j (j = 1, . . . , 4) has a canonical reduction curve surrounding three punctures.

y (i) = x (i)
As in the previous paragraph, we can find a braid Pi so that P -1 i ỹ(i) j Pi has a round canonical reduction curve surrounding three punctures. The corresponding homeomorphism of the five times punctured sphere also has a reduction curve intersecting the equator only twice. Thus as in the proof of Lemma 2.2 we can explicitly write a 4-strand braid P i such that the pure braid P -1 i y (i) P i has a round reducing curve surrounding two punctures. Thus the twelfth root P -1 i x (i) P i has the same round reducing curves.

To summarize, if the search for round reducing curves surrounding two punctures is unsuccessful in both braids x (i) (i = 1, 2), then both braids are pseudo-Anosov, and we cannot answer the question whether they are conjugate. If for one of them the search is successful and for the other it is not, then the two braids are not conjugate. If for both braids we find conjugates with round reducing curves surrounding two punctures, then we consider for each of them a 3-braid z (i) obtained by merging the two inner strands of a reducing curve into a single strand. We then solve the reducibility problem for each of the z (i) 's. This can be done quickly, according to Proposition 1.14. Our two braids x (i) are conjugate only if the braids z (i) have the same Nielsen-Thurston type.

The braids z (i) cannot be periodic because otherwise the braids x (i) would have a reducing curve surrounding 3 punctures. If the z (i) 's are pA, then the braids x (i) are conjugate if and only if the following two conditions are satisfied. Firstly, the winding numbers of the two inner strands must coincide, and secondly, the two three-strand braids z (i) must be conjugate. Again, both of these conditions can be checked in polynomial time. Finally if both braids z (i) are reducible, one can find 4-braids u (i) conjugate to x (i) so that u (i) has 2 round reducing curves, each of them surrounding two punctures. Moreover, the conjugating element can be explicitly written as a product of simple 4-braids corresponding to the conjugating 3-braids occurring during iterated cycling applied to z (i) , but with the strand corresponding to the round reducing curve of P -1 i x (i) P i duplicated. Now, the braids x (i) are conjugate if and only if the winding number of the two fat strands in u (1) is the same as in u (2) , and if the two winding numbers of the pairs of strands inside the two tubes of u (1) coincide with those in u (2) . This can once again be checked quickly.

3. Proof of Proposition 1.10 3.1. Outline of the proof, notation. We shall give a proof by contradiction. So let us suppose that there exists a reducible 4-braid in its own SSS which admits an essential reduction curve of complexity 2 or greater than 2 surrounding 3 punctures. By multiplying the braid by a sufficiently high power of ∆ 2 one may suppose that it is positive. Moreover we may suppose this essential reduction curve to be of complexity exactly 2. If it was greater, then the "convexity" of the SSS (see Corollary 4.2. of [START_REF] Elrifai | Algorithms for positive braids[END_REF]) and the existence in the SSS of a braid with round essential reduction curve would yield another braid in the SSS with a complexity 2 essential reduction curve.

Hence we start with a positive reducible 4-braid x in its own SSS with an essential reduction curve of complexity 2 surrounding 3 punctures. Let us denote this curve by C. We recall that C is fixed by x, because it is essential. We call outer the strand whose puncture base is not surrounded by the curve C, the other three are inner. For the rest of this section we denote by x the 3-braid z (i) obtained from x by removing the outer strand.

The plan of the proof is as follows: first we list all curves of complexity 2 surrounding 3 punctures in D 4 . Next we prove that x and x have the same canonical length, and that x is a rigid braid. Finally, using a careful case-by-case analysis, we show that Proposition 1.9 and the rigidity of x together imply that none of the curves in our list can be an essential reduction curve for x.

3.2.

Curves of complexity 2 surrounding 3 punctures in D 4 . Let us classify the simple closed curves of complexity 2 surrounding 3 punctures in D 4 . In order to describe them we may also consider isotopy classes of smooth arcs which start at one of the punctures and end on the boundary of the disk, considered up to sliding the endpoint along the boundary of D 4 . We require that these isotopy classes have intersection number with every vertical line in the disk at most 1 and with the horizontal axis at least 1 (not counting the endpoints). The bijective correspondence between the two notions is as follows: given such an arc γ we consider a tubular neighborhood N of γ ∪ ∂D 4 ; the corresponding simple closed curve is then the boundary of D n -N .

Figure 3 gives all the possibilities of such arcs. We shall first make two remarks concerning this figure which will be useful for the end of this section: Remark 3.1. (1) Curves of type 1 and 2 are symmetric to each other with respect to the horizontal axis. Hence acting by σ i on one of these curves and by σ -1 i on the other yields two curves with the same symmetry. The curves of type 3 and 4 have the same properties with respect to each other.

(2) One can obtain the curves 3 from the curves 2 (and 4 from 1) by applying the half twist ∆ 4 . Moreover this symmetry is preserved by the respective actions of a braid x and its conjugate τ (x).

3.3.

The two braids x and x have the same canonical length. For a 4-braid y with an essential reduction curve surrounding 3 punctures let us denote by v y the number of crossings in y where the outer strand is involved, counted with sign. This number is invariant under conjugacy. We remark that the winding number of the outer strand with each other strand is vy 6 . Lemma 3.2. Let y be a positive reducible 4-braid with an essential reduction curve of complexity 2 surrounding 3 punctures. Then v y < 3 sup(y).

Proof. Because y is a positive braid, y is a product of sup(y) simple braids. Because each simple braid contributes at most 3 to v y , we have v y 3 sup(y). Suppose that the equality holds, then each simple braid contributes exactly 3 to v y , so that the outer strand crosses all the inner strands in each Garside factor of y. If the outer strand is the first or the fourth then sup(y) is even because of the purity of this outer strand, and the circle surrounding the punctures 2, 3, 4, or 1, 2, 3, respectively, is preserved by y; this is a contradiction since both of these circles cross each of the curves in Figure 3. If the outer strand is the second or the third then the Garside factors of y other than ∆ must be σ 1 σ 2 σ 1 σ 3 σ 2 and σ 2 σ 3 σ 2 σ 1 σ 2 alternately, so that by the purity of the outer strand, sup(y) is also even and the circle surrounding the punctures numbered 1 and 2 and the circle surrounding the punctures numbered 3 and 4 are preserved by y. We conclude as above.

We now see that removing the outer strand of x does not affect the canonical length: Proposition 3.3. The equalities inf(x) = inf(x) and sup(x) = sup(x) hold.

Proof. First notice that sup(x) sup(x) and inf(x) inf(x) because x was obtained from x by removing a strand. Let P be the minimal standardizer of C. By removing the outer strand in P -1 xP we obtain a 3-braid x ′ , conjugate to x: if P ′ ∈ B 3 is obtained from P by removing the outer strand, then x ′ = P ′-1 xP ′ . Since P -1 xP preserves a round curve surrounding 3 punctures, its left normal form can be written (see [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF]) as P -1 xP = x 0 x 1 , with x 0 ∈ B 2 and x 1 ∈ B 3 . (This notation means that x 1 is the braid obtained from P -1 xP by removing the outer strand and x 0 is the 2-braid obtained when considering x 1 as a fat strand.) Note that x 1 = x ′ . Hence if P ′′ is the 4-braid obtained from P ′ by adding a trivial strand in the suitable position and if we define X = P ′′ P -1 xP P ′′-1 , then X = x 0 x; that is X is a conjugate of x in which we have a tubular braid equal to x and an outer strand making vx 6 twists around this "fat strand" (we also have

x 0 = σ vx/3 1
). Now according to [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF] one has sup(X) = max(sup(x 0 ), sup(x)) and because x ∈ SSS(x) one has sup(X) sup(x).

Next we prove that sup(x 0 ) < sup(X) (and in particular sup(X) = sup(x)). For if we had sup(X) = sup(x 0 ), then v X = 3 sup(X) because of the roundness of the curve preserved by X; and by conjugacy v x = v X . Now, according to Lemma 3.2 we also have v x < 3 sup(x). Hence

v x < 3 sup(x) 3 sup(X) = v X = v x ,
which is a contradiction. The second part of the proposition follows as sup(x) sup(x) sup(X) = sup(x).

In a similar way we now have inf(X) = min(inf(x 0 ), inf(x)).

Moreover inf(X) < inf(x 0 ), for if we had an equality, ∆ -inf(X) X would be a split braid (see Section 6 in [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF]). Noticing that (by purity of the outer strand) inf(X) is even, it would follow that ∆ -inf(X) x is also split and positive (because x ∈ SSS(x), one has inf(X) inf(x)) so that by Proposition 6.2 in [START_REF] Lee | A Garside theoretic approach to the reducibility problem in braid groups[END_REF] the outermost curves in CRS(∆ -inf(X) x) = CRS(x) are round. This is impossible since the only circles which do not cross the curves in Figure 3 are inner to them. Hence inf(X) = inf(x) inf(x) inf(X), where the last inequality holds since x ∈ SSS(x). We finally obtain inf(X) = inf(x) = inf(x).

Hence the proposition is shown and we remark also that X ∈ SSS(x).

Corollary 3.4. With the above notations we have x ∈ SSS(x).

Proof. Let us suppose by contradiction that there exists a 3-braid ẑ in the conjugacy class of x with inf(ẑ) > inf(x) or sup(ẑ) < sup(x). Let us also denote by ŷ the conjugating element, that is ẑ = ŷ-1 xŷ. Let z be the 4-braid obtained by conjugating X by ŷ augmented with a trivial strand in the suitable position, such that z has the same round essential reduction curve as X and z = x 0 ẑ. By the same argument using Lemma 3.2 as in the proof of Proposition 3.3 (with z playing the role of X), we have sup(z) = sup(ẑ) and inf(z) = inf(ẑ). Now suppose that sup(ẑ) < sup(x). Then sup(z) = sup(ẑ) < sup(x) = sup(x); which is a contradiction, because the braids z and x are conjugate and x lies in its own SSS.

Similarly suppose that inf(ẑ) > inf(x). Then inf(z) = inf(ẑ) > inf(x) = inf(x). This is again a contradiction.

Corollary 3.5. The braid x is rigid.

Proof. See Proposition 1.13.

3.4.

Analyzing the left normal form of x. Our strategy for proving Proposition 1.10 is to obtain a contradiction by proving the following statement: Lemma 3.6. None of the curves in Figure 3 can be an essential reduction curve for x.

We do this by analyzing precisely the factors of the left normal form of x. These are composed of an inner 3-braid and possibly a move of the outer strand. Because of the equalities sup(x) = sup(x) and inf(x) = inf(x) (see Proposition 3.3), and according to Proposition 1.12, the factors of the left normal form of x are exactly the inner components of the factors of the left normal form of x. Recall that the only nontrivial non-∆ simple elements in B 3 are σ 1 , σ 2 , σ 1 σ 2 and σ 2 σ 1 .

h h h h h h h h h h h h h h h h h h h h

Inner factor

Number of the outer strand 1 2

σ 1 σ 2 σ 2 σ 1 σ 2 σ 1 σ 2 σ 2 σ 1 σ 2 σ 3 σ 1 σ 2 σ 1 σ 2 σ 1 σ 2 σ 1 σ 2 σ 1 σ 3 σ 1 σ 2 σ 2 σ 3 σ 2 σ 1 σ 3 σ 2 σ 1 σ 3 σ 2 σ 2 σ 1 σ 3 σ 2 σ 3 σ 1 σ 2 σ 3 σ 1 σ 2 σ 1 σ 3 σ 2 σ 1 σ 3 σ 2 σ 2 σ 1 σ 3 σ 2 σ 3 σ 2 σ 3 σ 3 σ 1 σ 1 σ 2 σ 3 σ 2 σ 3 σ 1 σ 2 σ 3 σ 3 σ 1 σ 3 σ 2 σ 3 σ 2 σ 3 σ 2 σ 1 σ 3 σ 2 σ 1 σ 3 σ 1 σ 2 σ 1 σ 3 σ 2 σ 1 σ 2 σ 3 σ 2 σ 1 σ 3 σ 2 σ 1 σ 3 σ 1 σ 2 σ 3 σ 2 σ 3 σ 1 σ 3 σ 1 σ 2 σ 1 Table 1.
Table 1 gives all the possibilities of non-trivial non-∆ positive simple braids in B 4 depending on the position of the outer strand (at the beginning of the braid) and on the value of the inner braid; for every possibility on the inner braid there are four possibilities for the corresponding braid on four strands. For the rest of this section we shall abbreviate "nontrivial non-∆ simple 4-braids" by "simple 4-braids" and they will be supposed positive unless otherwise stated. We saw that curves for which the outer strand is the third or the fourth are images under the half-twist ∆ of curves for which the outer strand is the second or the first, respectively. If the outer strand is the third (or the fourth) then the simple 4-braids whose interior component is σ 1 , σ 1 σ 2 , σ 2 , or σ 2 σ 1 , are images under the automorphism τ of simple 4-braids with outer strand in second position (or first position respectively) and whose inner component is σ 2 , σ 2 σ 1 , σ 1 , or σ 1 σ 2 , respectively. This allows us to construct the rest of Table 1. 3.5. Proof of Lemma 3.6. We make a constant implicit use of Proposition 1.9, asserting that if ∆ p x 1 • • • x r is the left normal form of x and if x preserves one of the complexity 2 curves, then for 1 i r the image of the considered curve under ∆ p x 1 • • • x i is again a complexity 2 (or lower than 2) curve. By the following four lemmas we are going to eliminate all types of curves depicted in Figure 3.

Lemma 3.7. The curves of type T cannot be essential reduction curves of x.

Proof. First notice that it is sufficient to prove the claim for curves T 1 and T 2 (because of the symmetries between the curves).

For both curves T 1 and T 2 the outer strand is the first. The simple 4-braids whose outer strand is the first and whose inner component starts with the letter σ 2 or σ 1 send the curve T 1 or T 2 , respectively, to strictly more complex curves. By the symmetries mentioned above, the simple 4-braids whose outer strand is the fourth and whose inner component starts with the letter σ 1 or σ 2 send the curves T 4 or T 3 , respectively, to strictly more complex curves. Similarly, by Remark 3.1, the action of a negative simple 4-braid whose outer strand is the first and whose inner component starts with the letter σ -1 1 or σ -1 2 on the curve T 1 or T 2 , respectively, yields a strictly more complex curve (as does the action of a negative simple 4braid whose outer strand is the fourth and whose inner component starts with the letter σ -1 2 or σ -1 1 on the curve T 4 or T 3 , respectively). Now suppose that the curve T 1 or T 2 is an essential reduction curve for x.

If inf(x) is even then the first factor of ∆ -inf(x) x must start with the letter σ 1 (or σ 2 , respectively), by Proposition 1.9 and the previous paragraph. By the rigidity of x the last factor of x (which is the inner component of the last factor of x) must end with the letter σ 1 (or σ 2 , respectively). Because of the symmetries between the curves T 1 and T 2 mentioned above, the image of the essential reduction curve at the beginning of the last factor of x has to be of complexity greater than 2. This contradicts Proposition 1.9.

If inf(x) is odd, then the essential reduction curve at the beginning of the first non-∆ factor of x is T 4 or T 3 , respectively. Thus the first letter of ∆ -inf(x) 3

x must be σ 2 , or σ 1 , respectively. And by the rigidity of x the last letter of x must then be σ 1 , or σ 2 , respectively. As before we obtain a contradiction by considering the symmetries with respect to the horizontal axis.

These two cases and the remark at the beginning of the proof together achieve the proof of the lemma.

Lemma 3.8. The curves of type U cannot be essential reduction curves for x.

Proof. As before we prove the statement only for curves U 1 and U 2 . We are going to assume, for a contradiction, that one of the curves U 1 or U 2 is an essential reduction curve for x. Hence Proposition 1.9 forces the image of this curve under each Garside factor of x to be of complexity at most 2.

Claim 1. Assume that the curve U 1 is an essential reduction curve for x. Then the first letter of ∆ -inf(x) 3

x is 4(a) is a guide for the proof of this claim. We are just going to use Proposition 1.9 and the left-weightedness of pairs of consecutive factors of x.

σ 2 if inf(x) is even, σ 1 if inf(x) is odd. Proof. Figure
First suppose that inf(x) is even. In order to show that the first letter of ∆ -inf(x) x is σ 2 , we are going to search which simple 4-braids could be the factors of the left normal form of ∆ -inf(x) x, provided the first letter of ∆ -inf(x) x is σ 1 . Among all possible simple 4-braids whose outer strand is the second and whose inner component starts with the letter σ 1 , only two do not increase the complexity of the curve U 1 . These two are σ 1 σ 2 and σ 1 σ 2 σ 3 . We prove that neither of these two braids can be the first factor of ∆ -inf(x) x.

The first sends U 1 to S 1 and the second to T 1 ; their inner components are σ 1 and σ 1 σ 2 , respectively. Now T 1 is sent to strictly more complex curves by simple four-braids whose inner component starts with the letter σ 2 (by Lemma 3.7), thus the only possibility left is the first. Now the only simple 4-braids whose inner component starts with the letter σ 1 , whose outer strand is the first (as in the curve S 1 ) and which do not increase the complexity of the curve S 1 are σ 2 and σ 2 σ 3 . The first fixes this curve and its inner braid is σ 1 , the second sends S 1 to T 1 and its inner braid is σ 1 σ 2 ; by the same argument as above this second case is impossible.

Hence we have shown that if the first letter of ∆ -inf(x) x is σ 1 then the curve U 1 cannot be preserved by x. This shows the first part of the claim. Now suppose that inf(x) is odd. The essential reduction curve U 1 of x is transformed (after the action of an odd number of factors ∆) into the curve U 4 at the beginning of the first factor of ∆ -inf(x) x. This situation is analogous to the situation we described in the proof of the first half of the claim, up to applying τ . This proves the second part of Claim 1.

Claim 2. Assume that the curve U 2 is an essential reduction curve for x. Then the first letter of ∆ -inf(x) 3

x is Proof. This proof is illustrated in Figure 4(b). Again we look at which simple 4-braids can occur in the left normal form of ∆ -inf(x) x.

σ 1 if inf(x) is even, σ 2 if inf(x) is odd. T2 σ2 • • • (a) (b) other σ1 • • • σ1σ2σ3 & σ1σ2 σ2σ3 & σ1σ2 other σ1 • • • σ2 & σ1 other σ2 • • • σ1σ3σ2σ1σ3 & σ1σ2 σ2σ3σ2σ1 & σ2σ1 σ1 • • • other σ1 • • • σ1σ3σ2σ1σ3 & σ2σ1 σ2σ3σ2 & σ2 σ1σ3σ2σ1 & σ1 σ1σ2 & σ1 U1 S1 σ2 • • • T1 T1 S2 S3 U2 σ2 • • • T3
First suppose that inf(x) is even. Among all simple 4-braids whose interior braid starts with the letter σ 2 and whose outer strand is the second, only two do not increase the complexity of the curve U 2 , namely σ 2 σ 3 σ 2 and σ 2 σ 3 σ 2 σ 1 . The first one has as its inner braid σ 2 and it sends U 2 to T 3 whereas T 3 is sent to strictly more complex curves by all simple 4-braids whose inner component starts with the letter σ 2 : this case cannot occur. The second one induces σ 2 σ 1 on the inner strands and sends U 2 to S 3 . Among all suitable simple 4-braids the only ones which do not increase the complexity of the curve S 3 are σ 1 σ 3 σ 2 σ 1 and σ 1 σ 3 σ 2 σ 1 σ 3 . Their inner components are σ 1 and σ 1 σ 2 , and they send the curve S 3 to T 2 and S 2 , respectively. Because simple 4-braids whose inner component starts with the letter σ 1 always send T 2 to strictly more complex curves, the only possibility left is the second. The following Garside factor of x is then preceded by the curve S 2 and its inner braid starts with the letter σ 2 . This situation is the image under τ of the situation at the beginning of the preceding factor. Thus this third factor must be σ 1 σ 3 σ 2 σ 1 σ 3 and at its end the curve becomes S 3 , a situation we already treated. Hence we see that if the inner braid ∆ -inf(x) x starts with the letter σ 2 , then we never retrieve the curve U 2 . This shows the first part of the claim. Now, suppose that inf(x) is odd. In this situation, the odd number of factors equal to ∆ transform U 2 to U 3 . Up to applying τ we saw that no 3-braid starting with the letter σ 1 can be the inner braid of ∆ -inf(x) x, hence ∆ -inf(x) x has to start with the letter σ 2 . This achieves the proof of Claim 2. Now, since x is rigid, if U 1 is preserved by x then the last letter of x must be σ 2 . However using the symmetry with respect to the horizontal axis, the action of negative simple 4-braids whose inner component starts with the letter σ -1 2 on the curve U 1 can be seen from the action of positive simple 4-braids whose inner component starts with the letter σ 2 on the curve U 2 . So we look at the action of the reversed word rev(∆ -inf(x) x) on the curve U 2 . Though this word, with separations as in the left normal form of x, is not necessarily in left normal form, the word rev(∆ -inf(x) x) is, by Proposition 1.12. We saw in the proof of Claim 2 that this action cannot yield the curves U 1 or U 2 . (Notice that in the proofs of the two claims we only used the left-weightedness of the pairs of consecutive factors in x and the fact that the image of the essential reduction curve is of complexity bounded by 2 after each Garside factor of x.) Similarly if U 2 is preserved by x then the last letter of x must be σ 1 . An argument analogous to the previous one yields the desired contradiction. Lemma 3.9. The curves of type S cannot be essential reduction curves for x.

Proof. The proof is similar to the proof of the previous lemma and can be derived with the help of Figure 4. We just have to use an additional argument since in fact there exist both: factors whose inner component starts with the letter σ 1 and which preserve the complexity of the curve S 1 on one hand, and factors whose inner component starts with the letter σ 2 and which preserve the complexity of the curve S 2 on the other hand. However, in both cases these factors are unique and ∆ -inf(x) x only consists of repetitions of the following factors: σ 2 in the first case, yielding a circle preserved by x and which crosses the curves of type S (namely the circle surrounding punctures 2, 3 and 4); σ 1 σ 3 σ 2 σ 1 σ 3 in the second case, also yielding circles having non-empty intersection with the curves of type S and being preserved by x (the two circles surrounding punctures 1,2 and 3 and punctures 2,3 and 4). At this point we have achieved the analogues of Claims 1 and 2 of the previous lemma; we conclude in the same way because of the rigidity of x.

Lemma 3.10. The curves of type R cannot be essential reduction curves for x.

Proof. The proof is modeled on that of Lemma 3.8. We prove the statement only for curves R 1 and R 2 .

Claim 3. Assume that the curve R 1 is an essential reduction curve for x. Then the first letter of ∆ -inf(x) 3

x is

σ 1 if inf(x) is even, σ 2 if inf(x) is odd.
Proof. See Figure 5(a).

We first suppose that inf(x) is even. The only simple 4-braids whose outer strand is numbered 1, whose inner component starts with the letter σ 2 , and which do not increase the complexity of the curve R 1 when applied to it, are σ 3 σ 2 σ 1 , σ 3 σ 2 and σ 3 . The first two have σ 2 σ 1 as their inner braid, the third has σ 2 . Since R 1 * σ 3 σ 2 σ 1 = U 1 , the following Garside factor of x (whose inner component has to start with the letter σ 1 ) must be σ 1 σ 2 or σ 1 σ 2 σ 3 as in the proof of Lemma 3.8. This implies that in this case we can never retrieve the curve R 1 , nor obtain the curve R 4 .

We also have R 1 * σ 3 σ 2 = T 2 . Because of Lemma 3.7 we can eliminate this case. Finally σ 3 (which has σ 2 as its inner braid) fixes the curve R 1 . Thus the only possibility left, provided the first letter of ∆ -inf(x) x is σ 2 , is that x = ∆ inf(x) σ p 3 for some natural integer p; in this case x preserves a round curve (the circle surrounding punctures 2, 3 and 4) whose intersection with R 1 is non-empty.

Up to applying τ (for the case when inf(x) is odd) this also shows the second statement of the claim. Claim 4. Assume that the curve R 2 is an essential reduction curve for x. Then the first letter of ∆ -inf(x) 3

x is

σ 2 if inf(x) is even, σ 1 if inf(x) is odd.
Proof. See Figure 5(b). We prove the claim only for even inf, the case of odd inf is symmetric. The only simple 4-braids whose inner component starts with the letter σ 1 and which do not increase the complexity of the curve R 2 are σ 2 σ 1 σ 2 , σ 2 σ 1 σ 2 σ 3 and σ 2 σ 3 σ 1 σ 2 σ 3 . The first two induce σ 1 on the inner strands. They yield U 3 and T 4 , respectively. By Lemma 3.7 we can exclude the latter. The first case is the image under ∆ of the situation we described in Lemma 3.8. In this case we can never obtain R 2 or R 3 .

Finally the only possibility left is σ 2 σ 3 σ 1 σ 2 σ 3 (which induces σ 1 σ 2 as its inner braid) and one has R 2 * σ 2 σ 3 σ 1 σ 2 σ 3 = R 3 . According to the discussion just above, the following Garside factor of x must be τ (σ 2 σ 3 σ 1 σ 2 σ 3 ) = σ 2 σ 1 σ 3 σ 2 σ 1 (since R 3 = R 2 * ∆). This factor has σ 2 σ 1 as its inner component and yields the curve R 2 when applied to the curve R 3 . This forces the braid ∆ -inf(x) x to consist of a succession of the factors σ 2 σ 3 σ 1 σ 2 σ 3 and σ 2 σ 1 σ 3 σ 2 σ 1 alternately. In this case x preserves round curves (namely the two circles surrounding the punctures 1 and 2 and the punctures 3 and 4) which cross the curve R 2 . This achieves the proof of the claim. Claims 3 and 4 determine the last letter of x because of the rigidity of x, and we conclude exactly as we did in the previous lemmas.

Examples and conjectures

In this last section we shall see that our result is sharp in some sense. We give some examples which we obtained with the aid of [START_REF] González-Meneses | Braiding software[END_REF].

The first example shows that we cannot remove the case of almost round curves in the statement of Proposition 1.10. We conjecture that our results can be improved:

Conjecture 4.4. Proposition 1.10 can be generalized to every simple closed curve in D 4 (even those surrounding 2 punctures) using the same kind of arguments.

However there are more curves of complexity 2 surrounding 2 punctures in D 4 than curves of complexity 2 surrounding three punctures in D 4 , thus the proof would be more difficult.

We finish by briefly looking at two conceivable alternative approaches to the reducibility problem in B n , for every n ∈ N. The first one concerns the cyclic sliding operation:

Conjecture 4.5. There is a polynomial bound on the number of times one has to apply cyclic sliding in order to decrease the complexity of any essential reduction curve which is not round or almost round.

Conjecture 4.5 would imply a polynomial algorithm for solving the reducibility problem in all braid groups. This is because the results in [START_REF] Tao | Linearly bounded conjugator property for mapping class groups[END_REF] imply that the complexity of any essential reduction curve of a reducible braid is linearly bounded by after each Garside factor of u (see Figure 7(c)). Notice that the inner braid is also pseudo-Anosov.

1 . Introduction 1 . 1 .

 111 Statement of the main result. In the 1980's Thurston gave a complete classification of the elements of the mapping class groups of surfaces into three types: periodic, pseudo-Anosov (pA), or reducible.

Figure 2 .

 2 Figure 2. Above, the round curves surrounding 3 punctures in D 4 ; below, the set of curves obtained from the above ones by applying a simple braid; i.e. the set of almost-round curves surrounding 3 punctures.

  Figure 3

Figure 4 .

 4 Figure 4. (a) The action on the curve U 1 of simple 4-braids whose inner component starts with the letter σ 1 . (b) The action on the curve U 2 of simple 4-braids whose inner component starts with the letter σ 2 . Underlined letters σ i indicate inner braids. Bold crosses indicate curves of complexity greater than 2. We can also see in (a) the action on the curve S 1 of simple 4-braids whose inner component starts with the letter σ 1 and in (b) the action on the curve S 2 of simple 4-braids whose inner component starts with the letter σ 2 . This will be used in Lemma 3.9

Figure 5 .

 5 Figure 5. (a) The action on the curve R 1 of simple 4-braids whose inner component starts with the letter σ 2 . (b) The action on the curve R 2 of simple 4-braids whose inner component starts with the letter σ 1 . Underlined letters σ i indicate inner factors. Bold crosses indicate curves of complexity greater than 2. Factors which immediately yield more complex curves are not represented here.

Example 4 . 1 .Example 4 . 2 .

 4142 Let us consider the braidx = σ 1 σ 2 σ 3 σ 2 .σ 2 σ 1 σ 3 .σ 3 σ 1 .σ 3 σ 2 σ 1 .σ 1 ∈ B 4 ,which is in left normal form as written. Then x ∈ SSS(x) and x has an almost round essential reduction curve surrounding 3 punctures and no round reduction curve. See Figure6(a).There are similar examples for curves surrounding two punctures: Consider the 4-braidy = σ 2 σ 3 σ 1 .σ 1 σ 2 σ 3 σ 2 .σ 2 .σ 2 σ 3 .Again y lies in its own SSS, has no round reduction curve, and preserves an almost round curve surrounding 2 punctures. See Figure6(b).

Figure 6 .Example 4 . 3 .= σ 1 σ 2 σ 1 σ 3 σ 2 σ 1 .σ 1 σ 3 .σ 1 σ 3 σ 2 σ 4 .σ 2 σ 1 σ 4 σ 3 σ 2 σ 1 .σ 1 σ 2 σ 1 .σ 1 σ 2 σ 1 σ 3 σ 2 .σ 3 ∈ B 5 ,

 64313411235 Figure 6. The braids x and y and their essential reduction curves. The dashed lines separate Garside factors. Now let us show that our result cannot be extended to the n 5 case. Example 4.3. Consider the braidz = σ 1 σ 2 σ 1 σ 3 σ 2 σ 1 .σ 1 σ 3 .σ 1 σ 3 σ 2 σ 4 .σ 2 σ 1 σ 4 σ 3 σ 2 σ 1 .σ 1 σ 2 σ 1 .σ 1 σ 2 σ 1 σ 3 σ 2 .σ 3 ∈ B 5 ,which is in left normal form as written. Then z ∈ SSS(z) and z has neither round reduction curves, nor almost round reduction curves. In fact z preserves the complexity 2 curve shown in Figure7(a). Notice that the interior braid is pseudo-Anosov.

Acknowledgements The authors are grateful to Sergey Matveev for helpful comments on the paper, and in particular for bringing to their attention Corollary 1.3. The first-named author's doctoral studies are supported by a grant ARED (Région Bretagne). He was also supported by a grant for international mobility from the Université Européenne de Bretagne.

the length of this braid. The following example shows that the most optimistic version of Conjecture 4.5, namely that the complexity of the reduction curve decreases in every single step, is wrong.

Example 4.6. Consider the braid z in Example 4.3. After one cyclic sliding one obtains from z the braid

in left normal form, which still has a curve of complexity 2, shown in Figure 7(b), as an essential reduction curve.

Another approach to the reducibility problem in B n comes from the following:

x r be a reducible braid in left normal form such that x ∈ SSS(x), and let C be an essential reduction curve of x. Then there is some i between 1 and r such that the curve C is sent to a round or almost round curve by the braid

Note that Theorem 1.6, together with the truth of this conjecture, would yield a polynomial time algorithm for solving the reducibility problem in B n .

The hypothesis that x ∈ SSS(x) in the statement of Conjecture 4.7 is necessary, as the following example shows:

The essential reduction curve of u is of complexity 2 and it is sent to curves of complexity 2


Nouha Omrane

Adeline Nazarenko

Peter Rosina

Sylvie Szulman

Christoph Westphal

Lexicalized ontology for the management of business rules An industrial experiment

This paper 1 describes a simple formalism designed to encode lexicalized ontologies and shows how it is used in a business rule management platform 2 of the automotive domain.

Introduction

Business Rules Management Systems (BRMSs) are software applications that help organizations to separate their application code from their business knowledge. BRMSs help the users to author and maintain business rules and apply decision logic that reflects this business knowledge. However, domain experts who are not always business rules experts may have difficulties expressing their knowledge in formalized logic languages. Supporting them in their management of the knowledge needed to write these rules is one of the goals of the ONTORULE project.

We propose building an ontology as a formal model for representing conceptual vocabulary that is used to express business rules in written policies. OWL-DL language is used to represent concepts and properties of the domain ontology but such an ontology must be linked to the lexicon used to express rules in the text, so experts can query source documents. This calls for a formalism to link linguistic elements to conceptual ones. We opt to use the SKOS 3 language which provides basic elements to link domain concepts to terms from the text. The combination of OWL entities, SKOS concepts and their related information form a lexicalized ontology which supports the semantic annotation of documents.

The paper is organized as follows. Section 2 describes the Audi use case, on which this approach has been tested. Section 3 explains the choice of SKOS combined with OWL as language to support the lexicalized ontology. Section 4 reports the experimentations made in the Audi use case.

The Audi use case

Nowadays, the development of new cars has become very challenging and many different process steps are involved. Computer Aided technologies, like virtual modeling, simulations or the analysis and planning of physical testing, need to be integrated even tighter to satisfy the higher requirements and reduced time-to-market which also shortens the development cycles.

In the ONTORULE project, Audi is developing a prototype BRMS that makes use of ontologies and business rules. Ontologies together with business rules help Audi to keep abreast of technology advances and use them in its R&D IT applications. Especially the interweaving of the various Computer Aided technologies will help Audi to reduce development time and cost.

One of the difficulties with business knowledge rules is that various departments or roles sometimes use different vocabularies for the same things so they cannot understand each other immediately. Addionally, formalized rules per se are often not easy to understand. Using an ontology as a unified model for a heterogeneous vocabulary will reduce misunderstandings and ensure that people are discussing the same thing. Also, the users can easily confirm and verify the appropriateness of the modeled semantic relations. Finally, the prototype that is to be developed is expected to handle links between source documents, such as policies or internal documents, and the concepts and instances of the ontology.

3 A formalism for lexicalized ontologies

Existing formalisms

Many research activities have tackled the problem of linking an ontology to a lexicon. Two major areas are of interest. The first is the NLP domain which aims at adding some semantic structure to a lexicon by linking its elements to ontology's elements. There are several ways to combine a lexicon with an ontology: LMF 4 standard [START_REF] Francopoulo | Lexical markup framework: ISO standard for semantic information in NLP lexicons[END_REF], TMF 5 , OLIF 6 , LMM 7 . The other group trys to link an ontology to a lexicon by modeling linguistic information in the ontology as in [START_REF] Reymonet | Modélisation de ressources termino-ontologiques en OWL[END_REF], LexOnto [START_REF] Cimiano | LexOnto: A Model for Ontology Lexicons for Ontology-based NLP[END_REF] or LIR [START_REF] Peters | Multilingual and localization support for ontologies[END_REF]. There also exist more abstract approaches like LingInfo [START_REF] Buitelaar | A Multilingual/Multimedia Lexicon Model for Ontologies[END_REF], which defines a meta class to link the linguistic properties to the concept or to its Data/Object properties, or [START_REF] Ma | Ontologies étendues pour l'annotation sémantique[END_REF], which introduces a set of annotation rules to link an existing ontology to its lexicon.

From a practical point of view, the choice of one model or another depends on the aimed application and the task. Our aim is to build a lexicalized ontology to allow annotating the technical documents and thus to help the expert in exploring documents by querying its set of annotations. We use for that SKOS W3C standard that links linguistic to semantic knowledge.

A SKOS-based approach

A key issue for experts in managing a rule base is to be able to mine textual sources to understand how a given concept is used in business documents, what rules are related to it and how those concepts and rules evolve when the policies are updated. This is achieved through the semantic annotation of the documents in which the mentions of the ontological entities (concepts, instances and roles) are highlighted and can be searched for. 4 Lexical Markup Framework 5 Terminological Markup Framework 6 Open Lexicon Interchange Format 7 Linguistic Meta Model Our aim is therefore to save the terms related to the conceptual vocabulary that is used to express the business rules. We don't need to encode sophisticated information such as the morphological structure of terms since we do not perform a deep analysis of the documents. We simply need to save the various linguistic units that denote a concept, instance or role. SKOS supports encoding of SKOS concepts that represent the links between the OWL concepts and their related terms, which are encoded as skos labels8 . This relation is described by <rdf:Description rdf:about>.

When designing and updating business rules, experts face the problem of the heterogeneity of information sources and multilingualism. SKOS also supports that normalization of vocabularies. A given SKOS concept can be associated with the various terms or labels that denote it in the texts or any other information source. For a given concept, SKOS supports distinguishing one preferred label and as many alternative labels as necessary, using the <skos:prefLabel> and <skos:altLabel> properties. In the Audi ontology, for example, the SKOS concept LowTemperatureChamber is linked to two terms: low temperature chamber is encoded as the preferred label and refrigerated cabinet as its alternative form.

SKOS also supports the encoding of multilingual information.

The information about the language used is described by <rdf:lang=''en''>.

For example, the SKOS concept TrolleyTest has a preferred label "trolley test" which is mentioned in English texts, and an alternative label "Schlittentest" in German.

Since experts often have to manage a large volume of information but do not always formally describe all the concepts, it is important to add informal documentation when it is available. Defining concepts in natural language is very important to understand what concepts mean, especially if they have ambiguous or implicit labels. Those definitions can sometimes be extracted from the source documents when designing the ontology. In that case, they are associated to the related SKOS concepts using the label <skos:definition>.

In such a lexicalized ontology, the domain concepts and their occurrences in the text can be matched from one to another thanks to the linkage of OWL entities, SKOS concepts and labels. This is a simple efficient way to represent lexicalized ontologies and we show in the following section its benefit for the Audi BRMS. Figure 1 describes how the Audi ontology is linked to the lexicon and annotated text.

Figure 1: A lexicalized ontology for annotating source documents. Each concept from the ontology is linked to a SKOS concept SC and each SKOS concept is related to its labels. The annotations link some text entities to these labels

The Audi lexicalized ontology

This section presents the Audi ontology and illustrates the benefit in the Audi use case of having such a lexicalized ontology.

That ontology has been built in two steps. At first, the goal was to integrate the various existing knowledge sources in a single one. This resulted into a small conceptual model (around 30 concepts) associated with a large knowledge base (thousands of instances).

In a second step, in order to better fits the experts' needs for semantic querying and document mining, the initial ontology has been restructured and lexicalized. It also appeared useful to increase the granularity of the domain model so as to represent for instance not only the various types of tests but also their actual occurrences in the car manufacturing process (instances that are related to the different tests applied to specific vehicle models).

This led to encoding various elements as concepts rather than instances (90 concepts were added). The conceptual structure has been reorganized (4 subsumption levels instead of 1). A SKOS resource has been associated with this resulting ontology: each concept is related to at least 1 preferred label and up to 5 alternative labels. In addition, using a subset of the initial ontology for the exploration of written policies showed that some of the mentioned concepts were missing in the initial ontology and led us to enrich it (Omrane et al., 2011b).

Once the ontology is lexicalized, domain experts can query source documents to search for fragments of texts that describe specific concepts mentioned in rules. For example, they can find all references of the concept BreakingStrengthOfS-trapTest in the text, wherever it is mentioned in the documents. They can also search for all sentences where the physical methods are mentioned in the text. As the concepts expressing tests are subconcepts of the concept "MethodInformation", we query the text by searching about all labels describing subconcepts of "MethodInformation".

Thanks to the labels of concepts, the ontology can be used to annotate the documents. Figure 2 shows an example of texts where all the mentions of known concepts are emphasized. This supports experts in browsing of documents.

Conclusion

The proposed integration of Computer Aided technologies will increase the flexibility of the development process, allowing Audi to meet the increasing market demand for product diversification. This integration relies on the design of an application that is currently under development and is based on a BRMS.

Our approach for the acquisition and management of the knowledge embodied in such BRMS relies on a lexicalized ontology which unifies and normalizes the various vocabularies and links the conceptual knowledge to the source policies and regulation written in natural language. Using a lexicalized ontology enables experts to determine the most suitable Computer Aided technologies from given functional requirements and to query sources documents.

These new approaches, standards and technologies are already partially integrated in some processes. During the next years Audi will continue to incorporate the ONTORULE platform in their landscape which will lead to even less time-consuming, cheaper and higher quality processes in the innovation and development cycles.

Figure 2 :

 2 Figure 2: A fragment of text annotated by the lexicalized ontology.

This paper is an extract from our paper(Omrane et al.,

2011a) 2 This work was realised as part of the FP7 231875 ON-TORULE project (http://ontorule-project.eu). We thank our partners for the fruitful discussions, especially to Audi for the collaboration on their use case.3 Simple Knowledge Organization System

http://www.w3.org/2004/02/skos/


Applicability of DGT to groundwater monitoring of trace elements

The aim of this work is to evaluate the advantages and limits of DGT (passive sampling technology) for groundwater monitoring of trace elements. Four campaigns of measurements were conducted in order to estimate some characteristics of DGT in groundwater context and to compare concentrations in water estimated by passive sampling with those obtained by classical sampling. Classical Chelex DGT were used with some application of DGT with different diffusive gel thickness.

Diffusive boundary layer estimation

Interpretation of monitoring results

These data show very contrasted results regarding the element which is considered and also regarding the difference for this element between spot sampling results before and after purging of the piezometer (classical underground water sampling usually includes a purge of the piezometer to get representative water). • V, Cr, Co, Pb, U and Cu : small differences before and after purging. DGT results seems representative of concentration in the water body. The ratios DGT/spot sampling are variable between around 10% for V, Cr, Co to around 70-80% for Cu (around 30% for Pb and U). The ratio is certainly dependant on the speciation of the element in solution (oxyanions forms for example) and/or of the non suitable value of the applied diffusion coefficient (issue from bibliography) in the context of underground water. • Al, Mn, Fe, Ni, Zn, Cd : small or important differences between spot sampling before and after purging are observed. Then DGT results seem more representative of water concentration in the piezometer than in the water body. For example at the end of campaign 4, Ni concentration before and after purging was 12 and 1 µg/l respectively (11,3 and 0,8 µg/l for Zn -39 and 4 ng/l for Cd). It is important to note that this piezometer is very small and could be influenced by leaching of surface water.

Deployment of DGT in underground water allows the sampling at a define depth (interesting characteristic in some hydrogeological studies). However, quantitative interpretation of DGT results in this context seems difficult due to, the apparently non negligible diffusive bound layer, to the complex speciation of element and/or of question related to the fitness of classical diffusion coefficient. Another key point is the representativity of the water which is locally sampled in the piezometer compared to the water body. The absence of purging during DGT deployment could be a difficulty for some elements impacted by local contamination. Another experiment in deeper piezometer indicates that this phenomenon seems amplified here by the small depth of the piezometer.

Monitoring results

Cr : 220 ng/l

Results are given for the 4 campaigns (blue, red, green and purple). Confidence interval are 2 times standard deviation of DGT triplicates. Brown line and brown digits are mean value of spot sampling results after purging (these results were rather stable so mean result is presented)

Conclusion

Acknowledgement : the authors thank ONEMA for its financial support and the field and laboratory technicians' team Deployment strategy CAPDEVILLE Robin LAURIOUX Thierry GHESTEM Jean Philippe Diffusive boundary layer thickness estimation (mm)

	Al	Cr	Mn	Fe	Ni	Co	Cu	Zn	Cd	Pb
	0.9	0.8	0.6	5	1.0	0.7	1.0	1.3	1.6	0.6


Nicolas Obin
email: nobin@ircam.fr

Christophe Veaux

Pierre Lanchantin

Making Sense of Variations: Introducing Alternatives in Speech Synthesis

Keywords: speech synthesis, speech prosody, speech alternatives

This paper addresses the use of speech alternatives to enrich speech synthesis systems. Speech alternatives denote the variety of strategies that a speaker can use to pronounce a sentence -depending on pragmatic constraints, speaking style, and specific strategies of the speaker. During the training, symbolic and acoustic characteristics of a unit-selection speech synthesis system are statistically modelled with context-dependent parametric models (GMMs/HMMs). During the synthesis, symbolic and acoustic alternatives are exploited using a GENERALI-ZED VITERBI ALGORITHM (GVA) to determine the sequence of speech units used for the synthesis. Objective and subjective evaluations supports evidence that the use of speech alternatives significantly improves speech synthesis over conventional speech synthesis systems.

Introduction

A speaker has a variety of alternatives that may be likely used to pronounce a sentence. These alternatives depend on the speaking style, specific strategies of the speaker, pragmatic constraints, and eventually arbitrary choice of the speaker. This variability can be observed either in terms of symbolic (prosodic prominence, prosodic break) or acoustic (prosodic contour) speech characteristics. Current speech synthesis systems [START_REF] Zen | Statistical parametric speech synthesis[END_REF][START_REF] Hunt | Unit selection in a concatenative speech synthesis system using a large speech database[END_REF] do not exploit this variety during statistical modelling or synthesis. During the training, the symbolic and acoustic speech characteristics are usually estimated with a single normal distribution which is assumed to correspond with a single strategy of the speaker. During the synthesis, the sequence of symbolic and acoustic speech characteristics are entirely determined by the sequence of linguistic characteristics associated with the sentence -the most-likely sequence. In real-world speech synthesis applications (e.g., announcement, story-telling, or interactive speech systems), expressive speech is required. However, current speech synthesis systems are often perceived as poorly natural due to the presence of speech artefacts and the absence of variety in the synthesized speech. The use of speech alternatives in speech synthesis may significantly improve both the variety and the quality of the synthesized speech. Firstly, alternatives can be used to provide a variety of speech candidates that may be exploited to vary the speech synthesized for a given sentence. Secondly, alternatives †. The present study has been conducted during the stay of authors in the sound analysis and synthesis department at IRCAM. can also be advantageously used as a relaxed-constraint for the determination of the sequence of speech units to improve the quality of the synthesized speech. For instance, the use of a symbolic alternative (e.g., insertion/deletion of a pause) may conduct to a significantly improved sequence of speech units. This paper addresses the use of speech alternatives to improve the quality and the variety of speech synthesis. The proposed speech synthesis system (IRCAMTTS) is based on unit-selection, and uses various context-dependent parametric models to represent the symbolic/acoustic characteristics of speech prosody (GMMs/HMMs). During the synthesis, symbolic and acoustic alternatives are exploited using a GENERALIZED VITERBI ALGORITHM (GVA) ( [START_REF] Hashimoto | A list-type reduced-constraint generalization of the Viterbi algorithm[END_REF]). First, a GVA is used to determine a set of symbolic candidatescorresponding to the K most-likely sequences of symbolic characteristics, in order to enrich the further selection of speech units. For each symbolic candidate, a GVA is then used to determine the optimal sequence of speech units under the joint constraint of segmental and speech prosody characteristics. Finally, the optimal sequence of speech units is determined so as to maximize the cumulated symbolic/acoustic likelihood.

The speech synthesis system used for the study is presented in section 2. The use of speech alternatives during the synthesis, and the GENERALIZED VITERBI ALGORITHM are introduced in section 3. The proposed method is compared to various configurations of the speech synthesis system (modelling of speech prosody, use of speech alternatives), and validated with objective and subjective evaluations in section 4.

Speech Synthesis System

Unit selection speech synthesis is based on the optimal selection of a sequence of speech units that corresponds to the sequence of linguistics characteristics derived from the text to synthesize. The optimal sequence of speech units is generally determined so as to minimize an objective function usually defined in terms of concatenation and target acoustic costs. Additional linguistic information (e.g., prosodic events -TOBI labels) can also be derived from the text to enrich the linguistic description used for unit selection.

Idealistically, the optimal sequence of speech units u can be determined by jointly maximizing the symbolic/acoustic likelihood of the sequence of speech units u = [u1, . . . , uN ] conditionally to the sequence of linguistic characteristics c = [c1, . . . , cN ] :

u = argmax u p(O(u)|c) (1)
where :

O(u) = [O symb. (u), Oacou.(u)
] denotes the symbolic and acoustic characteristics associated with the sequence of speech units u.

A sub-optimal solution to this equation is usually obtained by factorizing the symbolic/acoustic characteristics :

u symb. = argmax u symb. p(O symb. (u symb. )|c) (2) uacou. = argmax u p(Oacou.(uacou.)|c, u symb. ) (3)
In other words, the symbolic sequence of speech units (e.g., prosodic events) is first determined, and then used for the selection of acoustic speech units.

This conventional approach presents two main inconsistencies :

1. symbolic and acoustic modelling are processed separately during training and synthesis, which remain sub-optimal and may degrade the quality of the speech synthesized.

2. a single sequence of speech characteristics is determined for unit selection, while the use of symbolic/acoustic alternatives may improve the quality and the variety of the speech synthesized.

The optimal solution would consists of a joint symbolic/acoustic unit selection system combined with the integration of speech alternatives. For clarity, the present study will focus only on the use of symbolic/acoustic alternatives in unit selection speech synthesis. In the present study, symbolic alternatives are used to determine a set of symbolic candidates u symb. so as to enrich the further selection of speech units (eq. ( 2)). For each symbolic candidate, the sequence of acoustic speech units uacou. is determined based on a relaxed-constraint search using acoustic alternatives (eq. ( 3)). Finally, the optimal sequence of speech units u is determined so as to maximize the cumulated symbolic/acoustic likelihood.

The use of symbolic/acoustic alternatives requires adequate statistical models that explicitly describe alternatives, and a dynamic selection algorithm that can manage these alternatives during speech synthesis. Symbolic and acoustic models used for this study are briefly introduced in section 2.1 and 2.2. Then, the dynamic selection algorithm used for unit selection is described in section 3.

Symbolic Modelling

The symbolic modelling of prosodic events is a statistical model in which linguistic and metric constraints are combined -based on HMMs [START_REF] Obin | HMM-based Prosodic Structure Model Using Rich Linguistic Context[END_REF] and explicit modelling of the metric constraint (length of a prosodic unit) (cf. [START_REF] Obin | Reformulating Prosodic Break Model into Segmental HMMs and Information Fusion[END_REF] for a detailed description). Additionally, information fusion is used for the optimal combination of linguistic and metric constraints. The prosodic events used cover accent and boundaries, associated with intermediate prosodic phrase and prosodic phrase. Prosodic phrases refer to speech segments that end with a prosodic prominence followed by a long pause ; intermediate prosodic phrases refer to syntactic chunks that end with a prosodic prominence.

Acoustic Modelling

In order to capture the natural speech prosody of a speaker, the acoustic and prosodic models are based on contextdependent GMMs (cf. [START_REF] Veaux | Prosodic control of unit-selection speech synthesis : A probabilistic approach[END_REF] for a detailed description). Three different observation units (phone, syllable and phrase) are considered, and separate GMMs are trained for each of these units. The model associated with the phone unit is merely a reformulation of the target and concatenation costs traditionally used in unit-selection speech synthesis [START_REF] Hunt | Unit selection in a concatenative speech synthesis system using a large speech database[END_REF]. The other models are used to represent the local variation of prosodic contours (F0 and durations) over the syllables and the major prosodic phrases, respectively. The use of GMMs allows to capture prosodic alternatives associated with each of the considered units.

Exploiting Alternatives

!"#$ " !"#$ % !"#$ & ! !"#$ " !"#$ % !"#$ & '!()*+,-. /#"#+ k-2 k-1 k FIGURE 2 -Illustration of the GENERALIZED VITERBI SEARCH.
The boxes represent the list of states among which the best S path are selected. Some survivor path (alternative candidates) can share the same previous states whereas some unlikely states may be pruned in order to limit the overall complexity of the search.

In a conventional synthesizer, the search for the optimal sequence of speech units (eq. ( 1)) is decomposed in two separate optimisation problems (eq. ( 2) and ( 3)). These two equations are generally solved using the Viterbi algorithm. This algorithm defines a trellis whose states at each time t are the N candidate units. At each time t, the Viterbi algorithm considers N lists of competing paths, each list being associated to one of the N states. Then, for each list, only one survivor path is selected for further extension. Therefore the Viterbi algorithm can be described as a N-list 1-survivor (N,1) algorithm. The GENERALIZED VITERBI ALGORITHM [START_REF] Hashimoto | A list-type reduced-constraint generalization of the Viterbi algorithm[END_REF] consists in a twofold relaxation of the path selection.

• First, more than one survivor path can be retained for each list. • Second, a list of competing paths can encompass more than one state.

An illustration of this approach is given in figure 2, which shows that the GVA can retain survivor paths that would otherwise be merged by the classical Viterbi algorithm. Thus, the GVA can keep track of several symbolic/prosodic alternatives until the final decision is made.

In this study, the GVA is first used to determine a set of symbolic candidates -corresponding to the K most-likely sequences of symbolic characteristics, in order to enrich the further selection of speech units. For each symbolic candidate, a GVA is then used to determine the optimal sequence of speech units under the joint constraint of segmental characteristics (phone model) and prosody (syllable and phrase models). Finally, the optimal sequence of speech units is determined so as to maximize the cumulated symbolic/acoustic likelihood.

Evaluation

Objective and subjective evaluations were conducted to address the use of speech alternatives in speech synthesis, with comparison to a BASELINE (no explicit modelling of speech prosody, no use of speech alternatives) and a CONVENTIONAL (explicit modelling of speech prosody, no use of speech alternatives) speech synthesis systems (table 1). Additionally, symbolic alternatives have been optionally used for each compared method to assess the relevancy of symbolic and acoustic alternatives separately.

Speech Material

The speech material used for the evaluation is a 5 hours French story-telling database interpreted by a professional actor, that was designed for expressive speech synthesis. The speech database comes with the following linguistic processing : orthographical transcription ; surface syntactic parsing (POS and word class) ; manual speech segmentation into phonemes and syllables, and automatic labelling/segmentation of prosodic events/units (cf. [START_REF] Obin | HMM-based Prosodic Structure Model Using Rich Linguistic Context[END_REF] for more details).

Objective evaluation

An objective evaluation has been conducted to assess the relative contribution of speech prosody and symbolic/acoustic alternatives to the overall quality of the TTS system. In particular, a specific focus will be made on the use of symbolic/acoustic alternatives.

Procedure

The objective evaluation has been conducted with the 173 sentences of the fairy tale "Le Petit Poucet" ("Tom Thumb").

For this purpose, a cumulated log-likelihood has been defined as a weighted integration of the partial log-likelihoods (symbolic, acoustic). First, each partial log-likelihood have been averaged over the utterance to be synthesized so as to normalize the variable number of observations used for the computation (e.g., phonemes, syllable, prosodic phrase). Then, log-likehoods have been normalized to ensure comparable contribution of each partial log-likelihood during the speech synthesis. Finally, the cumulated log-likelihood of a synthesized speech utterance has been defined as follows :

LL = w symbolic LL symbolic + w acoustic LL acoustic (4)
where LL symbolic and LL acoustic denote the partial loglikelihood associated with the sequence of symbolic and acoustic characteristics ; and w symbolic , w acoustic corresponding weights.

Finally, the optimal sequence of speech units is determined so as to maximize the cumulated log-likelihood of the symbolic/acoustic characteristics. In this study, 10 alternatives have been considered for the symbolic characteristics, and 50 alternatives for the selection of speech units, and weights have been heuristically chosen as w symb = 1, w phone = 1, w syllab = 5, and w phrase = 1.

Discussion

Cumulated likelihood obtained for the compared methods is presented in figure 3, without and with the use of symbolic alternatives. The PROPOSED method (modelling of prosody, use of acoustic alternatives) moderately but significantly outperforms the CONVENTIONAL method (modelling of prosody, no use of acoustic alternatives) ; and dramatically outperforms the BASELINE method. Additionally, the use of symbolic alternatives conducts to a significant improvement regardless to the method considered. Finally, the optimal synthesis is obtained for the combination of symbolic/acoustic alternatives with the modelling of speech prosody. For further investigation, partial likelihoods obtained for the compared methods are presented in figure 4, without and with the use of symbolic alternatives. Not surprisingly, the modelling of speech prosody (syllable/phrase) successfully constraints the selection of speech units with adequate prosody, while this improvement comes with a slight degradation of the segmental characteristics (phone). The use of acoustic alternatives conducts to an improved speech prosody (significant over the syllable, not significant over the phrase) that comes with a slight degradation of the segmental characteristics (non significant). This suggests that the phrase modelling (as described in [START_REF] Veaux | Prosodic control of unit-selection speech synthesis : A probabilistic approach[END_REF]) has partially failed to capture relevant variations, and that this model remains to be improved. Finally, symbolic alternatives are advantageously used to improve the prosody of the selected speech units, without a significant change in the segmental characteristics.

Subjective evaluation

A subjective evaluation has been conducted to compare the quality of the BASELINE, CONVENTIONAL, and PROPOSED speech synthesis systems.

Procedure

For this purpose, 11 sentences have been randomly selected from the fairy-tale, and used to synthesize speech utterances with respect to the considered systems. 15 native French speakers have participated in the evaluation. The evaluation has been conducted according to a crowd-sourcing technique using social networks. Pairs of synthesized speech utterances were randomly presented to the participants who have been asked to attribute a preference score according to the naturalness of the speech utterances on the comparison mean opinion score (CMOS) scale. Participants have been encouraged to use headphones.

Discussion

Figure 5 presents the CMOS obtained for the compared methods. The PROPOSED method is substantially preferred to the other methods, which indicates that the use of sym-bolic/acoustic alternatives conducts to a qualitative improvement of the speech synthesized over all other systems. Then, CONVENTIONAL method is fairly preferred to the BASELINE method, which confirms that the integration of speech prosody also improves the quality of speech synthesis over the BASE-LINE system (cf. observation partially reported in [START_REF] Veaux | Prosodic control of unit-selection speech synthesis : A probabilistic approach[END_REF]). CONV.

PROP.

CMOS

FIGURE 5 -CMOS (mean and 95% confidence interval) obtained for the compared methods.

Conclusion

In this paper, the use of speech alternatives in unit-selection speech synthesis have been introduced. Speech alternatives may be advantageously used either to improve the quality and the variety of the speech synthesis. Objective and subjective evaluations supports evidence that the use of speech alternatives qualitatively improves speech synthesis over conventional speech synthesis systems. In further studies, the use of speech alternatives will be integrated into a joint modelling of symbolic/acoustic characteristics so as to improve the consistency of the selected sequence of speech units.

FIGURE 1 -

 1 FIGURE 1 -Illustration of alternatives in speech prosody.

  the dimensionality of the search space.

Figure 1 :

 1 Figure 1: Principle of the GVA. The boxes represent

FIGURE 3 -

 3 FIGURE 3 -Cumulated likelihood (mean and 95% confidence interval) obtained for the compared TTS, without (left) and with (right) use of symbolic alternatives.

TABLE 1 -

 1 Description of TTS systems used for the evaluation.