Pierre Boullier
email: pierre.boullier@inria.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Multi-Component Tree Insertion Grammars

In this paper we introduce a new mildly context sensitive formalism called Multi-Component Tree Insertion Grammar. This formalism is a generalization of Tree Insertion Grammars in the same sense that Multi-Component Tree Adjoining Grammars is a generalization of Tree Adjoining Grammars. We show that this class of grammatical formalisms is equivalent to Multi-Component Tree Adjoining Grammars, and that it also defines a hierarchy of languages whose supplementary formal power between two increasing levels is more gently delivered than the one given by Multi-Component Tree Adjoining Grammars. We show that Multi-Component Tree Insertion Grammars and simple Range Concatenation Grammars are equivalent and we show how to transform a grammar of one type into an equivalent grammar of the other type. Such a transformation gives a method to build efficient parsers for Multi-Component Tree Insertion Languages.

Introduction

The notion of mild context-sensitivity (MCS) [START_REF] Joshi | In: How much context-sensitivity is necessary for characterizing structural descriptions -Tree Adjoining Grammars[END_REF][START_REF] Weir | Characterizing Mildly Context-Sensitive Grammar Formalisms[END_REF] is an attempt to express the formal power needed to define the syntax of natural languages. However, all incarnations of MCS formalisms are not equivalent. On the one hand, near the bottom of the hierarchy, we find tree adjoining grammars (TAGs) [START_REF] Joshi | An introduction to tree adjoining grammars[END_REF], the most popular mild context-sensitive formalism, and some other weakly equivalent formalisms. On the other hand, near the top of the hierarchy, we find Multi-Component Tree Adjoining Grammars (MCTAGs) which are, in turn and among others, equivalent to Linear Context-Free Rewriting Systems (LCFRSs) [START_REF] Vijay-Shanker | Characterizing structural descriptions produced by various grammatical formalisms[END_REF].

In this paper we introduce a new mild context-sensitive formalism, the multicomponent tree insertion grammar (MCTIG) which plays, w.r.t. tree insertion grammar TIG the same role as MCTAG plays w.r.t. TAG. We know that TIGs are weakly equivalent to context-free grammars (CFGs) but they allow to build (parse) structures that are not possible to build with CFGs. From a practical point of view we know that TIGs, which may be seen as a restriction of TAGs, are of importance since many usual linguistic constructions do not need the power of TAGs. On the other hand there exist linguistic constructions that cannot be expressed with TAGs. Thus MCTAGs have been introduced. These various formalisms named k-MCTAGs form a strict hierarchy which depends upon an integer k. TAGs are 1-MCTAGs and the languages of k-MCTAGs (k-MCTALs) are strictly included into k + 1-MCTALs. However the extra power earned when we use k + 1-MCTAGs instead of k-MCTAGs is too large. For example let L i be the counting language for i (L i = {a n 1 . . . a n i | n ≥ 0}). It is well known that 1-MCTAGs (i.e., TAGs) can define L 1 , L 2 , L 3 and L 4 but not L 5 . If we want to define L 5 we must use 2-MCTAGs. However, doing that we can also define L 6 , L 7 and L 8 . We shall see that the power of k-MCTIGs is more balanced.

On the other hand, though being non MCS, there is a very attractive powerful formalism named Range Concatenation Grammar (RCG). Its power comes from the fact that it exactly covers the class PTIME and its attractivity comes from both theoretical and practical considerations. From a theoretical point of view it possesses many closure properties among which the closure by intersection is the most salient. From a practical point of view there exist very efficient polynomial parse time parsers. For example TAGs and MCTAGs have been transformed into equivalent RCGs [START_REF] Boullier | On TAG parsing[END_REF][START_REF] Boullier | On Multicomponent TAG parsing[END_REF] whose parsers achieved top-of-the-art efficiency [START_REF] Barthlemy | ric de la Clergerie: Guided parsing of range concatenation languages[END_REF].

In this paper we define MCTIGs and study its relationships with both MC-TAGs and RCGs, thus exhibiting a way to produce an efficient MCTIG parser.

Basic notions and notations

Tree Insertion Grammars

We suppose that the reader is familiar with Tree Adjoining Grammars (TAGs), as defined in, e.g., [START_REF] Joshi | An introduction to tree adjoining grammars[END_REF].

Tree Insertion Grammar (TIG) [START_REF] Schabes | Tree insertion grammar: A cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced[END_REF] is a variant of TAG in which the auxiliary tree shapes have a restricted form: wrapping auxiliary trees are prohibited leaving only left and right auxiliary trees. 1 A left auxiliary tree (resp. right auxiliary tree) is an auxiliary tree in which the foot node is the rightmost (resp. leftmost) leaf node and in which adjunction nodes of its spine only select left auxiliary trees (resp. right auxiliary trees) or empty auxiliary trees. It is a well known result [START_REF] Schabes | Tree insertion grammar: A cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced[END_REF] that TIGs are (weakly) equivalent to CFGs and can be parsed in O(n 3 ) time.

Multi-Component Tree Adjoining Grammars

Multi-component TAGs (MCTAGs) are an extension of TAGs which was introduced in [START_REF] Joshi | Tree adjunct grammars[END_REF] and later refined in [START_REF] Joshi | An introduction to tree adjoining grammars[END_REF], in which the adjunction operation involves a set of auxiliary trees instead of a single auxiliary tree. In a MCTAG, the elementary structures, both initial and auxiliary, instead of being two sets of single trees, consist of two finite sets of (ordered) finite tree sets. In MCTAGs, the adjunction operation of an auxiliary tree set is defined as the simultaneous adjunction of each of its component trees and accounts for a single step in the derivation process. This multi-component adjunction (MCA) operation is defined as follows. All the trees of an auxiliary tree set can be adjoined into distinct nodes (addresses) in a single elementary (initial or auxiliary) tree set. If the maximum cardinality of the elementary tree sets is k, we have a k-MCTAG. Of course, if the cardinality of each tree set is one, a 1-MCTAG is a TAG. In [START_REF] Weir | Characterizing Mildly Context-Sensitive Grammar Formalisms[END_REF], the author has shown that the languages defined by MCTAGs are equal to the languages defined by Linear Context-Free Rewriting Systems (LCFRSs) [START_REF] Vijay-Shanker | Characterizing structural descriptions produced by various grammatical formalisms[END_REF].

We assume that (multi-component) substitution operations are disallowed and are replaced by MCA operations. Thus, without loss of generality, we assume that initial tree sets are singletons whose root nodes are all labelled by the start symbol S. Moreover, we assume that adjunction is allowed neither at the root nor at the foot of any tree and that MCAs are mandatory on inside nonterminal nodes which are thus called adjunction nodes.

We can think of two types of locality for MCAs, one type, named tree locality, requires that all trees in an auxiliary tree set adjoin to a unique tree of an elementary tree set; the other type, named set locality, requires that all trees in an auxiliary tree set adjoin to the same elementary tree set, not necessarily to a unique tree and not necessarily to all the trees in this elementary tree set. We choose to consider the set-local interpretation of the term since it is more general than the tree-local version and is the one equivalent to LCFRS. Example 1. For example, let G be a 3-MCTAG in which the set of initial tree sets is I = {{α}} and the set of auxiliary tree sets is A = {β 1 , β 2 , β 3 }, where each tree set β 1 , β 2 and β 3 contains three trees: β 1 = {β 11 , β 12 , β 13 }, β 2 = {β 21 , β 22 , β 23 } and β 3 = {β 31 , β 32 , β 33 }. Its elementary trees are depicted below. 2 We can easily see that the language defined by G is the non-TAL three-copy language {www | w ∈ {a, b} * }. Each simultaneous adjunction of an auxiliary tree set β 1 or β 2 in the elementary tree sets α, β 1 or β 2 produces respectively three related a's or three related b's, while the MCA of (the trees in) β 3 terminates the process. 2 The same denotation is used both for nonterminal nodes and their addresses, while terminal nodes are denoted by their terminal labels or ε. The root node of an elementary tree τ is also denoted by τ . Nonterminal nodes are annotated by their nonterminal labels while terminal nodes have no annotations. In auxiliary trees, foot node labels are marked by an * . For example, the root of tree β11 is the node β11, whose label is A, and the foot node of this tree is β11.2.1 and its label is A * .

α :

       α S α.1 A ε α.2 B ε α.3 C ε        β 1 :          β 11 A

Positive Range Concatenation Grammars

A positive range concatenation grammar (PRCG) G = (N, T, V, P, S) is a 5-tuple in which:

-T and V are disjoint alphabets of terminal symbols and variable symbols respectively.

-N is a non-empty finite set of predicates of fixed arity (also called fan-out).

We write k = arity(A) if the arity of the predicate A is k. A predicate A and its arguments is noted A(α) with a vector notation s.

