Jérémie Bettinelli

Emmanuel Jacob

Grégory Miermont

The scaling limit of uniform random plane maps, via the Ambjørn-Budd bijection

We prove that a uniform rooted plane map with n edges converges in distribution after a suitable normalization to the Brownian map for the Gromov-Hausdorff topology. A recent bijection due to Ambjørn and Budd allows to derive this result by a direct coupling with a uniform random quadrangulation with n faces.

Introduction

Context

The topic of limits of random maps has met an increasing interest over the last two decades, as it is recognized that such objects provide natural model of discrete and continuous 2-dimensional geometries [START_REF] Ambjørn | Quantum geometry. A statistical field theory approach[END_REF][START_REF] Angel | Uniform infinite planar triangulations[END_REF]. Recall that a plane map is a cellular embedding of a finite graph (possibly with multiple edges and loops) into the sphere, considered up to orientation-preserving homeomorphisms. By cellular, we mean that the faces of the map (the connected components of the complement of edges) are homeomorphic to 2-dimensional open disks. A popular setting for studying scaling limits of random maps is the following. We see a map m as a metric space by endowing the set V (m) of its vertices with its natural graph metric d m : the graph distance between two vertices is the minimal number of edges of a path linking them. We then choose at random a map of "size" n in a given class and look at the limit as n → ∞ in the sense of the Gromov-Hausdorff topology [START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF] of the corresponding metric space, once rescaled by the proper factor.

This question first arose in [START_REF] Chassaing | Random planar lattices and integrated super-Brownian excursion[END_REF], focusing on the class of plane quadrangulations, that is, maps whose faces are of degree 4, and where the size is defined as the number of faces. A series of papers, including [MM06, LG07, Mie09, LG10, BG08], have been motivated by this question and contributed to its solution, which was completed in [START_REF] ¸ois | Uniqueness and universality of the Brownian map[END_REF][START_REF] Miermont | The Brownian map is the scaling limit of uniform random plane quadrangulations[END_REF] by different approaches. Specifically, there exists a random compact metric space S called the Brownian map such that, if Q n denotes a uniform random (rooted) quadrangulation with n faces, then the following convergence holds in distribution for the Gromov-Hausdorff topology on the set of isometry classes of compact metric spaces: 9 8n

1/4 Q n (d) ----→ n→∞ S. (1)
Here and later in this paper, if X = (X, d) is a metric space and a > 0, we let aX = (X, ad) be the rescaled space, and we understand a map m as the metric space (V (m), d m ).

Le Gall [START_REF] ¸ois | Uniqueness and universality of the Brownian map[END_REF] also gave a general method to prove such a limit theorem in a broader context, that applies in particular to uniform p-angulations (maps whose faces are of degree p) for any p ∈ {3, 4, 6, 8, 10 . . .}. When this method applies, the scaling factor n -1/4 and the limiting metric space S are the same, only the scaling constant (9/8) 1/4 may differ. One says that the Brownian map possesses a property of universality, and one actually expects the method to work for many more "reasonable" classes of maps. Roughly speaking, this approach relies on two ingredients: (i) A bijective encoding of the class of maps by a family of labeled trees that converge to the Brownian snake, in which the labels represent the distances to a uniform point of the map.

(ii) A property of invariance under re-rooting for the model under consideration and for the limiting space S.

Interestingly enough, as of now, the only known method to derive the invariance under re-rooting of the Brownian map needed in (ii) is by using the convergence of some root-invariant discrete model to the Brownian map, as in (1). A robust and widely used bijective encoding in obtaining (i) is the Cori-Vauquelin-Schaeffer bijection [START_REF] Cori | Planar maps are well labeled trees[END_REF][START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF] and its generalization by Bouttier-Di Francesco-Guitter [START_REF] Bouttier | Planar maps as labeled mobiles[END_REF], see for instance [START_REF] Marckert | Invariance principles for random bipartite planar maps[END_REF][START_REF] Miermont | An invariance principle for random planar maps[END_REF]. However, this bijection becomes technically uneasy to manipulate when dealing with non-bipartite maps (with the notable exception of triangulations) or maps with topological constraints. Recently, Addario-Berry and Albenque [START_REF] Addario | The scaling limit of random simple triangulations and random simple quadrangulations[END_REF] obtained the convergence to the Brownian map for the classes of simple triangulations and simple quadrangulations (maps without loops or multiple edges), by using another bijection due to Poulalhon and Schaeffer [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF].

In the present paper, we continue this line of research with another fundamental class of maps, namely uniform random plane maps with a prescribed number of edges. The key to our study is to use a combination of the Cori-Vauquelin-Schaeffer bijection, together with a recent bijection due to Ambjørn and Budd [START_REF] Ambjørn | Trees and spatial topology change in causal dynamical triangulations[END_REF], that allows to couple directly a uniform (pointed) map with n edges and a uniform quadrangulation with n faces, while preserving distances asymptotically. This allows to transfer known results from uniform quadrangulations to uniform maps, in a way that is comparatively easier than a method based on the Bouttier-Di Francesco-Guitter bijection. However, and this was a bit of a surprise to us, proving the appropriate re-rooting invariance necessary to apply (ii) above does require some substantial work.

We note that our results answer a question asked in the very recent preprint [START_REF] Bouttier | On the two-point function of general planar maps and hypermaps[END_REF]. Let us also mention that, in parallel to our work, Céline Abraham [START_REF] Abraham | Rescaled bipartite planar maps converge to the Brownian map[END_REF] has obtained a similar result to ours for uniform bipartite maps, by using an approach based on the Bouttier-Di Francesco-Guitter bijection.

Main results

We need to introduce some notation and terminology at this point. If e is an oriented edge of a map, the face that lies to the left of e will be called the face incident to e. We denote by e -, e + and rev(e) the origin, end and reverse of the oriented edge e. It will be convenient to consider rooted maps, that is, maps given with a distinguished oriented edge called the root, and usually denoted by e * . The root vertex is by definition the vertex e - * . We let M n be the set of rooted plane maps with n edges, and M • n be the set of rooted and pointed plane maps with n edges, i.e., of pairs (m, v * ) where m ∈ M n and v * is a distinguished element of V (m).

Similarly, we let Q n (resp. Q • n ) be the set of rooted (resp. rooted and pointed) quadrangulations with n faces. We also let T n be the set of well-labeled trees with n edges, i.e., of pairs (t, l) where t is a rooted plane tree with n edges, and l is an integer-valued label function on the vertices of t that assigns the value 0 to the root vertex of t, and such that |l(u)l(v)| 1 whenever u and v are neighboring vertices in t.

There exists a well-known correspondence, sometimes called the trivial bijection, between the sets M n and Q n . Starting from a rooted map m, we add a vertex inside each face of m, and join this vertex to every corner of the corresponding face by a family of non-crossing arcs. If we remove the relative interiors of the edges of m, then the map formed by the added arcs is a quadrangulation q, which we can root in a natural way from the root of m by fixing some convention. In this construction, the set of vertices of m is exactly the set V 0 (q) of vertices of q that are at even distance from the root vertex: this comes from the natural bipartition V 0 (q) ⊔ V 1 (q) of V (q) given by the vertices of m and the vertices that are added in the faces of m.

However, the graph distances in m and those in q are not related in an obvious way, except for the elementary bound

d q (u, v) 2d m (u, v) ∆(m) 2 d q (u, v) u, v ∈ V (m) = V 0 (q),
where ∆(m) denotes the largest degree of a face in m. On the other hand, it was noticed recently by Ambjørn and Budd [START_REF] Ambjørn | Trees and spatial topology change in causal dynamical triangulations[END_REF] that there exists another natural bijection between M • n × {0, 1} and Q • n , which is much more faithful to graph distances. This bijection is constructed in a way that is very similar to the well-known Cori-Vauquelin-Schaeffer (CVS) bijection between Q • n and T n × {0, 1}, and is in some sense dual to it. For the reader's convenience, we will introduce the two bijections simultaneously in Section 2.

The Ambjørn-Budd (AB) bijection provides a natural coupling between a uniform random element

(Q n , v * ) of Q • n , and a uniform random element (M • n , v * ) of M • n .
Using this coupling, it was observed already [START_REF] Ambjørn | Trees and spatial topology change in causal dynamical triangulations[END_REF][START_REF] Bouttier | On the two-point function of general planar maps and hypermaps[END_REF] that the "two-point functions" that govern the limit distribution of the distances between two uniformly chosen points in M • n and Q n coincide. In this paper, we show that much more is true.

