Maria Chlouveraki

Nicolas Jacon

SCHUR ELEMENTS FOR THE ARIKI-KOIKE ALGEBRA AND APPLICATIONS

We study the Schur elements associated to the simple modules of the Ariki-Koike algebra. We first give a cancellation-free formula for them so that their factors can be easily read and programmed. We then study direct applications of this result. We also complete the determination of the canonical basic sets for cyclotomic Hecke algebras of type G(l, p, n) in characteristic 0.

Introduction

Schur elements play a powerful role in the representation theory of symmetric algebras. In the case of the Ariki-Koike algebra, that is, the Hecke algebra of the complex reflection group G(l, 1, n), they are Laurent polynomials whose factors determine when Specht modules are projective irreducible and whether the algebra is semisimple.

Formulas for the Schur elements of the Ariki-Koike algebra have been obtained independently, first by Geck, Iancu and Malle [START_REF] Geck | Weights of Markov traces and generic degrees[END_REF], and later by Mathas [START_REF] Mathas | Matrix units and generic degrees for the Ariki-Koike algebras[END_REF]. The first aim of this paper is to give a cancellation-free formula for these polynomials (Theorem 3.2), so that their factors can be easily read and programmed. We then present a number of direct applications. These include a new formula for Lusztig's a-function, as well as a simple classification of the projective irreducible modules for Ariki-Koike algebras (that is, the blocks of defect 0).

The second part of the paper is devoted to another aspect of the representation theory of these algebras in connection with these Schur elements: the theory of canonical basic sets. The main aim here is to obtain a classification of the simple modules for specialisations of cyclotomic Hecke algebras in characteristic 0. In [START_REF] Chlouveraki | Schur elements and Basic sets for Cyclotomic Hecke algebras[END_REF], we studied mainly the case of finite Weyl groups. In this paper, we focus on cyclotomic Hecke algebras of type G(l, p, n). Using Lusztig's a-function, defined from the Schur elements, the theory of canonical basic sets provides a natural and efficient way to parametrise the simple modules of these algebras.

The existence and explicit determination of the canonical basic sets is already known in the case of Hecke algebras of finite Weyl groups (see [START_REF] Geck | Irreducible Representations of Hecke algebras at roots of unity, Algebras and Applications[END_REF] and [START_REF] Chlouveraki | Schur elements and Basic sets for Cyclotomic Hecke algebras[END_REF]). The case of cyclotomic Hecke algebras of type G(l, p, n) has been partially studied in [START_REF] Geck | Irreducible Representations of Hecke algebras at roots of unity, Algebras and Applications[END_REF][START_REF] Genet | Modular representations of cyclotomic Hecke algebras of type G(r[END_REF], and recently in [START_REF] Chlouveraki | Cell modules and canonical basic sets for Hecke algebras from Cherednik algebras[END_REF] using the theory of Cherednik algebras. Answering a question raised in [START_REF] Chlouveraki | Cell modules and canonical basic sets for Hecke algebras from Cherednik algebras[END_REF], the goal of the last part of this paper is to complete the determination of the canonical basic sets in this case.

Preliminaries

In this section, we introduce the necessary definitions and notation.

2.1.

A partition λ = (λ 1 , λ 2 , λ 3 , . . .) is a decreasing sequence of non-negative integers. We define the length of λ to be the smallest integer ℓ(λ) such that λ i = 0 for all i > ℓ(λ). We write |λ| := i≥1 λ i and we say that λ is a partition of m, for some m ∈ N, if m = |λ|. We set n(λ) := i≥1 (i -1)λ i .

The authors would like to thank I. Gordon, S. Griffeth, M. Fayers and A. Mathas for useful conversations. In particular, the first author is indebted to Stephen Griffeth for explaining the results of his paper [START_REF] Dunkl | Generalized Jack polynomials and the representation theory of rational Cherednik algebras[END_REF], which inspired part of this paper. Maria Chlouveraki gratefully acknowledges the support of the EPSRC through the grant EP/G04984X/1.

1

We define the set of nodes [λ] of λ to be the set

[λ] := {(i, j) | i ≥ 1, 1 ≤ j ≤ λ i }. A node x = (i, j) is called removable if [λ] \ {(i, j)} is still the set of nodes of a partition. Note that if (i, j) is removable, then j = λ i .
The conjugate partition of λ is the partition λ ′ defined by

λ ′ k := #{i | i ≥ 1 such that λ i ≥ k}. Obviously, λ ′ 1 = ℓ(λ). The set of nodes of λ ′ satisfies (i, j) ∈ [λ ′ ] ⇔ (j, i) ∈ [λ].
Note that if (i, λ i ) is a removable node of λ, then λ ′ λ i = i. Moreover, we have

n(λ) = i≥1 (i -1)λ i = 1 2 i≥1 (λ ′ i -1)λ ′ i . If x = (i, j) ∈ [λ]
and µ is another partition, we define the generalised hook length of x with respect to (λ, µ) to be the integer: h λ,µ i,j := λ ii + µ ′ jj + 1. For µ = λ, the above formula becomes the classical hook length formula (giving the length of the hook of λ that x belongs to). Moreover, we define the content of x to be the difference cont(x) = ji.

The following lemma, whose proof is an easy combinatorial exercise (with the use of Young diagrams), relates the contents of the nodes of (the "right rim" of) λ with the contents of the nodes of (the "lower rim" of) λ ′ . Lemma 2.2. Let λ = (λ 1 , λ 2 , . . .) be a partition and let k be an integer such that 1 ≤ k ≤ λ 1 . Let q and y be two indeterminates. Then we have

1 (q λ 1 y -1) •   1≤i≤λ ′ k q λ i -i+1 y -1 q λ i -i y -1   = 1 (q -λ ′ k +k-1 y -1) •   k≤j≤λ 1 q -λ ′ j +j-1 y -1 q -λ ′ j +j y -1   .

2.3.

Let l and n be positive integers. An l-partition of n is an ordered l-tuple λ = (λ 0 , λ 1 , . . . , λ l-1 ) of partitions such that 0≤s≤l-1 |λ s | = n. We denote by Π l n the set of l-partitions of n. 2.4. Let R be a commutative domain with 1. Fix elements q, Q 0 , . . . , Q l-1 of R, and assume that q is invertible in R. Set q := (Q 0 , . . . , Q l-1 ; q). The Ariki-Koike algebra H q n is the unital associative R-algebra with generators T 0 , T 1 , . . . , T n-1 and relations:

(T 0 -Q 0 )(T 0 -Q 1 ) • • • (T 0 -Q l-1 ) = 0, (T i -q)(T i + 1) = 0 for 1 ≤ i ≤ n -1, T 0 T 1 T 0 T 1 = T 1 T 0 T 1 T 0 , T i T i+1 T i = T i+1 T i T i+1 for 1 ≤ i ≤ n -2, T i T j = T j T i for 0 ≤ i < j ≤ n -1 with j -i > 1.
The last three relations are the braid relations satisfied by T 0 , T 1 , . . . , T n-1 . The Ariki-Koike algebra H q n is a deformation of the group algebra of the complex reflection group G(l, 1, n) = (Z/lZ) ≀ S n . Ariki and Koike [START_REF] Ariki | A Hecke algebra of (Z/rZ) ≀ Sn and construction of its irreducible representations[END_REF] have proved that H q n is a free R-module of rank [START_REF] Ariki | Representations of quantum algebras and combinatorics of Young tableaux[END_REF]Proposition 13.11]). In addition, when R is a field, they have constructed a simple H q n -module V λ , with character χ λ , for each l-partition λ of n (see [START_REF] Ariki | Representations of quantum algebras and combinatorics of Young tableaux[END_REF]Theorem 13.6]). These modules form a complete set of non-isomorphic simple modules in the case where H q n is split semisimple (see [2, Corollary 13.9]).

l n n! = |G(l, 1, n)| (see

2.5.

There is a useful semisimplicty criterion for Ariki-Koike algebras which has been given by Ariki in [START_REF] Ariki | On the semi-simplicity of the Hecke algebra of (Z/rZ) ≀ Sn[END_REF]. This criterion will be recovered from our results later (see Theorem 4.2), so let us simply assume from now on that H q n is split semisimple. This happens, for example, when q, Q 0 , . . . , Q l-1 are indeterminates and R = Q(q, Q 0 , . . . , Q l-1 ). Now, there exists a linear form τ : H l n → R which was introduced by Bremke and Malle in [START_REF] Bremke | Reduced words and a length function for G(e, 1, n)[END_REF], and was proved to be symmetrizing by Malle and Mathas in [START_REF] Malle | Symmetric cyclotomic Hecke algebras[END_REF] whenever all Q i 's are invertible in R. An explicit description of this form can be found in any of these two articles. Following Geck's results on symmetrizing forms (see [START_REF] Geck | Characters of finite Coxeter groups and Iwahori-Hecke algebras[END_REF]Theorem 7.2.6]), we obtain the following definition for the Schur elements associated to the irreducible representations of H q n . Definition 2.6. Suppose that R is a field and that H q n is split semisimple. The Schur elements of H q n are the elements s λ (q) of R such that

τ = λ∈Π l n 1 s λ (q) χ λ .
2.7. The Schur elements of the Ariki-Koike algebra H q n have been independently calculated by Geck, Iancu and Malle [START_REF] Geck | Weights of Markov traces and generic degrees[END_REF], and by Mathas [START_REF] Mathas | Matrix units and generic degrees for the Ariki-Koike algebras[END_REF]. From now on, for all m ∈ N, let [m] q := (q m -1)/(q -1) = q m-1 + q m-2 + • • • + q + 1. The formula given by Mathas does not demand extra notation and is the following: Theorem 2.8. Let λ = (λ 0 , λ 1 , . . . , λ l-1 ) be an l-partition of n. Then

s λ (q) = (-1) n(l-1) (Q 0 Q 1 • • • Q l-1 ) -n q -α(λ ′ ) 0≤s≤l-1 (i,j)∈[λ s ] Q s [h λ s ,λ s i,j ] q • 0≤s<t≤l-1 X λ st , where α(λ ′ ) = 1 2 0≤s≤l-1 i≥1 (λ s ′ i -1)λ s ′ i and X λ st = (i,j)∈[λ t ] (q j-i Q t -Q s ) • (i,j)∈[λ s ]   (q j-i Q s -q λ t 1 Q t ) 1≤k≤λ t 1 q j-i Q s -q k-1-λ t ′ k Q t q j-i Q s -q k-λ t ′ k Q t   .
The formula by Geck, Iancu and Malle is more symmetric, and describes the Schur elements in terms of beta numbers. If λ = (λ 0 , λ 1 , . . . , λ l-1 ) is an l-partition of n, then the length of λ is ℓ(λ) = max{ℓ(λ s ) | 0 ≤ s ≤ l -1}. Fix an integer L such that L ≥ ℓ(λ). The L-beta numbers for λ s are the integers β s i = λ s i + Li for i = 1, . . . , L. Set B s = {β s 1 , . . . , β s L } for s = 0, . . . , l -1. The matrix B = (B s ) 0≤s≤l-1 is called the L-symbol of λ. Theorem 2.9. Let λ = (λ 0 , . . . , λ l-1 ) be an l-partition of n with L-symbol B = (B s ) 0≤s≤l-1 , where

