Parikshit Kolipaka
email: parikshit@csa.iisc.ernet.in.

Sathish Govindarajan

Two player game variant of the Erd ős-Szekeres problem

Keywords: Erdős-Szekeres problem, Ramsey theory, convex k-gon, empty convex k-gon

The classical Erdős-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdős-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant.

In this paper, we introduce the following two player game variant of the Erdős-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Introduction

The Erdős-Szekeres Problem is defined as follows:

For any integer k, k ≥ 3, determine the smallest positive integer N(k) such that any planar point set in general position that has at least N(k) points contains k points that are the vertices of a convex k-gon.

In 1935 Erdős and Szekeres proved the finiteness of N (k) using Ramsey theory [START_REF] Erdős | A combinatorial problem in geometry[END_REF]. There has been a series of improvements to bound the value of N (k) and the current best known bounds are

2 k-2 + 1 ≤ N (k) ≤ 2k-5 k-2 + 1,
see [START_REF] Erdős | Some more problems on elementary geometry[END_REF][START_REF] Kleitman | Finding convex sets among points in the plane[END_REF][START_REF] Toth | The Erdős-Szekeres theorem: upper bounds and related results[END_REF]. Erdős and Szekeres conjectured that the current lower bound is tight. This conjecture has been proved for k ≤ 6. N (4) = 5 was a geometric observation by Esther Klien. N (5) = 9 was shown by Kalbfeisch et al. [START_REF] Kalbfeisch | A combinatorial problem on convex regions[END_REF]. N (6) = 17 has been proved by Szekeres and Peters using an combinatorial model of planar configurations [START_REF] Szekeres | Computer solution to the 17-point Erdős-Szekeres problem[END_REF]. See survey [START_REF] Morris | The Erdős-Szekeres problem on points in convex position a survey[END_REF][START_REF] Barany | Problems and results around the Erdős-Szekeres convex polygon theorem[END_REF] for a detailed description about the history of the problem and its variants.

Erdős asked the Empty Convex k-gon Problem which is defined as follows:

For any integer k, k ≥ 3, determine the smallest positive integer H(k) such that any planar point set in general position that has at least H(k) points contains k points that are the vertices of a an empty convex k-gon, i.e., the vertices of a convex k-gon containing no points in its interior.

It is easy to see that H(4) = 5. H(5) = 10 was proved by Harboth [START_REF] Harborth | Konvexe Funfecke in ebenen Punktmengen[END_REF]. Gerken [START_REF] Gerken | On empty convex hexagons in planar point sets[END_REF] and Nicholes [START_REF] Nicolas | The empty hexagon theorem[END_REF] proved independently the existence of a empty hexagon. The current best bounds on H(6) are 30 ≤ H(6) ≤ 463 [START_REF] Koshelev | On the Erdős-Szekeres type problem in combinatorial geometry[END_REF][START_REF] Overmars | Finding set of points without empty convex 6-gons[END_REF]. Horton showed that H(k) does not exist for any k, k ≥ 7 [START_REF] Horton | Sets with no empty convex 7-gons[END_REF].

The Erdős-Szekeres Problem has been studied in higher dimensions [START_REF] Erdős | A combinatorial problem in geometry[END_REF][START_REF] Erdős | Some more problems on elementary geometry[END_REF][START_REF] Valtr | Sets in R d with no large empty convex subsets[END_REF]. Other related variants that are well studied are the convex k-gon with specified number of interior points [START_REF] Avis | On the existence of a point subset with 4 or 5 interior points[END_REF][START_REF] Avis | On the existence of a point subset with a specified number of interior points[END_REF][START_REF] Fevens | A note on the point subset with specified number of interior points[END_REF][START_REF] Hosono | On the existence of a convex point subset containing one triangle in the plane[END_REF][START_REF] Wei | More on an Erdős-Szekeres-type problem for interior points[END_REF] and the chromatic variant [START_REF] Devillers | Chromatic variants of the Erdős-szekeres theorem[END_REF][START_REF] Aichholzar | Large bichromatic point sets admit empty monochromatic 4-gons[END_REF].

We introduce a two player game variant of Erdős-Szekeres Problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The game ends when a convex k-gon is formed and the player who placed the last point loses the game.

The goal of both the players is to avoid losing the game. In the scenario where a player is bound to lose the game, his goal is to prolong the game as much as possible.

Since computational efficiency is not an issue in our context, we assume that both players follow an optimal strategy that achieves their goal.

Since N (k) is finite, we know that the game will end in atmost N (k) number of steps. Can the game end before N (k) steps?

Define N G (k) as the minimum number of steps for the game to end when both the players follow their optimal strategy.

In this paper we focus on finding the exact value of N G (k). We denote the player who plays first as player 1 and the player who plays second as player 2.

We also consider the two player game for the empty convex k-gon and correspondingly define H G (k). It is easy to see that N G (3) = H G (3) = 3, N G (4) = H G (4) = 5.

Combinatorial two player games have been well studied in the Maker/Breaker setting which is defined as follows:

Let X be a finite set and let F ⊆ 2 X be a family of subsets. In the game (X, F), two players (Maker and Breaker) take turns in claiming one previously unclaimed element of X. The objective of the Maker is to claim some f ∈ F i.e claim all the elements of f. The objective of the Breaker is to prevent the Maker from claiming any f ∈ F.

Chvátal and Erdős introduced the Maker/Breaker-type game [START_REF] Chvátal | Biased positional games[END_REF] for spanning trees, Hamiltonian cycles on graphs. There are a lot of results on Maker/Breaker-type games where (X, F) denotes random graphs, non planar graphs, near-perfect matchings, k-connected spanning subgraphs. There has also been a long line of research that studies the biased version of the various Maker/Breaker-type games [START_REF] Hefetz | Fast winning strategies in Maker-Breaker games[END_REF][START_REF] Beck | Combinatorial Games: Tic-Tac-Toe Theory[END_REF][START_REF] Bednarska | Biased positional games for which random strategies are nearly optimal[END_REF][START_REF] Gebauer | Asymptotic random graph intuition for the biased connectivity game[END_REF][START_REF] Krivelevich | The critical bias for the Hamiltonicity game is (1 + o(1)) log n[END_REF][START_REF] Krivelevich | Biased positional games and small hyper graphs with large covers[END_REF].

A complimentary variant of the Maker/Breaker game is the Avoider/Enforcer game where one player wants to avoid the formation of a structure and the other player wants to force the formation of that structure [START_REF] Lu | A note on biased and non-biased games[END_REF][START_REF] Beck | Combinatorial Games: Tic-Tac-Toe Theory[END_REF].

The two player game variant of the Erdős-Szekeres Problem that we study in this paper is different from the Maker/Breaker, Avoider/Enforcer games since in our game the objective of both the players is the same, i.e., avoiding the formation of convex k-gon.

In this paper, we focus on the Erdős-Szekeres two player game for k = 5. We show a winning strategy for player 2 and prove that N G (5) = 9 and H G (5) = 9. i.e., the game will end in the 9th step.