t. |α| = k and α[j] is its j th argument. An argument is a string in (V ∪ T ) * . -S is a distinguished predicate called the start predicate (or axiom) of arity 1. -P is a finite set of clauses. A clause c is a rewriting rule of the form A 0 (α 0 ) → A 1 (α 1 ) . . . A r (α r ) where r, r ≥ 0 is its rank. By definition c[i] = A i (α i ), 0 ≤ i ≤ r where A i is a predicate together with α i its arguments and c[i][j] is its j th argument X 1 . . . X nij (the X k 's are terminal or variable symbols), while c[i][j][k], 0 ≤ k ≤ n ij is a position.
For a given clause c, each subargument occurrence is denoted by a pair of positions

(c[i][j][k], c[i][j][k ′ ]) with k ≤ k ′ .
Let w = a 1 . . . a n be an input string in T * , each occurrence of a substring a l+1 . . . a u is a pair of positions (w[l], w[u]) s.t. 0 ≤ l ≤ u ≤ n called a range and noted l..u w or l..u when w is implicit. In the range l..u , l is its lower bound while u is its upper bound. If l = u, the range l..u is an empty range, it spans an empty substring. If ρ 1 = l 1 ..u 1 , . . . and ρ m = l m ..u m are ranges, the concatenation of ρ 1 , . . . , ρ m noted ρ 1 . . . ρ m is the range ρ = l..u if and only if we have

u i = l i+1 , 1 ≤ i < m, l = l 1 and u = u m . If c = A 0 (α 0 ) → A 1 (α 1 ) . . . A r (α r ) is a clause, each of its subargument occurrence (c[i][j][k], c[i][j][k ′ ]
) may take a range ρ = l..u as value, in that case, we say that it is instantiated by ρ.

-If the subargument is the empty string (i.e., k = k ′ ), ρ is an empty range.

-If the subargument is a terminal symbol (i.e., k

+ 1 = k ′ and X k ′ ∈ T ), ρ is such that l + 1 = u and a u = X k ′ .
Note that several occurrences of the same terminal symbol may be instantiated by different ranges.

-If the subargument is a variable symbol (i.e., k

+ 1 = k ′ and X k ′ ∈ V ), any occurrence (c[i ′ ][j ′ ][m], c[i ′ ][j ′ ][m ′ ]) of X k ′ is instantiated by ρ.
Thus, each occurrence of the same variable symbol must be instantiated by the same range.

-If the subargument is the string X k+1 . . . X k ′ , ρ is its instantiation if and only if we have ρ = ρ k+1 . . . ρ k ′ in which ρ k+1 , . . . , ρ k ′ are respectively the instantiations of X k+1 , . . . ,

X k ′ .
If in c we replace each argument by a valid instantiation, we get an in-

stantiated clause noted A 0 (ρ 0 ) → A 1 (ρ 1 ) . . . A r (ρ r ) in which each A i (ρ i ) is an instantiated predicate.
A binary relation called derive and noted ⇒ G,w is defined on strings of instantiated predicates. If Γ 1 and Γ 2 are strings of instantiated predicates, we have

Γ 1 A 0 (ρ 0 ) Γ 2 ⇒ G,w Γ 1 A 1 (ρ 1 ) . . . A m (ρ m ) Γ 2 if and only if A 0 (ρ 0 ) → A 1 (ρ 1 ) . . . A m (ρ m ) is an instantiated clause. The (string) language of a PRCG G is the set L(G) = {w | S( 0..|w| w ) + ⇒ G,w
ε}. In other words, an input string w ∈ T * , |w| = n is a sentence of G if and only there exists a complete derivation which starts from S( 0..n ) (the instantiation of the start predicate on the whole input text) and leads to the empty string (of instantiated predicates). The parse forest of w is the CFG whose axiom is S( 0..n ) and whose productions are the instantiated clauses used in all complete derivations. 3We say that the arity of a PRCG is k, and we write k-PRCG, if and only if k is the maximum arity of its predicates (k = max A∈N arity(A)). We say that a k-PRCG is simple, we have a simple k-PRCG, if and only if each of its clause is non-combinatorial: the arguments of its RHS predicates are single variables; non-erasing: each variable which occur in its LHS (resp. RHS) also occurs in its RHS (resp. LHS); linear: there are no variables which occur more than once in its LHS and in its RHS.

The subclass of simple PRCGs is of importance since it is MCS and is the one equivalent to LCFRSs.

We say that a simple 2-PRCG clause of the form

φ → A 1 (X 1 , X ′ 1 ) . . . A p (X p , X ′ p ) B 1 (Y 1 ) . . . B q (Y q )
in which the LHS is either of the form B 0 (α) or A 0 (α 0 , α ′ 0 ) with α = α 0 α ′ 0 is well-balanced if and only if α is a Dyck string w.r.t. the pairs (X i , X ′ i ) which play the role of parentheses, X i is an open parenthese while X ′ i is a closing parenthese. A simple 2-PRCG is well-balanced if its clauses are all well-balanced.

TAGs and MCTAGs vs. Simple PRCGs

In this Section we briefly present the algorithms of [START_REF] Boullier | A generalization of mildly context-sensitive formalisms[END_REF][START_REF] Boullier | On TAG parsing[END_REF] with a slight modification due to our (simplified) vision 4 of TAGs and MCTAGs.

Transforming TAGs into Simple 2-PRCGs

If we consider an auxiliary tree τ and the way it evolves until no more adjunction is possible, we realize that some properties of the final tree are already known on τ . The yield derived by the part of τ to the left (resp. to the right) of its spine are contiguous terminals and the left yield (produced by the left part) lies to the left of the right yield in any input string. Thus, for any elementary tree τ consider its m internal adjunction nodes. We decorate each such node η i with two variables L ηi and R ηi (1 ≤ i ≤ m) which are supposed to capture respectively the left and right yield of the trees that adjoined at η i . Each terminal leaf has a single decoration which is its terminal label. Then, during a top-down left-toright traversal of τ , we collect into a string σ τ called decoration string, all such decorations. If τ is an auxiliary tree, let σ l τ and σ r τ be the part of σ τ gathered before and after the traversal of the root of τ . To each elementary tree τ , we associate a simple 2-PRCG clause constructed as follows:

-its LHS is the predicate S(σ τ ) if τ is an initial S-tree or -its LHS is the predicate A(σ l τ , σ r τ ) if τ is an auxiliary A-tree; -its RHS is ψ 1 . . . ψ i . . . ψ m with ψ i = A i (L ηi , R ηi ) where A i is the label of η i . Example 2. The following TAG S α A ε A β 1 a A A * a A β 2 b A A * b A β 3 A *
where α is its initial tree and β 1 , β 2 and β 3 are its auxiliary trees, defines the language {ww | w ∈ {a, b} * } which is translated into the strongly equivalent simple 2-PRCG5

S(L

A R A ) → A(L A , R A ) A(aL A , aR A ) → A(L A , R A ) A(bL A , bR A ) → A(L A , R A ) A(ε, ε) → ε
As an example, the arguments of the LHS predicate of the second clause have been gathered during the following traversal of

β 1 A a L A A R A A * a a a
It has been shown in [START_REF] Boullier | On TAG parsing[END_REF] how the simple 2-PRCG generated by the previous algorithm can be turned into a normal form which contains at most two variables (the 2-var form) in each argument. 6 Since the standard parser of [START_REF] Boullier | Range Concatenation Grammars[END_REF] has a worst case parse time complexity of O(|G|n k+v ) for a k-RCG G in which v is the maximum number of variables per clause, we reach the classical O(n 6 ) parse time for TAGs.

Transforming Set-Local k-MCTAGs into Simple 2k-PRCGs

The transformation of any set-local k-MCTAG into an equivalent simple 2k-PRCG is based upon a generalization of the algorithm of Section 3.1. The difficulty is to identify the nodes where MCA operations can take place. This will be done in introducing the notion of cover.

Let us consider an elementary tree set γ. For each of its internal nodes η which is a (mandatory) adjunction node, we have to find a tree τ i (in some auxiliary tree set β) which could be adjoined at η. A mapping noted ξ from each adjunction node of γ to an auxiliary tree τ i (we have τ i = ξ(η)) in some auxiliary tree set β is called a cover (of γ). Note that different adjunction nodes of γ may be associated with trees that come from different tree sets. To be a cover, the total function ξ must fullfilled three constraints for each internal node η:

1. if ξ(η) = τ i , the label of η must be the label of the root of τ i (only adjunction of A-trees are allowed on A-nodes); 2. if β is the tree set such that τ i ∈ β, then for each auxiliary tree τ j ∈ β there exists an adjunction node of γ such that ξ(η ′ ) = τ j (this constraint is the consequence of the definition of a MCA operation as the simultaneous adjunction of all its component trees in an auxiliary tree set) and 3. if η 1 and η 2 are two distinct nodes of γ s.t. ξ(η 1 ) = τ and ξ(η 2 ) = τ for some auxiliary tree τ in some auxiliary tree set β and if τ ′ is another tree of β then there exist two distinct nodes η ′ 1 and η ′ 2 of γ s.t. ξ(η ′ 1 ) = τ ′ and ξ(η ′

2 ) = τ ′ (this constraint forces trees in an auxiliary tree set to be adjoined the same number of times during any MCA).

Note that empty auxiliary trees have exactly one cover, namely the empty cover.

Of course, for any given elementary tree set γ its cover is, in the general case, not unique (it may even not exist, and in this case γ can not be used in a derivation). However, for any elementary tree set in any given MCTAG, the number of its covers is bounded. Let cover(γ) be the set of all the covers of the elementary tree set γ.

The generation of RCG clauses proceeds as follow. Each elementary tree set γ will yield |cover(γ)| simple PRCG clauses, one for each cover ξ in cover(γ). All these clauses will share the extraction of the decoration strings of γ. If γ is an initial tree set (a singleton), we associate a single decoration string σ γ , while, if γ is an auxiliary tree set s.t. |γ| = k, we associate a sequence of 2k decoration strings σ l γ.1 , σ r γ.1 , . . . , σ l γ.k , σ r γ.k , the pair σ l γ.h , σ r γ.h in this sequence being respectively the left and right decoration strings of the (auxiliary) tree of rank h in γ. All |cover(γ)| simple PRCG clauses will have the same LHS: S(σ γ ) if γ is an initial tree set or < γ > (σ l 1 , σ r 1 , . . . , σ l k , σ r k ) if γ is an auxiliary tree set. Now consider the RHS's of these clauses. Each ξ in cover(γ) will produce a different RHS. For a given ξ, let β 1 , . . . , β m be the list of auxiliary tree sets that it selects. The RHS of the clause computed for ξ will be of the form

< β 1 > (L 1 1 , R 1 1 . . . , L |β1| 1 , R |β1|
1 ) . . . < β m > (L 1 m , R 1 m . . . , L |βm| m , L |βm| m
) in which the L's and R's are the left and right variables that occur in the LHS decoration strings and that are associated to the adjunction nodes of γ. For each node η in γ let its two variables be L η and R η and let r be the rank of the auxiliary tree ξ(η) in the auxiliary tree set β j . We thus have L η = L

α = L α.1 R α.1 L α.2 R α.2 L α.2 R α.2 . It yields the three clauses S(L α.1 R α.1 L α.2 R α.2 L α.2 R α.2 ) →< β 1 > (L α.1 , R α.1 , L α.2 , R α.2 , L α.2 , R α.2 ) S(L α.1 R α.1 L α.2 R α.2 L α.2 R α.2 ) →< β 2 > (L α.1 , R α.1 , L α.2 , R α.2 , L α.2 , R α.2 ) S(L α.1 R α.1 L α.2 R α.2 L α.2 R α.2 ) →< β 3 > ((L α.1 , R α.1 , L α.2 , R α.2 , L α.2 , R α.2 )
since, for α there are three covers ξ i , 1 ≤ i ≤ 3

ξ i α.1 α.2 α.3 β i1 β i2 β i3
The six decorations strings associated with the auxiliary tree sets β i , 1 ≤ i ≤ 2 have the form σ l β ik = aL β ik .2 and σ r β ik = aR β ik .2 , for 1 ≤ k ≤ 3. They yield the six clauses (1 ≤ i ≤ 2 and 1 ≤ j ≤ 3)

< β i > (aL βi1.2 , R βi1.2 , aL βi2.2 , R βi2.2 , aL βi3.2 , R βi3.2 ) →< β j > (L βi1.2 , R βi1.2 , L βi2.2 , R βi2.2 , L βi3.2 , R βi3.2 )
since for β 1 and β 2 there are the six covers

ξ ij , 1 ≤ i ≤ 2 and1 ≤ j ≤ 3 ξ ij β i1 .2 β i2 .2 β i3 .2 β j1 β j2 β j3
Finally the six trivial decoration strings of β 3 , i.e., σ l β 3k = σ r β 3k = ε for 1 ≤ k ≤ 3 yield the single clause < β 3 > (ε, ε, ε, ε, ε, ε) → ε, since there are no covers for β 3 . 7If we apply to this particular case the general formula of [START_REF] Boullier | Range Concatenation Grammars[END_REF], we get for the generated simple 2k-PRCG G a worst case parse time complexity of O(|G|n 2(k+v) ) where v is the maximum number of adjunction nodes in an elementary tree set.

However, in the TAG case, since the decoration strings are well parenthesized, the generated simple 2-PRCG can be transformed into an equivalent 2-var form in which the dependance w.r.t. to the number of variables (i.e., twice the number of adjunction nodes in an elementary tree) can always be reduced to four, leading to the famous O(n 6 ). Thus, we can wonder whether a similar transformation cannot be performed in the MCTAG case. Unfortunately, the answer is no. This comes from the fact that, in the general case, the decoration strings of elementary tree sets are so completely interlaced that it is not possible to isolate one MCA site, without isolating the others. The search of an optimal solution (in which the arity k may change) is still an open problem.

Simple 2-PRCGs vs. TAGs

We have seen in Section 3.1 how any TAG can be transformed into a strongly equivalent simple 2-PRCG. We will show below, thanks to two examples, that there exist simple 2-PRCGs which cannot be transformed into equivalent TAGs. This shows that the set of all simple 2-PRCLs strictly contains that of TALs.

Example 4. Consider the language

L = {a n 1 b m 1 a n 2 b m 2 | n, m > 0} which may be seen as a transducted copy of a n 1 b m 1 into a n 2 b m 2 .
It is not difficult to see that L is a TAL. But if we add the constraint that both the a's and b's must be related in such a way that they are well parenthesized ((a 1 , a 2 ) and (b 1 , b 2 ) are parenthesized), one can show that this additional constraint cannot be fulfilled by a TAG. However the following simple 2-PRCG in 2-var-form defines L. But we can note that the second clause is not well-balanced.

S(XY

) → S 0 (X, Y ) S 0 (L A L B , R A R B ) → A(L A , R A ) B(L B , R B ) A(a 1 L A , R A a 2 ) → A(L A , R A ) A(ε, ε) → ε B(b 1 L B , R B b 2 ) → B(L B , R B ) B(ε, ε) → ε Example 5.
It can be shown thanks to the pumping lemma for LCFRLs [START_REF] Seki | On multiple context-free grammars[END_REF] that the language

L 2 = {a m b m c n d n e m f m g n h n | m, n > 0} is not a TAL.
However it is defined by the following simple 2-RCL in 2-var form. Once again, we can see that the second clause is not well-balanced.

S(XY )

→ [a m b m c n d n , e m f m g n h n ](X, Y ) [a m b m c n d n , e m f m g n h n ](XY, ZT ) → [a m b m , e m f m ](X, Z) [c n d n , g n h n ](Y, T ) [a m b m , e m f m ](aXb, eZf ) → [a m b m , e m f m ](X, Z) [a m b m , e m f m ](ε, ε) → ε [c n d n , g n h n ](cY d, gT h) → [c n d n , g n h n ](Y, T ) [c n d n , g n h n ](ε, ε) → ε
In other words, simple 2-PRCGs are more powerful than TAGs, both from a weak and strong point of view.

If a simple 2-PRCG can be transformed into an equivalent simple 2-PRCG in 2-var form (not necessarily well-balanced), this PRCG can be parsed in O(n 6 ) time. However, there exist simple 2-PRCGs that cannot be transformed into equivalent 2-var form and thus cannot be parsed in O(n 6 ) (by the standard parsing algorithm).

Example 6. This is for example the case for a clause of the form

E(L A L B L C L D , R C R A R D R B ) → A(L A , R A ) B(L B , R B ) C(L C , R C ) D(L D , R D )
for which there exist no non-empty substrings σ 1 , σ 2 , σ 3 and, σ 4 , such that

σ 1 σ 2 = L A L B L C L D , σ 3 σ 4 = R C R D R A R B
and σ 3 and σ 4 (or σ 4 and σ 3 ) contain all the closing patenthesizes of σ 1 and σ 2 . Thus this clause, of parse time complexity O(n 10 ), cannot be decomposed into more simple clauses of arity 2 with a number of variables less than 8.

Multi-Component TIGs

Definition

As mentioned in Section 2.1, a TIG is a restricted TAG where auxiliary trees must be either empty or left or right (auxiliary TIG tree for short) and adjunctions are disallowed on both root and foot nodes of auxiliary trees.

A Multi-Component TIG (MCTIG), is a MCTAG in which all trees in an auxiliary tree set are auxiliary TIG trees. Of course, if an adjunction node is on the spine of a left (resp. right) auxiliary tree, only a left (resp. right) auxiliary TIG tree or an empty tree can be adjoined at that node.

The maximum number k of auxiliary TIG trees in an auxiliary tree set is the arity of the MCTIG, we thus have a k-MCTIG.

TIGs are equivalent to Simple 1-PRCGs

Of course, a 1-MCTIG is a TIG. We will first see how it is possible to transform a TIG into an equivalent simple 1-PRCG. In fact this transformation is a simplification of the algorithm shown in Section 3.1 wich transforms a TAG into an equivalent PRCG: in all cases an elementary TIG tree gives birth to a single decoration string during its top-down left-to-right traversal. The top-down traversal of the root node produces an empty symbol (since it is either an initial S-tree and there is no auxiliary S-trees or it is an auxiliary tree and adjunctions are not allowed at its root). The left-to-right traversal of leaf nodes labelled by a, a ∈ T ∪ {ε} produces the symbol a. The top-down (resp. bottom-up) traversal of an adjunction node η of label A produces the variable L η (resp. R η ) if there exist left (resp. right) auxiliary A-trees or ε in the other cases.

Each non-empty elementary (initial or auxiliary) tree τ gives birth to a simple 1-PRCG clause c. Let σ be the decoration string of τ . If τ is an initial S-tree, the LHS of c is S(σ), while if τ is a left (resp. right) auxiliary A-tree, the LHS of c is

[A] l (σ) (resp. [A] r (σ)).
If τ is a non-empty elementary tree with |τ | adjunction nodes, the RHS of c has the form φ l η1 φ r η1 . . . φ l η |τ | φ r η |τ | . Let us denote by A i the label of the node

η i . If L ηi (resp. R ηi ) is a variable in σ we have φ l ηi = [A i ] l (L Ai ) (resp. φ r ηi = [A i ] r (R Ai )) or if L ηi (resp. R ηi )
is not (a variable) in σ we have φ l ηi = ε (resp. φ r ηi = ε). If τ is an empty auxiliary A-tree, it gives birth to the pair of clauses [A] l (ε) → ε and [A] r (ε) → ε. 8Example 7. We can find below the elementary trees of a TIG 9 which defines the language {a n b n | n ≥ 0}. To each tree is associated its decoration string and the associated generated clauses. We can note that the absence of right auxiliary tree in that TIG implies that there are no R-variables and thus no [] r -predicates.

S A ε A a A b A * A A * σ = L A σ = aL A b σ = ε S(L A ) → [A] l (L A ) [A] l (aL A b) → [A] l (L A ) [A] l (ε) → ε
In [START_REF] Boullier | A cubic time extension of context-free grammars[END_REF], Boullier has shown that any 1-RCG can always be transformed into an equivalent 1-RCG in 2-var form and can thus be parsed in O(n 3 ) time. This is an other way to show that TIGs can be parsed in O(n 3 ) time.

For space reasons, we will not show here how to perform the reverse conversion from a simple 1-PRCG to a TIG. 10 However, put together, these two conversion algorithms prove that simple 1-PRCGs are equivalent to TIGs and thus to 1-MCTIGs. which defines the lan-

guage a n b n c n d n , n > 0 is transformed into the 2-MCTIG        S A l ε A r ε               A l a A l ε b A * l A r A * r c A r ε d           A l A * l A r A * r   
At this point, we know that any TAG can be transformed into a strongly equivalent simple 2-PRCG, and that simple 2-PRCGs and 2-MCTIGs are two equivalent formalisms. However, we have exhibited an example that shows that there are languages which can be defined by 2-MCTIG (or equivalently by simple 2-PRCGs) but which cannot be defined by TAGs.

2k-MCTIGs are equivalent to Simple 2k-PRCGs

We have already studied in Section 4.3 the case k = 1 which has been distinguished because of the particular importance of TAGs (i.e., 1-MCTAGs). In the general case, the results are very similar.

First of all, h-MCTIGs and simple h-PRCGs are two equivalent formalisms, and the arity h remains the same. On the one hand, to show that a h-MCTIG can be transformed into an equivalent simple h-PRCG is only a trivial generalization of what we have seen in Section 4.3. On the other hand, to show that a simple h-PRCG can be transformed into an equivalent h-MCTIG is also only a trivial generalization of the algorithm we have evoked in Section 4.3.

k-MCTAGs vs. 2k-MCTIGs

It is easy to show that a k-MCTAG can be transformed into an equivalent 2k-MCTIG either indirectly by first using the transformation from MCTAG to simple PRCG of Section 3.2, followed by the transformation from a simple PRCG to a MCTIG mentioned in the same section. However, this transformation can be direct in generalizing the algorithm depicted in Section 4.4.

As for 2-MCTIG (and simple 2-PRCG), the converse is not true: 2k-MCTIGs (and simple 2k-PRCGs) are more powerful than k-MCTAGs.

However, MCTAGs, MCTIGs and simple PRCGs define the same class of languages since, by definition, a h-MCTIG may be seen as a h-MCTAG.

Conclusion: Hierarchies Comparison

Since k-MCTIGs and simple k-PRCGs are equivalent formalism, the hierarchy w.r.t. k of the class of languages defined by k-PRCGs, implies an identical hierarchy on the class of languages defined by k-MCTIGs. In particular let L i be the counting language for i (L i = {a n 1 . . . a n i | n ≥ 0}), the languages L and L 2h can be defined by a h-MCTIG while L 2h+1 , L 2h+2 , . . . cannot. If we consider the class of MCTAGs, this figure slightly differs since the languages L 4h-3 , L 4h-2 , L 4h-1 and L 4h can be defined by a h-MCTAG while L 4h+1 , L 4h+2 , . . . cannot. This example shows that MCTAGs are more coarse-grained than MCTIGs in the sense that a single increment in the value of k delivers more (formal) power than the same increment in MCTIGs. In other words, for these three formalisms, in a k + 1-class there exist languages that cannot be define by the corresponding k-class.

The following diagram summarizes, for each value of k and for each grammar class, in which other grammar class it can be transformed. This diagram shows that for each value of k, k-MCTIGs and simple k-PRCGs are equivalent formalisms. But, with MCTAGs, the relation is not so simple. We know that a h-MCTAG can be transformed into an equivalent simple 2h-PRCG (and hence into an equivalent 2h-MCTIG), but we know that 2h-PRCGs (or 2h-MCTIG) are more powerful than h-MCTAGs. On the other hand we know that a 2h-MCTIG is, by definition a 2h-MCTAG.

We can wonder whether there exists a value l with h < l ≤ 2h such that the two formalisms l-MCTAGs and a 2h-MCTIGs are equivalent? The answer is no. Assume that such a value l exists. In that case we know that the counting language L 4l can be defined by a l-MCTAG but L 4l can only be defined by a k-MCTIG in which k ≥ 2l. This is in contradiction with the fact that h < l.

From an operational point of view, the equivalence results presented in this paper show that we can parse k-MCTIGs with a worse-case parsing complexity of O(|G|n k+v ), where G is the equivalent PRCG and v the maximum number of adjunction nodes in an elementary tree set.

  of auxiliary trees A can be partitioned into three sets L, R and E, respectively the set of left, right and empty trees.

Example 3 .

 3 Let us consider the 3-MCTAG of Example 1. The decoration string σ α of its initial tree set α is σ

In the original definition of TIGs, there exist other differences which are not considered in this article. In particular we disallow simultaneous adjunctions at a single node (they can be performed by the usual adjunction operation), but we allow empty auxiliary trees.

Note that this parse forest has no terminal symbols (its language is the empty string).

No substitution, no adjunction neither at the root nor at the foot node and mandatory adjunction on inside nodes.

[START_REF] Boullier | On TAG parsing[END_REF] Since there is no possible confusion, nodes are addressed directly by their labels.

Such a transformation, which is always possible, is based upon the fact that decoration strings are well-parenthesized (Dyck) string.

We can note that this translation is not optimal in the sense that since β1, β2 and β3 play a symetric role, the three predicates < β1 >, < β2 > and < β3 > could be merged into a single predicate < β123 >.

Note that the first (resp. second) clause will never be used in any derivation if there is no left (resp. right) auxiliary A-trees. Of course, in that case, their generation may

be skipped. 9 Since there is no possible confusion, their nodes are addressed by their labels. 10 The underlying idea is very simple: each clause is transformed into a (left) auxiliary tree: the root A0 is the LHS predicate name; in A0's (unique) argument, each sequence ui ∈ T * corresponds to leave nodes attached to the root, and each variable symbol X k ∈ V correspond to a subtree Before considering the general case of the k-MCTIGs we study, in this Section, the relationships between TAGs, 2-MCTIGs and Simple 2-PRCGs. We first show that 2-MCTIGs and Simple 2-PRCGs are two equivalent formalisms.

2-MCTIGs and Simple 2-PRCGs are equivalent

To start, we show that a 2-MCTIG can be transformed into an equivalent simple 2-PRCG.

Let α be an initial tree set. By definition we have |α| = 1 and τ is a S-tree if α = {τ }. The translation of α gives birth to a S-clause, where S is the unary start predicate. Let β be an auxiliary tree set. By definition we have |β| ≤ 2. The translation of β gives birth to

We will only consider there the more intricate case of a binary auxiliary tree set, leaving the reader to figure out how the other (simpler) cases can be processed. Let β = {τ 1 , τ 2 } be a binary auxiliary tree set with its two decoration strings σ τ1 and σ τ2 , and with ξ one of its cover in cover(β) (see Section 3.2). Let η 1 and η 2 be a pair of adjunction nodes in β and let τ ′ 1 and τ ′ 2 be the two auxiliary TIG trees of some auxiliary tree set β ′ selected by ξ (we have

1 is a left (resp. right) auxiliary tree, we erase the variable R η1 (resp. L η1 ) from the (argument) string (σ τ1 , σ τ2 ). Similarily, if τ ′ 2 is a left (resp. right) auxiliary tree, we erase the variable R η2 (resp. L η2 ) from the string (σ τ1 , σ τ2 ). Let K η1 and K η2 the variables which have thus been kept.

In the RHS of our clause we generate a binary predicate [β ′ ] whose two arguments are either

1 is the second tree in β ′ . Of course, we perform the same operation for all the other nodes of τ 1 and τ 2 . When all the values of ξ are exhausted, we have built a RHS say φ ξ and a new argument string (σ ′ τ1 , σ ′ τ2 ). This yields the clause [β](σ ′ τ1 , σ ′ τ2 ) → φ ξ . Example 8. We can find below the elementary trees of a 2-MCTIG which defines the language {a n b n c n d n | n > 0}. The various ξ's are represented by dashed arrows. Below each tree set we display its decoration string. Since this grammar is a left 2-MCTIG, there are no R-variables. Below each decoration string we show the generated clauses.

We can note that this translation is not optimal since the two predicates [β 1 ] and [β 2 ] play the same role, the can be merged and thus led to a simple 2-PRCG which only contains three clauses.

For space reasons we will not show here how to perform the reverse conversion from a simple 2-PRCG to a 2-MCTIG. 11 However, put together, these two conversion algorithms prove that simple 2-PRCGs are equivalent to 2-MCTIGs.

TAGs vs. 2-MCTIGs

In this section we show that any TAG can be transformed into an equivalent 2-MCTIG, but that the converse is not true.

Of course, to show that a TAG can be transformed into an equivalent 2-MCTIG, we can perform a TAG to PRCG transformation followed by a PRCG to MCTIG transformation. But below we propose a direct transformation, that easily extends to k-MCTAGs and 2k-MCTIGs (see Section 4.6).

Let σ be a TAG tree decoration string. This decoration string is either associated to an initial TAG tree or associated to the left part or the right part of an auxiliary TAG tree. As usual, two variables L η and R η are associated to an adjunction node η and will occur in σ if that node is not on the spine. If η is on the spine of an auxiliary tree β, only L η will occur in the left decoration string of β while only R η will occur in the right decoration string of β. Now, we rewrite σ in changing each occurrence of L η (resp. R η ) by A l (resp. A r ) if A is the label of η.

This process will transform each initial TAG tree (a S-tree) into an initial tree set of cardinality 1 (this single tree is a S-tree) of the 2-MCTIG.

where A is the label of η

It will also transform each auxiliary TAG tree (say an A-tree) into an auxiliary ordered tree set of cardinality 2 (an A l -tree and an A r -tree) of the 2-MCTIG. 11 Informally, it is a generalization of the transformation sketched in footnote 10. For a given clause, we first rename all variables (i.e., all RHS arguments) such that the first argument of predicate Ai is A 1 i and its second argument is A 2 i . Then, if the LHS predicate A0 is unary, it gives birth to an A 1 0 -rooted left auxiliary tree in the same way as in footnote 10; if A0 is binary, it gives birth to an ordered set of two trees rooted by A 1 0 (resp. A 2 0 ), and built similarily, but using only A 1 i s (resp. A 2 i s). This supposes that the 2-PRCG has been first transformed into a strongly equivalent grammar in a so-called LR-form (A 1 i s are only in A0's first argument and A 2 i s only in A0's second argument), which can be proven always possible.

The A l -tree (resp. A r -tree) is built by the part of the auxiliary TAG tree to the left (resp. right) of its spine and by the spine itself.


Srinivas Bangalore

Pierre Boulllier
email: pierre.boullier@inria.fr

Alexis Nasr
email: alexis.nasr@lif.univ-mrs.frrambow@ccls.columbia.edu

Owen Rambow

Benoît Sagot
email: benoit.sagot@inria.fr

MICA: A Probabilistic Dependency Parser Based on Tree Insertion Grammars Application Note

MICA is a dependency parser which returns deep dependency representations, is fast, has state-of-the-art performance, and is freely available.

Overview

This application note presents a freely available parser, MICA (Marseille-INRIA-Columbia-AT&T).1 MICA has several key characteristics that make it appealing to researchers in NLP who need an off-the-shelf parser.

• MICA returns a deep dependency parse, in which dependency is defined in terms of lexical predicate-argument structure, not in terms of surface-syntactic features such as subject-verb agreement. Function words such as auxiliaries and determiners depend on their lexical head, and strongly governed prepositions (such as to for give) are treated as co-heads rather than as syntactic heads in their own right. For example, John is giving books to Mary gets the following analysis (the arc label is on the terminal). The arc labels for the three arguments John, books, and Mary do not change when the sentence is passivized or Mary undergoes dative shift.

• MICA is based on an explicit phrase-structure tree grammar extracted from the Penn Treebank. Therefore, MICA can associate dependency parses with rich linguistic information such as voice, the presence of empty subjects (PRO), wh-movement, and whether a verb heads a relative clause.

• MICA is fast (450 words per second plus 6 seconds initialization on a standard high-end machine on sentences with fewer than 200 words) and has state-of-the-art performance (87.6% unlabeled dependency accuracy, see Section 5).

• MICA consists of two processes: the supertagger, which associates tags representing rich syntactic information with the input word sequence, and the actual parser, which derives the syntactic structure from the n-best chosen supertags. Only the supertagger uses lexical information, the parser only sees the supertag hypotheses.

• MICA returns n-best parses for arbitrary n; parse trees are associated with probabilities. A packed forest can also be returned.

• MICA is freely available2 , easy to install under Linux, and easy to use. (Input is one sentence per line with no special tokenization required.)

There is an enormous amount of related work, and we can mention only the most salient, given space constraints. Our parser is very similar to the work of [START_REF] Shen | Incremental ltag parsing[END_REF]. They do not employ a supertagging step, and we do not restrict our trees to spinal projections. Other parsers using supertagging include the LDA of [START_REF] Bangalore | Supertagging: An approach to almost parsing[END_REF], the CCG-based parser of [START_REF] Clark | Parsing the WSJ using CCG and log-linear models[END_REF], and the constraint-based approach of [START_REF] Wang | A statistical constraint dependency grammar (CDG) parser[END_REF]. Widely used dependency parsers which generate deep dependency representations include Minipar [START_REF] Lin | PRINCIPAR-an efficient, broadcoverage, principle-based parser[END_REF], which uses a declarative grammar, and the Stanford parser [START_REF] Levy | Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation[END_REF], which performs a conversion from a standard phrase-structure parse. All of these systems generate dependency structures which are slightly different from MICA's, so that direct comparison is difficult. For comparison purposes, we therefore use the MALT parser generator [START_REF] Nivre | Memory-based dependency parsing[END_REF], which allows us to train a dependency parser on our own dependency structures. MALT has been among the top performers in the CoNLL dependency parsing competitions.

Supertags and Supertagging

Supertags are elementary trees of a lexicalized tree grammar such as a Tree-Adjoining Grammar (TAG) [START_REF] Aravind | An introduction to Tree Adjoining Grammars[END_REF]. Unlike context-free grammar rules which are single level trees, supertags are multi-level trees which encapsulate both predicateargument structure of the anchor lexeme (by including nodes at which its arguments must substitute) and morpho-syntactic constraints such as subjectverb agreement within the supertag associated with the anchor. There are a number of supertags for each lexeme to account for the different syntactic transformations (relative clause, wh-question, passivization etc.). For example, the verb give will be associated with at least these two trees, which we will call tdi and tdi-dat. (There are also many other trees.

) tdi tdi-dat S NP 0 ↓ VP V♦ NP 1 ↓ PP P to NP 2 ↓ S NP 0 ↓ VP V♦ NP 2 ↓NP 1 ↓
Supertagging is the task of disambiguating among the set of supertags associated with each word in a sentence, given the context of the sentence. In order to arrive at a complete parse, the only step remaining after supertagging is establishing the attachments among the supertags. Hence the result of supertagging is termed as an "almost parse" (Banga-lore and Joshi, 1999).

The set of supertags is derived from the Penn Treebank using the approach of [START_REF] Chen | Towards Efficient Statistical Parsing Using Lexicalized Grammatical Information[END_REF]. This extraction procedure results in a supertag set of 4,727 supertags and about one million words of supertag annotated corpus. We use 950,028 annotated words for training (Sections 02-21) and 46,451 (Section 00) annotated words for testing in our experiments. We estimate the probability of a tag sequence directly as in discriminative classification approaches. In such approaches, the context of the word being supertagged is encoded as features for the classifier. Given the large scale multiclass labeling nature of the supertagging task, we train supertagging models as one-vs-rest binary classification problems. Detailed supertagging experiment results are reported in [START_REF] Bangalore | Factoring global inference by enriching local representations[END_REF] which we summarize here. We use the lexical, part-ofspeech attributes from the left and right context in a 6-word window and the lexical, orthographic (e.g. capitalization, prefix, suffix, digit) and partof-speech attributes of the word being supertagged. Crucially, this set does not use the supertags for the words in the history. Thus during decoding the supertag assignment is done locally and does not need a dynamic programming search. We trained a Maxent model with such features using the labeled data set mentioned above and achieve an error rate of 11.48% on the test set.

Grammars and Models

MICA grammars are extracted in a three steps process. In a first step, a Tree Insertion Grammar (TIG) [START_REF] Schabes | Tree Insertion Grammar[END_REF] is extracted from the treebank, along with a table of counts. This is the grammar that is used for supertagging, as described in Section 2. In a second step, the TIG and the count table are used to build a PCFG. During the last step, the PCFG is "specialized" in order to model more finely some lexico-syntactic phenomena. The second and third steps are discussed in this section.

The extracted TIG is transformed into a PCFG which generates strings of supertags as follows. Initial elementary trees (which are substituted) yield rules whose left hand side is the root category of the elementary tree. Left (respectively right) auxiliary trees (the trees for which the foot node is the left (resp. right) daughter of the root) give birth to rules whose left-hand side is of the form X l (resp. X r ), where X is the root category of the elementary tree. The right hand side of each rule is built during a top down traversal of the corresponding elementary tree. For every node of the tree visited, a new symbol is added to the right hand side of rule, from left to right, as follows:

• The anchor of the elementary tree adds the supertag (i.e., the name of the tree), which is a terminal symbol, to the context-free rule.

• A substitution node in the elementary tree adds its nonterminal symbol to the context-free rule.

• A interior node in the elementary tree at which adjunction may occur adds to the context-free rule the nonterminal symbol X * r or X * l , where X is the node's nonterminal symbol, and l (resp. r) indicates whether it is a left (resp. right) adjunction. Each interior node is visited twice, the first time from the left, and then from the right. A set of non-lexicalized rules (i.e., rules that do not generate a terminal symbol) allow us to generate zero or more trees anchored by X l from the symbol X * l . No adjunction, the first adjunction, and the second adjunction are modeled explicitly in the grammar and the associated probabilistic model, while the third and all subsequent adjunctions are modeled together.

This conversion method is basically the same as that presented in [START_REF] Schabes | Tree Insertion Grammar[END_REF], except that our PCFG models multiple adjunctions at the same node by positions (a concern [START_REF] Schabes | Tree Insertion Grammar[END_REF] do not share, of course). Our PCFG construction differs from that of [START_REF] Hwa | Learning Probabilistic Lexicalized Grammars for Natural Language Processing[END_REF] in that she does not allow multiple adjunction at one node [START_REF] Schabes | An alternative conception of tree-adjoining derivation[END_REF]) (which we do since we are interested in the derivation structure as a representation of linguistic dependency). For more information about the positional model of adjunction and a discussion of an alternate model, the "bigram model", see [START_REF] Nasr | Parsing with lexicalized probabilistic recursive transition networks[END_REF].

Tree tdi from Section 2 gives rise to the following rule (where tdi and tCO are terminal symbols and the rest are nonterminals):

S → S * l NP VP * l V * l tdi V * r NP PP * l P * l tCO P * r NP PP * r VP * r S * r
The probabilities of the PCFG rules are estimated using maximum likelihood. The probabilistic model refers only to supertag names, not to words. In the basic model, the probability of the adjunction or sub-stitution of an elementary tree (the daughter) in another elementary tree (the mother) only depends on the nonterminal, and does not depend on the mother nor on the node on which the attachment is performed in the mother elementary tree. It is well known that such a dependency is important for an adequate probabilistic modelling of syntax. In order to introduce such a dependency, we condition an attachment on the mother and on the node on which the attachment is performed, an operation that we call mother specialization. Mother specialization is performed by adding to all nonterminals the name of the mother and the address of a node. The specialization of a grammar increase vastly the number of symbols and rules and provoke severe data sparseness problems, this is why only a subset of the symbols are specialized.

Parser

SYNTAX [START_REF] Boullier | Le système SYNTAX TM -manuel d'utilisation et de mise en oeuvre sous UNIX TM[END_REF]) is a system used to generate lexical and syntactic analyzers (parsers) (both deterministic and non-deterministic) for all kind of context-free grammars (CFGs) as well as some classes of contextual grammars. It has been under development at INRIA for several decades. SYNTAX handles most classes of deterministic (unambiguous) grammars (LR, LALR, RLR) as well as general context-free grammars. The non-deterministic features include, among others, an Earley-like parser generator used for natural language processing [START_REF] Boullier | Guided Earley parsing[END_REF].

Like most SYNTAX Earley-like parsers, the architecture of MICA's PCFG-based parser is the following:

• The Earley-like parser proper computes a shared parse forest that represents in a factorized (polynomial) way all possible parse trees according to the underlying (non-probabilistic) CFG that represents the TIG;

• Filtering and/or decoration modules are applied on the shared parse forest; in MICA's case, an nbest module is applied, followed by a dependency extractor that relies on the TIG structure of the CFG.

The Earley-like parser relies on Earley's algorithm [START_REF] Earley | An efficient context-free parsing algorithm[END_REF]. However, several optimizations have been applied, including guiding techniques [START_REF] Boullier | Guided Earley parsing[END_REF], extensive static (offline) computations over the grammar, and efficient data structures. Moreover, Earley's algorithm has been extended so as to handle input DAGs (and not only sequences of forms). A particular effort has been made to handle huge grammars (over 1 million symbol occurrences in the grammar), thanks to advanced dynamic lexicalization techniques [START_REF] Boullier | Are very large grammars computationnaly tractable?[END_REF]. The resulting efficiency is satisfying: with standard ambiguous NLP grammars, huge shared parse forest (over 10 10 trees) are often generated in a few dozens of milliseconds.

Within MICA, the first module that is applied on top of the shared parse forest is SYNTAX's n-best module. This module adapts and implements the algorithm of [START_REF] Huang | Better k-best parsing[END_REF] for efficient n-best trees extraction from a shared parse forest. In practice, and within the current version of MICA, this module is usually used with n = 1, which identifies the optimal tree w.r.t. the probabilistic model embedded in the original PCFG; other values can also be used. Once the n-best trees have been extracted, the dependency extractor module transforms each of these trees into a dependency tree, by exploiting the fact that the CFG used for parsing has been built from a TIG.

Evaluation

We compare MICA to the MALT parser. Both parsers are trained on sections 02-21 of our dependency version of the WSJ PennTreebank, and tested on Section 00, not counting true punctuation. "Predicted" refers to tags (PTB-tagset POS and supertags) predicted by our taggers; "Gold" refers to the gold POS and supertags. We tested MALT using only POS tags (MALT-POS), and POS tags as well as 1-best supertags (MALT-all). We provide unlabeled ("Un") and labeled ("Lb") dependency accuracy (%). As we can see, the predicted supertags do not help MALT. MALT is significantly slower than MICA, running at about 30 words a second (MICA: 450 words a second).

MICA MALT-POS MALT-all Pred Gold Pred Gold Pred Gold Lb 85.8 97.3 86.9 87.4 86.8 96.9 Un 87.6 97.6 88.9 89.3 88.5 97.2

We would like to thank Ryan Roth for contributing the MALT data.

http://www1.ccls.columbia.edu/˜rambow/mica.html


Francesco Boccardo
email: fboccardo@unige.it.

Pamela Guglielmini

Andrea Parodi

Alessandra Rubagotti

Prof Francesco Boccardo

Chemotherapy versus Tamoxifen versus Chemotherapy plus Tamoxifen in Node-positive , Estrogen Receptorpositive breast cancer patients. Very late results of the "Gruppo di Ricerca per la Chemio-Ormonoterapia Adiuvante (GROCTA)" 01-Trial in early breast cancer

Keywords: early breast cancer, chemotherapy, Tamoxifen, chemotherapy plus Tamoxifen

    Chemotherapy versus tamoxifen versus chemotherapy plus tamoxifen in node-positive, oestrogen receptor-positive breast cancer patients. Very late results of the 'gruppo di ricerca per la chemio-ormonoterapia adiuvante (GROCTA)' 01-Trial in early breast cancer

Introduction

The combination of chemotherapy (CT) together with Tamoxifen (T ), or aromatase inhibitors in post menopause, is the present paradigm to manage node-positive, ER-positive early breast cancer patients [START_REF]NCCN practice guidelines in oncology[END_REF], though there is increasing evidence that endocrine manipulations alone might possibly represent an appropriate treatment for selected groups of these women [START_REF] Thürlimann | Is chemotherapy necessary for premenopausal women with lower-risk node-positive, endocrine responsive breast cancer? 10-year update of International Breast Cancer Study Group Trial 11-93[END_REF][START_REF] Pagani | Is adjuvant chemotherapy of benefit for postmenopausal women who receive endocrine treatment for highly endocrine-responsive, node-positive breast cancer? International Breast Cancer Study Group Trials VII and 12-93[END_REF][START_REF] Albain | Adjuvant chemotherapy and timing of tamoxifen in postmenopausal patients with endocrine-responsive, node-positive breast cancer: a phase 3, open-label, randomised controlled trial[END_REF].

Several individual trials and large meta-analysis have contributed to the building-up of the present state of art [START_REF] Fisher | Postoperative chemotherapy and tamoxifen compared with tamoxifen alone in the treatment of positive-node breast cancer patients aged 50 years and older with tumors responsive to tamoxifen: results from the National Surgical Adjuvant Breast and Bowel Project B-16 tral[END_REF][START_REF] Boccardo | Chemotherapy versus tamoxifen versus chemotherapy plus tamoxifen in node-positive, estrogen receptor-positive breast cancer patients: results of a multicentric Italian study[END_REF][START_REF] Rivkin | Adjuvant CMFVP versus tamoxifen versus concurrent CMFVP and tamoxifen for postmenopausal, node-positive, and estrogen receptor-positive breast cancer patients: a Southwest Oncology Group study[END_REF][START_REF]Effectiveness of adjuvant chemotherapy in combination with tamoxifen for node-positive postmenopausal breast cancer patients[END_REF][START_REF] Pritchard | Randomized trial of cyclophosphamide, methotrexate, and fluorouracil chemotherapy added to tamoxifen as adjuvant therapy in postmenopausal women with nodepositive ,estrogen and/or progesterone receptor-positive breast cancer: a report of the National Cancer Institute of Canada Clinical Trials Group[END_REF][START_REF]Tamoxifen after adjuvant chemotherapy for premenopausal women with lymph node-positive breast cancer: International Breast Cancer Study Group Trial 13-93[END_REF][START_REF] Gelber | Adjuvant chemotherapy plus tamoxifen compared with tamoxifen alone for postmenopausal breast cancer : meta-analysis of quality adjusted survival[END_REF][START_REF]Early Breast Cancer Trialist's Group (2005) Effects of chemotherapy and hormonal therapy for early breast cancer on recurrence and 15-years survival: an overview on the randomised trials[END_REF].

The GROCTA 01-Trial is one of the trials which concurred to this task. In fact, the original trial aim was to investigate whether in ER-positive women, T might represent a valuable alternative to CT (the standard at the time the trial was designed) and whether the co-administration of the two would provide additional benefits. Herein, we report the 25-year results of our trial with two major aims: 1) to show the long-term outcomes, both overall and in pre-defined groups, in order to evaluate if early benefits achieved by CTT persisted, also after such a prolonged follow-up time; and-2) to show treatment outcomes according to quantitative ER or PgR levels in order to assess whether it could be possible to define, though on a retrospective basis, the preferable therapeutic choice according to tumor-receptor concentrations.