L ≥ ℓ(λ). Let a L := n(l -1) + l 2 L 2 and b L := lL(L -1)(2lL -l -3)/12. Then s λ (q) = (-1) a L q b L (q -1) -n (Q 0 Q 1 . . . Q l-1 ) -n ν λ /δ λ , where ν λ = 0≤s<t≤l-1 (Q s -Q t ) L 0≤s, t≤l-1 bs∈B s 1≤k≤bs (q k Q s -Q t ) and δ λ = 0≤s<t≤l-1 (bs,bt)∈B s ×B t (q bs Q s -q bt Q t ) 0≤s≤l-1 1≤i<j≤L (q β s i Q s -q β s j Q s ).
As the reader may see, in both formulas above, the factors of s λ (q) are not obvious. Hence, it is not obvious for which values of q the Schur element s λ (q) becomes zero.

A cancellation-free formula for the Schur elements

In this section, we will give a cancellation-free formula for the Schur elements of H q n . This formula is also symmetric.

3.1.

Let λ = (λ 0 , λ 1 , . . . , λ l-1 ) be an l-partition of n. The multiset (λ s i ) 0≤s≤l-1, i≥1 is a composition of n (i.e. a multiset of non-negative integers whose sum is equal to n). By reordering the elements of this composition, we obtain a partition of n. We denote this partition by λ. (e.g., if λ = ((4, 1), ∅, (2, 1)), then λ = (4, 2, 1, 1)). Theorem 3.2. Let λ = (λ 0 , λ 1 , . . . , λ l-1 ) be an l-partition of n. Then

(1) s λ (q) = (-1) n(l-1) q -n( λ) (q -1) -n 0≤s≤l-1 (i,j)∈[λ s ] 0≤t≤l-1 (q h λ s ,λ t i,j Q s Q -1 t -1).
Since the total number of nodes in λ is equal to n, the above formula can be rewritten as follows:

(2)

s λ (q) = (-1) n(l-1) q -n( λ) 0≤s≤l-1 (i,j)∈[λ s ]   [h λ s ,λ s i,j ] q 0≤t≤l-1, t =s (q h λ s ,λ t i,j Q s Q -1 t -1)   .
3.3. We will now proceed to the proof of the above result. Following Theorem 2.8, we have that

s λ (q) = (-1) n(l-1) (Q 0 Q 1 • • • Q l-1 ) -n q -α(λ ′ ) 0≤s≤l-1 (i,j)∈[λ s ] Q s [h λ s ,λ s i,j ] q • 0≤s<t≤l-1 X λ st ,
where

α(λ ′ ) = 1 2 0≤s≤l-1 i≥1 (λ s ′ i -1)λ s ′ i and X λ st = (i,j)∈[λ t ] (q j-i Q t -Q s ) • (i,j)∈[λ s ]   (q j-i Q s -q λ t 1 Q t ) 1≤k≤λ t 1 q j-i Q s -q k-1-λ t ′ k Q t q j-i Q s -q k-λ t ′ k Q t   .
The following lemma relates the terms q -n( λ) and q -α(λ ′ ) .

Lemma 3.4. Let λ be an l-partition of n. We have that

α(λ ′ ) + 0≤s<t≤l-1 i≥1 λ s ′ i λ t ′ i = n( λ).
Proof. Following the definition of the conjugate partition, we have

λ′ i = 0≤s≤l-1 λ s ′ i , for all i ≥ 1. Therefore, n( λ) = 1 2 i≥1 ( λ′ i -1) λ′ i = 1 2 i≥1     0≤s≤l-1 λ s ′ i -1   • 0≤s≤l-1 λ s ′ i   = 1 2 i≥1   0≤s<t≤l-1 2 • λ s ′ i λ t ′ i + 0≤s≤l-1 λ s ′ i 2 - 0≤s≤l-1 λ s ′ i   = 0≤s<t≤l-1 i≥1 λ s ′ i λ t ′ i + 1 2 0≤s≤l-1 i≥1 (λ s ′ i -1)λ s ′ i = 0≤s<t≤l-1 i≥1 λ s ′ i λ t ′ i + α(λ ′ )
Hence, to prove Equality (2), it is enough to show that, for all 0 ≤ s < t ≤ l -1,

(3)

X λ st = q -i≥1 λ s ′ i λ t ′ i Q |λ t | s Q |λ s | t (i,j)∈[λ s ] (q h λ s ,λ t i,j Q s Q -1 t -1) • (i,j)∈[λ t ] (q h λ t ,λ s i,j Q t Q -1 s -1).
3.5. We will proceed by induction on the number of nodes of λ s . We do not need to do the same for λ t , because the symmetric formula for the Schur elements given by Theorem 2.9 implies the following: if µ is the multipartition obtained from λ by exchanging λ s and λ t , then

X λ st (Q s , Q t ) = X µ st (Q t , Q s ). If λ s = ∅, then X λ st = (i,j)∈[λ t ] (q j-i Q t -Q s ) = Q |λ t | s (i,j)∈[λ t ] (q j-i Q t Q -1 s -1) = Q |λ t | s 1≤i≤λ t ′ 1 1≤j≤λ t i (q j-i Q t Q -1 s -1) = Q |λ t | s 1≤i≤λ t ′ 1 1≤j≤λ t i (q λ t i -j+1-i Q t Q -1 s -1) = Q |λ t | s (i,j)∈[λ t ] (q h λ t ,λ s i,j Q t Q -1 s -1),
as required.

3.6. Now assume that our assertion holds when #[λ s ] ∈ {0, 1, 2, . . . , N -1}. We want to show that it also holds when #[λ s ] = N ≥ 1. If λ s = ∅, then there exists i such that (i, λ s i ) is a removable node of λ s . Let ν be the multipartition defined by

ν s i := λ s i -1, ν s j := λ s j for all j = i, ν t := λ t for all t = s. Then [λ s ] = [ν s ] ∪ {(i, λ s i )}. Since Equation (3) holds for X ν st and X λ st = X ν st •   (q λ s i -i Q s -q λ t 1 Q t ) 1≤k≤λ t 1 q λ s i -i Q s -q k-1-λ t ′ k Q t q λ s i -i Q s -q k-λ t ′ k Q t   ,
it is enough to show that (to simplify notation, from now on set λ := λ s and µ := λ t ):

(4) (q λ i -i Q s -q µ 1 Q t ) 1≤k≤µ 1 q λ i -i Q s -q k-1-µ ′ k Q t q λ i -i Q s -q k-µ ′ k Q t = q -µ ′ λ i Q t (q λ i -i+µ ′ λ i -λ i +1 Q s Q -1 t -1) • A • B,
where

A := 1≤k≤λ i -1 q λ i -i+µ ′ k -k+1 Q s Q -1 t -1 q λ i -i+µ ′ k -k Q s Q -1 t -1 and B := 1≤k≤µ ′ λ i q µ k -k+λ ′ λ i -λ i +1 Q t Q -1 s -1 q µ k -k+λ ′ λ i -λ i Q t Q -1 s -1 .
Note that, since (i, λ i ) is a removable node of λ, we have λ ′ λ i = i. We have that

A = q λ i -1 1≤k≤λ i -1 q λ i -i Q s -q k-1-µ ′ k Q t q λ i -i Q s -q k-µ ′ k Q t .
Moreover, by Lemma 2.2, for y

= q i-λ i Q t Q -1 s , we obtain that B = (q µ 1 +i-λ i Q t Q -1 s -1) (q -µ ′ λ i +λ i -1+i-λ i Q t Q -1 s -1) •   λ i ≤k≤µ 1 q -µ ′ k +k-1+i-λ i Q t Q -1 s -1 q -µ ′ k +k+i-λ i Q t Q -1 s -1   , i.e., B = Q -1 t q µ ′ λ i -λ i +1 (q λ i -i Q s -q µ 1 Q t ) (q µ ′ λ i -λ i +1+λ i -i Q s Q -1 t -1) •   λ i ≤k≤µ 1 q λ i -i Q s -q k-1-µ ′ k Q t q λ i -i Q s -q k-µ ′ k Q t   .
Hence, Equality (4) holds.

First consequences

We give here several direct applications of Formula (2) obtained in Theorem 3.2.

4.1.

A first application of Formula ( 2) is that we can easily recover a well-known semisimplicity criterion for the Ariki-Koike algebra due to Ariki [START_REF] Ariki | On the semi-simplicity of the Hecke algebra of (Z/rZ) ≀ Sn[END_REF]. To do this, let us assume that q, Q 0 , . . . , Q l-1 are indeterminates and R = Q(q, Q 0 , . . . , Q l-1 ). Then the resulting "generic" Ariki-Koike algebra H q n is split semisimple. Now assume that θ : Z[q ±1 , Q ±1 0 , . . . , Q ±1 l-1 ] → K is a specialisation and let KH q n be the specialised algebra, where K is any field. Note that for all λ ∈ Π l n , we have

s λ (q) ∈ Z[q ±1 , Q ±1 0 , . . . , Q ±1 l-1 ].
Then by [13, Theorem 7.2.6], KH q n is (split) semisimple if and only if, for all λ ∈ Π l n , we have θ(s λ (q)) = 0. From this, we can deduce the following: Theorem 4.2 (Ariki). Assume that K is a field. The algebra KH q n is (split) semisimple if and only if θ(P (q)) = 0, where

P (q) = 1≤i≤n (1 + q + • • • + q i-1 ) 0≤s<t≤l-1 -n<k<n (q k Q s -Q t )
Proof. Assume first that θ(P (q)) = 0. We distinguish three cases: (a) If there exists 2 ≤ i ≤ n such that θ(1 + q + . . . + q i-1 ) = 0, then we have θ([h λ 0 ,λ 0 1,n-i+1 ] q ) = 0 for λ = ((n), ∅, . . . , ∅) ∈ Π l n . Thus, for this l-partition, we have θ(s λ (q)) = 0, which implies that KH q n is not semisimple.

(b) If there exist 0 ≤ s < t ≤ l -1 and 0 ≤ k < n such that θ(q k Q s -Q t ) = 0, then we have

θ(q h λ s ,λ t 1,n-k Q s Q -1 t -1) = 0 for λ ∈ Π l n such that λ s = (n), λ t = ∅.
We have θ(s λ (q)) = 0 and KH q n is not semisimple. (c) If there exist 0 ≤ s < t ≤ l -1 and -n < k < 0 such that θ(q k Q s -Q t ) = 0, then we have

θ(q h λ t ,λ s 1,n+k Q t Q -1 s -1) = 0 for λ ∈ Π l n such that λ s = ∅, λ t = (n)
. Again, we have θ(s λ (q)) = 0 and KH q n is not semisimple. Conversely, if KH q n is not semisimple, then there exists λ ∈ Π l n such that θ(s λ (q)) = 0. As for all 0 ≤ s, t ≤ l -1 and (i, j) ∈ [λ s ], we have -n < h λ s ,λ t i,j

< n, we conclude that θ(P (q)) = 0.

4.3.

We now consider a remarkable specialisation of the generic Ariki-Koike algebra. Let u be an indeterminate. Let r ∈ Z >0 and let r 0 , . . . , r l-1 be any integers. Set r := (r 0 , . . . , r l-1 ) and η l := exp(2 √ -1π/l). For all i = 0, . . . , l -1, we set m i := r i /r and we define m := (m 0 , . . . , m l-1 )