We consider convex layer configurations at each step and give a strategy for player 2 such that the game will reach a specific set of configurations until the 8th step and finally we argue in the 9th step that a convex 5-gon or an empty convex 5-gon is formed.

We further show that the convex 5-gon and empty convex 5-gon game always ends in the 9th step, i.e., there is no strategy for player 2 to end the game earlier.

The paper is organized as follows. Section 2 contains the preliminaries and definitions that we will be using in the rest of the paper. Section 3 describes the proof for the convex 5-gon game. Section 4 describes the proof for the empty convex 5-gon game.

Preliminaries and Definitions

We assume in the rest of this paper that our point set P is in general position, i.e., no 3 points of the point set are collinear. We denote the convex hull of a point set P as conv(P ) and the vertices of conv(P ) as CH(P ).

(i 1 , i 2 , ...i k ), |P | = |i k |, if P 1 = CH(P ) is of size i 1 , P 2 = CH(P \ P 1 ) is of size i 2 . . .
The type of point set P describes the sizes of the different convex layers of P . We denote P 1 as the first convex layer and P 2 as the second convex layer. Definition 2.5 U(i,j) of point set P: Point set having i points of the first convex layer of P and j points of the second convex layer of P . 3). O region is the region such that any point in it along with ABCD forms a convex 5-gon. I and Z regions are the regions such that any point in these regions along with ABCD forms a point set of type(4, 1). I region is outside the convex 4-gon and Z region is inside the convex 4-gon. S region is the region such that any point in it along with ABCD forms a point set of type(3, 2). Definition 2.9 Regions of a configuration: A configuration divides the plane into 4 types of regions I, O, S, Z. A region is called an O region of a configuration if it is an O region with respect to some convex 4-gon. The complement of the union of all the O regions of a configuration is further divided into I, S, Z regions. A region is called an I region of a configuration if it is an I region with respect to some convex 4-gon. Similarly we define S and Z regions of the configuration. Definition 2.10 Feasible regions of a configuration for the convex 5-gon game: A feasible region of a configuration for the convex 5-gon game is a region which is not contained in any of the O regions of the convex 4-gon's of the configuration.

Definition 2.11 Feasible regions of a configuration for the empty convex 5-gon game: A feasible region of a configuration for the empty convex 5-gon game is a region which is not contained in any of the O regions of the empty convex 4-gon's of the configuration.

We define the following set of point configurations that will be used in our proofs (see Fig. 4

Game for the convex 5-gon

In this section, we show that the second player has a winning strategy in the convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, . . . ) and player 2 plays in the even steps (2nd, 4th, . . . ). In player 1's turn, we argue that any point added without forming an convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.10) for placing the point that results in specific configurations that are favorable for player 2.

W.l.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2: Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1 and 7.2.1 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an convex 5-gon results in configuration 5.1 or 5.2 (in the 5th step) and in configuration 7.1 or 7.2.1 (in the 7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a convex 5-gon and player 2 will always win in the 9th step.

Any convex 5-gon game follows a path in the game tree shown in Fig. 4. We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

Parikshit Kolipaka and Sathish Govindarajan

Fig. 4: Game tree for the convex 5-gon We make the following observations on the number of points that can be contained in type 1 and type 2 beams without forming an empty convex 5-gon. We will assume that the points in the beam are in convex position with the points that form the beam. Thus, if the point set does not contain a convex 5-gon, type 1 beam has atmost 1 point and type 2 beam does not contain any point. Lemma 3.1 A strategy for player 2 exists such that convex 5-gon game will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: A triangle is formed by the first 3 points of the game. The 4th point is placed in such a manner that the resultant point set forms a parallelogram ABCD (configuration 4). For the 5th step, we divide the regions of the parallelogram into I, O, Z regions as shown in Fig. 5. The feasible regions where a point can be placed are the I and Z regions. If the 5th point, say E, is placed in the interior of the parallelogram i.e., Z region, the resultant point set forms configuration 5.1 (see Fig. 6). If E is placed in I region the resultant point set forms configuration 5.2 (see Fig. 7).

In the 6th step we show a feasible region in configuration 5.1 and configuration 5.2 where a point is added such that the resultant point set formed is either configuration 6.1 or configuration 6.2.

If the 5 point set formed is configuration 5.1, then let us suppose that E has been placed in Z 1 region (see Fig. 6), then the 6th point, say F is placed in Z 3 such that EF is parallel to AD and this forms configuration 6.1 (see Fig. 8). Let us call this as {Z 1 , Z 3 } point placement. By symmetry {Z 2 , Z 4 } point placement is similar and they form configuration 6.1. Now we argue for configuration 5.2. Let us suppose that E has been placed in I 1 region (see Fig. 7). The 6th point, say F , is placed in I 8 region such that EF is parallel to AD (see Fig. 9). Let us call this as {I 1 , I Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2. Thus, the feasible regions of configuration 6.1 (the regions that are not contained in any O region of convex 4-gons) are portions of R k where k = 1, 2, 3, 4 and Z region. From Fig. 10, we can verify that region I 1 of R 1 and Z 1 of Z is not contained in any of the O regions of the convex 4-gons. Fig. 10 shows Thus, the feasible regions of configuration 6.2 (the regions that are not contained in any O region of convex 4-gons) is S \ O 4 and portions of R k and Z regions. From Fig. 11, we can verify that region I 1 of R 1 is not contained in any of the O regions of these convex 4-gons. Fig. 11 shows I 1 in R 1 region and Z 1 in Z region. Z 1 is the region formed by triangle EDM where M is the intersection point of -→ AE and --→ BD. Symmetrically, there are feasible regions

I 1 in R 1 region
I k in R k region and Z k in Z region where k = 2, 3, 4.
If the point is placed in

I k of R k or Z k of Z where k = 1, 2, 3, 4, the resultant point set is configuration 7.2.1. If the point is placed in S \ O 4 the resultant point set is configuration 7.1. ✷
Now we prove that given a set of 7 points in configuration 7.1 or 7.2.1 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

Lemma 3.3 A (4,3) configuration where the 4 points of the outer convex layer is of the form (I,O,O,O) (3 points each in different O regions and 1 point in a I region of the inner triangle) contains a convex 5-gon.

Proof:

Let the inner triangle be ABC and the 3 points in the O regions of the triangle be F , G, H. Let the point in the I region be E and w.l.o.g let this I region be in between the O regions which contain the points F and H (see Fig. 12). We claim that the pair of rays ( --→ BF , --→ CH) does not intersect. Hence I * is feasible region where a point is added and the resultant point set that is formed is configuration 8.

Case 2 (configuration 7.2.1): Configuration 7.2.1 is a point set of (4,3) convex layer configuration without a convex 5-gon. First, we give the following characterization of configuration 7.2.1:

An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14). Let us assume that point G lies in region X 1 (see Fig. 15). The case when the point G is in X 2 can be argued in a similar fashion (see Fig. 17). We have 2 cases corresponding to EBG being a anti-clockwise turn or clockwise turn. Any point added to I * results in configuration 8. Type 2 (when G lies in X 1 and EBG is a clockwise turn): Consider the convex 4-gons of this configuration. The convex 4-gons are either of the type U (2, 2), U (1, 3) or U (3, 1) (see Fig. 16). We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the convex 5-gon game if the point set has no convex 5-gon and any point added to the point set forms an convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i -1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 3.5 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3) and (4,2) are the only valid convex layer configurations for the convex 5-gon game. To show that a (3,3), (4,2) convex layer configurations are not bad configurations we show a feasible region where a point is added without forming an convex 5-gon. (4,2) Convex layer configuration: Consider the line joining EF of the second convex layer (see Fig. 18(a)). This line divides the first convex layer into 2 parts. If either of the parts contains 3 points of the first convex layer then they form an empty convex 5-gon with the 2 points of the second convex layer. So the only other possible option is that both the parts contain 2 points.