Theorem 1. Let (Q n , v * ) and (M • n , v * ) be uniform random elements of Q • n and M •
n respectively, that are in correspondence via the Ambjørn-Budd bijection. Then we have the following joint convergence in distribution for the Gromov-Hausdorff topology

9 8n 1/4 M • n , 9 8n 1/4 Q n (d) --→ n→∞ (S, S),
where S is the Brownian map.

A very striking aspect of this is that the scaling constant (9/8) 1/4 is the same for M • n and for Q n . This implies in particular that

n -1/4 d GH (M • n , Q n ) P ----→ n→∞ 0
where d GH is the Gromov-Hausdorff distance beween two compact metric spaces, which, to paraphrase the title of [START_REF] Marckert | The rotation correspondence is asymptotically a dilatation[END_REF], says that "the AB bijection is asymptotically an isometry." Although obtaining this scaling constant is theoretically possible using the methods of [START_REF] Miermont | An invariance principle for random planar maps[END_REF], the computation would be rather involved.

At the cost of an extra "de-pointing lemma," (Proposition 4) this will imply the following result.

Corollary 1. Let M n be a uniformly distributed random variable in M n . The following convergence in distribution holds for the Gromov-Hausdorff topology 9 8n

1/4 M n (d) ----→ n→∞ S
where S is the Brownian map.

As was pointed to us by Éric Fusy, it is likely that our methods can also be used to prove convergence of uniform (pointed) bipartite maps with n edges. Indeed, following [START_REF] Bouttier | On the two-point function of general planar maps and hypermaps[END_REF], these are in natural correspondence via the AB bijection with pointed quadrangulations with no confluent faces (see below for definitions). In turn, the latter are in correspondence via the CVS bijection with "very well-labeled trees," which are elements of T n in which the labels of two neighboring vertices differ by exactly 1 in absolute value (this has the effect of replacing the scaling constant (9/8) 1/4 with 2 -1/4 ). However, checking the details of this approach still requires some work, and we did not pursue this to keep the length of this paper short, and because this result has already been obtained by Abraham [Abr13] using a more "traditional" and robust bijective method.

In Section 2, we present the two abovementionned bijections. Section 3 is devoted to the comparison between the distributions of M n and M • n . Section 4 is dedicated to the heart of the proof of Theorem 1, and Section 5 proves the key re-rooting identity (ii).

Cori-Vauquelin-Schaeffer and Ambjørn-Budd bijections

In most of this section, we fix an element (q, v * ) ∈ Q • n , and consider one particular embedding of q in the plane. We label the elements of V (q) by their distance to v * , hence letting l

+ (v) = d q (v, v * ).
Using the bipartite nature of quadrangulations, each quadrangular face is of either one of two types, which are called simple and confluent, depending on the pattern of labels of the incident vertices. This is illustrated on Figure 1, where the four edges incident to a face of q are represented in thin black lines, and the four corresponding vertices are indicated together with their respective labels. The Cori-Vauquelin-Schaeffer (CVS) bijection consists in adding one extra "red" arc inside each face, linking the vertex with largest label of simple faces to the next one in the face in clockwise order, and the two vertices with larger label in confluent faces. The Ambjørn-Budd (AB) bijection adopts the opposite rules, adding the "green" arcs to q.

The connected graphs whose edge-sets are formed by the arcs of either color (red or green) are obviously embedded graphs. The Cori-Vauquelin-Schaeffer bijection For the CVS bijection, the "red" embedded graph is a plane tree t with n edges, with vertex set V (t) = V (q) \ {v * }. This tree also inherits a label function, which is simply the label function l + above. It also inherits a root from the root e * of q, following a convention that we will not need to describe in detail. What is important about the rooting convention, however, is the following. If we are given a vertex v and an oriented edge e in q, we say that e points towards v if d q (e + , v) = d q (e -, v) -1. Then the root vertex of t is equal to e - * if e * points towards v * , and to e + * otherwise. We let ǫ be respectively equal to 0 or 1 depending on which of these two situations occur.

Remark. Throughout this work, we will never consider the root (edge) of the tree; only its root vertex, that is, the origin of its root, will be of importance.

It is then usual to define the label function

l(v) = l + (v) -l + (root(t)) = l + (v) -l + (e - * ) -ǫ, with values in Z. Proposition 1. The mapping CVS : Q • n → T n × {0, 1}
sending the pointed quadrangulation (q, v * ) to the pair ((t, l), ǫ) as above, is a bijection.

In the following, we will often omit ǫ from the notation, and will only refer to it when it plays an indispensable role.

The Ambjørn-Budd bijection On the other hand, the "green" embedded graph formed following the rules of the AB bijection is a plane map m with n edges, but with vertex-set equal to V (q) \ V max (q), where V max (q) is the set of vertices v of q that are local maxima of the function l + , i.e., such that d q (u, v * ) = d q (v, v * ) -1 for every neighbor u of v. Note that V max (q) really depends on the pointed map (q, v * ) rather than on q alone, but we nevertheless adopt this shorthand notation for convenience. One should note that the distinguished vertex v * ∈ V (q) is never a local maximum of l (it is indeed the global minimum!), so that it is an element of V (m), also naturally distinguished.

By the Euler formula, this implies that m has #V max (q) faces. One can be more precise by saying that when embedding m and q jointly in the plane as in the above construction, each face of m contains exactly one of the vertices of V max (q). Finally, we can use the root e * of q to root the map m according to some convention that we will not describe fully, but for which the root vertex of m is equal to e + * if e * points towards v * , and to e - * otherwise. We let ǫ be equal to 0 or 1 accordingly. See Figure 3 for an example of both bijections.

Proposition 2. The mapping AB :

Q • n → M • n × {0, 1}
sending the pointed quadrangulation (q, v * ) to the pair ((m, v * ), ǫ) as above, is a bijection.

Again, we will usually omit ǫ from the notation. The map m also inherits the labeling function l + from the quadrangulation q, but contrary to what happens for the CVS bijection, this information turns out to be redundant thanks to the remarkable identity

d m (v, v * ) = d q (v, v * ) = l + (v), v ∈ V (m) = V (q) \ V max (q). (2)
In fact, we are going to make this identity slightly more precise by showing that q and m actually "share" some specific geodesics to v * . In order to specify the exact meaning of this, we need a couple extra definitions. Let e be an oriented edge in q, and let f be the face incident to e. We say that e is special if the green arc associated with f by the AB bijection is incident to the same two vertices as e (in particular, f must be a simple face). In this case, we let ẽ be this green arc. On the above picture of a simple face, the face is incident to exactly one special edge, which is the one on the left, oriented from top to bottom. More generally, we use the following definition:

Definition 1. If c = (e 1 , e 2 , . . . , e k
) is a chain of oriented edges in q, in the sense that e + i = e - i+1 for every i ∈ {1, 2 . . . , k -1}, and if all these oriented edges are special, then we say that the chain c is special and we let c = (ẽ 1 , . . . , ẽk ) be the corresponding chain in m.

Next, if e is an edge of q, we can canonically give it an orientation so that it points towards v * . Then, among all geodesic chains (e, e 1, . . . , e k ) from e -to v * with first step e (so that k = d q (e -, v * )-1), there is a distinguished one, called the left-most geodesic to v * with first step e, which is the one for which the clockwise angular sector between e i and e i+1 , and excluding e i+1 , contains only edges pointing towards e + i = e - i-1 , with the convention that e 0 = e. We let γ(e) be this distinguished geodesic, and γ(e) = (e 1 , e 2 , . . . , e k ) be the same path, with the first step removed. This is illustrated in the following picture, where two corresponding steps of the geodesic γ(e) are depicted. Proposition 3. Let e be an oriented edge of q that points toward v * . Then the chain γ(e) is special.