∈ Q l . Assume that R = Z[q ±1 , Q ±1 0 , . . . , Q ±1 l-1
] and consider the morphism

θ : R → Z[η l ][u ±1 ]
such that θ(q) = u r and θ(Q j ) = η j l u r j for j = 0, 1, . . . , l -1. We will denote by H m,r n the specialisation of the Ariki-Koike algebra H q n via θ. The algebra H m,r n is called a cyclotomic Ariki-Koike algebra. It is defined over Z[η l ][u ±1 ] and has a presentation as follows:

• generators: T 0 , T 1 ,. . . , T n-1 ,

• relations:

(T 0 -u r 0 )(T 0 -η l u r 1 ) • • • (T 0 -η l-1 l u r l-1 ) = 0 (T j -u r )(T j + 1) = 0 for j = 1, ..., n -1
and the braid relations symbolised by the diagram

t 4 t t • • • t T 0 T 1 T 2 T n-1 .
We set K := Q(η l ). The algebra K(u)H m,r n , which is obtained by extension of scalars to K(u), is a split semisimple algebra. As a consequence, one can apply Tits's Deformation Theorem (see, for example, [13, §7.4]), and obtain that

Irr(K(u)H m,r n ) = {V λ | λ ∈ Π l n }.
Using the Schur elements, one can attach to every simple K(u)H m,r n -module V λ a rational number a (m,r) (λ), by setting a (m,r) (λ) to be the the negative of the valuation of the Schur element of V λ in u, that is, the negative of the valuation of θ(s λ (q)). We call this number the a-value of λ . By [12, §5.5], this value may be easily computed combinatorially: Let λ ∈ Π l n and let s ∈ Z >0 be such that s ≥ min{i ∈ Z | ∀j ∈ {0, 1, . . . , l -1}, λ j i = 0}. Let B be the shifted m-symbol of λ of size s ∈ Z >0 . This is the l-tuple (B 0 , . . . , B l-1 ) where, for all j = 0, . . . , l -1 and for all i = 1, . . . , s + [m j ] (where [m j ] denotes the integer part of m j ), we have

B j i = λ j i -i + s + m j and B j = (B j s+[m j ] , . . . , B j 1 ) . Write κ 1 ≥ κ 2 ≥ • • • ≥ κ h
for the elements of B written in decreasing order (allowing repetitions), where h

= ls+ 0≤j≤l-1 [m j ]. Let κ m (λ) = (κ 1 , . . . , κ h ) ∈ Q h ≥0 and define n m (λ) := 1≤i≤h (i -1)κ i .
Then, by [12, Proposition 5.5.11], the a-value of λ is :

a (m,r) (λ) = r(n m (λ) -n m (∅)).
Generalising the dominance order for partitions, we will write κ m (λ) ⊲ κ m (µ) if κ m (λ) = κ m (µ) and 1≤i≤t κ i (λ) ≥ 1≤i≤t κ i (µ) for all t ≥ 1. The following result [12, Proposition 5.5.16] will be useful in then next sections: Proposition 4.4. Assume that λ and µ are two l-partitions with the same rank such that κ m (λ) ⊲ κ m (µ). Then a (m,r) (µ) > a (m,r) (λ). Now, Formula (2) allows us to give an alternative description of the a-value of λ:

Proposition 4.5. Let λ ∈ Π l n . The a-value of λ is a (m,r) (λ) = r   n(λ) - 0≤s≤l-1 (i,j)∈[λ s ] 0≤t≤l-1,t =s min(h λ s ,λ t i,j + m s -m t , 0)   .
4.6. We now consider another type of specialisation. Let v 0 , . . . , v l-1 be any integers. Let k be a subfield of C and let η be a primitive root of unity of order e > 1. Assume that R = Z[q ±1 , Q ±1 0 , . . . , Q ±1 l-1 ] and consider the morphism

θ : R → k(η)
such that θ(q) = η and θ(Q j ) = η v j for j = 0, 1, . . . , l -1. By Theorem 4.2, the specialised algebra k(η)H q n is not generally semisimple, and a result by Dipper and Mathas which will be specified later (see §5.2) implies that the study of this algebra is enough for studying the non-semisimple representation theory of Ariki-Koike algebras in characteristic 0. Let

D = ([V λ : M ]) λ∈Π l n , M ∈Irr(k(η)H q n )
be the associated decomposition matrix (see [13, §7.4]), which relates the irreducible representations of the split semisimple Ariki-Koike algebra H q n and the specialised Ariki-Koike algebra k(η)H q n . We are interested in the classification of the blocks of defect 0. That is, we want to classify the l-partitions λ ∈ Π l n which are alone in their blocks in the decomposition matrix. These correspond to the modules V λ which remain projective and irreducible after the specialisation θ. By [17, Lemme 2.6], these elements are characterized by the property that θ(s λ (q)) = 0. In our setting, using Formula (2), we obtain the following: Proposition 4.7. Under the above hypotheses, λ ∈ Π l n is in a block of defect 0 if and only if, for all 0 ≤ s, t ≤ l -1 and (i, j) ∈ [λ s ], e does not divide h λ s ,λ t i,j

+ v s -v t .
Remark 4.8. As pointed out by M. Fayers and A. Mathas, the above proposition should also be obtained using [START_REF] Fayers | Weights of multipartitions and representations of Ariki-Koike algebras. II. Canonical bases[END_REF].

Canonical basic sets for Ariki-Koike algebras

In this part, we generalise some known results on basic sets for Ariki-Koike algebras, using a fundamental result by Dipper and Mathas. This will help us determine the canonical basic sets for cyclotomic Ariki-Koike algebras in full generality.

5.1.

We consider the cyclotomic Ariki-Koike algebra H m,r n defined in §4.3, replacing from now on the indeterminate u by the indeterminate q (following the usual notation). Let θ : Z[η l ][q ±1 ] → K(η) be a specialisation such that θ(q) = η ∈ C * . We obtain a specialised Ariki-Koike algebra K(η)H m,r n . The relations between the generators are the usual braid relations together with the following ones:

(T 0 -η r 0 )(T 0 -η l η r 1 ) • • • (T 0 -η l-1 l η r l-1 ) = 0 (T j -η r )(T j + 1) = 0 for j = 1, ..., n -1. Let D = ([V λ : M ]) λ∈Π l n , M ∈Irr(K(η)H m,r n )
be the associated decomposition matrix (see [13, §7.4]). The matrix D relates the irreducible representations of the split semisimple Ariki-Koike algebra K(q)H m,r n and the specialised Ariki-Koike algebra K(η)H m,r n . The goal of this section is to study the form of this matrix in full generality.

First assume that η is not a root of unity. Then, for all 0 ≤ i = j ≤ l -1, we have η i-j l η r i -r j = η rd for all d ∈ Z >0 . By the criterion of semisimplicty due to Ariki (Theorem 4.2), this implies that the algebra K(η)H m,r n is split semisimple, and thus D is the identity matrix. Hence, from now, one may assume that η is a primitive root of unity of order e > 1. Then there exists k ∈ Z >0 such that gcd(k, e) = 1 and η = exp(2 √ -1πk/e).

5.2.

We will now use a reduction theorem by Dipper and Mathas which will help us understand the form of D. Set I = {0, 1, . . . , l -1}. There is a partition

I = I 1 ⊔ I 2 ⊔ . . . ⊔ I p such that 1≤α<β≤p (i,j)∈Iα×I β -n<d<n (η rd -η i-j l η r i -r j ) = 0.
For all i = 1, . . . , p, we set l i := |I i | and we consider I i as an ordered set

I i = (i 1 , i 2 , . . . , i l i ) with i 1 < i 2 < • • • < i l i .
We define

π i : Q l → Q l i (x 0 , x 1 , . . . , x l-1 ) → (x i 1 , x i 2 , . . . , x i l i ) For n i ∈ Z ≥0 , we have an Ariki-Koike algebra of type G(l i , 1, n i ) which we denote by H m i ,r n i with m i := π i (m) = (m i 1 , m i 2 , . . . , m i l i ).
The relations between the generators are the usual braid relations together with the following ones:

(T 0 -η i 1 l q r i 1 )(T 0 -η i 2 l q r i 2 ) • • • (T 0 -η i l i l q r i l i ) = 0 (T j -q r )(T j + 1) = 0 for j = 1, ..., n i -1.
Note however that H m i ,r n i is not a cyclotomic Ariki-Koike algebra in general, because l i = l. The specialisation θ i : Z[η l ][q ±1 ] → K(η) such that θ(q) = η defines a specialised algebra K(η)H m i ,r n i , and we have an associated decomposition matrix

D i n i = ([V λ : M ]) λ∈Π l i n i , M ∈Irr(K(η)H m i ,r n i
)

.

In [START_REF] Dipper | Morita equivalences of Ariki-Koike algebras[END_REF], Dipper and Mathas have shown that K(η)H m,r n is Morita equivalent to the algebra

n 1 , . . . , n p ≥ 0 n 1 + • • • + n p = n K(η)H m 1 ,r n 1 ⊗ K(η) K(η)H m 2 ,r n 2 ⊗ K(η) • • • ⊗ K(η) K(η)H m p ,r np .
Thus, for a suitable ordering of the rows and columns, D has the form of a block diagonal matrix where each block is given by D

1 n 1 ⊗ • • • ⊗ D p np with n 1 + . . . + n p = n.
More precisely, we have the following result ([8, Proposition 4.11]):

Theorem 5.3 (Dipper-Mathas). Let λ ∈ Π l n and M ∈ Irr(K(η)H m,r n ). There exist integers n 1 , . . . , n p ≥ 0 with n 1 + • • • + n p = n, and M i ∈ Irr(K(η)H m i ,r n i ) such that [V λ : M ] =    1≤i≤p [V π i (λ) : M i ], if π i (λ) ∈ Π l i n i ∀i ∈ [1, p] 0, otherwise.
5.4. We now fix i ∈ {1, . . . , p}. By definition of I i = (i 1 , i 2 , . . . , i l i ), one may assume that, for all j = 1, . . . , l i , there exist s j ∈ Z such that

η i j -i 1 l η r i j -r i 1 = η rs j
(with s 1 = 0). We have r i jr i 1 = rs je(i ji 1 )/(kl), whence we deduce the following relation:

(5) m i jm i 1 = s je(i ji 1 )/(klr).

Set s i := (s 1 , . . . , s l i ).

5.5. Keeping the above notation, let us consider the Ariki-Koike algebra

K(η)H m i ,r n i of type G(l i , 1, n i ) (with n i ≤ n) with relations (T 0 -η i 1 l η r i 1 )(T 0 -η i 2 l η r i 2 ) • • • (T 0 -η i l i l η r i l i ) = 0 (T j -η r )(T j + 1) = 0 for j = 1, ..., n i -1.
This is then isomorphic to the Ariki-Koike algebra with relations

(T 0 -η rs 1 )(T 0 -η rs 2 ) • • • (T 0 -η rs l i ) = 0 (T j -η r )(T j + 1) = 0 for j = 1, ..., n i -1.
The following is a direct consequence of [12, Theorem 6.7.2].