Based upon the position of E, F in the diagonal triangles of the first convex layer, (4,2) convex layer configurations are divided into 3 cases. In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. 18). Thus (4,2) convex layer configurations are not bad configurations.

(3,3) Convex layer configuration: We make the following observations on the placement of the three points of the first convex layer in the I and O regions of the triangle formed by the second convex layer (see Fig. 14). If an I region has 3 points then the triangle in the second convex layer will not be contained in the triangle of the first convex layer. Hence an I region cannot have 3 points. Similarly an O region also cannot have 3 points. If an O region has 2 points then the opposite I region has to have the third point. In this case, there is an empty convex 5-gon being formed by these 2 points with the 3 points of the triangle. Hence an O region cannot have more than 1 point. In each of the above cases a feasible region K exists where a point can be added without forming a convex 5-gon (see shaded region in Fig. [START_REF] Koshelev | On the Erdős-Szekeres type problem in combinatorial geometry[END_REF][START_REF] Krivelevich | The critical bias for the Hamiltonicity game is (1 + o(1)) log n[END_REF][START_REF] Krivelevich | Biased positional games and small hyper graphs with large covers[END_REF][START_REF] Lu | A note on biased and non-biased games[END_REF][START_REF] Morris | The Erdős-Szekeres problem on points in convex position a survey[END_REF]. Thus [START_REF] Avis | On the existence of a point subset with a specified number of interior points[END_REF][START_REF] Avis | On the existence of a point subset with a specified number of interior points[END_REF] Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 3.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 3.5), the game will not end in the 7th step. By Lemma 3.2 the game will reach either configuration 7.1 or 7.2.1. By Lemma 3.4, the game will reach configuration 8 and finally since N (5) = 9 the game ends in the 9th step and player 2 wins the game. ✷

4 Game for the empty convex 5-gon

In this section, we show that the second player has a winning strategy in the empty convex 5-gon game and the game ends in 9 moves.

Overview of our proof and player 2's strategy to win the empty convex 5-gon game.

In our game, player 1 plays in the odd steps (1st, 3rd, . . . ) and player 2 plays in the even steps (2nd, 4th, . . . ). In player 1's turn, we argue that any point added without forming an empty convex 5-gon will always result in specific configurations. In player 2's turn we show a feasible region (Definition 2.11) for placing the point that results in specific configurations that are favorable for player 2. W.l.o.g., assume that the first 3 points of the game forms a triangle. We now describe the winning strategy for player 2: Player 2 will place the point in the 4th step such that the resultant point set forms a parallelogram (configuration 4). In the 6th step, we show that there exists a feasible region in both configuration 5.1 and 5.2 where the 6th point is placed, so that it will reach configuration 6.1 or configuration 6.2. Similarly in the 8th step we show that there will exist a feasible region in configuration 7.1, 7.2.1 and 7.2.2 where the 8th point is placed such that the resultant point set is configuration 8.

In player 1's turn we show that any point added by player 1 without forming an empty convex k-gon results in configuration 5.1 or 5.2 (5th step) and in configuration 7.1, 7.2.1 or 7.2.2 (7th step).

Finally, we argue that any point added by player 1 to configuration 8 will result in the formation of a empty convex 5-gon and player 2 will always win in the 9th step.

Any empty convex 5-gon game follows a path in the game tree shown in Fig. 24.