e i e i+1 l + 1 l l -1 l + 1 l + 1 l l -1 l + 1 l -1 v e ′
Proof. Here the reader might want to use Figure 2 to follow the details of this proof. Fix i ∈ {0, 1, . . . , k -1} and let v = e + i = e - i+1 . Consider the last edge e ′ before e i+1 in clockwise order around v. Then by definition of the left-most geodesic, e ′ must be pointing towards v. Then the face incident to v that has the sector between e ′ and e i+1 as a corner is necessarily a simple face, and the vertex of this face that is diagonally opposed to v must have label equal to the label l = d q (v, v * ) of v (since the other two labels must be l + 1 = d q ((e ′ ) -, v * ) and l -1 = d q (e + i+1 , v). Therefore, e i+1 is the special edge incident to this simple face.

Since by hypothesis e = e 0 is pointing towards v * , this implies by our argument that e 1 is special, and we can conclude by an induction argument.

Proposition 3 has an apparently anecdotal consequence on which, in fact, most of this work relies. Let e, e ′ be two oriented edges of q pointing towards v * . The two left-most geodesics γ(e) = (e 0 , e 1 , . . . , e k ) and γ(e ′ ) = (e ′ 0 , e ′ 1 , . . . , e ′ k ′ ) share a maximal common suffix, say e k-r+1 = e ′ k ′ -r+1 , . . . , e k = e ′ k ′ where r 0 is the largest possible. (Note that r may be equal to k + 1 or k ′ + 1, in the case where one geodesic is entirely a suffix of the other one.) But then it always holds that e + k-r = (e ′ k ′ -r ) + , so that the sequence (e 0 , e 1 , . . . , e k-r , rev(e ′ k ′ -r ), rev(e ′ k ′ -r-1 ), . . . , rev(e ′ 1 ), rev(e ′ 0 )) is a chain, with total length that we denote by d • q (e, e ′ ). Recall that ∆(m) denotes the largest face degree of m.

Corollary 2. Let v, v ′ ∈ V (m) = V (q) \ V max (q) be
given, and let e, e ′ be two oriented edges in q both pointing towards v * , and such that e -= v and (e ′ ) -= v ′ . Then it holds that

d m (v, v ′ ) d •
q (e, e ′ ) + ∆(m). Proof. We assume that e = e ′ to avoid trivialities. By Proposition 3, the geodesics γ(e) and γ(e ′ ) are special, so that there are paths in m starting from e + and (e ′ ) + with edges (ẽ 1 , . . . , ẽk ) and (ẽ ′ 1 , . . . , ẽ′ k ′ ) respectively. But then the maximal suffix shared by these paths has the same length as the one shared by γ(e) and γ(e ′ ). Therefore, we can join e + and (e ′ ) + in m by a path of length d • q (e, e ′ ) -2. Now by construction of the AB bijection, the edge e lies in a single face of m, so that we can join e -to e + with a path of length at most ∆(m)/2. The same is true for the extremities of e ′ , which allows to conclude.

Comparing pointed and non-pointed maps

Let M n be a uniformly distributed random variable in M n , and let (M • n , v * ) be a uniformly distributed random variable in M • n . The superscript in M • n is here to indicate that, even after forgetting the distinguished vertex v * , it does not have same distribution as M n . Rather, it holds that

P (M • n = m) = #V (m) #M • n , m ∈ M n . (3)
Note that, by contrast, if

(Q n , v * ) is a uniformly distributed random variable in Q • n , then Q n is indeed uniform in Q n since
a quadrangulation with n faces has n + 2 vertices, so that pointing such a quadrangulation does not introduce a bias. The goal of this subsection is to obtain the following comparison theorem for the laws of M n and M • n . Let µ n be the law of M n and µ • n be the law of M • n . We let • denote the total variation norm of signed measures. Proposition 4. It holds that µ n -µ • n → 0 as n → ∞. Proof. By (3), one has

µ n -µ • n = m∈Mn 1 #M n - #V (m) #M • n . Now recall that #M n = #Q n = 2 n + 2 3 n n + 1 2n n , #M • n = 1 2 #Q • n = 3 n n + 1 2n n ,
where we used the trivial graph bijection between a rooted map with n edges and a rooted quadrangulation with n faces on the one hand, and the AB bijection on the other hand. This implies that

µ n -µ • n = 1 #M n m∈Mn 2 #V (m) n + 2 -1 = E 2 #V (M n ) n + 2 -1 . (4)
To show that this vanishes as n → ∞, we compute the first two moments of #V (M n ). Note that by the trivial graph bijection, #V (M n ) has same distribution as the number of vertices at even distance from the root vertex e - * in a uniform rooted quadrangulation Q n . By an obvious symmetry argument, this implies that

E #V (M n ) = 1 2 E #V (Q n ) = n + 2 2 . ( 5
)
For the second moment, we use the CVS bijection again. Select a uniform random vertex v * among the n + 2 elements of V (Q n ) and let

((T n , ℓ n ), ǫ) = CVS(Q n , v * ). Since ℓ n (v) = d Qn (v, v * ) - d Qn (e - * , v * ) -ǫ for every v ∈ V (Q n ),
we have that the vertices v at even distance from e - * are those for which ℓ n (v) + ǫ is even. So

E #V (M n ) 2 = E   u,v∈V (Tn)∪{v * } 1 {ℓn(u)+ǫ≡ℓn(v)+ǫ≡0[mod 2]}   = (n + 2) 2 P ℓ n (U ) + ǫ ≡ ℓ n (V ) + ǫ ≡ 0[mod 2] .
where U, V are uniformly chosen in V (T n ) ∪ {v * } conditionally given T n and independently of (ℓ n , ǫ).

Plainly, the probability under consideration is equivalent to the same quantity where U, V are instead chosen uniformly in V (T n ). Furthermore, conditionally given T n , U, V , the labels along the branch from U to V in T n form a random walk with i.i.d. steps that are uniform in {-1, 0, 1}, and thus the parity of the labels follow an irreducible Markov chain with values in {0,1} with transition matrix 1/3 2/3 2/3 1/3 and stationary measure (1/2, 1/2). It follows that the probability that ℓ n (U ) and ℓ n (V ) have same parity is a function of d Tn (U, V ) with limit 1/2 at infinity, while the probability that ℓ n (U ) + ǫ is even is exactly 1/2 since ǫ is a Bernoulli(1/2) random variable independent of (T n , ℓ n , U, V ). On the other hand, it is classical that d Tn (U, V )/ √ 2n converges to a Rayleigh distribution as n → ∞, so that d Tn (U, V ) converges to ∞ in probability. These facts easily entail that

P (ℓ n (U ) + ǫ ≡ ℓ n (V ) + ǫ ≡ 0[mod 2]) converges to 1/4 as n → ∞. Consequently, E #V (M n ) 2 = n 2 4 1 + o(1) , as n → ∞. (6)
Together, equations (5) and (6) imply that 2 #V (M n )/n converges to 1 in L 2 , which entails the result by (4).

From this, we deduce a bound in probability for ∆(M • n ). Theorem 3 of Gao and Wormald [START_REF] Gao | The distribution of the maximum vertex degree in random planar maps[END_REF] shows that if ∆ V (M n ) denotes the largest degree of a vertex in M n , then

P (∆ V (M n ) > log n) → 0 as n → ∞.
From the obvious fact that the dual map of M n has same distribution as M n , the same is true if we replace ∆ V (M n ) with ∆(M n ). By Proposition 4 we conclude that the same holds for M • n .

Lemma 1. It holds that as n → ∞,

P (∆(M • n ) > log n) → 0.

Encoding with processes and convergence results

We now proceed by following the general approach introduced by Le Gall [LG07, LG13], which we mentioned in the Introduction. It first requires to code maps with stochastic processes. Let (Q n , v * ) be a uniform random element of Q • n , and let

((T n , ℓ n ), ǫ) = CVS(Q n , v * ) and ((M • n , v * ), ǫ) = AB(Q n , v * ).
Since CVS and AB are bijections, the random variables (T n , l n ) and (M • n , v * ) are respectively uniform in T n and M • n , while ǫ is uniform in {0,1} and independent of (T n , ℓ n ) and (M • n , v * ). Note that our conventions imply that the variable ǫ is indeed the same in the images by the two bijections.

Coding with discrete processes

For i ∈ {0, 1, . . . , 2n} we let c i be the i-th corner of T n in contour order, starting from the root corner, so in particular c 0 = c 2n . We extend this to a sequence (c i , i ∈ Z) by 2n-periodicity. Let also v i be the vertex of T n that is incident to c i . The contour and label functions of (T n, ℓ n ) are defined by

C n (i) = d Tn (v i , v 0 ), L n (i) = ℓ n (v i ), i ∈ {0, 1, . . . , 2n},
and these functions are extended to continuous functions [0, 2n] → R by linear interpolation between integer coordinates. Now recall that the sets V (T n ) and V (Q n ) \ {v * } are identified by the CVS bijection, so that we can view v i , 0 i 2n as elements of V (Q n ). With this identification we let