Methods

Patients and procedures

The GROCTA 01 Trial was a phase 3, open-label, parallel-group randomised controlled trial. Details about study design, assigned treatments and main results have been previously published [START_REF] Boccardo | Chemotherapy versus tamoxifen versus chemotherapy plus tamoxifen in node-positive, estrogen receptor-positive breast cancer patients: results of a multicentric Italian study[END_REF][START_REF] Boccardo | Chemotherapy versus tamoxifen versus chemotherapy plus tamoxifen in node-positive, oestrogen-receptor positive breast cancer patients. An update at 7 years of the 1st GROCTA (Breast Cancer Adjuvant Chemo-Hormone Therapy Cooperative Group) trial[END_REF]. Five hundred and four, 35-65 year old patients with node-positive, ER-positive tumors and no evidence of distant metastases were recruited. Patients were well-balanced according to median age at entry, menopausal status, treatment of primary (either radical mastectomy or segmental mastectomy followed by breast irradiation), tumor size and number of involved nodes. Within 6 weeks from mastectomy, patients were randomly allocated to ( according to a 1:1:1 ratio), and administered one of the three following treatments: (1) T: 10 mg orally three times per day for 5 years or until disease relapse; [START_REF] Thürlimann | Is chemotherapy necessary for premenopausal women with lower-risk node-positive, endocrine responsive breast cancer? 10-year update of International Breast Cancer Study Group Trial 11-93[END_REF] combination chemotherapy (CT) with the following regimens: cyclophosphamide 500 mg/m 2 plus methotrexate 40 mg/m 2 and fluorouracil 600 mg/m 2 (CMF) for a total of 6 courses, followed by epirubicin 75 mg/m 2 for another 4 courses. All drugs were given intravenously (IV) every 3 weeks. In the case of myelotoxicity occurring, drugs dosages were not reduced but treatment restart was usually delayed for 1 or 2 weeks until recovery; or-(3) a combination of both treatments (CTT) according to the same dosages and schedules.