The feasible regions of the convex 5-gon game is a subset of the feasible regions of the empty convex 5-gon game (by Definitions 2.10, 2.11). Thus in the even step (player 2's turn to place the point) for configurations without a convex 5-gon (configurations 5.1, 5.2, 7.1, 7.2.1), the proof for the convex 5-gon game also applies for the empty convex 5-gon game. For configurations with a convex 5-gon (configurations 7.2.2) we give a separate proof.

We further show that there is no better strategy for player 2 to end the game earlier (in the 5th or 7th step) by arguing that all configurations of 4 points and 6 points have a feasible region.

Proof for H G (5) = 9

Lemma 4.1 The game for the empty convex 5-gon will always reach either configuration 6.1 or configuration 6.2 at the end of 6th step.

Proof: From Lemma 3.1 it is easy to see that the game for the empty convex 5-gon will always reach either configuration 5.1 or configuration 5.2 at the end of the 5th step.

Since the feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game, by Lemma 3.1 the game will reach either configuration 6.1 or configuration 6.2 at the end of 6th step. ✷ Lemma 4.2 Any point added by player 1 to either configuration 6.1 or configuration 6.2 without forming an empty convex 5-gon, results in either configuration 7.1, 7.2.1 or 7.2.2.

Parikshit Kolipaka and Sathish Govindarajan

Fig. 24: Game tree for the empty convex 5-gon Proof: We consider 2 cases corresponding to configuration 6.1 and configuration 6.2. We will now describe the O regions of configuration 6.1 and 6.2.

Case 1 (configuration 6.1): Let us consider all the empty convex 4-gons of configuration 6.1 (see Fig. 25). The convex 4-gons of configuration 6.1 that are formed by U (4, 0), U (3, 1) are not empty, so they are not considered. The empty convex 4-gons are of the form U (2, 2) of configuration 6. k region will result in configuration 7.2.2. Case 2 (configuration 6.2): Let us consider the empty convex 4-gons of configuration 6.2 (see Fig. 26). The convex 4-gons of configuration 6.2 that are formed by U (4, 0), U (3, 1) are not empty, so they are not considered. The empty convex 4-gons are of the form U (2, 2) of configuration 6.2 (see Fig. 26).

U(2,2) of configuration 6. If the point is placed in

I k , I * k of R k or Z k of Z where k = 1, 2,

Proof:

The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. By Lemma 3.4, there exists a feasible region such that a point added by player 2 in this feasible region results in configuration 8.

Let us now consider configuration 7.2.2 (which has non-empty convex 5-gon). First we will give the following characterization of configuration 7.2.2. An I region or an O region of the inner triangle cannot have more than 1 point (see Fig. 14 Let us consider all the empty convex 4-gons of this configuration (see Fig. 27). The regions that are not contained in the O regions of empty convex 4-gons are precisely the regions where a point is added without forming an empty convex 5-gon. We will show that there exists a region I * in these feasible regions where a point is placed forming configuration 8. The convex 4-gons that are formed by U (4, 0) of configuration 7.2.2 are not empty, so they are not considered. The remaining empty convex 4-gons of configuration 7.2.2 are of the form U (2, 2), U (1, 3), U (3, 1). It is important to note that GHE should be an anticlockwise turn and GF E a clockwise turn, otherwise we do not have a convex 4-gon in the first convex layer. U [START_REF] Avis | On the existence of a point subset with a specified number of interior points[END_REF][START_REF] Aichholzar | Large bichromatic point sets admit empty monochromatic 4-gons[END_REF] Any point added to I * results in configuration 8. ✷

We will now show that any point added to configuration 8 forms an empty convex 5-gon and hence the empty convex 5-gon game also ends in the 9th step. First we prove the following lemma. Proof: Let F , G, H, J be the 4 points of CH(P ). Let A, B, C be the points in the second convex layer and D, E be the points of the inner most convex layer (see Fig. 28).

The points F , G, H, J lie in the union of beams formed by the beams DE : CB, D : AB and E : AC. Since beam DE : CB is type 2, if there exists a point in its beam region then there exists an empty convex 5-gon. Thus, one of the type 1 beams D : AB or E : AC beams has atleast 2 points, which forms an empty convex 5-gon. ✷ The case where E is in the triangle KBC is symmetrical to the case when it is in triangle ABK. The case where E is in the triangle KAD is symmetrical to the case when it is in triangle KCD.

✷

Proof:

We consider 2 cases depending on whether the point is added inside EF GH convex 4-gon or outside EF GH convex 4-gon (see Fig. 31). We now argue that there is no strategy for player 2 to end the game earlier, i.e., the game will always reach the 9th step. We call a point set as bad configuration for the empty convex 5-gon game if the point set has no empty convex 5-gon and any point added to the point set forms an empty convex 5-gon. Note that the game ends in the ith step only if the point set reached in the i -1th step is a bad configuration.

It is easy to see that the game cannot end in the 5th step since no 4 point set is a bad configuration.

Lemma 4.8 There is no strategy for player 2 such that the game ends in the 7th step.

Proof: We prove this by showing that there are no 6 point sets which are bad configurations. When the point set contains 6 points it is easy to see that (3,3), (4,2) and (5,1) are the only valid convex layer configurations for the empty convex 5-gon game.

The feasible regions for the convex 5-gon game is a subset of the feasible regions for the empty convex 5-gon game. Thus by Lemma 3.5, there exists a feasible region for the (3,3), (4,2) convex layer configurations in the empty convex 5-gon game. Therefore (3,3), (4,2) convex layer configurations are not bad configurations for the empty convex 5-gon game.

To show that a (5,1) convex layer configuration is not a bad configuration we show a feasible region where a point is added without forming an empty convex 5-gon. Proof: The game does not end in the 5th step because no 4 point sets are bad configurations. By Lemma 4.1, the game will reach either configuration 6.1 or 6.2. Since all 6 point sets are not bad configurations (Lemma 4.8), the game will not end in the 7th step. By Lemma 4.2 the game will reach either configuration 7.1, 7.2.1 or 7.2.2. By Lemma 4.3, the game will reach configuration 8 and finally from Lemma 4.7 the game ends in the 9th step and player 2 wins the game. ✷

Conclusion

In our paper we have introduced the two player game variant of Erdős-Szekeres problem and proved that the game ends in the 9th step for the convex 5-gon and empty convex 5-gon game and player 2 wins in both the cases.

One natural question would be to analyze the game for higher values of k i.e. determine N G (k) and H G (k) for k > 5. Our approach will be very tedious for higher values of k as with the increase in the number of points in the point set, the number of point configurations increases exponentially.

We have shown that configuration 8 is a bad configuration for the empty convex 5-gon game. Another natural question is to determine whether there exists bad configurations for k > 5. More specifically, does there exist point configurations with the property that any point added to this configuration forms an empty convex k-gon or convex k-gon for k > 5. A negative result for the above question gives a lower bound for N G (k) and H G (k).

Definition 2 . 1

 21 Convex k-gon: is a convex polygon with k vertices. Definition 2.2 Empty Convex k-gon: is a convex k-gon with no points in its interior. Definition 2.3 Points in convex position: A point set P is said to be in convex position if CH(P ) = P . Definition 2.4 Type of a point set P: A point set P is called type

Definition 2 . 6 Definition 2 . 7

 2627 Type 1 Beam: A : BC denotes the region of the plane formed by deleting triangle ABC from the convex region in the plane bounded by the rays --→ AB and -→ AC (see Fig. 1). Type 2 Beam: AB : CD denotes the region of the plane formed by deleting convex 4-gon ABCD from the convex region in the plane bounded by the segment AB and the rays --→ AD and --→ BC (see Fig.2).Let A, B, C, D be 4 points in convex position.

Fig. 1 : 2 :Fig. 3 :

 123 Fig. 1: Type 1 beam Fig. 2: Type 2 beam

Fig. 5 :

 5 Fig. 5: Division of parallelogram regions

Fig. 6 :Fig. 7 :

 67 Fig. 6: Configuration 5.1

FFig. 8 :Fig. 9 :

 89 Fig. 8: Configuration 6.1

1 Fig. 10 :

 110 Fig. 10: Configuration 6.1 divided into regions

1 MFig. 11 :

 111 Fig. 11: Configuration 6.2 divided into regions

Fig. 12 :Fig. 13 : 1 Case 1 (

 121311 Fig. 12: (I,O,O,O) (4,3) convex layer configuration

Fig. 14 :

 14 Fig. 14: Division of triangle into regions

Fig. 15 :

 15 Fig. 15: Configuration 7.2.1 (I,I,O,O) G is in X1 and EBG is anticlockwise turn

Fig. 16 :

 16 Fig. 16: Configuration 7.2.1 (I,I,O,O) G is in X1 and EBG is clockwise turn

Fig. 17 :

 17 Fig. 17: Configuration 7.2.1 (I,I,O,O) G is in X2

Case 1 : 3 Fig. 18 :

 1318 Fig. 18: Cases of (4,2) configuration

Fig. 20 :Fig. 22 :Fig. 23 :

 202223 Fig. 19: (I,I,I) configuration

Theorem 3 . 1

 31 convex layer configurations are not bad configurations.✷ The convex 5-gon game always ends in the 9th step.

Fig. 25 :

 25 Fig. 25: Configuration 6.1 divided into regions

  1. U(2,2) of configuration 6.1: EF DA, EF CB, BEDF , AECF are the empty convex 4-gons of this form. Consider EF DA empty convex 4-gon. The regions that are contained in the O regions of EF DA are O 1 , O 7 , O 8 , O 9 , O 10 . Similarly the regions that are contained in the O regions of EF CB empty convex 4-gon are O 2 , O 3 , O 4 , O 5 , O 6 . The O regions of BEDF , AECF empty convex 4-gons does not contain the entire region of Z (Z region of ABCD convex 4-gon) and R k where k = 1, 2, 3, 4. Thus, the only feasible regions of configuration 6.1 (the regions that are not contained in any O region of empty convex 4-gons) are portions of R k where k = 1, 2, 3, 4 and Z region. From Fig. 25, we can verify that region I 1 , I * 1 of R 1 and Z 1 of Z is not contained in any of the O regions of the empty convex 4-gons. Fig. 25 shows I 1 , I * 1 only in R 1 region and Z 1 in Z region. Symmetrically, there are feasible regions I k , I * k in R k region and Z k in Z region where k = 2, 3, 4. Any point added in I k or Z k region will result in configuration 7.2.1. Any point added in I *

2 :Fig. 26 :

 226 Fig. 26: Configuration 6.2 divided into regions R 1 region and Z 1 in Z region. Symmetrically, there are feasible regions I k , I * k in R k region and Z k in Z region where k = 2, 3, 4. If the point is placed in I k , I * k of R k or Z k of Z where k = 1, 2, 3, 4, the resultant point set is either configuration 7.2.1 or configuration 7.2.2. If the point is placed in S \ O 4 the resultant point set is configuration 7.1. ✷

Fig. 27 :

 27 Fig. 27: Configuration 7.2.2 (I,O,O,O)

Lemma 4 . 4 A

 44 [START_REF] Barany | Problems and results around the Erdős-Szekeres convex polygon theorem[END_REF][START_REF] Avis | On the existence of a point subset with a specified number of interior points[END_REF][START_REF] Avis | On the existence of a point subset with 4 or 5 interior points[END_REF] convex layer configuration has an empty convex 5-gon.

Fig. 28 :

 28 Fig. 28: (3,2) configuration

Lemma 4 . 5 A 2 Fig. 29 :

 45229 Fig. 29: Cases for (4,4,1) configuration

Fig. 30 :

 30 Fig. 30: Cases according to the intersection of pairs of rays Case1: When none of the rays -→ AE, --→ BF , --→ CG, --→ DH intersect each other (see Fig. 30(a)).

8 Case1:

 8 Fig. 31: Configuration 8 Case1: Placing the point inside EF GH convex 4-gon: The point added lies in I region, S region, Z region or O region of ABCD convex 4-gon. If the point is placed in the O region of ABCD convex 4-gon then there exists an empty convex 5-gon. If point is placed in the S region of ABCD convex 4-gon then it forms a (4,3,2) convex layer configuration which contains an empty convex 5-gon (Lemma 4.4). If the point is placed in the I or Z region of the ABCD convex 4-gon then it forms a (4,4,1) convex layer configuration which contains an empty convex 5-gon (Lemma 4.5).Case2: Placing the point outside the EF GH convex 4-gon:

Fig. 32 :Theorem 4 . 1

 3241 Fig.32:(5,1) configuration[START_REF] Beck | Combinatorial Games: Tic-Tac-Toe Theory[END_REF][START_REF] Aichholzar | Large bichromatic point sets admit empty monochromatic 4-gons[END_REF] Convex layer configuration: A feasible region K exists where a point can be added without forming a empty convex 5-gon (see shaded region in Fig.32). ✷ Theorem 4.1 The empty convex 5-gon game always ends in the 9th step.

  and 24). An 8 point set of type[START_REF] Barany | Problems and results around the Erdős-Szekeres convex polygon theorem[END_REF][START_REF] Barany | Problems and results around the Erdős-Szekeres convex polygon theorem[END_REF] where the 4 points of the first convex layer are placed such that each point lies in different I region of the convex 4-gon of the second convex layer.

	Definition 2.13 Configuration 5.1: A 5 point set of type(4, 1) where the 4 points in the first convex layer
	form a parallelogram.
	Definition 2.14 Configuration 5.2: A 5 point set of type(4, 1) where the 3 points in the first convex layer
	with the 1 point in the interior form a parallelogram.
	Definition 2.15 Configuration 6.1: A 6 point set of type(4, 2) where 4 points in the first convex layer
	form a parallelogram and the 2 points inside the parallelogram are symmetrically placed in opposite
	triangles formed by diagonals of parallelogram.
	Definition 2.16 Configuration 6.2: A 6 point set of type(4, 2) where 4 points in the first convex layer
	form a trapezoid and the 2 points inside the trapezoid are symmetrically placed in opposite triangles
	formed by the diagonals.
	Definition 2.17 Configuration 7.1: A 7 point set of type(3, 4) where the 3 points of the first convex layer
	are in different I regions of the parallelogram formed by the 4 points in the second convex layer.
	Definition 2.18 Configuration 7.2.1: A 7 point set of type(4, 3) that does not have a convex 5-gon.
	Definition 2.19 Configuration 7.2.2: A 7 point set of type(4, 3) that has a non-empty convex 5-gon.
	Definition 2.20 Configuration 8:
	Definition 2.12 Configuration 4: A 4 point set forming a parallelogram.

  8 } point placement. By symmetry {I 2 , I 3 } , {I 4 , I 5 } , {I 6 , I 7 } point placements are similar and they form configuration 6.2.

✷ Lemma 3.2 Any point added by player 1 to configuration 6.1 or configuration 6.2 without forming an convex 5-gon, results in either configuration 7.1 or configuration 7.2.1.

  and Z 1 in Z region. Symmetrically, there are feasible regions I k in R k region and Z k in Z region where k = 2, 3, 4. Any point added in I k or Z k region will result in configuration 7.2.1.Case 2 (configuration 6.2): Let us consider the convex 4-gons of configuration 6.2 (see Fig.11). The convex 4-gons of configuration 6.2 are of the form U (4, 0), U (3, 1), U (2, 2).

  3, 4, the resultant point set is either configuration 7.2.1 or configuration 7.2.2. If the point is placed in S \ O 4 the resultant point set is configuration 7.1. ✷ Now we prove that given a set of 7 points in configuration 7.1, 7.2.1 or 7.2.2 there exists a feasible region where a point is added such that the resultant point set is configuration 8.

	Lemma 4.3 There exists a feasible region in configuration 7.1, 7.2.1 and 7.2.2 such that a point added
	by player 2 in this feasible region results in configuration 8.

  of configuration 7.2.2 (I,O,O,O): EHAF is the empty convex 4-gon of this type and it has I * contained in its I region. Thus I * is feasible for these convex 4-gons. F ACB, HABC, ACGB are the empty convex 4-gons of this type. F ACB, HABC have I * contained in there I regions and ACGB has I * inside. Thus I * is feasible for these convex 4-gons. U(2,2) of configuration 7.2.2 (I,O,O,O): EABF , EHCA are the empty convex 4-gons of this type and these have I * contained in there I regions. Thus I * is feasible for these convex 4-gons.

	U(1,3) of configuration 7.2.2 (I,O,O,O):

  Let E, F, G, H be the points of the first convex layer and A, B, C, D be the points of the second convex layer of configuration 8. Without loss of generality, let us assume that rays

	--→ DA,	--→ CB intersect.		--→ AB,	--→ DC intersect and rays
	Lemma 4.6 The 4 type 2 beams AB : FE, BC : GF, DC : GH, AD : HE contain the entire outer region in
	configuration 8.
	Proof: We consider 2 cases depending on the intersections of the rays	-→ AE,	--→ BF ,	--→ CG,	--→ DH.

  The regions contained by AB : F E, BC : GF , DC : GH, AD : HE beams are correspondingly O 1 , O 2 , O 3 , O 4 beam regions which contain the entire outer region in configuration 8. Consider EA and F B, extend them inside ABCD convex 4-gon until they intersect with CD. Let the points of intersection be J, K. When GC is extended inside the ABCD convex 4-gon it has to intersect BK before it intersects AB or AD. Hence ( The regions contained by AB : F E, BC : GF , DC : GH, AD : HE beams are correspondingly O 1 , O 2 , O 3 , O 4 beam regions (see Fig.30(b)) which contain the entire outer region in configuration 8.

	Case2: When some of the rays Now we prove that atmost one of the pairs of rays ( -→ AE, --→ BF , --→ CG, --→ DH intersect each other (see Fig. 30(b)). -→ AE, --→ BF ) or ( --→ CG, --→ BF ) can intersect in configura-tion 8. Assume that ( -→ AE, --→ BF ) intersect (see Fig. 30(b)). The case ( --→ CG, --→ BF ) intersecting is symmetrical.
	--→ BF , HD intersects AJ before it intersects AB or BC. Hence ( --→ CG) do not intersect. By a similar reasoning, ray --→ -→ AE, --→ DH) do not intersect. The pair of rays ( -→ CG, --→ DH) do not intersect because the pair of rays ( --→ BC, --→ AD) do not intersect.

✷ Lemma 4.7 Any point added to configuration 8 forms an empty convex 5-gon.


Gilles Sérasset
email: gilles.serasset@imag.fr

Interlingual Lexical Organisation for Multilingual Lexical Databases in NADIA

Keywords: multilingual lexical database, acception, linguistic structure

We propose a lexical organisation for multilingual lexical databases (MLDB). This organisation is based on acceptions (word-senses). We detail this lexical organisation and show a mock-up built to experiment with it. We also present our current work in defining and prototyping a specialised system for the management of acception-based MLDB.

Introduction

Needs for large scale lexical resources for Natural Language Processing (NLP) in general and for Machine Translation (MT) in particular, increase every day. These resources are considered to represent the most expensive part of almost any NLP system. Hence, an increasing interest in the development of reusable dictionaries can be observed.

To develop a Multilingual Lexical Database (MLDB), we think of two main approaches. First, the transfer approach where the links between the languages are realized via unidirectional bilingual dictionaries. This approach is used by many MT systems and by some lexical database projects (notably Acquilex or Multilex). Second, the interlingual approach where the links between the languages are realized via an unique interlingual dictionary. The KBMT-89 project (Knowledge Based Machine Translation) at Carnegie Mellon University in the US and the EDR (Electronic Dictionary Research) project in Japan use this approach.

In the context of multilingual MT systems, we are interested in the problems posed when constructing and using an application and theory independent MLDB. We are developing a Lexical Database Management System, NADIA, based on an interlingual approach. We chose acceptions as interlingual units. NADIA provides many tools for the management of MLDBs. Moreover, this system gives the linguist a great liberty in the choice of the linguistic structures.

We first give an overview of the project, beginning with its lexical organization. Then, we give the results of our experimentations on this lexical organization. Finaly, we present our current work: the definition and prototyping of a specialized system for the management of acceptionbased MLDBs.

NADIA is the continuation of a work done for the Multilex ESPRIT project. The coherence checker and software architecture have been defined for Multilex and adapted to our lexical organization.

I. Acception-based lexical organization

After studying and comparing different projects of lexical databases, including EDR (EDR 1993) , KBMT-89 (Nirenburg and Defrise 1990;[START_REF] Goodman | The KBMT project: a case study in Knowledge-Based Machine Translation[END_REF] Multilex and of Multilingual MT systems, such as CICC [START_REF] Uchida | Interlingua. International Symposium on Multilingual Machine Translation (MMT-91)[END_REF] and ULTRA [START_REF] Farwell | The Automatic Creation of Lexical Entries for a Multilingual MT system[END_REF] , we have concluded in favor of an interlingual lexical organization for our MLDBs.

Some of the international projects of lexical databases are based on a multi-bilingual approach (e.g. Multilex) while others use knowledge representation as an interlingua (e.g. KBMT-89 or EDR). Much like ULTRA, our approach is interlingual and linguistic rather than knowledge-based.

The dictionaries

A MLDB consists of two kinds of dictionaries: the monolingual dictionaries and the acception dictionary.

Monolingual dictionaries

The monolingual dictionaries are accessible by entries. These entries are lemmas ("normal form" of words, e.g. in English, infinitive for verbs, singular for nouns, etc.).

Items of the monolingual dictionaries (monolingual acceptions) are generally accepted meanings of words or expressions, as we can find them in standard printed dictionaries. These monolingual acceptions are combined with their linguistic information.

Monolingual acceptions of a language L are acceptions that are connected to a word or an expression of L. Such an acception can be accessed from one (or more) entries.

Acception dictionary

The interlingual dictionary, called acception dictionary, contains interlingual acceptions. Some information can be linked to these interlingual acceptions.

In a MLDB composed of n monolingual dictionaries, the set of interlingual acceptions is equal to the union of the sets of monolingual acceptions of the n dictionaries, with an equality relation bound to the semantic identity. Some contrastive problems may appear when two monolingual acceptions of two different languages are semantically slightly different. This appears when there is a non-direct translation of a word (e.g. 'river' can be translated in French by 'rivière' or by 'fleuve' 1 ). This kind of problem is solved by a relation from acception to subacception which is pre-defined in all NADIA lexical databases: the contrastive relation. It is intended to code contrastive problems induced by a non-direct translation, it is not intended to code any kind of ontological information.

Lexical organization

In the acception-based lexical organization, the monolingual acceptions and the interlingual acceptions must satisfy the following criteria:

2.1. Well-formedness criteria

• Each interlingual acception corresponds to at least one monolingual acception. This criterion states that an interlingual acception must correspond to at least one entry of one language (as monolingual acceptions). • An interlingual acception corresponds to at most one monolingual acception of the same language. An interlingual acception is not necessarily connected to a monolingual acception of each language of the MLDB. • A monolingual acception corresponds to one and only one interlingual acception. A monolingual acception is always related to an interlingual acception and (as stated by the preceding criterion) is one-one.

Translation criteria

• Two monolingual acceptions of different languages correspond to a unique interlingual acception if, and only if, they have the same meaning. This criterion states the semantic identity of two monolingual acceptions of different languages (provided that they correspond to the same interlingual acception) allowing the use of the interlingual dictionary for lexical translation purposes. • If entry e1 of language L1 is translated by entry e2 in language L2 via a non-direct equivalence, the corresponding interlingual acception must be linked by the contrastive relation or by a relation of quasisynonymy. This criterion allows the use of the acception dictionary for lexical translation purposes even when there is no direct translation.

II. Experimentation

The Parax mock-up

In order to experiment this lexical organization, É. Blanc has built the Parax mock-up [START_REF] Sérasset | Une approche par acceptions pour les bases lexicales multilingues[END_REF] . This mock-up is a small acception-based lexical database of 5 languages (English, French, German, Russian, Chinese).

Parax, produced on Macintosh with HyperCard™, was designed to experiment problems inherent to the acception-based lexical organization. Hence, items of the monolingual dictionaries are combined with rather simple linguistic information.

An entry of a monolingual dictionary is linked to several acceptions. These acceptions are provided with their linguistic information (left column in fig. 2). Each of these monolingual acceptions is related to an interlingual acception along with its definition (in French) and some semantic information (right column in fig. 2).

To accede to the acception dictionary, the user selects an acception in the middle column. The acception is displayed along with its sub-acceptions (middle column of fig. 3). From this point, it is possible to get a translation by selecting a target language for one of the acceptions. The translation appears in the right column of fig. 3 shows the German translation of the acception). In the example given, there is no direct equivalence from French to Russian as Russian introduces a distinction on the gender of the subject. To get the Russian translation, we have to select one of the sub-acceptions. Then, we can get 'жениться' for a man or 'замуж', 'замуж (выйти -за)' or 'замужем' for a woman.

Indexing methodology 2.1. Indexing in Parax

As the platform we used for this mock-up was not specialized for such a task, we have used an indexing methodology for the construction of this MLDB.

The starting point of our work was a small French corpus we wanted to index. Hence, we began to index French words and for each created acceptions, we gave a translation in the other languages.

After creating an entry, the lexicographer gives its different word-senses and their linked linguistic information (the kind of information depends on the language of the entry).

Then, the lexicographer links the word senses to an interlingual acception. As the number of acceptions is still small, it is possible to select an already existing acception by browsing directly in the acception dictionary. If the searched acception does not exist, it is created along with a definition in French and some semantic information.

2.2. General case When developing a large scale MLDB, it is no longer possible to select existing interlingual acceptions by directly browsing through the acception dictionary. Moreover, the different dictionaries will have to be indexed by different lexicographers. Hence, it is necessary to define another methodology.

The process of creation of an entry and its monolingual acceptions does not change. After creating an entry, the lexicographer selects a possible translation for the considered acception in a language of the database. If this translation is already indexed in the target language, he selects the corresponding acception in the target dictionary. The source and target monolingual acceptions are automatically linked to the same interlingual acception. If the translation is not already indexed in the target language, the lexicographer indexes it (partially) and asks the person in charge of the target dictionary to complete the new entry.

The acception dictionary is thus constructed and managed by the system and the lexicographers work in more or less the same way as when indexing bilingual dictionaries. This automatic management of the interlingual dictionary involves the automatic verification of the criteria defined above.

When a problem is detected the system attaches a warning for the lexicographer in charge of the acception dictionary, and proposes a default solution.

Some results

The corpus we wanted to index in the Parax mock-up consisted of 135 entries in French corresponding to a representative set of verbs, nouns, adjectives, and adverbs of general vocabulary. We have indexed these entries and the related acceptions. As we started the indexation with a French corpus, only some of the entries in the other languages have been given all their acceptions.

The distribution of the entries and acceptions of the different languages is the following:

III. Current work

Our current work consists in the definition and prototyping of a specialized management system for acception based MLDBs.

Related projects

Some international projects have already started the development of a system for MLDBs. We have studied and we use some of their results.

In Europe, we have participated in the Multilex project (CEC -DG XIII -ESPRIT project) which aims at the definition of standards for lexical databases systems. We use some of its results (e.g. the software architecture, some of the tools).

Multilex's software architecture, based on three layers (presentation level, internal level and database level), clearly separates the presentation from the coding and the coding from the storage of the information. This organization allows to change the presentation of the structures (giving the possibility to define user interfaces hiding the internal structure).

We have also studied the Japanese EDR project which has developed large dictionaries of about 300,000 words in both English and Japanese (200,000 of general vocabulary, 100,000 of terminological vocabulary). EDR has also developed dictionaries of 400,000 concepts, dictionaries of 300,000 co-occurrences (both in English and Japanese) and dictionaries of 300,000 bilingual entries (both for Japanese-English and English-Japanese) (EDR 1993) .

In EDR, individual concepts are introduced in the word dictionary and correspond to the word senses. Hence, our acceptions are really close to their concepts. However, they do not use a contrastive relation to code problems between the languages.

The CICC (Center of International Cooperation for Computerization, Japan) has also used a very close organization to construct a MLDB (Japanese, Chinese, Thai, Malay, and Indonesian) for its Multilingual Machine Translation system. This lexical database contains 50,000 words or terms [START_REF] Uchida | Interlingua. International Symposium on Multilingual Machine Translation (MMT-91)[END_REF].

Toward a specialized management system

A specialized management system for acception-based lexical databases must offer ways to automatise the management of the acception dictionary. It must also offer tools to define, index and manage the monolingual dictionaries.

2.1. Overview

The NADIA system has to detect potential errors in the acception database. Each potential error is given to a lexicographer who is in charge of the correction. This detection is independent of the linguistic structure of the monolingual dictionary. It consists in the detection of geometric inconsistencies in the relations between the elements of the database (entries, monolingual acceptions, interlingual acceptions).

The NADIA system also provides tools to help the users define, index, and manage a MLDB.

These tools depend on the linguistic structure of the different dictionaries. Hence, a linguist has to declare the structure of the articles of the dictionaries via a specialized language. To encode the linguistic information, the linguist can use predefined basic data structures (strings, lists, sets, trees, graphs, automata or Typed Feature Structures).

Several tools have been defined to help the users:

• Editor: this tool provides a default interface to edit items of a dictionary. It is also possible to customize the interface -this tool is a structured editor à la GRIF [START_REF] André | Structured Documents[END_REF]) . • Browser: this tool gives ways to browse through the database.