D n (i, j) = d Qn (v i , v j ), i, j ∈ {0, 1, . . . , 2n},
and we extend D n to a continuous function [0, 2n] 2 → R by linear interpolation between integer coordinates, successively on each coordinate. We also let, for i, j ∈ {0, 1, . . . , 2n},

D • n (i, j) = L n (i) + L n (j) -2 max( Ľn (i, j), Ľn (j, i)) + 2.1 {max( Ľn(i,j), Ľn(j,i))<Ln(i)∧Ln(j)} ,
where

Ľn (i, j) = inf{L n (k) : i k j} if i j and Ľn (i, j) = inf{L n (k) : k ∈ [0, j] ∪ [i, 2n]} if i > j.
The somehow unusual indicator in this definition only serves the purpose to match our definition of d • q ; see Lemma 2. We now recall how the mapping CVS -1 is constructed. Starting from a given plane embedding of T n , we add the extra vertex v * arbitrarily in the unique face f of the map T n , and declare it to be incident to a unique corner that we denote by c ∞ . Next, for every i ∈ Z we let s(i) = inf{j > i : L n (j) = L n (i) -1}, which we call the successor of i. Note that s

(i) = ∞ if L n (i) = min L n .
The successor of the corner c i is then s(c i ) = c s(i) by definition. The construction then consists in drawing an arc e i from c i to s(c i ) for every i ∈ {0, 1, . . . , 2n-1}, in such a way that these arcs do not cross each other, and that the relative interior of e i is contained in f . This construction uniquely defines a map, which is Q n , and this map is pointed at v * (here again, we will not specify the rooting convention). By construction, there is a one-to-one correspondence between the corners c i of T n and the edges e i of Q n . It turns out that the natural orientation of e i obtained in the construction (that is, from v i to v s(i) ) coincides with the orientation that we introduced above for quadrangulations, namely, e i points towards v * in Q n . Consequently, the oriented paths following the arcs are geodesics towards v * . See Figure 3. Lemma 2. Let e be an edge of Q n , and let c be the corner of T n such that e is the arc linking c with s(c). Let k = d q (e -, v * ) -1 and for 0 i k let e (i) be the arc going from s i (c) to s i+1 (c). Then the chain (e (0) , e (1) , . . . , e (k) ) is the left-most geodesic to v * with first step e. Consequently,

D • n (i, j) = d •
Qn (e i , e j ), i, j ∈ {0, 1, . . . , 2n}.

Proof. Fix i ∈ {0, 1, . . . , k}. By construction, every arc between e (i) and e (i+1) in the clockwise order around e + (i) is necessarily pointing toward e + (i) . The first claim easily follows. The second claim follows by noticing that the event {max( Ľn (i, j), Ľn (j, i)) < L n (i) ∧ L n (j)} appearing in the indicator in the definition of D • n says that neither of the left-most geodesic to v * with first steps e i or e j is a suffix of the other.

We now define a function Dn similar to D n but associated with the map M • n . Recall that e i is the arc of Q n from the corner c i of T n to s(c i ). We let ṽi = e + i so that for every i ∈ {0, 1, . . . , 2n}, ṽi is always an element of

V (M • n ). Set Dn (i, j) = d M • n (ṽ i , ṽj ), i, j ∈ {0, 1, . . . , 2n}.
We also extend Dn to a continuous function [0, 2n] 2 → R as we did for D n . Clearly, the set {ṽ

i : i ∈ {0, 1, . . . , 2n}} is equal to V (M • n ), so that ({0, 1, . . . , 2n}, Dn ) is a pseudo-metric space iso- metric to (V (M • n ), d M • n ) through the mapping i → ṽi .
Combining Corollary 2 and Lemma 2, we obtain the bound

Dn (i, j) D • n (i, j) + ∆ n , i, j ∈ {0, 1, . . . , 2n}, (7)
where ∆ n := ∆(M • n ), and this remains true for every s, t ∈ [0, 2n] in place of i, j.

Scaling limits and proof of Theorem 1

We now introduce renormalized versions of our encoding processes. Namely, for s, t ∈ [0, 1], let

C (n) (s) = C n (2ns) √ 2n , L (n) (s) = 9 8n 1/4 L n (2ns), D (n) (s, t) = 9 8n 1/4 D n (2ns, 2nt)
and define D • (n) (s, t) and D(n) (s, t) similarly to D (n) by replacing D n with D • n and Dn . The main result of [START_REF] ¸ois | Uniqueness and universality of the Brownian map[END_REF][START_REF] Miermont | The Brownian map is the scaling limit of uniform random plane quadrangulations[END_REF] (which implies (1)) shows that one has the following convergence in dis-

tribution as n → ∞ in C([0, 1], R) × C([0, 1], R) × C([0, 1] 2 , R): (C (n) , L (n) , D (n) ) -→ (e, Z, D), (8)
where (e, Z) is a pair of stochastic processes sometimes called the head of the Brownian snake, and D is a random pseudo-distance on [0, 1] defined from (e, Z) as follows. Define two pseudodistances on [0, 1] by the formulas

d e (s, t) = e(s) + e(t) -2 min{e(u) : s ∧ t u s ∨ t} and d Z (s, t) = Z(s) + Z(t) -2 max( Ž(s, t), Ž(t, s)),
where similarly as for the definition of D • n we let Ž(s, t) = min{Z(u) : s u t} if s t, and Ž(s, t) = min{Z(u) : u ∈ [s, 1] ∪ [0, t]} otherwise. Then D is the largest pseudo-distance d on [0, 1] that satisfies the following two properties:

{d e = 0} ⊂ {d = 0} and d d Z . (9)
At this point, we recall that the Brownian map S is the quotient space [0, 1]/{D = 0}, endowed with the (true) distance function induced by D on this set, which we still denote by D.

We would like to study the joint convergence of (8) with D(n) , and show that the limit of the latter is D as well. To this end, we proceed in three steps.

First step: tightness

We observe that (8) implies that D • (n) converges (jointly) to d Z . On the other hand, the bound (7) combined with Lemma 1 easily implies that the laws of D(n) , n 1, form a relatively compact family of probability measures on C([0, 1] 2 , R), by repeating the argument of [START_REF] ¸ois | The topological structure of scaling limits of large planar maps[END_REF]. Indeed, for every δ > 0, let

ω( D(n) , δ) = sup | D(n) (s, t) -D(n) (s ′ , t ′ )| : |s -s ′ | ∨ |t -t ′ | δ
be the modulus of continuity of D(n) evaluated at δ, so by the triangle inequality and (7), we have

ω( D(n) , δ) 2 sup D(n) (s, s ′ ) : |s -s ′ | δ 2 sup D • (n) (s, s ′ ) : |s -s ′ | δ + ∆ n (8n/9) 1/4 .
It follows from Lemma 1 and the convergence in distribution (8) that for every ε > 0, lim sup

n→∞ P ω( D(n) , δ) ε P 2 sup {d Z (s, s ′ ) : |s -s ′ | δ} ε
and the a.s. continuity of Z implies that this converges to 0 as δ → 0. Since D(n) (0, 0) = 0, this entails the requested tightness result. Hence, up to extraction of a subsequence (n k ), we may assume that

C (n) , L (n) , D • (n) , D (n) , D(n) , n -1/4 ∆ n -→ e, Z, d Z , D, D, 0 (10)
in distribution, where D is a random continuous function on [0, 1] 2 . In order to simplify the arguments to follow, we apply the Skorokhod representation theorem, and assume that the underlying probability space is chosen so that this convergence holds almost surely rather than in distribution. Until the end of the paper, all the convergences as n → ∞ are understood to take place along this subsequence (n k ).

Second step: bound on D It is not difficult to check that D is a pseudo-distance, because D(n) is already symmetrical and satisfies the triangle inequality, and because D(n) (s, s) = 0 as soon as s is in {k/2n : k ∈ {0, 1, . . . , 2n}}. Let us prove that D satisfies the properties appearing in (9). First, assume that d e (s, t) = 0. Then it is elementary to see that there are sequences of integers i n , j n such that i n /2n and j n /2n respectively converge to s and t, and such that v in = v jn . As a consequence, it holds that ṽin and ṽjn lie in the same face or in two adjacent faces of M • n , and therefore are at distance at most ∆ n in M • n . Consequently, one has that