Proposition 5.6. Under the above hypothesis, there exists a set

Φ l i n i (s i ) ⊂ Π l i n i with |Φ l i n i (s i )| = | Irr(K(η)H m i ,r n i )|
such that the following property is satisfied: For any M ∈ Irr(K(η)H m i ,r n i ), there exists a unique

l i -partition λ M ∈ Φ l i n i (s i ) such that • Φ 2 2 (s 1 ) = {((2), ∅), ((1), (1))}, • Φ 2 1 (s 1 ) = {((1), ∅)}, • Φ 1 1 (s 2 ) = {(1)}, • Φ 1 2 (s 2 ) = {(2)}.
Therefore, the canonical basic set with respect to θ for H m,r 2 is B θ = {((2), ∅, ∅), ((1), (1), ∅), ((1), ∅, (1)), (∅, ∅, (2))}.

6. Canonical basic sets for cyclotomic Hecke algebras of type G(l, p, n)

The purpose of this last part is to deduce from the last section the existence of the explicit parametrisation of the basic sets for Cyclotomic Hecke algebra of type G(l, p, n).

6.1. Let l, p, n be three positive integers with n > 2 (we can also take n = 2, but then we must assume that p is odd). Set d := l/p. Let r ∈ Z >0 and let r 0 , r 1 , . . . , r d-1 be any integers. For all i = 0, . . . , d-1, we set m i := r i /(pr) and we define m := (m 0 , . . . , m d-1 , m 0 , . . . , m d-1 , . . . , m 0 , . . . , m d-1 ) ∈ Q l (where the d-tuple (m 0 , . . . , m d-1 ) is repeated p times). We consider the cyclotomic Hecke algebra H m,pr p,n of type G(l, p, n) over Z[η l ][q ±1 ] with presentation as follows: • generators: t 0 , t 1 ,. . . , t n , • relations:

(t 0 -q pr 0 )(t 0 -η d q pr 1 ) • • • (t 0 -η d-1
d q pr d-1 ) = 0 (t jq pr )(t j + 1) = 0 for j = 1, ..., n and the braid relations t 1 t 3 t 1 = t 3 t 1 t 3 , t j t j+1 t j = t j+1 t j t j+1 for j = 2, . . . , n -1, -t 1 t 2 t 3 t 1 t 2 t 3 = t 3 t 1 t 2 t 3 t 1 t 2 , -t 1 t j = t j t 1 for j = 4, . . . , n, -t i t j = t j t i for 2 ≤ i < j ≤ n with ji > 1, -t 0 t j = t j t 0 for j = 3, . . can be viewed as a subalgebra of index p of the cyclotomic Hecke algebra H m,pr n of type G(l, 1, n): in fact, H m,pr n is a "twisted symmetric algebra" of G over H m,pr p,n (see [5, §5.5.1]). The action of G on Irr(K(q)H m,pr n ) corresponds to the action generated by the cyclic permutation by d-packages on the l-partitions of n:

σ : λ = (λ 0 , . . . , λ d-1 , λ d , . . . , λ 2d-1 , . . . , λ pd-d , . . . , λ pd-1 )

→ σ λ = (λ pd-d , . . . , λ pd-1 , λ 0 , . . . , λ d-1 , . . . , λ pd-2d , . . . , λ pd-d-1 ).

By [7, Proposition 2.5], we have a (m,pr) (λ) = a (m,pr) ( σ λ).

6.3.

In this section, we will use extensively some results known as "Clifford theory". For more details, the reader may refer to [5, §2.3] and [START_REF] Genet | Modular representations of cyclotomic Hecke algebras of type G(r[END_REF]. At the end, we will be able to deduce the existence and the explicit parametrisation of a canonical basic set for H m,pr p,n . The proof below is inspired from [14, Proof of Theorem 3.1]. From now on, we will write H for H m,pr n and H for H m,pr p,n . Let θ : Z[η l ][q ±1 ] → K(η) be a specialisation such that θ(q) = η ∈ C * . As before, one may assume that η is a primitive root of unity of order e > 1.

Let E ∈ Irr(K(q) H). By Clifford theory, there exists V λ ∈ Irr(K(q)H) such that E is a composition factor of Res H H(V λ ). We write E λ for E. Moreover, there is an action of G on Irr(K(q) H) such that, if we denote by Ωλ the orbit of E λ under the action of G, we have

[Res H H(V λ )] = E∈ Ωλ [E].
Let V ∈ Irr(K(q)H). The elements of Ωλ appear as composition factors in Res H H(V ) if and only if V = g V λ for some g ∈ G. In particular, if σ is the map defined in §6.2, we have

[Res H H( σ V λ )] = [Res H H(V λ )].
We deduce that Irr(K(q) H) = {E | E ∈ Ωλ , λ ∈ Π l n }. Now, if we denote by Ω λ the orbit of V λ under the action of G, we have

|Ω λ || Ωλ | = |G| = p. (see [14, Lemma 2.2]). Thus, | Ωλ | = |G λ |, where G λ := {g ∈ G | g λ = λ}. Furthermore,

applying the restriction functor Res H

H does not affect the a-value of simple modules over K(q) (see [START_REF] Chlouveraki | Blocks and families for cyclotomic Hecke algebras[END_REF]Proposition 2.3.15]). Hence, we obtain: [START_REF] Chlouveraki | Schur elements and Basic sets for Cyclotomic Hecke algebras[END_REF] a (m,pr) (λ) = a (m,pr) ( σ λ) = a (m,pr) (E), for all E ∈ Ωλ . Now, to each simple K(η)H-module M , one can attach an a-value as follows:

a (m,pr) (M ) = min{a (m,pr) (λ) | [V λ : M ] = 0}.
Respectively, to each simple K(η) H-module N , one can attach an a-value as follows:

a (m,pr) (N ) = min{a (m,pr) (E) | E ∈ Irr(K(q) H), [E : N ] = 0}.
Let N ∈ Irr(K(η) H). By Clifford theory, there exists M ∈ Irr(K(η)H) such that N is a composition factor of Res H H(M ). We write N M for N . There is an action of G on Irr(K(η) H) such that, if we denote by ωM the orbit of N M under the action of G, we have

[Res H H(M )] = N ∈ω M [N ].
By Theorem 5.10, the algebra H admits a canonical basic set B θ with respect to θ. Thus, there exists λ M ∈ B θ such that the conditions of Theorem 5.10 are satisfied. By [7, Proposition 3.2], we also have σ λ M ∈ B θ . Therefore, there exists σ M ∈ Irr(K(η)H) such that σ λ M = λσ M ∈ B θ . This action of G on Irr(K(η)H) agrees with the action on Irr(K(η) H), that is

[Res H H( σ M )] = [Res H H(M )] = N ∈ω M [N ].
Let L ∈ Irr(K(η)H). The elements of ωM appear as composition factors in Res H H(L) if and only if L = g M for some g ∈ G.

By definition of B θ , we get a (m,pr) (M ) = a (m,pr) (λ M ) = a (m,pr) ( σ λ M ) = a (m,pr) ( σ M ) and [V λ M ] = [M ] + a (m,pr) (L)<a (m,pr) (M )

[V λ M : L][L].
By definition of the a-function and Equation ( 7), we get a (m,pr) (M ) = a (m,pr) (N ), for all N ∈ ωM .

Moreover, if L is a simple K(η)H-module such that [V λ M : L] = 0 and a (m,pr) (L) < a (m,pr) (M ), and N ′ ∈ Irr(K(η) H) is a composition factor of Res H H(L), then a (m,pr) (M ) > a (m,pr) (N ′ ).

We deduce that [N ] + sum of classes of simple modules with a-value strictly less than a (m,pr) (M ) .

Suppose that N M is a composition factor of E λ M . Then σ N M is a composition factor of σ E λ M , and, in general, g N M is a composition factor of g E λ M , for all g ∈ G. This is possible only if

|ω M | = | Ωλ M | = |G λ M |. For g, h ∈ G λ M , we get [ g E λ M : h N M ] =    1, if g = h 0, otherwise.
Hence, we have

[ g E λ M ] = [ g N M ] +
sum of classes of simple modules with a-value strictly less than a (m,pr) ( g N M ) .

Thus, we have proved the following result: In addition, we have that E ∈ Bθ if and only if there exists λ ∈ B θ ⊂ Π l n such that E ∈ Ωλ . Remark 6.5. In this section, we have also shown that the assumptions of [14, Theorem 3.1], which yields the existence of canonical basic sets for cyclotomic Hecke algebras of type G(l, p, n), are satisfied for any choice of H. 6.6. Let us give an example where we will apply Theorem 6.4 in the case where G(l, p, n) = G(3, 3, 2) ∼ = S 3 . 1 Note that we have d = 1, thus we can take m = (0, 0, 0). Let r = 2 and consider the cyclotomic Hecke algebra H m, 6 3,2 of type G(3, 3, 2), with generators t 1 , t 2 and relations t 2 t 1 t 2 = t 1 t 2 t 1 , (t 1q 6 )(t 1 + 1) = (t 2q 6 )(t 2 + 1) = 0.

The algebra H m, 6 3,2 is a subalgebra of index 3 of the cyclotomic Hecke algebra H m,6 2 of type G(3, 1, 2) with generators T 0 , T 1 and relations T 0 T 1 T 0 T 1 = T 1 T 0 T 1 T 0 , T 3 0 = 1, (T 1q 6 )(T 1 + 1) = 0.

1 Of course, there is an easier way to deal with this case, but we simply want to illustrate the use of Theorem 6.4 in a small example.

  λ M )] = [Res H H(M )] +sum of classes of simple modules with a-value strictly less than a (m,pr) (M ) ,

Theorem 6 . 4 .

 64 The algebra H admits a canonical basic set Bθ with respect to any specialisation θ :Z[η l ][q ±1 ] → K(η) such that θ(q) = η ∈ C * , i.e., there exists a set Bθ ⊂ Irr(K(q) H) with | Bθ | = | Irr(K(η) H|such that the following property is satisfied: For any N ∈ Irr(K(η) H), there exists a unique E N ∈ Bθ such that• [E N : N ] = 1 and • [E : N ] = 0 for E ∈ Irr(K(q) H) only if a (m,pr) (E) > a (m,pr) (E N ) or E = E N .

  . , n, -t 0 t 1 t 2 = t 1 t 2 t 0 , -t 2 t 0 t 1 t 2 t 1 t 2 t 1 . . . t 1 t 2 t 1 t 2 t 1 t 2 . . . Let us denote by G the cyclic group of order p. The algebra H m,pr

	p+1 factors	= t 0 p+1 factors	.
	6.2. p,n

• [V λ M : M ] = 1 and • [V λ : M ] = 0 for λ ∈ Π l i n i only if κ m i (λ M ) ⊲ κ m i (λ) or λ = λ M . Proof. For j = 1, 2, . . . , l i , set m i j := s jei j /(klr) and m i := (m i 1 , . . . , m i l i

). By [START_REF] Geck | Irreducible Representations of Hecke algebras at roots of unity, Algebras and Applications[END_REF]Theorem 6.7.2], there exists a set Φ l i n i ⊂ Π l i n i satisfying the property of the proposition except that κ m i is replaced by κ m i . By Equality [START_REF] Chlouveraki | Blocks and families for cyclotomic Hecke algebras[END_REF], we have