• Coherence checker: the linguist may define some coherence and integrity rules that apply on an article, on a dictionary or on the whole lexical database. These rules are checked and the result depends on the strength of the rule. • Defaulter: the linguist may also define rules to default entries of a dictionary. These rules can be applied in batch mode (in order to expand an existing dictionary) or in interactive mode (to help the lexicographer in the indexing process). • Import/export: the linguist may write importing and exporting procedures from the internal structure to an external format based on the SGML language and TEI guidelines.

Definition of the linguistic structures and coherence checking

As an example of the use of the NADIA management system for acception-based MLDB, we give the definition of the linguistic structure used in the Parax mock-up (see above). Then, we give some constraints that can be defined on this database.

3.1. Definition of Linguistic Structure (DLS) The linguistic structure used in Parax is inspired by the structures of the dictionaries of GETA's ARIANE system. It is a flat list of attribute-value pairs.

An example: Parax "DLS"

We give here a LISP form of the definition of the structures. Other dialects will be defined in order to hide this LISP form to the linguist (see below).

Definition of the database

Before defining the structures of a dictionary, the linguist has to define the database. This definition consists of a declaration of the dictionaries contained in it (here, a database called "Parax" with 4 monolingual dictionaries). For each dictionary, the linguist enters its name, its language, its owner, an optional comment and the classes used to code its entries and acceptions.