D(s, t) = lim n→∞ D(n) i n 2n , j n 2n = lim n→∞ 9 8n 1/4 d M • n (ṽ in , ṽjn ) = 0,
as wanted. Finally, the bound D d Z is a simple consequence of (7) and (10). From this and the definition of D as the largest pseudo-distance satisfying (9), we obtain that D D. On the other hand, let s * be the (a.s. unique [START_REF] ¸ois | Conditioned Brownian trees[END_REF]) point at which Z attains its minimum. Taking a sequence (i n ) such that ṽin = v * , it is not difficult to see, using the convergence of L (n) to Z, that i n /2n must converge to s * . Therefore, by choosing other sequences (j n ) such that j n /2n converges, it follows from (2) that, almost surely,

D(s * , s) = D(s * , s) = Z s -Z s * for every s ∈ [0, 1]. ( 11
)
Third step: re-rooting argument The final crucial property on which the proof relies is that if U 1 , U 2 are independent random variables in [0, 1] that are also independent of all the previously considered random variables, then

D(U 1 , U 2 ) (d) = D(s * , U 1 ). ( 12
)
number of edges e of Q n pointing towards v * such that e + = v. Using the construction of the AB bijection, one can see that this number of edges is precisely the degree of v in M • n , but we leave this as an exercise to the reader as we are not going to use it explicitly.

On the other hand, (12) will follow if ṽ⌊2nU1⌋ can be coupled with a uniformly chosen vertex

V 1 in M • n in such a way that d M • n (ṽ ⌊2nU1⌋ , V 1 ) = o(n 1/4
) almost surely, possibly along a subsequence of (n k ). This is what we now demonstrate, except that the vertex V 1 that we will produce (denoted by v jn below) will be uniform on

V (M • n ) \ {v * } rather than on V (M • n ). This distinction is of course of no importance. First recall that V (M • n ) = V (Q n ) \ V max (Q n ) where V max (Q n )
was defined in Section 2 as the set of vertices of Q n whose neighbors are all closer to v * . With the usual identification of vertices of

V (Q n ) \ {v * } with V (T n ), we can view the vertices V max (Q n ) as a subset of V (T n ). Lemma 3. A vertex v ∈ V (T n ) is an element of V max (Q n ) if and
only if its label is a local maximum in T n in the broad sense. Namely, for every vertex u adjacent to v in T n , it holds that ℓ n (u) ℓ n (v).

Proof. Let l = ℓ n (v). Assume first that one of the neighbors u of v has a label l + 1. Let c be the last corner of u before visiting v in contour order. Then the successor s(c) in the CVS bijection is by construction a corner incident to v, so that u and v are adjacent in Q n , but u is further away from v * than v, so that v ∈ V max (Q n ). Conversely, if a vertex u adjacent to v has label l or l -1, consider the maximal subtree of T n that contains u but not v. Then clearly every corner incident to a vertex in this subtree with label l + 1 cannot be linked by an arc to v. Moreover, by construction, every corner of v is linked to a vertex with label l -1. So if v is a local maximum in T n in the broad sense, v has no neighbors in Q n that are further away from v * than v, so v ∈ V max (Q n ).

If (t, l) is a labeled tree, we will let V max (t, l) be the set of vertices of t that are local maxima of l in the broad sense, so the last lemma states that

V max (Q n ) = V max (T n , ℓ n ).
Now let N 0 = 0 and, for j ∈ {1, 2, . . . , 2n}, let N j be the number of vertices in {v 0 , v 1 , . . . , v j-1 } that do not belong to V max (T n , ℓ n ). Note that

N 2n = #V (T n ) -#V max (T n , ℓ n ) = #V (M • n ) -1 (the -1 comes from the fact that V (T n ) = V (M • n )\{v * }).
Fix t ∈ [0, 1] and let i = ⌊2nt⌋. Let also v(0), v(1), . . . , v(h) = v i be the spine consisting of the ancestors of v i in T n indexed by their heights, so that v(0) = v 0 is the root vertex of T n and h = C n (i) is the height of v i . Note that the vertices v 0 , v 1 , . . . , v i-1 , v i are the vertices contained in the subtrees of T n rooted on v(0), v(1), . . . , v(h) that lie to the left of the spine, and more specifically, between the root corner c 0 and the corner c i of T n . We let T (0), T (1), . . . , T (h) be these trees, ordered by size, that is, in such a way that n 0 n 1 . . . n h where n j = #E(T (j)) (we arbitrarily choose in case of ties). Note that T (j) is naturally rooted at the first corner of a vertex v(k j ) visited by the contour exploration of T n . For j > h, we set n j = 0.

We also let L j be the label function ℓ n restricted to T (j), and shifted by the label of the root, so that L

j (u) = ℓ n (u) -ℓ n (v(k j )) for u ∈ V (T (j)).
We then note two important facts:

1. Conditionally given (n 0 , n 1 , . . .), the labeled trees (T (0), L 0 ), (T (1), L 1 ), . . . , (T (h), L h ) are independent uniform elements of T n0 , T n1 , . . . , T n h respectively, where h = max {i : n i > 0}.

2. For every ε > 0, there exists K > 0 such that, for sufficiently large n, P (n

0 + n 1 + • • • + n K < n(t -ε)) < ε.
The first property is easy. To see why the second is true, note that the contour processes of T (0), T (1), . . . , T (h) are the excursions of (C n (s), 0 s i) above the process (inf{C n (u) : s u i}, 0 s i). The convergence of the rescaled contour function C (n) to the normalized Brownian excursion e then easily implies that for every j 0, the j+1-th longest of these excursions (the one coding T (j)) converges uniformly to the j + 1-th longest excursion of e above the process (inf{e(u) : s u t}, 0 s t). Note that this excursion is unambiguously defined. This implies that n j /n converges to the length of the j + 1-th longest excursion. By standard properties of Brownian motion, these excursion lengths sum to t, and this implies the wanted result. Now since the label functions L j are just shifted versions of ℓ n , note that

N i - h j=0 Γ j ≤ h,
where Γ j := #V (T (j)) -#V max (T (j), L j ). Since h = C n (i) converges after renormalization by √ 2n to e(t), we obtain that h/n converges to 0 in probability. Also, conditionally given n 1 , n 2 , . . ., point 1. above implies that the random variables Γ j , j 0, are independent and, by Lemma 3, Γ j has the same distribution as V (M • nj ) -1. But the L 2 convergence of 2 #V (M n )/n to 1 established in the proof of Proposition 4 entails that 2(#V (M • n ) -1)/n also converges to 1 in probability, by Proposition 4. Fix ε > 0, K as in point 2. above, and N such that n ≥ N implies that both the conclusion of point 2. and P (|2(#V (M The last inequality is obtained by conditioning on n j and treating separately whether n j ≥ N or n j < N . As n K /n converges to a non-degenerate random variable, it follows that 2N i /n converges in probability to t. Since this is valid for every t ∈ [0, 1], standard monotony arguments entail that

2N ⌊2nt⌋ n , 0 t 1 -→ n→∞ Id [0,1] .
in probability for the uniform norm. Upon further extraction from (n k ), we can in fact assume that this convergence holds a.s. Now let U 1 be uniform in [0, 1] as above, and let j n be the first integer j such that N j > U 1 ×N 2n . By definition, the vertex v jn is uniformly distributed in

V (T n ) \ V max (T n , ℓ n ) = V (M • n ) \ {v * }.
On the other hand, the previous convergence implies that j n /2n → U 1 . Consequently, since v jn is at distance at most ∆ n from ṽjn in M n , 9 8n

1/4 d M • n (v jn , ṽ⌊2nU1⌋ ) ≤ 9 8n 1/4
Dn (j n , ⌊2nU 1 ⌋) + ∆ n -→ D(U 1 , U 1 ) = 0, where the last convergence comes from (10), and this is what we needed to conclude.

Figure 1 :

 1 Figure 1: Convention for adding arcs in the bijections.

Figure 2 :

 2 Figure 2: Two consecutive steps of a left-most geodesic.

Figure 3 :

 3 The two bijections, and some notation. The three green vertices correspond to the three faces of the map obtained by the AB bijection.

  K + 1)P (n K < N ).

  • n ) -1)/n -1| > ε/t) < ε/(K + 1) hold. Observe that if both j=K+1 n j n (t + 2ε), because it always holds that Γ j n j and

	K j=0 n j then, on the one hand, 2	n(t -ε) and h j=0 Γ j 2	K j=0 n j (1 -ε/t)	2	K j=0 Γ j	K j=0 n j (1 + ε/t) hold, h j=0 Γ j
	2	K j=0 Γ j + 2				h j=0 n j nt. As
	a result,
			
		P	 2 n