Patients were informed about the experimental nature of this trial which had been approved by the Human Investigations Committee of the National Cancer Research Institute of Genoa, Italy, in line with Italian l Legislation of that time.

Hormonal receptor assay

Tumor-ER concentration was measured using the standard dextran-coated charcoal technique and a cut-off value equal to 10 cytosol fmol/mg of protein was arbitrarily chosen to define the positivity of the assay and to select the patients who were suitable for recruiting into the trial. PgR assay was not mandatory, though it was performed almost in all patients according to the same technique. No entry restrictions were planned on the basis of PgR concentration.

Trial end-points

Disease-free survival (DFS), -defined as the time from randomization to local-regional recurrence, recurrence in the omo-lateral breast, distant metastases and contra lateral breast cancer, as well as overall survival (OS), defined as the time from randomization to any death, were the major trial end-points.

Follow-up studies and data collection

Patients were clinically examined every 3 months for the first 3 years, then every 4 months until the fifth year. A clinical check-up every 6 months was planned thereafter for a further 5 years. During the first five years, blood counts were repeated every 3 months, chest x-rays every 6 months and a yearly bone scan A mammography was also repeated every year. Chest tomography, liver scan and/or ultrasonography and all other investigations were carried out whenever deemed necessary by the patient's physician. Beyond the 10 th year, follow-up was continued at the discretion of local investigators or the patients' requirements, though commonly a mono-or bilateral mammogram was obtained on a yearly basis.