It easily follows that κ m i (λ M ) ⊲ κ m i (λ) if and only if κ m i (λ M ) ⊲ κ m i (λ), which yields the desired result. 5.7. We now need an easy combinatorial lemma. In this section, all multisets of rational numbers are ordered so that their elements form decreasing sequences. Moreover, if X and Y are multisets, we will write X ⊔ Y for the multiset consisting of all the elements of X and Y together, so that

Lemma 5.8. Let µ and ν be two multisets of positive rational numbers. Assume that there exist multisets µ 1 , µ 2 , . . . , µ h and ν 1 , ν 2 , . . . , ν h such that

Then µ ν (with the equality holding only when µ i = ν i for all i = 1, . . . , h).

Proof. If h = 1, there is nothing to prove. Suppose that h = 2, and let t ≥ 1. We have 1≤j≤t µ j = 1≤j≤t µ 1 j + 1≤j≤t 2 µ 2 j for some t 1 , t 2 ≥ 1 such that t 1 + t 2 = t, and

and we have

and we can conclude because

Induction yields the result for h > 2.

5.9. We are now in position to prove the main result of this section:

Theorem 5.10. In the setting of §4.3, the algebra H m,r n admits a canonical basic set B θ with respect to any specialisation θ :

In addition, we have that λ ∈ B θ if and only if there exist integers n 1 , . . . , n p ≥ 0 with

First note that, by §5.2, we have

n and M ∈ Irr(K(η)H m,r n ). By Proposition 5.3, there exist integers n 1 , . . . , n p ≥ 0 with

We consider the l-partition λ M ∈ Π l n such that π i (λ M ) = λ M i for all i = 1, . . . , p, where

Following Equation ( 6) and Proposition 5.6, if [V λ : M ] = 0, then, for all i = 1, . . . , p,

By the definition of κ m , we have κ m (λ) = p i=1 κ m i (π i (λ)). By Lemma 5.8, since λ = λ M , we must have κ m (λ M ) ⊲ κ m (λ). The result follows now from Proposition 4.4.

Remark 5.11. If r = 1, then the elements of B θ are the e-Uglov l-partitions of n. (cf. [15, Definition 3.2]). For r > 1, we will refer to the elements of B θ as generalised e-Uglov l-partitions of n. 5.12. Let us give an example, where we calculate the canonical basic set when n = 2, r = 6 and m = (1/2, -1/6, -1/3). Consider the cyclotomic Ariki-Koike algebra H m,r 2 of type G(3, 1, 2), with generators T 0 , T 1 and relations

) be a specialisation such that θ(q) = η 12 (we have e = 12 and k = 1). Then the specialised Ariki-Koike algebra Q(η 12 )H m,r 2 is generated by T 0 and T 1 with relations

where m 1 = (1/2, -1/6) and m 2 = (-1/3). We now have that

is isomorphic to the cyclotomic Ariki-Koike algebra of type G(2, 1, 2) ∼ = B 2 with generators T 0 and T 1 , and relations

) be a specialisation such that θ(q) = η 12 . Then the specialised Hecke algebra Q(η 12 )H m,6 2 is generated by T 0 and T 1 with relations

where

1 is isomorphic to the algebra of the trivial group, and the algebra Q(η 12 )H m j ,6 2 is isomorphic to the cyclotomic Hecke algebra of type G(1, 1, 2) ∼ = S 2 with quadratic relation (T 1 + 1) 2 = 0. Keeping the notation of §5.4 and Proposition 5.6, we have Φ 1 1 (s j ) = {(1)} and Φ 1 2 (s j ) = {(2)}. Therefore, the canonical basic set with respect to θ for H m,6 2 is B θ = {((1), (1), ∅), (∅, (1), (1)), ((1), ∅, (1)), ((2), ∅, ∅), (∅, (2), ∅), (∅, ∅, (2))}. Following Theorem 6.4, the canonical basic set with respect to θ for H m, 6 3,2 is Bθ = {E ((1),(1),∅) , E ((2),∅,∅) }.


Paolo Rosso
email: prosso@dsic.upv.es

Santiago Correa

Davide Buscaldi
email: buscaldi@univ-orleans.fr

Passage Retrieval in Legal Texts

Keywords: Passage retrieval, legal texts, treaties, patents, contracts

Legal texts usually comprise many kinds of texts, such as contracts, patents and treaties. These texts usually include a huge quantity of unstructured information written in natural language. Thanks to automatic analysis and Information Retrieval (IR) techniques, it is possible to filter out information that is not relevant and, therefore, to reduce the amount of documents that users need to browse to find the information they are looking for. In this paper we adapted the JIRS passage retrieval system to work with three kinds of legal texts: treaties, patents and contracts, studying the issues related with the processing of this kind of information. In particular, we studied how a passage retrieval system might be linked up to automated analysis based on logic and algebraic programming for the detection of conflicts in contracts. In our setup, a contract is translated into formal clauses, which are analysed by means of a model checking tool; then, the passage retrieval system is used to extract conflicting sentences from the original contract text.

Introduction

Nowadays, there is an increasing interest in the automatic processing of legal texts, such as contracts, treaties or patents, from both the academic and business sectors. Legal or law informatics [START_REF] Van Koppen | Rationality, Progress and Information in Psychology and Law[END_REF], as well as forensic linguistics 1 , are some of the interdisciplinary fields interested in the automatic processing of these kinds of legal texts [START_REF] Correa | Passage Retrieval and Intellectual Property in Legal Texts[END_REF] with the aim of solving legal cases with the help of a computer-assisted tool, mining relevant information from contracts, or retrieving the relevant prior art of a patent 2 as, for instance, in the research works carried out by Chieze et al. [START_REF] Chieze | An Automatic System for Summarization and Information Extraction of Legal Information[END_REF] and Francesconi et al. [START_REF] Francesconi | Semantic Processing of Legal Texts: Where the Language of Law Meets the Law of Language[END_REF], or in the research work of Sarkar et al. on term burstiness [START_REF] Sarkar | A Bayesian Mixture Model for Term Re-occurrence and Burstiness[END_REF]. Special attention needs also to be paid to legal contracts (e-contracts, social contracts, deontic contracts as well as security policies or protocols) due to the increasing interest in the study of the contract language, contract analysis, reasoning [START_REF] Prisacariu | An Action-Based Logic for Reasoning about Contracts[END_REF] and conflict discovery [START_REF] Fenech | CLAN: A Tool for Contract Analysis and Conflict Discovery[END_REF].

Legal and patent retrieval tracks have been recently introduced in the context of international competitions such as TREC 3 , CLEF 4 , and NTCIR 5 . Patents themselves can be considered legal texts written in a very specific jargon. There is a big interest worldwide in patent analysis and more specifically in patent retrieval and patent mining whose aim is to look for hidden information in order to create technical trend maps from a set of patents and also to search for possible cases of plagiarism of ideas [START_REF] Martin | Plagiarism: Policy Against Cheating or Policy For Learning?[END_REF] (conflict discovery in patents).

The above competitions are commonly considered as the reference for the last developments in Information Retrieval (IR). IR is the task of finding relevant documents given a question 6 (e.g. When was the Lisbon Treaty signed? ) or a query7 (e.g. Anti-lock braking system) which expresses a user's needs. Passage Retrieval (PR) is a specific kind of IR where the task consists in finding those portions (passages) of documents that are relevant. PR helps to filter out the information that is not relevant because it reduces the original document collection to a set of passages in which the user information needs are satisfied.

In this paper, we report on three experiments in which we have employed the Passage Retrieval system JIRS to retrieve relevant passages from three types of legal texts: treaties, patents and contracts. Contracts express potential obligations, permissions and prohibitions of different actors and can be used to protect the interest of the organisations engaged in services exchanged [START_REF] Pace | A Controlled Language for the Specification of Contracts[END_REF]. Due to the potentially dynamic composition of services with different contacts, as well as the combination of service contracts with local contracts, unexpected conflicts could arise. Therefore, there is a need for automatic techniques dedicated to contract analysis in order to make sure that such contracts (i.e., mechanisms that protect enterprises and organisations giving restrictions on service behaviour) are conflict-free, meaning that the contracts will never lead to conflicting or contradictory directives.

In Section 2 we briefly describe the characteristics of passage retrieval and specifically the simple language-independent JIRS system. Section 3 and Section 4 are devoted to the description of how JIRS has been adapted, respectively, for legal text and for patent retrieval tracks. Section 5 illustrates a case study of an airline check-in desk presented in [START_REF] Fenech | Automatic Conflict Detection on Contracts[END_REF], and how we used our passage retrieval system to find conflicting sentences in a given contract. Finally, in Section 6 we draw some conclusions and we discuss further work.

Methodology of the Employed System

Various methods to determine the similarity between passages and a question or a query have been proposed. Among them, Tellex et al. [START_REF] Tellex | Quantitative evaluation of passage retrieval algorithms for question answering[END_REF] consider that the two most representative approaches are those where the similarity depends on: (i) the overlap between the question or the query and the passage terms (i.e., a large overlap means a great likeness); (ii) the density of the question or the query terms in the passage (i.e., a passage is more similar to the question if its terms are narrowly distributed). The comparison of the PR systems used in the TREC8 competition [START_REF] Tellex | Quantitative evaluation of passage retrieval algorithms for question answering[END_REF] shows that the best PR systems are those that are based on density, with the methods of IBM [START_REF] Ittycheriah | IBM's Statistical Question Answering System[END_REF] and SiteQ [START_REF] Lee | SiteQ: Engineering High Performance QA System Using Lexico-Semantic Pattern Matching and Shallow NLP[END_REF] being the most effective ones. The PR systems that participated in the CLEF competition can also be split into these two categories, even if most of them were based on term overlap [START_REF] Bouma | Question Answering with Joost at CLEF[END_REF][START_REF] Roger | Using AliQAn in Monolingual QA@CLEF[END_REF][START_REF] Martínez-González | The MIRACLE Team at the CLEF 2008 Multilingual Question Answering Track[END_REF][START_REF] Strötgen | A Fast Forward Approach to Cross-Lingual Question Answering for English and German[END_REF] rather than density [START_REF] Amaral | Priberam's Question Answering System for Portuguese[END_REF][START_REF] Besançon | The OEDipe System at CLEF-QA[END_REF].

It must be noted that some systems do not fall completely into one of these two categories. Among them the most interesting ones are: (i) the system described by Adriani and Rinawati in [START_REF] Adriani | Finding Answers to Indonesian Questions from English Documents[END_REF] which takes into account not only the density but also the order of appearance of the question or query terms; (ii) the system illustrated by Sutcliffe et al. in [START_REF] Sutcliffe | Cross-Language French-English Question Answering Using the DLT System at CLEF[END_REF] which combines the term overlap with question reformulation; (iii) the system of Tanev et al. [START_REF] Tanev | Exploiting Linguistic Indices and Syntactic Structures for Multilingual Question Answering: ITC-irst at CLEF[END_REF] which calculates the similarity at the syntactical level by using edit distance between trees; (iv) the system of Hartrump [START_REF] Hartrumpf | Extending Knowledge and Deepening Linguistic Processing for the Question Answering System InSicht[END_REF] which transforms both the question and the passage into a semantic representation in order to find their similarity; (v) the system of Costa [START_REF] Costa | 20th Century Esfinge (Sphinx) Solving the Riddles at CLEF[END_REF] which uses logical-syntactical patterns to determine the relevant passages.