K j=0 Γ j n (t -2ε

) and, on the other hand, 2 h

Acknowledgments

We thank Jérémie Bouttier and Éric Fusy for stimulating discussions and insights during the elaboration of this work.

The proof of this re-rooting identity is a bit long so that we postpone it to the next Section. Let us see how this concludes the proof of Theorem 1. Observe that D also satisfies property (12) (which can be obtained using the fact that quadrangulations are invariant under re-rooting, see [START_REF] ¸ois | Uniqueness and universality of the Brownian map[END_REF]). Given this and (11), we deduce that

s., since we already know that D D. By Fubini's theorem, this shows that a.s. D and D agree on a dense subset of [0, 1] 2 , hence everywhere by continuity. The convergence (10) can thus in part be rewritten

from which it is easy to deduce Theorem 1, using the fact that the Gromov-Hausdorff distance between two metric spaces is bounded by the distortion of any correspondence between these spaces, see for instance Section 3.3 in [START_REF] ¸ois | Scaling limits of random trees and planar maps[END_REF]. Namely, we can assume again that (13) holds almost surely rather than in distribution by a further use of the Skorokhod representation theorem. Then, if we denote by p : [0, 1] → S the canonical projection, we note that the sets (v ⌊2nt⌋ , p(t)) : t ∈ [0, 1] and (ṽ ⌊2nt⌋ , p(t)) : t ∈ [0, 1] are correspondences between, on the one hand, the metric spaces

Proof of the re-rooting identity

It remains to prove (12). This again relies on a limiting argument. Namely, recall that the distin-

are two other such elements, chosen independently, and independently of v * , then it holds trivially that

). On the other hand, let (i n ) be a sequence of integers such that ṽin = v * , so that i n /2n → s * . If U 1 , U 2 are uniform on [0, 1] as above, then they naturally code the vertices ṽ⌊2nU1⌋ , ṽ⌊2nU2⌋ , and so by (10) we have that

Therefore, (12) would follow directly if the vertices ṽ⌊2nU1⌋ and ṽ⌊2nU2⌋ were uniform in V (M • n ). Unfortunately, the probability that ṽ⌊2nU1⌋ is equal to a given vertex v of M • n is proportional to the


Claire Gardent

Yannick Parmentier

Guy Perrier

Sylvain Schmitz

Lexical Disambiguation in LTAG using Left Context

Keywords: parsing, lexical disambiguation, lexicalized tree adjoining grammar, supertagging

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

When parsing with a lexicalized grammatical formalism such as lexicalized tree adjoining grammars (LTAG), a first step (called lexical selection) consists in retrieving, for each word of the sentence to parse, the associated grammatical structures (here the elementary LTAG trees).

As shown by Bangalore and Joshi [START_REF] Bangalore | Supertagging: An approach to almost parsing[END_REF], in large lexicalized grammars, lexical selection usually yields an intractable search space. This is because each given word may be associated with hundreds of grammatical structures resulting in an exponential number of sequences of structures to be explored (namely, the cartesian product of the sets of lexical entries of each word of the sentence to parse). In practice however, very few of these sequences can yield a complete parse.

In this paper, we adapt an optimization technique proposed by Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] for interaction grammars [START_REF] Perrier | Interaction grammars[END_REF] to prune the initial search space to LTAG and we illustrate the impact of this optimization on two benchmarks. We also relate our approach to a more general optimization technique proposed by Bonfante et al. [START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF] and Morey [START_REF] Morey | Étiquetage grammatical symbolique et interface syntaxe-sémantique des formalismes grammaticaux lexicalisés polarisés[END_REF].

The paper is structured as follows. In Section 2, we summarize related work. Section 3 gives a brief introduction to LTAG. In Section 4 and 5, we present the optimization proposed and we illustrate its impact on two small benchmarks. In Section 6, we relate our approach to the more general approach of companions introduced in [START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF][START_REF] Morey | Étiquetage grammatical symbolique et interface syntaxe-sémantique des formalismes grammaticaux lexicalisés polarisés[END_REF]. Section 7 concludes.

Related Work

Drawing inspiration from part-of-speech tagging techniques, Bangalore and Joshi [START_REF] Bangalore | Supertagging: An approach to almost parsing[END_REF] use n-grams and probabilities to compute the set of most probable grammatical structures given an LTAG and an input string. This probability-based lexical selection is called supertagging. A major drawback of this approach is that it heavily relies on the training corpus used for assigning lexical probabilities. Supertagging may thus ignore valid structures (i.e. structures that are in fact needed to parse the input sentence), which in turn can degrade parsing accuracy.

To prevent lexical selection from ignoring valid structures, Boullier [START_REF] Boullier | Supertagging: a non-statistical parsing-based approach[END_REF] proposed to compute an abstract grammar from the input one, and to use this abstract grammar to parse the input sentence. For each set of abstract structures that succeed in parsing the input sentence, one then selects the corresponding original structures and parse with the original grammar. This technique improves parsing efficiency only if parsing with the abstract grammar is significantly less complex than parsing with the input grammar. In his experiments, Boullier abstracted a context-free grammar (CFG) from an LTAG: the most common parsing algorithms for LTAGs have a polynomial time complexity in O(n 6 ), n being the length of the input sentence, while those for CFGs have a complexity in O(n 3 ). The main drawback of this approach is that one needs to first parse with the abstract grammar, which may still be quite time-consuming.

Following Boullier, Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] proposed a non-probabilistic lexical selection algorithm which uses a polarity-based abstraction, an abstraction inspired by interaction grammar [START_REF] Perrier | Interaction grammars[END_REF]. In this formalism, grammatical structures are tree descriptions where nodes are labeled with polarized feature-structures and parsing corresponds to computing syntactic tree models where polarities are neutralized. Bonfante et al. thus aimed at reducing the initial search space by applying a preliminary filter based on the polarity constraints. In their approach, each input grammatical structure is associated with a set of polarities. Valid lexical selection sequences are then those sequences whose total polarity set is neutral (we will elaborate on this in Section 4).

Perrier [START_REF] Perrier | Désambiguisation lexicale à l'aide d'automates de polarités[END_REF] proposes a finer abstraction in which the position of the polarities with respect to the anchor of the elementary structures of the grammar is taken into account. On this basis, he proposes a disambiguation algorithm which takes into account the linear order of the words in the sentence As discussed in Section 6, our work takes inspiration from [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF][START_REF] Perrier | Désambiguisation lexicale à l'aide d'automates de polarités[END_REF] and proposes an algorithm that is similar to that proposed in [START_REF] Perrier | Désambiguisation lexicale à l'aide d'automates de polarités[END_REF] though less costly in terms of space.

Lexicalized Tree-Adjoining Grammars

A tree-adjoining grammar [START_REF] Joshi | Tree-adjoining grammar[END_REF] is a tree rewriting system, where elementary trees can be rewritten using one of the two following operations: substitution and adjunction. Substitution consists in replacing a leaf node (marked with '↓') of an elementary or derived tree with an elementary tree whose root is labeled with the same syntactic category as this leaf node. Adjunction consists in replacing an internal node of an elementary or derived tree with an elementary tree having both a root node and a distinguished leaf node (marked with '⋆', and called the foot node) labeled with the same category as this internal node. Furthermore, in a lexicalized TAG, every elementary tree is associated with at least one lexical item called its anchor. If a tree is associated with several lexical items, there is one anchor, and several co-anchors. Figure 1 shows on the left the substitution (resp. adjunction) of a tree anchored by 'John' (resp. 'deeply') into a tree anchored by 'sleeps', the two operations resulting in the derived tree displayed on the right. Figure 2 shows a toy LTAG that will be used throughout to illustrate the workings of the algorithms.

Lexical Disambiguation

Following Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF][START_REF] Bonfante | Lexical disambiguation with polarities and automata[END_REF], our approach for lexical disambiguation uses a polarity-based abstraction over the input grammar. We first explain how this abstraction is built by Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF]. We then show how it can be applied to LTAG. Finally we show how this first filtering algorithm can be extended to improve disambiguation performance by taking word order information into account.

Polarity-Based Lexical Disambiguation

Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] define a framework for lexical disambiguation which involves the following three-steps:

Polarization: First, the input grammar is polarized. That is, each grammatical structure g is associated with a set of polarities S g where a polarity is a tuple (f, v, p) with f is a feature, v a value, and p a (possibly negative) integer. The sets of possible features and feature values are assumed to be finite. Since the grammar is lexicalized, we can associate each word w of the lexicon with its corresponding multiset of polarities M (recall that a word can anchor several grammatical structures, each associated with a possibly non-unique set of polarities). Neutralization: Second, an abstract lexical selection is operated using the previously computed polarized grammar. This amounts to first computing the cartesian product P of the multisets associated with the words

w 1 • • • w n of the input sentence: P = M 1 × • • • × M n .
Then, a binary rewriting rule, called the neutralization rule, is applied on the elements E = (S 1 , . . . , S n ) of this product P as follows: Let (S, S ′ ) be a couple of polarity sets in E, these are replaced with a set S + S ′ such that:

if a feature f with value v is present in both S and S ′ as (f, v, p) and (f, v, p ′ ) respectively, then the polarity (f, v, p

+ p ′ ) is added to S + S ′ . -any other polarity (f, v, p) in S ∪ S ′ is copied into S + S ′ .
This rewriting goes on (in an arbitrary order) until all elements of E have been consumed, thus producing one polarity set per element E in P . Filtering: In the end, an element E of P is called well-formed if, after neutralization, it consists of exactly one polarity (cat, S, +1) (where S is the category of sentences), an arbitrary number of polarities of the form (f, v, 0) and nothing else. Filtering only keeps the well-formed elements in P . For each such element, the associated grammatical structures in the input grammar are lexically selected.

A crucial point of this approach lies in the definition of polarization. It ought to include enough information to distinguish between useful grammatical structures in the context of the sentence to parse, and useless ones. Yet it should not lead to a complex, time-consuming abstraction: applying neutralization to polarized structures should remain fast.

Application to LTAG

We now show how this lexical disambiguation process can be applied to LTAG.

The polarization step consists in associating each tree t of the input LTAG with a set of polarities. For LTAG, we define our polarities to be of the form (cat, x, p), where x is a syntactic category labeling a tree node and p = 1-n with n the number of substitution or foot nodes labeled with x if x is the category of the root and p = n otherwise.

For instance, the tree schemas used in Fig. 1 are polarized as follows:

polarities(α np ) = {(cat, NP, +1)} , polarities(α intr ) = {(cat, S, +1), (cat, NP, -1)} , polarities(β ad ) = {(cat, VP, 0)} .
To take co-anchors into account, we change co-anchors in the grammar to substitution leaves and we add corresponding single node trees to match these new requirements.

The neutralization step first constructs the cartesian product of the set of polarities according to the sentence to parse. In the case of Fig. 1 ('John sleeps deeply'), this set contains a single element:

P = {(cat, NP, +1)}, {(cat, S, +1), (cat, NP, -1)}, {(cat, VP, 0)} .
Next, neutralization sums the polarities for compatible (f, v) pairs for each element E of P . In our toy example, neutralization yields the following set of polarities for the single element of P :

neutralization(E) = {(cat, S, +1), (cat, NP, 0), (cat, VP, 0)} .
The filtering step keeps the well-formed elements of P . In our case, there is only one element in P and it is well-formed.

Note that lexical selection based on polarization as presented here does not rely on any particular word order. One can compute the well-formed elements of P following or not the word order defined by the input sentence.

Automata Representation

Using an automaton to represent the results of lexical selection is necessary in order to deal with the large number of resulting sequences of structures, and can be seamlessly integrated in the parsing process with the same O(|G| • n 6 ) time complexity, now with n being the number of states [START_REF] Lang | Recognition can be harder than parsing[END_REF]. Hence we assume lexical selection to yield an automaton, which can later be processed by the parsing algorithm. The various lexical disambiguation algorithms strive to eliminate spurious paths from this automaton, i.e. combinations of grammatical structures that cannot yield a valid parse. In the case of polarity filtering, this polarity automaton tags each state with the sum of the polarities associated with the structures labeling the path from the initial state to that state. For instance, the sentence 'John eats an apple' yields the polarized automaton shown in Fig. 3 (where we only display the non-zero polarities).

Thus the final states of the polarity automaton indicate the (common) neutralization result for all the paths that lead into them, and the filtering step can be implemented by only keeping the paths that lead to a well-formed final state. For instance in Fig. 3, the top branch (in red) is discarded by the filtering step because state 4 is not a well-formed final state. Filtering still enforces the result of neutralization to be well-formed on the first coordinate, but additionally constrains the successive neutralization results to only contain non-negative polarities in the second coordinate: during each neutralization step, b 1 + b 2 is constrained to only contain polarities of the form (f, v, i) where i ≥ 0. Intuitively, this constraint excludes sequences where a requirement on the left of the current token has not been fulfilled.

Automata Representation. Let us now see how this extension impacts the automaton-based implementation of lexical selection. Because the automaton construction already relied on the input sentence order, the extension is easily implemented by decorating the states with pairs of polarity sets. The nonnegativity constraint on the second component (which accounts for the left context polarities) is checked on-the-fly: as soon as a state has a negative polarity in the second component, the construction of its successors aborts. Consider the sentence 'Say it to John' and the grammar of Fig. 2. 5 The resulting automaton is shown in Fig. 4. We notice that only the imperative tree schema α imp for 'say' prevents the left context abstraction from having negative polarities; the construction for the transitive tree schema α tr (e.g., 'John said it') aborts immediately. This is a vast improvement over the basic polarity automaton, which requires building a full automaton before filtering can take place and select well-formed final states.

Implementation and Evaluation

In order to evaluate the benefits brought by left context, we have implemented polarity-based lexical selection using left context within the TuLiPA parser [START_REF] Parmentier | A syntaxsemantics parsing environment for mildly context-sensitive formalisms[END_REF]. 6TuLiPA is an open source parser for mildly context-sensitive formalisms which supports LTAG and already includes the automaton-based lexical selection of Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] presented in Section 4. This makes it easier to compare the two approaches.

To exhibit the benefits of left-context disambiguation, we used two types of resources, a toy LTAG and a large one. These are described below. The question of which metrics to use to evaluate the gain of polarity filtering is not trivial. We chose to compare the sizes of automata when using left context or not. Another interesting metrics would be total parsing times, even if the additional cost of automaton-based filtering is expected to be negligible compared with the cost of parsing with highly ambiguous grammars. Due to time and space restrictions, this is left for future work.

Qualitative Study

In a first experiment, we performed polarity-based lexical selection using a toy LTAG made of 12 tree schemas (intransitive verb with clitic / canonical/ extracted subject, active transitive verb with clitic / canonical / extracted subject, passive transitive verb with clitic / canonical / extracted subject, proper nouns, clitics and auxiliaries), 9 lemmas, and 30 morphological entries. There is no part-of-speech tagging ambiguity in our toy lexicon, i.e. lexical ambiguity here is purely grammatical. The results are given in Table 1. In Table 1, the first two figures provide the lexical ambiguity of the sentence before and after polarity-based filtering. In these toy examples, the remaining lexical ambiguity is the same whether we only use polarities or also consider left context information. The last two figures give the number of states in the automata representations after polarity filtering and polarity and left context filtering, respectively. One can notice that using left context significantly reduces the size of the automaton, even with a small grammar and short sentences.

Quantitative Study

In a second experiment, we used the French LTAG of Crabbé [START_REF] Crabbé | Représentation informatique de grammaires fortement lexicalisées : application à la grammaire d'arbres adjoints[END_REF]. This grammar is compiled from a metagrammar developed in the XMG language [START_REF] Duchier | The metagrammar compiler: an NLP application with a multi-paradigm architecture[END_REF]. 7 It contains 6,080 tree schemas, and focuses on verbal, adjectival and nominal predicatives.

We used this grammar to evaluate polarity-based lexical disambiguation on a subset of the Test Suite for Natural Language Processing [START_REF] Lehmann | TSNLP -Test suites for natural language processing[END_REF]. This subset contains 90 sentences whose length ranges from 2 to 12 words. Figure 5 displays the average number of states of the automaton (y-axis) depending on the length of the input sentence (x-axis). One can notice the combinatorial explosion of the size of the 'Polarity' automata of Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] compared to the 'Context' automata, when considering sentences with more than seven words.

As suggested by Fig. 5, for polarity filtering to stay computationally tractable when parsing real data, optimizations are needed. From these first experiments, 7 Crabbé's metagrammar is available from https://sourcesup.renater.fr/scm/ viewvc.php/trunk/METAGRAMMARS/FrenchTAG/?root=xmg and its French documentation from http://www.linguist.univ-paris-diderot.fr/ ~bcrabbe/ frenchgrammar/. using information about left context seems to be adequate in practice. This still needs to be confirmed with other evaluation resources and metrics.