For the purposes of the present analysis, information about the patients' status was obtained from consulting the flow charts of the women still being followed up. The vital status of women who discontinued their attendance to the outpatients clinics for more than one year or who had not been able to have a follow-up in the more recent years, was checked directly by phone call or by consulting local tumour registries or the registry office of a patient's place of residence.

It was possible to update DFS data for 75% of patients and S data for 95% of them.

Whenever possible, causes of death were recorded in detail. However, the cause of death was unknown for 45 patients.

In these cases, we arbitrarily choose to include the deaths occurring after documented disease-relapse among breast cancer-related deaths while all other lethal events were defined as breast cancer-unrelated.

All data were collected through appropriate CRFs and centralized at the Clinical Trials Unit of the Coordinating Center.

Sample size calculation

On the basis of literature data available at the time the study was designed, a 5-year disease recurrence rate of 40-50% was calculated for the patients assigned to CT. Because it was expected that the addition of Tamoxifen to chemotherapy would reduce this rate by about 20%, it was estimated that for an alpha error =5% and a beta error =20%, 100 patients per arm would provide the trial with an adequate statistical power to detect the superiority of CTT over CT under previous conditions. Due to it not being possible to reliably predict the outcome of T alone (as findings with T monotherapy available at that time were very preliminary and had been obtained from a mixed population of ERpositive and ER-negative patients), it was arbitrarily deemed that a comparable number of patients (i.e. 100) would be adequate to show non-inferiority of T, in respect to CT alone. However, to be prudent, predicted recruitment was augmented by 50% for each arm.