JIRS 9 (Java Information Retrieval System) is a passage retrieval system which is based on a density n-gram distance model, where an n-gram is a sequence of n words. For example, if we have the following sequence of words: "anti-lock braking system", we can say that this sequence is a trigram but we can also say that is composed of the "anti-lock" 1-gram and the "braking system" 2-gram. The general architecture of JIRS is shown in Figure 1. The user's query is given to a search engine (e.g. Yahoo) [START_REF] Gómez | Re-ranking of Yahoo snippets with the JIRS Passage Retrieval system[END_REF] that will search a document collection to return snippets in which relevant terms from the question (or the query) occur. The n-gram extraction module will return all the k-grams of size 1 ≤ k ≤ n, where n is the number of terms in the question (or query) q. This process is done for both q and each of the snippets retrieved by the search engine. Once the n-grams are obtained from the question (or query) and the snippets, a comparison is made to calculate a similarity value between them. This similarity value is used to sort the list of passages that will eventually be returned to the user. The similarity between the question (or query) and the retrieved passages is defined in Equation 1. The weighing scheme detailed here corresponds to the base JIRS scheme which has been used throughout our work.

Sim(p, q) = ∀x∈Q h(x, P ) 1 d(x, x max ) n i=1 w i (1)
Where Sim(p, q) is the function that measures the similarity of n-grams sets of the question (or the query) q with respect to the n-grams sets of the passage p. P is the n-gram set of the heaviest passage p (i.e., the one with most weight) whose terms are in the question (or the query); Q is the set of j-grams that are generated from the question q and n is the total number of terms in the question (or the query). There are three special and particular term functions:

• w i , is the weight of the i -th term of the question (or the query) which is determined by:

w i = 1 - log(n i ) 1 + log(N ) (2)
Where n i is the number of sentences in which the term t i occurs and N is the number of sentences in the collection;

• the function h(x, P ) measures the weight of each n-gram and is defined as:

h(x, P j ) = j k=1 w k if x ∈ P j 0 otherwise (3)
Where w k is the weight of the k-th term (see Equation 2) and j is the number of terms that compose the analyzed n-gram; • and the factor

1 d(x,xmax
) that is a distance factor which reduces the weight of the n-grams that are far from the heaviest n-gram. The function d(x, x max ) determines numerically the value of the separation according to the number of words between a n-gram and the heaviest one. That function is defined as show in Equation 4:

d(x, x max ) = 1 + k• ln(1 + L) (4)
Where k is a factor that determines the importance of the distance in the similarity calculation and L is the number of words between a n-gram and the heaviest one (see Equation 3).

To better understand the passage weighing scheme of JIRS, let us suppose we have a collection of documents that refer to legal treaties of the European Union. Given the following question: When was the Lisbon Treaty signed? JIRS PR system returns the two following passages:

1. The Lisbon Treaty was signed on December 13, 2007 2. The anti-smoking treaty was signed last year Figure 2 shows the details of the ranking calculated by JIRS. In order to calculate the Distance Factor of each n-gram we set a k factor equal to 0.3.

Buscaldi et al. [START_REF] Buscaldi | Answering Questions with an n-gram based Passage Retrieval Engine[END_REF] showed that JIRS is usually able to obtain a better answer coverage in the Question Answering task than other traditional PR models based on Vector Space Model, such as Lucene10 . A comparison between these two systems is showed in Figure 3. Answer coverage is calculated as follows: Where Q is the query (question) test set, P the set of passages p retrieved by the system (which size |P | is fixed before the search), and c(q, P ) is the query-by-query coverage calculated as:

ac P (Q) = q∈Q c(q, P ) |Q| (5)
c(q, P ) = 1 if ∃p ∈ P : p is relevant for q 0 elsewhere (6)
In the experiments related to Figure 3, the relevancy criterion consisted in p containing the right answer for question q.

An important difference between the Vector Space Model used in Lucene and the density n-gram distance model used in JIRS is that the density model privileges structure matching over frequency weights: for instance, let us suppose that given the query "anti-lock braking system", the the two retrieved passages are: ". . . braking system consist of disk brakes . . . " and ". . . anti-lock braking system developed by . . . ". A standard system such Lucene would give most weight to the first passage due to the repetition of words with the same stem ("brake"). JIRS would instead give most weight to the more relevant second passage due to the presense of the trigram "anti-lock braking system".

As we illustrated in Figure 1, JIRS makes use of a search engine in order to retrieve the relevant passages which are re-ranked at the end on the basis of its density-distance model. In order to appreciate the improvement that is obtained using the density-distance model on top of a search engine, we illustrate in Figure 4 the answer coverage of JIRS which exceeds by 19% the one obtained with Yahoo [START_REF] Gómez | Re-ranking of Yahoo snippets with the JIRS Passage Retrieval system[END_REF].

Experiment 1: Passage Retrieval in Treaties

Many data sets consisting of legal texts are currently available. In many cases they are composed of parallel texts which are written in several languages. Examples of such kind of data sets are: the Canadian Hansards data set 11 , the Europarl data set 12 and the JRC-ACQUIS data set 13 . In this section we describe the last data set, the way it was employed in the RespubliQA@CLEF-2009 track and our passage retrieval based approach we used for the participation in the competition.

The JRC-ACQUIS data set

The JRC-ACQUIS data set is composed of the total body of European Union (EU) law applicable in the the EU Member States. The collection includes articles written since 1950 and is updated constantly, due to the different languages present in the European Union. The data set is provided in 22 languages: Bulgarian, Czech, Danish, German, Greek, English, Spanish, Estonian, 11 For more information about the Canadian Hansards data set, refer to page: http://www.isi.edu/natural-language/download/hansard/ 243,187,303 Average of aligned documents per language 18,833 Average of links per language pair (average of all language pair) 1,052,759

Table 1: JRC-ACQUIS data set statistics, extracted from: http://wt.jrc.it/lt/Acquis/ Finnish, French, Hungarian, Italian, Lithuanian, Latvian, Maltese, Dutch, Polish, Portuguese, Romanian, Slovak, Slovene and Swedish. Besides, the data set also provides about 23, 000 documents per language, constituting one of the biggest parallel data sets in existence. The diversity of languages, the amount of information and the possibility of free download, make the JRC-ACQUIS data set a major source of data for the study of topics such as machine translation and information retrieval. Some statistics related to the data set can be seen in Table 1.

The CLEF ResPubliQA competition

The ResPubliQA@CLEF-200914 competition addresses the problem of question answering in legal texts. Given a pool of 500 independent natural language questions, each system must return the passage which answers each question from the JRC-ACQUIS collection of EU documentation where both questions and documents are translated and aligned for a subset of languages. An example of a question and a possible answer given by the organizers of the competition is as follows:

Question: In how many languages is the Official Journal of the Community published?

Passage: The Official Journal of the Community shall be published in the four official languages.

Two tasks were proposed by the organizers: monolingual and bilingual. In the monolingual task, questions, target document collection and answers are formulated in the same language, whereas in the bilingual task, questions are formulated in a different language than the target document collection and the corresponding answers. 11 groups participated in the competition with 12 runs submitted in English, 6 in Spanish, 4 in Romanian, 3 in French, 2 in German and 1 in Italian. Our group participated, submitting 5 runs, all of them for monolingual tasks: 1 in English, 2 in Spanish, 1 in French and 1 in Italian [START_REF] Peñas | Overview of respubliqa 2009: Question answering evaluation over european legislation, in: Multilingual Information Access Evaluation I[END_REF].

The systems that participated in the ResPubliQA competition have used different approaches. The best system, which was developed by Rodrigo et al. [START_REF] Rodrigo | Approaching Question Answering by means of Paragraph Validation, in: Multilingual Information Access Evaluation I[END_REF] relied on an IR phase focused on improving QA results, a validation step for removing unpromising paragraphs and a module based on n-grams overlapping for selecting the final answer. The second best system [START_REF] Puscaşu | Developing a Question Answering System for the Romanian-English Track at CLEF 2006[END_REF] was developed on the basis of three main modules: question analysis, mainly concerned with the identification of the semantic type of the entity sought by the question (in addition it also identifies the question focus, the question type and the set of keywords relevant for the question); passage retrieval, employing a conventional IR search engine (in this case Lucene) to select a set of relevant candidate passages from the text collection; and the third module, answer extraction and ranking, where the representation of the question and the representation of the candidate answer-bearing passages are compared and a set of candidate answers is returned, ranked according to the likelihood that hey constitute the correct answer. This estimation is based on three specific answer types: answering questions asking about Named Entities, answering questions looking for generic answers and answering definition questions. The approach of the third best system [START_REF] Ion | A Trainable Multi-factored QA System, in: Multilingual Information Access Evaluation I[END_REF] was implemented as workflow which was built on several web services: question preprocessing, query generation, search engine querying and paragraph ranking. This system is a trainable system that uses a linear combination of paragraph relevance scores to obtain a global relevance (to the question) measure which is used as the sort key. The system was trained on a specific parallel data set, but its functionality is independent of the linguistic register of the training data.

The two measures employed in the ResPubliQA competition [START_REF] Peñas | Overview of respubliqa 2009: Question answering evaluation over european legislation, in: Multilingual Information Access Evaluation I[END_REF] to assess the performance of the systems were:

• Accuracy: the number of right answers respect to the total number of questions:

accuracy = AR N (7)
• and c@1 which rewards those systems capable of identifying wrong answers by not answering some question.

c@1 = 1 N (AR + U nans AR N ) (8)
Where AR: is the number of correctly answered questions U nans: is the number of unanswered questions N : is the total number of questions

Our Passage Retrieval based approach

Our approach consists in the use of the JIRS passage retrieval system, (which is based on redundancy), with the assumption that it is possible to find the answer to a question in a large enough document collection. The retrieved passages are ranked depending on the number, length and position of the question n-grams structures found in the passages. The first part of the process involves the collection of documents indexed by the JIRS system; for this purpose documents in XML format, must be analysed and processed. JIRS uses passages as basic indexing unit (i.e., passages are extracted from the documents). Due to the characteristics in which the body is provided, in each document we take the paragraph included between <p> tags as a passage to index. Therefore, each paragraph is labelled with the name of the document which contains it and its paragraph number. In Figure 5 we illustrate an example of the XML format used in the JRC-ACQUIS data set.

Once the collection is indexed by JIRS, for each question, the system returns a list of passages, according to the JIRS weighting scheme, which probably contain the answer to the question. In Table 2 we show some results obtained in the ResPubliQA competition by our JIRS -based NLEL-MAAT system [START_REF] Correa | Multilingual Information Access Evaluation I[END_REF].