Generalization to Companions

We now show that the optimization we proposed for LTAG is a special case of the more general optimization framework developed in [START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF][START_REF] Morey | Étiquetage grammatical symbolique et interface syntaxe-sémantique des formalismes grammaticaux lexicalisés polarisés[END_REF].

The Notion of a Companion

In a polarized grammar, each grammatical structure is associated with a polarity and saturation rules define valid polarity combinations. For instance in LTAG, two trees may only combine if their polarity sets contains a positive and a negative triple for the same category e.g., {cat, NP, +1} and {cat, NP, -1}). Given a polarized grammar, Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] defines companions as follows. Definition 6.1. Let G be a polarized grammar. Given two grammatical structures G 1 and G 2 in G with polarities p 1 and p 2 respectively, p 2 is a companion of p 1 iff G 1 and G 2 can be combined by the grammar rules of G and p 1 , p 2 is a valid polarity combination according to the saturation rules defined by G.

Although the definition was initially designed for interaction grammars, it straightforwardly extends to the polarized version of LTAG described in subsection 4.2. Thus for instance, given the elementary trees of Fig. 1, the polarity {cat, NP, -1} triggered by the substitution node of α intr is a companion of the positive polarity {cat, NP, +1} associated with the root node of α np . More generally, the companions of a polarity in LTAG can be defined as follows. Given an initial tree whose root node has category C, the companions of the polarity of this root node are the polarities of all substitution nodes with category C. To account for word order and encode a filtering exploiting left context information as proposed in subsection 4.4, companions are furthermore divided into left-and right-companions. A left companion is a polarity associated with a substitution node occurring to the right of the anchor of the tree containing that substitution node. Conversely, a right companion is associated with a substitution node occurring to the left of the anchor of the tree containing that substitution node.

Using Companions for LTAG Filtering

Morey [START_REF] Morey | Étiquetage grammatical symbolique et interface syntaxe-sémantique des formalismes grammaticaux lexicalisés polarisés[END_REF] presents a general framework for filtering the initial search space when parsing with polarized grammars and in particular with interaction grammars. In particular, he defines the ICP algorithm which is based on the Integer Companionship Principle (ICP) and applies to systems with linear polarities. A polarity system is said to be linear if its non saturated polarities are grouped by pairs such that the only possible combination for a non saturated polarity is with its paired polarity. Thus the system of polarities for LTAG is linear: it has two non saturated polarities + and -. Furthermore, one positive polarity combines with exactly one negative polarity and conversely.

The ICP for interaction grammars is informally as follows:

For every path of the automaton, every polarity of a grammatical structure on this path must find a companion on the same path, and every possible companion on the path must be the companion of one polarity at most on the path, otherwise the path can be removed.

The ICP algorithm starts from some input automaton of lexical selections and builds, from this initial automaton, an automaton which validates the constraints enforced by the ICP. At each step of the automaton construction process, polarity information is updated and a constraint (called RC or right-companion constraint) is applied to filter paths which violate this constraint. We now explain each of these points.

Each state q in the ICP automaton is associated with a record r that summarizes the state of saturation for the polarities of each polarized category or co-anchor C present in the initial automaton. More specifically, for each category C, r records a triple (root, sat, sub):

root is the number of root nodes with category C whose polarity is not saturated sat is the number of root nodes with category C whose polarity has been saturated with substitution nodes placed occurring to the right of their anchor (i.e. with left companions) -lc is the number of left companions associated with nodes of category C which have not yet been saturated.

For instance, the record associated with a state occurring after a single transition from the initial state labeled with the tree schema α imp would be S: (1, 0, 0), NP: (0, 0, 2), to: (0, 0, 1) . This says that the tree schema α imp introduces an unsaturated root node with category 'S', two left companions of category 'NP' and one of category 'to' (i.e. three unsaturated substitution sites occurring to the right of their anchor).

Note that information about right companions (i.e. unsaturated substitution sites occurring to the left of their anchor) is not recorded. This is because right companions must be saturated immediately and thus need not be passed on through the automaton. As we shall see below the information is used by the RC-constraint however thereby filtering out paths violating this constraint.

Two constraints ensure the elimination of sequences of grammatical items which cannot possibly lead to a valid parse.

The first constraint, the right-companion constraint requires that all states must be such that the sum root + sat of saturated and unsaturated root nodes with category C is bigger or equal to the number rc of right companions of category C. This effectively enforces the left context constraint discussed in section 4 in that it requires that for any substitution node occurring to the left of the anchor there is a corresponding root node of the same category. This root node may be unsaturated (it has not been substituted in) or saturated (it has already been combined with a left companion, i.e. a substitution site occurring to the right of its anchor). In each case, it can be used to satisfy the right companion requirement and the polarity information is updated accordingly, i.e. either root or sat is decremented, and lc is possibly incremented.

Thus for instance, given the sentence 'Say it to John', selecting the transitive tree schema α tr for 'say' would result in a state tagged with {S: (1, 0, 0), NP: (0, 0, 1)} where the number of saturated and unsaturated roots of category 'NP' (0) is smaller than the number of right companions [START_REF] Bangalore | Supertagging: An approach to almost parsing[END_REF]. Since the RC-constraint is violated this state is not created and the path aborts. As a result, all combinations of α tr with the tree schemas selected by 'it', 'to' and 'John' will be ignored during parsing.

The second constraint, the valid path constraint, states that in the final state of a valid path (i.e. a path that will be considered for parsing), the lc value is null for all categories (all substitution nodes occurring to the right of the anchor of their containing tree have been filled), the root value is 1 for the S category and null for all other categories (all root nodes have been substituted in a substitution site). Since the RC-constraint ensures that all right companions have been saturated, this additional constraint ensures that the ICP principle is respected, i.e. that each every polarity on a path of the automaton has a companion on the same path, and further that each companion on a path is the companion of exactly one polarity on this path.

In sum, we have informally shown that the ICP algorithm integrates the Left-Context constraint. A formal proof is outstanding. An other open issue concerns the relative efficiency of the two algorithms (ICP and Left-Context Polarity filtering). The state information carried by the states of the ICP is richer than that of the Left-Context algorithm, thereby inducing a larger number of states when building the automaton. To assess the impact of this difference on effective running times, an empirical comparison would be needed.

Conclusion

In this paper, we presented a polarity based lexical disambiguation technique for LTAG and showed that it significantly reduces the size of the automata from which parsing proceeds. We also related out proposal to the general framework for polarity based lexical selection disambiguation presented in Bonfante et al. [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF], Perrier [START_REF] Perrier | Désambiguisation lexicale à l'aide d'automates de polarités[END_REF], Morey [START_REF] Morey | Étiquetage grammatical symbolique et interface syntaxe-sémantique des formalismes grammaticaux lexicalisés polarisés[END_REF]. Future work includes a formal proof of the relation between these approaches and a large scale empirical evaluation of the impact of the proposed filtering technique on parsing efficiency. Another interesting question concerns the definition of polarization. Here we restricted polarities to syntactic categories. It would be interesting to investigate how the approach extends to the rich set of feature values usually present in large scale LTAG.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Tree rewriting in an LTAG.

Fig. 3 :

 3 Fig.3: A polarity automaton for the sentence 'John eats an apple.'

Fig. 4 :

 4 Fig. 4: Lexical selection using left context for 'Say it to John.'

Fig. 5 :

 5 Fig. 5: Distribution of polarity automata sizes on the TSNLP.

Table 1 :

 1 Polarity-based lexical disambiguation.

		Sequences	States
	Sentence	Initial Polarity Polarity Context
	'Jean aime Marie' (John loves Mary)	12	2	26	4
	'Marie dort' (Mary sleeps)	3	1	5	3
	'Jean qui dort aime Marie' (John who sleeps loves Mary)	36	8	78	7
	'Marie est appelée par Jean' (Mary is called by John)	6	1	21	9
	'Jean qui dort est aimé par Marie' (John who sleeps is loved by Mary)	18	4	63	13

Recall that the grammar is modified so that co-anchors are represented as substitution nodes and additional single node trees are added to match these nodes. This explains why the αimp tree schema carries a to polarity feature.

[START_REF] Crabbé | Représentation informatique de grammaires fortement lexicalisées : application à la grammaire d'arbres adjoints[END_REF] See http://sourcesup.renater.fr/tulipa.