Statistical analysis

DFS and S curves were constructed using the Kaplan-Meir method and treatment effect comparisons were obtained through the log-rank test [START_REF] Kaplan | Non parametric estimation from incomplete observation[END_REF]. Cox proportional hazards regression models [START_REF] Cox | Regression model and life tables (1972)[END_REF] were used to check for prognostic features, to estimate Hazard Ratios (HRs) and 95% confidence intervals (CIs) for treatment comparisons, as well as to test for interaction between variables and treatment effects. Menopausal status at trial entry, tumor (t) size, hormone receptor levels and the number of involved nodes were included in the models. Hazard Rate curves for time to progression or death were smoothed by use of an Epanechinikov kernel with optimum bandwidth chosen by cross validation (STATA 9.0 sts graph command) [START_REF] Bonetti | A graphical method to assess treatment-covariate interactions using the Cox model on subsets of the data[END_REF]. Cumulative-incidence estimates for breast cancer-related and breast cancer-unrelated deaths were performed to check for competing risks. The difference between cumulative incidence curves in the presence of competing risks was tested using Fine and Gray's test [START_REF] Jones | Kernel smoothing[END_REF].

Interactions between treatments and ER or PgR median levels (in fmol/mg of proteins) were studied by means of the non-parametric STEPP (Sub-population Treatment Effect Pattern Plot) methodology.