Table 3 shows the results obtained by our JIRS -based system. We participated in 4 monolingual tasks (Task): English-English (en-en), French-French (fr-fr), Italian-Italian (it-it), Spanish-Spanish (es-es). Moreover, in another experiment (es-es2) we used the parallel data set to look for the answer in one of the 4 languages of the monolingual tasks (English, Spanish, Italian and French). As best answer we chose the one retrieved by JIRS with the highest score. On the basis of the identifier of the retrieved passage, the aligned passage in the target language (Spanish) was returned. The architecture of the multilingual JIRS -based system with which we participated in ResPubliQA is illustrated in SIM Q: In which countries can yards and miles be used? 4: c@1 measure obtained by our system, compared to the c@1 obtained by the best system from among the other RespubliQA2009 participants and the official baseline provided by organisers.

Figure 6.

With a low complexity passage retrieval system such as the JIRS -based one we succeeded in obtaining very good results, better than the majority of some resource-depending systems participating in the competition. Proof of this is the best rating in three of the four tasks we participated in (see Table 4 and the official track overview [START_REF] Peñas | Overview of respubliqa 2009: Question answering evaluation over european legislation, in: Multilingual Information Access Evaluation I[END_REF]). The only task in which the NLEL-MAAT system was not ranked as first among participants was the monolingual en-en task. The system was also able to perform better than the baseline (obtained using a standard IR system with tf • idf weighing scheme) in all languages with the exception of French. Thanks to the characteristics of (partial) language independence of JIRS we obtained very good results in all languages. The use of the parallel data set (es-es2 task) allowed us to improve the results of the Spanish monolingual task (es-es). We plan to further investigate the possibility of employing this approach also for the other languages.

Experiment 2: Passage Retrieval in Patents

Before applying for a patent, inventors must ensure, through a search, that the invention meets the novelty requirement and does not conflict with its prior art. A search is performed by patent examiners in order to determine its legitimacy. This is the main application of passage retrieval in patents. In this section we describe the European Patent Office (EPO) data set, the Intellectual Property (IP ) competition and, finally, our PR-based approach.

The European Patent Office data set

The European Patent Office 15 (EPO) data set 16 is composed of patents written since 1978. The whole collection consists of approximately 1.6 million individual patents. EPO patents are written in one of the three official languages (English, German and French) the documents are provided in XML format. Patent documents are structured documents consisting of four major sections:

(i) Bibliographic data (ii) Abstract (iii) Description (iv) Claims
A portion of a text file regarding a patent is shown in Figure 7:

The CLEF Intellectual Property competition

The Intellectual Property IP@CLEF-2009 task is coordinated by Information Retrieval Facility 17 (IRF) and Matrixware 18 and aims to find the prior art of a given set of patents. The basic task is to find the prior art of a set of 500 patents of a data set provided by the organizers. The statistics of this data set are shown in Table 5.

In the IP@CLEF-2009 competition, the best systems employed retrieval models (Kullback Leibler [START_REF] Manning | Introduction to Information Retrieval[END_REF], Okapi [START_REF] Jones | Peeling the Onion: OKAPI system architecture and software design issues[END_REF]) as well as regression models [START_REF] Lopez | Multiple Retrieval Models and Regression Models for Prior Art Search[END_REF][START_REF] José | University of Santiago de Compostela at CLEF-IP09[END_REF][START_REF] Julien Gobeill | Exploring a wide Range of simple Pre and Post Processing Strategies for Patent Searching in CLEF IP[END_REF]. Most of the systems participated in the competition despite the high complexity and obtained poor results [START_REF] Roda | CLEF-IP 2009: retrieval experiments in the Intellectual Property domain, in: Multilingual Information Access Evaluation I[END_REF]. This indicates the difficulty of the IP competition. There were four measures employed in the IP competition to assess the performance of the systems:

17 http://www.ir-facility.org/the irf/ 18 http://www.matrixware.com/

• Precision (P ) is the number of relevant documents retrieved n s over the total number of documents N s returned by the search:

P = n s N s (9)
• Mean Average Precision (MAP ): Precision is a single-value metric based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. MAP emphasizes ranking relevant documents higher. It is the average of precisions computed at the point of each of the relevant documents in the ranked sequence.

• Recall (R) measures the number n s of relevant documents retrieved over the total number of relevant documents N db on the data set:

R = n s N db (10)
• and nDCG measure is defined as:

nDCG = M i (2 r(i) -1) log(1 + i) (11)
where r(i) is the relevance of document in rank position i and M is the normalizing constant chosen in order to have the score always between 0 and 1 [START_REF] Fang | FacFinder: Search for Expertise in Academic Institutions[END_REF][START_REF] Järvelin | Cumulated gain-based evaluation of IR techniques[END_REF].

Our Passage Retrieval based approach

Our hypothesis is that the similarity between a patent candidate and another patent contained in the data set gives clues about the possibility that the latter is part of the prior art of a patent candidate [START_REF] Correa | NLEL-MAAT at CLEF-IP, in: Multilingual Information Access Evaluation I[END_REF] . In order to use JIRS for the IP task, it is necessary to clean the labels belonging to the XML format and filter the most important information of each patent in the data set provided to properly index the collection. In addition, for each patent it is possible to find several versions of it but, because they have an identification number that makes each patent unique, it is possible to eliminate the repeated information. Once we have finished this preprocessing, we obtain a sufficiently small portion of the data set to be indexed by the JIRS PR system. To search for the prior art of a patent, we construct a sequence of words that describe the content of each of the 500 patents to analyse. In order to do so, we decided to consider the title and the abstract to extract the relevant terms, employing the Random Walks summarisation technique [START_REF] Hassan | Random-Walk Term Weighting for Improved Text Classification[END_REF] on the description of each patent. The Random Walks algorithm is inspired by graph theory, where terms are vertices and their co-occurrence within a certain distance (usually 2 words) is represented by an edge between them. The in-degree is used to assign weights to terms, according to its contribution to the context of the document. This summarisation technique is used to extract the most relevant n-grams. In order to illustrate the method, let us consider the patent in Figure 7.

Patent title: Measurement relating to human energy metabolism

After applying the summary technique in the description we obtain the following relevant terms:

Relevant terms: The heart rate

The title and the concatenated information about the relevant terms is given to JIRS as a sequence of words. For the previous example we obtain the following word sequence:

Words sequence: Measurement relating to human energy metabolism, the heart rate Another problem which we faced was the multilingual nature of the competition. As we described in Section 4.1, patents may be submitted in three different languages: English, French and German. Therefore, we opted for using three passage retrieval systems, one for each language. Thus we had to translate each of the 500 patents, using the google translate tool 19 , in order to analyse them in the three languages and then look for the prior art for each patent in each language. The three ranking lists were merged into one in order to obtain the most similar 1,000 patents [START_REF] Correa | NLEL-MAAT at CLEF-IP, in: Multilingual Information Access Evaluation I[END_REF]. The architecture of the multilingual JIRS -based system we participated in the IP competition is illustrated in Figure 8.

Description:

The invention relates method device determining threshold values energy metabolism method testee subjected gradually increasing stress order obtain threshold values energy metabolism In DE-3439238 disclosed conventional heart rate monitor comprising chest-worn pulse transmitter wrist-worn receiver adapted wirelessly receive pulse signals transmitter. . .

In Table 6 we show the results obtained by our JIRS -based system. As previously stated, in general most of the results obtained by the participants were also low (Figure 9), due to the complexity of the IP task. We have to emphasize that with an approach as simple as the one we have proposed, we have obtained results were not too far from the ones obtained by the best systems. From a practical viewpoint, our aim was to apply the simple JIRS -based system in order to filter out information not relevant with respect to the prior art of a patent. This allowed us to sensibly reduce the size of the data set for further investigation, eventually employing a more formal approach.

The poor performance of the proposed approach is partially due to the fact that a certain quantity of data was not used in the various stages of processing: in particular, in the document indexing phase, a lot of proprietary information was not used because of the criterion used to reduce the amount of data needed to represent the document. The criterion consisted in using the text contained in the "title" and "abstract" fields for the generation of the sentence (query) for each input patent. Therefore, a substantial amount of information contained in the remaining fields of patents was lost. A text mining approach applied to these data would have allowed summarization of this information in an effective way in order to produce the query associated to the input patent. We have to remark that the need to reduce the size of the data arose from the performance limitations, as the maximum quantity of textual data that can be processed, of JIRS, and not from the method design.

Another factor responsible for the results was that JIRS is not able to deal with synonyms, because of the n-grams approach explained above. We noticed that different patents describe similar objects using different terms, for instance "stroller" and "buggy" may be used to describe the same baby transport device. A possible solution to this failure may be to employ term expansion or to introduce synonyms into the n-gram generation phase.

Experiment 3: Passage Retrieval and Conflict Detection in Contracts

There are many kinds of documents that an enterprise must deal with: contracts, complaints, manuals, incident reports, technical reports, invoices, news, blogs, etc. Table 7 summarises just some of them taking into account the areas that an enterprise could be interested in: customer service, internal management, R+D or market analysis. Due to the overload of information to be processed by an enterprise on a daily basis, there is a real need to have tools such as passage retrieval systems in order to filter out the information that is not relevant. JIRS PR system, thanks to its simple n-gram approach, is able Interest area

Documentation type

Market analysis

Blogs, news, invoices, etc. Internal management Technical reports, contracts, etc. Customer service Complaints, contracts, suggestions, etc. R+D Articles, technical reports, manuals, etc. to process any document that is written in natural language and to return only the relevant information to the enterprise's needs.

In this section, with the help of an example built on an invented contract between an airline and a ground operations company, we explore the possibility of employing the JIRS passage retrieval system to retrieve from a contract those passages where there is a conflict. To this aim, we used the formal constraint framework introduced by [START_REF] Fenech | Automatic Conflict Detection on Contracts[END_REF]. A contract written in English is translated to a set of Contract Language (CL) clauses. The contract in this form is analysed by a model checker in order to detect conflicts (i.e., obligations and prohibitions to do the same thing or obligations to do contradictory things, etc.). The model checking is carried out by means of the contract analysis tool CLAN20 [START_REF] Fenech | CLAN: A Tool for Contract Analysis and Conflict Discovery[END_REF]. Once a conflict is detected, the tool gives a counter-example explaining where the conflict is. This is done at the logical level; the user has to manually find the clauses in the original raw text which correspond to the detected conflict. Our goal is to link the automated analysis based on logic with the passage retrieval system in order to take the output of CLAN (the CL formula showing the conflict), write the corresponding approximate English sentence and then use the passage retrieval to find the original English text containing the conflicting sentences. It should be noted that clauses are not directly related to natural language sentences, and the size of contracts may be considerably greater than the one of the "toy" contract proposed here, thus justifying the use of an IR system to extract the relevant passages.

In [START_REF] Fenech | Automatic Conflict Detection on Contracts[END_REF] Fenech et al. consider a contract between an airline company and a company managing the ground operations (mainly the check-in process), where the normative specification is given as the following contract:

1. The ground crew is obliged to open the check-in desk and request the passenger manifest two hours before the flight leaves. 2. The airline is obliged to reply to the passenger manifest request made by the ground crew when opening the desk with the passenger manifest. 3. After the check-in desk is opened the check-in crew is obliged to initiate the check-in process with any customer present by checking that the passport details match what is written on the ticket and that the luggage is within the weight limits. Then they are obliged to issue the boarding pass.

4.