(define-database Parax :owner "GETA" :comment "This database is the same as the Parax mock-up defined by Etienne Blanc with hypercard."

:dictionaries (define-dictionary French :language "Français" :owner "GETA" :entry 'French-entry :acception 'French-acception) (define-dictionary English :language "English" :owner "GETA" :entry 'English-entry :acception 'English-acception) ...)

Structures of the French dictionary

The linguist defines the linguistic structures of the dictionaries with an object-oriented language. This task is analogous to the definition of classes in an object-oriented language, or to the definition of the structure of a structured document (à la GRIF, LaTeX or FrameMaker).

Two "classes" are already defined by the system: entry and acception. The linguist determines the structures to be associated with these objects. Here, we give the definition of the structure of the French dictionary.

The predefined class entry implements a tree with acceptions on its leaves. In the following example, an entry consists in a feature structure with two features (a graphic-form and a category).

(def-linguistic-class french-entry (entry) (feature-structure (graphic-form string) (category category) ))

(def-linguistic-class category () (one-of 'nc 'np 'vb 'vbimp 'vbrefl 'adj 'card 'deict 'repr 'sub 'coord))

The predefined class acception provides a way to code its relation with an interlingual acception. In the example, we define an acception as a feature structure with features representing derivation information (with the kind and the source of a derivation), information on valencies, etc.

(def-linguistic-class french-acception (acception) (feature-structure (cat category) ;; information on the derivation.

(drvv (feature-structure (deriv-kind (one-of 'naction 'nresult 'nlieu 'nagent 'ninstr 'adject 'adjpass 'adjpotpas 'adjresact 'verbe)) (deriv-from symbol))) (drvn (feature-structure (deriv-kind (one-of 'ncond 'nlieu 'ninstr 'ncollect 'nperson 'adjrelat 'adjqual 'verbe)) (deriv-from symbol))) (drva (feature-structure (deriv-kind (one-of 'nabst 'nperson 'verbe)) (deriv-from symbol))) ;; information on the valencies (val0 valency) (val1 valency) (val2 valency) (val3 valency) (val4 valency) ;; other information (gnr (any-of 'masc 'fem)) (nbr (any-of 'sg 'pl)) (aux (one-of 'être 'avoir)) (reciproque (one-of 'arg0-arg1 'arg1-arg1)) (aspect (one-of 'achevé 'inachevé 'début 'fin 'duratif 'fréquent 'instantané)) ))

(def-linguistic-class valency () (any-of 'nom 'à+nom 'avec+nom 'comme+nom 'contre+nom 'dans+nom 'de+nom 'en+nom 'entre+nom 'par+nom 'parmi+nom 'pour+nom 'sur+nom 'inf 'à+inf 'de+inf 'adj 'que+ind 'que+subj 'se-moy 'se-pass 'lieu-stat 'lieu-dyn 'manière 'zéro))

3.2. Coherence checking When the definition of the structure is done, the linguist can define coherence rules that will be applied on the entries.

Three kinds of rule

The linguist can define three kind of rules: • Integrity rules apply to an article of a dictionary.

They ensure that none of the article of the lexical database has an ill-formed configuration. • Local coherence rules apply to different articles of the same dictionary. They ensure that the dictionary is coherent. • Global coherence rules apply to different articles of different dictionaries of the lexical database. They ensure some coherence between dictionaries.

Three levels of coherence rules

The rules are associated with a strength:

• Warning: when the constraint is overridden, a message is passed to the lexicographer, but all treatments are allowed. The warning disappears as soon as the lexicographer validates the entry. These constraints are used to detect potential errors. • Delay: when the constraint is overridden, the lexicographer receives a message and some treatments are forbidden on the concerned entries. Incorrect entries will not be accessible by extraction requests. Interactive treatments such as browsing and editing are allowed. These constraints are used to handle temporarily incomplete entries. • Critical: these constraints can't be overridden. If a transaction overrides such a constraint, it will be canceled (rollback).

Example of coherence rule declaration

A coherence rule declaration is a method (in the sense of LISP/Common Lisp Object System) which is applied on all objects of the class defined in the parameter list. The body of the rule is a lisp expression that must return T or nil. If the result is nil, the exception mechanism corresponding to the strength of the rule is invoked.

Here is an example of an integrity rule for the French dictionary. This rule verifies that the derivation information is coherent with the category of the acception.

(def-integrity drv-cat-coherence ((acception french-acception) (dictionary french)) critical (cond ((is-one-of (cat acception) 'vb 'vbimp 'vbrefl) (and (empty-p (drvn acception)) (empty-p (drva acception)))) ((equal (cat acception) 'nc) (and (empty-p (drvv acception)) (empty-p (drva acception)))) ((equal (cat acception) 'adj)

(and (empty-p (drvv acception)) (empty-p (drvn acception)))) (t t)))

Conclusion

In this paper, we have presented our work on MLDBs. After a study of existing international projects and the definition and testing of the proposed lexical organization, we are currently defining and prototyping a specialized system for the management of acception-based MLDBs: the NADIA system.

This system introduces new interesting points. First, the acception-based lexical organization seems to offer the advantages of an interlingual approach while avoiding some of the theoretical and methodological problems of the knowledge-based approach [START_REF] Sérasset | Une approche par acceptions pour les bases lexicales multilingues[END_REF] . Second, it gives the linguist the possibility to freely define a collection of linguistic structures with a rather complete set of predefined data structures.

Our objective now is to integrate in this prototype features coming from research in the field of structured documents and a multidialectal facility in all tools, in order to provide lexicographers and other users with an interface in their mother tongue.

Fig. 1 :

 1 Fig. 1: illustration of the acception-based lexical organization

  Among these interlingual acceptions, 58 are subacceptions introduced by contrastive problems. The size of this mock-up is of the same order as that of Multilex.

		Entries	Acceptions
	French	135	484
	English	304	484
	German	388	509
	Russian	394	545
	This represents a total of 589 interlingual acceptions.

A 'rivière' is a rather small river flowing into another river. A 'fleuve' is a large river flowing into the see.

Acknowledgments

A part of this work was conducted in the Multilex project. I wish to thank all Multilex partners and GETA members for their support and feed-back.