For this STEPP analysis, each sub-population contained approximately 100 patients and each subsequent subpopulation was formed by moving from left to right, dropping approximately 5 patients with the lowest values of ER or PgR and adding approximately 5 patients with the next higher values of ER or PgR (SAS 9.2). Treatment effects estimated within each ER or PgR sub-group level were measured in terms of HRs obtained from Cox models [START_REF] Gray | A class of k-sample tests for comparing the cumulative incidence of a competing risk[END_REF].

All probability values were obtained from two-sided tests. All statistical tests were carried-out using SPSS package (version 18.0), SAS (version 9.2), R(version 2.9.2) and STATASE10.

Results

Trial recruitment started on November 1, 1983 and was terminated on June 30,1987, having largely achieved the predicted size. In total, 510 patients were entered into the study. Six patients were excluded from the trial because they were entered by a Center that was withdrawn due to it not providing any additional patient information after randomization.

All the remaining 504 randomized patients (CT=165; T=168 ; CTT 171) have been included into the analysis for the intention to treat method. The main characteristics of these patients are summarized in Table 1.

At a median follow-up time of 21 years (range: 0.5-26 years), -overall-, 316 patients developed a well-documented disease-related event and 352 died. Fig. 1 and2 show DFS and S curves in all patients and in each menopausal subgroup. Even after such a long follow-up time, both T and CTT were confirmed to yield significantly better DFS results.

However, the differences in respect to CT alone were more evident in postmenopausal women. In fact, there were no major differences between groups in pre-menopause. Comparably, T and CTT fared better than CT alone also relative to OS, while again no significant differences emerged between the two in this regard. The smoothed hazard estimates (Fig. 3) show, in addition, that the advantage favouring T, either alone or combined with CT, over CT alone, was quite exclusively confined to the first 6-7 years both in terms of DFS and of OS. No significant differences in the hazards of disease-progression or death were evident from Year 11 to Year 25.

CTT also confirmed to yield better DFS results than T alone, especially during the first 10-12 years and especially in post-menopausal women. However, there was no statistically significant difference between the two. Comparably, there was also no statistically significant difference between the two relative to OS. In fact, no difference at all between CTT and CT, even at 25 years of follow-up, was evident in menopausal women (Fig 2c). .Noteworthy is the fact that the S curves of the patients assigned to T or CTT crossed over between Year 10 and Year 12. In order to better investigate S curve cross-overs, competing risk analysis was performed according to causes of death as previously defined (Fig. 4). It is also worth noting that both cancer-related and cancer-unrelated deaths increased overtime. However, while there was no difference in breast cancer-unrelated mortality within the groups, breast cancer-related mortality risk was significantly higher for the patients initially assigned to CT and maintained so, even long term.

Finally, there was no statistically significant difference in treatment interactions according to the number of involved nodes relative either to DFS or to OS (data not shown).

It should be noted that all outcome results provided have been adjusted for menopausal status at entry (pre vs. post), the number of involved nodes (1-3 vs. > 3), t size (< 2cm vs. >2 cm) and median PgR level (<=55 vs. >55 fmol/mg). As shown in Table 2, all previous variables and assigned treatment were statistically significant predictors, both for the DFS (all variables except menopausal status) or for the OS (all variables) of the whole cohort of patients. In contrast to PgR levels, which were prognostic even when the positivity threshold was arbitrarily fixed at a value of 10 fmol/mg (similarly to ER), the ER levels were not prognostic at all, regardless of the cut-off level employed.

As previously described, non-parametric STEPP analysis was used to better define the putative value of ER or PgR quantitative levels in selecting the patients who might derive the greatest benefit from combining CT together T. As shown in Fig. 5a, which shows the STEPP data relative to DFS, the addition of CT to T appeared to benefit the patients with the lowest and the highest ER values, whilst providing no sustained benefit in the patients with intermediate values (between 40 and 100 fmol/mg). However, differences between treatments were not statistically significant at any point, except for the sub-group of patients with a median ER value equal to 172 fmol/mg (p<0.04). The situation was somewhat different relative to OS (Fig. 5b). In fact, the addition of CT to T appeared to produce a slight benefit only in women with lower ER or PgR values, while it did not show to produce any benefit at all in the women with ER or PgR values above 50-60 fmol/mg, though again differences were not statistically significant.