If the luggage weighs more than the limit, the crew is obliged to collect payment for the extra weight and issue the boarding pass. 5. The ground crew is prohibited from issuing any boarding cards without inspecting that the details are correct beforehand. 6. The ground crew is prohibited from issuing any boarding cards before opening the check-in desk. 7. The ground crew is obliged to close the check-in desk 20 minutes before the flight is due to leave and not before. 8. After closing check-in, the crew must send the luggage information to the airline. 9. Once the check-in desk is closed, the ground crew is prohibited from issuing any boarding pass or from reopening the check-in desk. 10. If any of the above obligations and prohibitions are violated a fine is to be paid.

We will illustrate the formal conflict analysis process and the way the JIRS passage retrieval system is linked up to a deontic logic based on CL. First of all the airline check-in desk is translated into CL. A generic CL clause has the form [β]C, meaning that if action β is performed, then contract C must be executed. Contracts may be obligations (O), permissions (P ) or prohibitions (F ). The notation O C (α) indicates a contract in which action α must be executed, with C the contract to be taken in case α is not executed. For instance, the reparation clause that corresponds to the penalty in our contract is O(f ine).

The & operator indicates concurrency, and α means "any action except α". The clauses written in natural language that include an implicit universal quantification, that is, statements such as "After the check-in desk is open" need to be interpreted as "At any time, after the check-in is open". This is reflected by the notation ([1 * ]). The clauses of our example contract can be translated as follows.

1

. [1 * ][2hBef ore]O O(f ine) (openCheckIn & requestInfo) 2. [1 * ][openCheckIn & requestInfo]O O(f ine) (replyInf o) 3. [1 * ][openCheckIn][1 * ](O(correctDetails & luggageInLimit)∧ [correctDetails & luggageInLimit]O O(f ine) (boardingCard)) 4. [1 * ][openCheckIn][1 * ][correctDetails & luggageInLimit] O O(f ine) (collectPayment & boardingCard) 5. [1 * ][correctDetails]F O(f ine) (boardingCard) 6. [openCheckIn]F O(f ine) (boardingCard) 7. ([1 * ][20mBef ore]O O(f ine) (closeCheckIn)) ∧ ([20mBef ore * ] F O(f ine) (closeCheckIn)) 8. [1 * ][closeCheckIn]O O(f ine) (sendLuggageInf o) 9. [1 * ][closeCheckIn][1 * ](F O(f ine) (openCheckIn)∧ F O(f ine) (boardingCard))
The conflict discovery algorithm identifies a state in conflict labelled with the obligation to perform action boarding Card and the prohibition of performing action boarding Card together with a trace leading to this state: once the crew opens the check-in desk (clause 3), they are always obliged to issue a boarding pass if the client has the correct details but, they are prohibited from issuing a boarding pass, once the check-in desk is closed (clause 9). Clauses 3 and 9 are in conflict once the check-in desk is closed and a client arrives to the desk with the correct details. Therefore, in order to fix this problem we need to change clause 3: after the check-in desk is opened, the ground crew is obliged to issue the boarding pass as long as the desk has not been closed. CLAN tools returns a trace that identifies the situation in which the check-in desk is closed at the same time as the client provides her correct details:

< openCheckIn, closeCheckIn & correctDetails, O(boardingCard) & F (boardingCard) >
In reality, a check-in desk cannot accept the passport details and close at the same time. In order to resolve this conflict, the two actions need to be mutually exclusive. In order to ensure that 2hBefore and 20mBefore, as well as openCheckIn and closeCheckIn occur in the correct order, we need to make use of path constraints. Therefore, clauses 3 and 4 need to be modified as follows:

• 3 ′ : [1 * ][openCheckIn][closeCheckIn * ][correctDetails & luggageInLimit]O O(f ine) (boardingCard) • 4 ′ : [1 * ][openCheckIn][closeCheckIn * ][correctDetails & luggageOverLimit]O O(f ine) (collectPayment & boardingCard)
In order to find in the contract written in natural language where the sentences containing the conflicts are, the output of CLAN could be translated from CL in natural language as follows:

• 3 ′′ : open check-in close check-in correct details luggage in limit fine boarding card

• 4 ′′ : open check-in close check-in correct details luggage over limit fine collect payment boarding card JIRS is fed with queries 3 ′′ and 4 ′′ , and thanks to its n-gram approach, it is able to automatically retrieve those sentences in the contract where the conflict occurs. JIRS returns a ranking list with the passages being most similar to each query. The obtained results for each query are shown in Table 8. It can be appreciated that the conflict clauses are ranked the top of the list. Although the airline check-in desk is a small case study, often services are frequently composed of different sub-services, each of which comes with its own contract. Therefore, not only it is important to ensure that each simple contract is conflict-free but also that the composition of all contracts has to be also conflict-free. Therefore, in the case of a real scenario, once the conflict has been detected by the CLAN tool, a passage retrieval system such as JIRS may help to automatically retrieve the passages where the conflict occurs that instead should be found manually. Figure 10 shows the architecture of the experiment. We used the output of the conflict-detection tool (CLAN ) to find the conflict clauses in natural language using JIRS.

Conclusions and further work

The automatic analysis of legal texts is a recent development in NLP and IR which consists in mining useful information from such closed domain documents, such as the identification of conflicts in contracts, the existence of a similar patents, or the retrieval of previous cases in order to find out how they have been resolved. In this paper we have described how a passage retrieval system may help in such scenarios. Two case studies of legal tasks have been presented and the JIRS passage retrieval system has been employed in order to retrieve relevant text passages when analysing legal treaties and patents. The described methods were tested in the CLEF framework, for cross-lingual retrieval in the legal domain, and patent retrieval.

This paper also attempts to shorten the gap between the natural language processing and the formal language and methods research communities, by exploring the possibility of employing JIRS for conflict resolution in contracts. Our experiments showed that JIRS, thanks to its n-gram approach, helped in correctly identifying and retrieving the sentences containing conflicts in a given contract. We consider that the combination of the passage retrieval technique with the analysis of CLAN's output opens many possibility for further collaboration between the two research communities. For instance, if CL clauses are translated into a structured English version of a CL formula (and vice versa), and CLAN is used to detect conflicts, JIRS passage retrieval system could help to find the location in the original text of the sentences expressed in the restricted English version.

As future work we aim to apply formal language and methods on a reduced subset of relevant passages previously retrieved by JIRS when analysing legal treaties and patents as well as contracts, claims and other kinds of legal texts.

Figure 1 :

 1 Figure 1: Architecture of JIRS Passage Retrieval system

Figure 2 :

 2 Figure 2: Density N-gram distance example (DF: Distance Factor, STW: Sum of Terms Weight, Sim: Similarity)

Figure 3 :

 3 Figure 3: Comparision of answer coverage obtained with up to 20 passages (1 ≤ |P | ≤ 20), using the CLEF-2006 test set (target document set extracted from news collections): JIRS vs. Lucene

Figure 4 :

 4 Figure 4: Comparision of answer coverage obtained with up to 20 passages (1 ≤ |P | ≤ 20), using CLEF-2006 questions with the web as collection: JIRS vs. Yahoo

Figure 5 :

 5 Figure 5: XML format used in JRC-ACQUIS corpus

  0.83 P: within the Community , distances may be expressed in yards or miles in the United Kingdom or Ireland if those countries so desire 0.54 P: Member States in which vehicle speed is , at the time of adoption of this Directive , measured in miles per hour , shall be permitted to require speedometer equipment fitted to vehicles sold in their countries to be marked both in kilometres per hour and in miles per hour , until such time as their national legislation is amended to require only the use of metric (SI) units of measurement in accordance with the provisions of Council Directive No 71/354/EEC (1) of 18 October 1971 on the approximation of the laws of the Member States relating to units of measurement , as amended by the Treaty of Accession (2)

Figure 7 :

 7 Figure 7: Text passage of a patent

  Given the previous patent, our JIRS -based PR system retrieved as prior art of the patent: Patent number: EP1103216 Title: Method device measuring blood pressure heart rate environment extreme levels noise vibrations Description: A method device measuring systolic diastolic blood pressure heart rate environment comprising extreme levels noise vibrations disclosed Blood pressure signals heart beat detected acoustic sensor patient artery. . .Patent number: EP0785748Title: Method and device for determining threshold values for energy metabolism

Figure 8 :

 8 Figure 8: Architecture of NLEL-MAAT multilingual system (IP competition)

Figure 9 :

 9 Figure 9: Comparative results (Precision @ 100) of the systems participating in the CLEF-IP 2009 competition. Data from the official track overview [3].

Figure 10 :

 10 Figure 10: Architecture of the experiment CLAN -JIRS : conflicting clauses in Contract Language (CL) and in Natural Language (NL)

Table 2 :

 2

	en-en	498	2	286	212	0.57	0.57
	fr-fr	488	11	171	317	0.35	0.35
	es-es	495	5	171	324	0.35	0.35
	it-it	493	7	253	240	0.51	0.51
	es-es2 466	34	218	248	0.44	0.47

Example of relevant passages returned by JIRS ; SIM: Similarity measure according to JIRS weighting scheme; Q: Question formulated by the competition Figure 6: Architecture of NLEL-MAAT multilingual system (ResPubliQA competition) Task Ans. Unans. A.R. A.W. Accuracy c@1

Table 5 :

 5 Sub-collection EPO data set statistics (Patent documents: 1,022,388)

Table 6 :

 6

Results at IP@CLEF-2009 competition; P: Precision, R: Recall, nDCG: normalized Discounted Cumulative Gain, MAP: Mean Average Precision

Table 7 :

 7 Relevant documents for internal analysis in an enterprise

Table 8 :

 8 JIRS ranking of clauses

	query 3"	query4"
	passage weight passage weight
	5	0.25	4	0.35
	4	0.23	5	0.20
	3	0.23	3	0.18
	1	0.19	1	0.16
	7	0.19	7	0.16
	8	0.15	8	0.13
	6	0.14	6	0.12
	9	0.14	9	0.12
	10	0.10	10	0.09
	2	0.06	2	0.05

http://trec-legal.umiacs.umd.edu/

Cross Language Evaluation Forum (http://www.clef-campaign.org).

http://www.ls.info.hiroshima-cu.ac.jp/~nanba/ntcir-8/cfp.html

question: linguistic expression used to make a request for information.

query: a form of questioning, a precise request for information retrieval within information systems.

Text Retrieval Conference (http://trec.nist.gov/).

http://sourceforge.net/projects/jirs/

http://lucene.apache.org/

For more information about the JRC-ACQUIS data set, refer to page: http://langtech.jrc.it/JRC-Acquis.html

For more information about the ResPubliQA@CLEF-2009 competition, refer to page: http://celct.isti.cnr.it/ResPubliQA/

Table3: Results for submitted runs at ResPubliQA@CLEF-2009 competition; Ans.: Answered, Unans.: Unanswered, A.R.: Answered Rigth, A.W.: Answered Wrong, Accuracy: Accuracy measure, c@1: c@1 measure.

http://translate.google.com/

Available from www.cs.um.edu.mt/ svrg/tools/CLTool/

Acknowledgements

We thank the MICINN (Plan I+D+i) TEXT-ENTERPRISE 2.0: (TIN2009-13391-C04-03) research project. The work of the second author has been possible thanks to a scholarship funded by Maat Gknowledge in the framework of the project with the Universidad Politécnica de Valencia Módulo de servicios semánticos de la plataforma G.