Discussion

Compared to present standards, our study has several limitations which result in the necessity of using caution before transferring the findings of the present analysis to today's clinical practice. Firstly, the study is to be considered undersized. We can say that 500 patients were a respectable number in 1983 when the trial was open to recruitment but, nowadays, this number qualifies the trial as a small one in respect to present day standards, though the predicted recruitment was largely achieved. The small size, in fact, renders the trial unpowered in respect to sub-group analysis.

An additional objection might be that the CT regimen used by us is not likely to completely fit the canons of modern chemotherapy, even though it included an anthracycline. The choice to deliver T concurrently with CT might also be questionable according to present recommendations which suggest the use of T at the completion of CT [START_REF]NCCN practice guidelines in oncology[END_REF]. However, this issue is still controversial, especially in respect to pre-menopausal women, and there is no definite proof as yet that sequencing CT with T might be more appropriate than giving the two concurrently [START_REF] Pritchard | Combining endocrine agents with chemotherapy: which patients and what sequence?[END_REF][START_REF] Pico | Epirubicin-cyclophosphamide adjuvant chemotherapy plus tamoxifen administered concurrently versus sequentially: randomized phase III trial in postmenopausal node-positive breast cancer patients. A GEICAM 9401 study[END_REF]. In spite of its limitations, our trial has the strength of a very long follow-up and of adopting a "modern" design based on the use of an appropriate T scheduling (5 years) and of ER positivity as a criterion to prospectively select the patients suitable for the comparisons on study. This long-term analysis clearly shows that the significant advantage of T over CT persisted throughout the years.

However, the magnitude of the effect differed in the two menopausal sub-groups. In fact, there was no significant difference either in terms of DFS or of OS between CT and T among pre-menopausal women. Findings were different in post-menopausal women and, in fact, the patients assigned to T showed a huge advantage over those assigned to CT, which, once again, maintained itself over-time, up to the 25 th year, thus definitively confirming that endocrine therapy, namely T, should represent the mainstay to manage ER-positive post-menopausal women, regardless of the severity of nodal involvement. Moreover, the analysis of smoothed hazard estimates clearly indicates that the benefit achieved by T and CT, respectively, differ mainly during the first 6-7 years with, the risks maintaining the same degree in size thereafter, up to Year 25. There is fairly clear evidence now that ER-positive tumors might be less sensitive to adjuvant CT, while they are obviously expected to respond very well to endocrine manipulations [START_REF]Early Breast Cancer Trialist's Group (2005) Effects of chemotherapy and hormonal therapy for early breast cancer on recurrence and 15-years survival: an overview on the randomised trials[END_REF][START_REF] Goldhirsch | Thresholds for therapies: highlights of the St Gallen International Expert Consensus on the primary therapy of early breast cancer 2009[END_REF]. Therefore, in spite of the well-documented carry-over effect both of T and of CT [START_REF]Early Breast Cancer Trialist's Group (2005) Effects of chemotherapy and hormonal therapy for early breast cancer on recurrence and 15-years survival: an overview on the randomised trials[END_REF], which is also clearly demonstrated by our own present findings, it appears that the different chemo-and endocrine sensitivity of E-positive women might play a more relevant role in determining early, rather than late, outcomes. Given that T is not inferior to CT, rather it comes out as the favourable "winner" over CT from pair wise comparisons, even after such a long follow-up time, the question remains as to whether the addition of CT was able to further improve the results and whether the benefit observed is so relevant to identify the combination as the advisable standard for all node-positive women.

If we look at the results achieved by combined treatment in respect to DFS, we see that the addition of CT to T was able to induce a small advantage which resulted in being roughly the same size in the whole cohort of women and in each menopausal sub-group. This is strongly supportive of the fact that the lack of statistical significance in our trial is likely to be due to an effect of its small size. However, this additional benefit appears to be limited to the first years and to diminish over time. This trend also comes out from the analysis of smoothed hazard estimates. In fact, this analysis shows an advantage favouring the combined treatment only during the first years. This might reflect the putative effect of CT in controlling primary resistance to T, a condition which has been described for selected groups of tumors also in the presence of ER or PgR positivity [START_REF] Arpino | Estrogen receptor-positive, progesterone receptor-negative breast cancer: association with growth factor receptor expression and Tamoxifen resistance[END_REF]. Relative to S, the tendency of curves towards crossing after a few years in the whole groups is likely to mainly reflect the tendency observed in pre-menopausal women. It is not so easy to explain the observed trend towards crossing. However, competing risk analysis of deaths appears to rule out that it might be related to the different incidence of breast cancer-unrelated deaths between groups. Once again, regardless of the mechanisms involved, it is a fact that, overall, the combination of CT with T did not improve the long term results achieved by T alone, especially in post-menopausal women, where the early DFS benefits achieved by the combination did not translate into a mortality advantage at any time.

In view of the limited benefit provided by the addition of CT to T in ER-positive patients, especially in post-menopause, it would be advisable to be able to discriminate a priori the women who might be safely managed by endocrine therapy alone. Through the STEPP analysis of our data, we tried to see whether quantitative ER or PgR values might help in discriminating such patients, especially in respect to their survival expectation. Indeed, the addition of CT to T did not appear to benefit the women with ER or PgR values above 50-60 fmol/mg at all. However, overall differences were not statistically significant. Thus ER or PgR quantitative levels do not appear to be completely affordable to indicate which women could be safely managed through T alone and additional bio-molecular predictors of endocrine responsiveness are probably required. The results reported on by Albain et al. [START_REF] Albain | Adjuvant chemotherapy and timing of tamoxifen in postmenopausal patients with endocrine-responsive, node-positive breast cancer: a phase 3, open-label, randomised controlled trial[END_REF] suggest that this might be the case. Albain's trial compared CAF vs. CAF plus T given concurrently vs. CAF followed by T in a population of node-positive, ER-positive post-menopausal women, demonstrating that the patient-subset with high ER concentration and HER-2 negative disease did not benefit further from CAF added to T. More recently, these investigators have reported on the predictive value of the 21-gene recurrence score (RS) assay originally described by Paik et al. [START_REF] Paik | Gene expression and benefit of chemotherapy in women with nodenegative, estrogen receptor-positive breast cancer[END_REF] as being able to predict the benefit from CMF added to T in a group of ER-positive, node-negative women. In summary, no significant benefit, either in terms of DFS or of OS, was achieved by combining CAF with T in the low or intermediate RS sub-groups [START_REF] Albain | Prognostic and predictive value of the 21-gene recurrence score assay in postmenopausal women with node-positive, oestrogen-receptor-positive breast cancer on chemotherapy: a retrospective analysis of a randomised trial[END_REF]. However, these investigators themselves conclude that prospective studies with larger samples sizes are essential to confirm the value of bio-molecular characterization and of multi-gene assays in establishing who benefits most from modern endocrine therapy and chemotherapy [START_REF] Albain | Prognostic and predictive value of the 21-gene recurrence score assay in postmenopausal women with node-positive, oestrogen-receptor-positive breast cancer on chemotherapy: a retrospective analysis of a randomised trial[END_REF].

In conclusion, we have confirmed that, even after such a long follow-up time, T demonstrated to represent an effective alternative to CT for node-positive, ER-positive, breast cancer patients, regardless of their actual menopausal status, and that the additional benefit, especially on late survival, provided by adding CT to T, was minimal. Thus, especially in post-menopausal women, the early benefits which might be expected from the addition of CT to T should be balanced with the low, if any, probability of a late mortality advantage.

Figure- legends Fig. 1 :Fig. 2 :Fig. 3 :Fig. 4 :Fig. 5 :

 legends12345 Figure-legends

ACKNOWLEDGEMENTS

The GROCTA 01 trial was originally funded in part by an unrestricted grant from ICI-Pharma (Milan, Italy). No funding was obtained by any entity to support present analysis.

The authors are indebted to M. Parodi and L. Zinoli (National Cancer Research Institute, Genoa,Italy) for their assistance in Data Management and to Dr C. Casella (Genoa Tumor Registry) for her valuable help in mortality data updating.

They are also indebted to Ms Suzanne Patten for reviewing the language format. Finally, they wish to express their gratitude to all the patients and the investigators who participated in this trial, namely, to the investigators listed below who have actively contributed to updating all data: M. Cantore (Ospedale Civile, Carrara); M. Mangoni (Ospedale Careggi, Firenze); C. Caroti (Ospedale Galliera, Genova); E. Rinaldi (Ospedale Civile, Magenta); E. Aitini (Ospedale Civile, Mantova); S. Banducci (Ospedale Civile, Merate); S. Girelli (Ospedale Fatebenefratelli, Milano); D. Aldigretti (Istituto Scientifico St Raffaele, Milano); B. Agostara, A. Traina (Ospedale Oncologico M. Ascoli, Palermo); G. Cruciani (Ospedale S. Maria delle Croci, Ravenna); C. Boni, R. Gnoni ( Ospedale S. Maria Nuova, Reggio Emilia); D. Guarneri ( Ospedale Civile, Sanremo); A. Farris, A. Lai (Oncologia Clinica, Università, Sassari); P.Sismondi, N.Biglia (I Clinica Ostetrica e Ginecologica, Università, Torino); M. Mansutti (Azienda Ospedaliera, Udine)

HR= Hazard ratio; 1 numbers represent median ER or PgR concentration in all patients; 2 HRs according to a PgR cutoff level of 10 fm/mg: >10 vs ≤ 10: Disease Progression: 0.73 (0.55-0.97, 95% CI) p< 0.000; Mortality: 0.65 (0.48-0.89, 95% CI) p< 0.006