V Crespo

A Maldonado

J A Galvis

P Kulkarni

I Guillamon

J G Rodrigo

H Suderow

S Vieira

S Banerjee

P Rodiere

Scanning microscopies of superconductors at very low temperatures

Keywords: Scanning Tunneling Microscopy and Spectroscopy, Vortex lattice, dichalcogenides

We discuss basics of scanning tunneling microscopy and spectroscopy (STM/S) of the superconducting state with normal and superconducting tips. We present a new method to measure the local variations in the Andreev reflection amplitude between a superconducting tip and the sample. This method is termed Scanning Andreev Reflection Spectroscopy (SAS). We also briefly discuss vortex imaging with STM/S under an applied current through the sample, and show the vortex lattice as a function of the angle between the magnetic field and sample's surface.

Introduction

Using Scanning Tunneling Microscopy and Spectroscopy (STM/S), one can, in principle, image many features of superconductors. In particular, the position of vortices and the symmetry of the lattice, as well as the spectroscopy inside and around vortex cores [START_REF] Fischer | Scanning tunneling spectroscopy of high-temperature superconductors[END_REF][START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF]. A vortex consists of supercurrents surrounding a magnetic core, and the Cooper pair wavefunction slips its phase by 2π in a ring around its center [START_REF] Abrikosov | On the Magnetic Properties of Superconductors of the Second Group[END_REF][START_REF] Blatter | Vortices in high-temperature superconductors[END_REF][START_REF] Brandt | The flux-line lattice in superconductors[END_REF]. The quantized finite circulation implies that the supercurrent velocity has to diverge at the center of the vortex. This divergence is avoided as the Cooper pair wavefunction drops continuously towards the center and becomes zero exactly at the vortex core. Materials Science and nanostructuring have been used to highlight different aspects of vortices, giving new physics or applications. For exam-1 * Corresponding author: hermann.suderow@uam.es ple, vortex lattice elasticity studies treat vortices as ropes with a rigid center in 3D or as disks in 2D, and are important in explaining vortex lattice disorder and melting [START_REF]Nanoscience and Engineering in Superconductivity[END_REF][START_REF] Giamarchi | Vortex phases[END_REF][START_REF] Banerjee | Vortex Nanoliquid in High-Temperature Superconductors[END_REF][START_REF] Guillamon | Direct observation of melting in a twodimensional superconducting vortex lattice[END_REF]. In anisotropic superconductors, non-local physics leads to anomalous vortex lattice symmetries [START_REF] Sakata | Imaging of a Vortex Lattice in YNi 2 B 2 C by Scanning Tunneling Spectroscopy[END_REF][START_REF] Eskildsen | Temperature dependence of the Flux Line Lattice Transition into Square Symmetry in Superconducting LuNi 2 B 2 C[END_REF]. Magnetism may increase vortex density or change its symmetry [START_REF] Eskildsen | Intertwined symmetry of the magnetic modulation and the flux-line lattice in the superconducting state of TmNi 2 B 2 C[END_REF][START_REF] Guillamon | Atomic resolution and vortex lattice studies of magnetic superconductors: A first approach in the nickel borocarbide TmNi 2 B 2 C[END_REF]. Conductance or T c oscillations, observed in regular arrays of dots or other nanostructures, highlight vortex pinning in terms of force balance [START_REF] Silhanek | Guided Vortex Motion and Vortex Ratchets in Nanostructured Superconductors[END_REF]. The observation of peaks in the density of states in the center of the vortex cores is understood in terms of the smooth changes of the Cooper pair wavefunction when approaching the center of the vortex [START_REF] Hess | Vortexcore structure observed with a scanning tunnelling microscope[END_REF][START_REF] Hayashi | Lowlying quasiparticle excitations around a vortex core in quantum limit[END_REF][START_REF] Nishimori | First Observation of the Fourfold-symmetric and Quantum Regime Vortex Core in YNi 2 B 2 C by Scanning Tunneling Microscopy and Spectroscopy[END_REF][START_REF] Guillamón | Intrinsic atomic-scale modulations of the superconducting gap of 2H-NbSe 2[END_REF].

In this paper we review some aspects of tunneling spectroscopy relevant for the study of superconductors, and discuss recent developments enabling new imaging possibilities, such as Scanning Andreev Reflection Spectroscopy. Measurements have been taken in several dilution and 3

He refrigerator

Preprint submitted to Elsevier 10 January 2012 STM/S set-ups described elsewhere [START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF][START_REF] Suderow | Compact very low temperature scanning tunneling microscope with mechanically driven horizontal linear positioning stage[END_REF][START_REF] Maldonado | Scanning tunneling spectroscopy under large current flow through the sample[END_REF]. Fig. 1. a) Calculated tunneling conductance between a normal tip and a s-wave BCS superconductor as a function of the bias voltage at Tc/65 (blue line) and at Tc/2 (red line). We use N S (E) as shown in the inset (with peak at ∆=1.76k B Tc=1meV) . b) Tunneling conductance between a tip having a Gaussian shaped peak of the density of states at the Fermi level, with a width of 15µeV (N T (E) as shown in the left inset) and a superconducting sample with the same density of states N S (E) as in a, at Tc/65 and at Tc/2. Inset shows the corresponding I(V) curves. c) Tunneling conductance between tip and sample with the same density of states as in a) at Tc/65 and at Tc/2. Bias voltage labels for c are given in mV at the bottom, and for a and b in mV at the top.

Spectroscopy with superconducting tips

One objective of a tunneling spectroscopy imaging experiment in a superconductor is to obtain with highest precision the energy dependence of the density of states of the superconductor N S (E) as a function of the position at all temperatures or magnetic fields. The tunneling current I between tip and sample can be written as

I(V ) ∝ dE[f (E -eV ) - f (E)]N T (E-eV )N S (E)
, and is the result of the convolution of the densities of states of tip N T and sample N S , weighted by the Fermi function f (E) [START_REF] Fischer | Scanning tunneling spectroscopy of high-temperature superconductors[END_REF][START_REF] Berthod | Electron tunneling and the local density of states[END_REF]. When the tip is made of a non superconducting metal, N T is energy-independent, and the differential tunneling conductance σ = dI/dV is simply N S (E) smeared by the Fermi function [START_REF] Fischer | Scanning tunneling spectroscopy of high-temperature superconductors[END_REF][START_REF] Song | A 10mk scanning probe microscopy facility[END_REF]. When k B T is low enough, σ is practically equal to N S (E), but when increasing the temperature, the tunneling conductance may be significantly smeared (Fig. 1 a), and measurement uncertainty coming from noise significantly influences the final de-convolution [START_REF] Crespo | Local Superconducting Density of States of ErNi 2 B 2 C[END_REF]. Consider now, for example, a tip with a δ function like sharp peak at the Fermi level, in an otherwise finite and energy independent density of states, such as the one produced by a localized state close to the tip [START_REF] Balatsky | Impurityinduced states in conventional and unconventional superconductors[END_REF][START_REF] Ternes | Spectroscopic manifestations of the Kondo effect on single adatoms[END_REF]. In that case, the I(V) curve directly reflects the density of states of the sample, with a peak at the gap edge. The conductance σ has correspondingly pronounced maxima and minima, and passes through zero exactly at the position of the peak in I(V). When increasing temperature, the current below the gap edge increases exponentially, reflecting the thermal behavior of the tail of the Fermi function [START_REF] Maldonado | Thermometry with a nearly temperature independent sensitivity using a normal-superconducting tunnel diode biased close to the superconducting gap[END_REF], but features in σ at the gap edge are largely unaffected (Fig. 1 b). If the density of states of the tip is well known and independent of temperature, then the de-convolultion of the sample's density of states from the I-V curve or from the tunneling conductance remains precise when increasing temperature. Localized state features which give peak shaped densities of states have been observed in some cases close to defects or impurities [START_REF] Balatsky | Impurityinduced states in conventional and unconventional superconductors[END_REF][START_REF] Ternes | Spectroscopic manifestations of the Kondo effect on single adatoms[END_REF][START_REF] Schmidt | Imaging the Fano lattice to hidden order transition in URu 2 Si 2[END_REF][START_REF] Aynajian | Visualizing the formation of the Kondo lattice and the hidden order in URu 2 Si 2[END_REF]. Tips with impurities located close to the apex could therefore give interesting results, although they still need to be realized in a controlled way.

A superconducting tip leads to even better results. The form and properties of the density of states of tips made of well known superconductors have been previously reported with detail [START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF][START_REF] Rodrigo | Superconducting nanobridges under magnetic fields[END_REF][START_REF] Rodrigo | On the use of STM superconducting tips at very low temperatures[END_REF][START_REF] Guillamón | Scanning tunneling spectroscopy with superconducting tips of Al[END_REF][START_REF] Suderow | A nodeless superconducting gap in Sr 2 RuO 4 from tunneling spectroscopy[END_REF][START_REF] Pan | Vacuum tunneling of superconducting quasiparticles from atomically sharp scanning tunneling microscope tips[END_REF][START_REF] Naaman | Fluctuation Dominated Josephson Tunneling with a Scanning Tunneling Microscope[END_REF][START_REF] Bergeal | Scanning Tunneling Spectroscopy on the Novel Superconductor CaC 6[END_REF][START_REF] Noat | Signatures of multigap superconductivity in tunneling spectroscopy[END_REF][START_REF] Suderow | Proximity effect and strong-coupling superconductivity in nanostructures built with an STM[END_REF]. The quasiparticle peaks located at the gap edge lead to a sharp anomaly at the sum of the tip and sample's superconducting gaps (Fig. 1c). When increasing temperature, the width of the corresponding anomaly does not change, making the determination of the LDOS of the sample through de-convolution accurate at all temperatures [START_REF] Rodrigo | STM study of multiband superconductivity in NbSe 2 using a superconducting tip[END_REF][START_REF] Crespo | Evolution of the Local Superconducting Density of States in ErRh 4 B 4 Close to the Ferromagnetic Transition[END_REF].

Scanning Andreev Reflection

Spectroscopy with superconducting tips.

Superconducting tips also allow, on the other hand, to probe the Josephson effect at the local level [START_REF] Rodrigo | On the use of STM superconducting tips at very low temperatures[END_REF][START_REF] Bergeal | Mapping the superconducting condensate surrounding a vortex in superconducting V3Si using a superconducting MgB 2 tip in a scanning tunneling microscope[END_REF][START_REF] Rodrigo | Scanning Tunnelling Spectroscopy of Vortices with Normal and Superconducting tips[END_REF], and they could enable designing, in future, local phase sensitive experiments [START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF][START_REF] Hanaguri | Coherence Factors in High-Tc Cuprate Probed by Quasi-Particle Scattering Off Vortices[END_REF].

There is yet another important feature which has not been explored until now. In particular, at the lowest temperatures, the current due to thermal excitations at voltages below the superconducting gap is exponentially small. Andreev reflection between tip and sample is always present, and the corresponding current depends exponentially on the tunneling barrier [START_REF] Andreev | Thermal conductivity of the intermediate state of superconductors[END_REF]. Therefore, reducing the tunnel barrier at the lowest temperatures leads to the observation of a small current at bias voltages below the superconducting gap which exponentially grows when the distance between tip and sample is reduced [START_REF] Blonder | Transition from metallic to tunneling regimes in superconducting microconstrictions: Excess current, charge imbalance, and supercurrent conversion[END_REF]. For instance, using a superconducting tip and a normal sample, with a tunneling conductance of around some tens of µS (i.e. some 0.1 G 0 , where G 0 is the quantum of conductance), the Andreev reflection accounts for the observation of a tunneling conductance of some per cent the high voltage conductance. When scanning with a superconducting tip a superconducting sample, Andreev reflection is further suppressed, as the process requires bouncing back and forth four electronic states, instead of the two states involved in a N-S Andreev reflection process [START_REF] Octavio | Subharmonic energy-gap structure in superconducting constrictions[END_REF].

Thus, scanning with, e.g. a superconducting tip of Pb, on a sample with superconducting and normal areas, leads to a conductance at a finite voltage below the superconducting gap which changes as a function of the position, being significantly larger on top of the normal areas. Of course, the experiment needs to be made at low enough temperatures to ensure that the result does not come from thermal excitations. Moreover, local variations in the magnetic field may result in changes in the tip's density of states which induce pair breaking effects, producing similarly a higher low bias conductance [START_REF] Guillamón | Scanning tunneling spectroscopy with superconducting tips of Al[END_REF]. Changing the tip-sample distance is the most effective way to separate Andreev processes from other variations of the low bias voltage conductance as a function of the position. In Fig. 2 we show results taken at a conductance of 17 µS (left panels of Fig. 2), and compare them with results taken at a conductance of 0.5 µS (right panels of Fig. 2), which is around 0.39% G 0 . While thermal excitations or pair breaking depend on the actual density of states of the tip and should be present at all tunneling tip-sample distances, Andreev reflections will decrease exponentially with distance. The left panel of Fig. 2b shows the vortex lattice of NbSe 2 at 0.1 T viewed by plotting as a function of the position the value of the Andreev conduc-tance. The signature of vortices is washed out when images are taken at low tunneling conductance, below µS, as shown in the right panel of Fig. 2b. When the image is built from the value of the conductance at 1 mV the observed features are due to changes in the local density of states, and have been discussed previously [START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF][START_REF] Rodrigo | Superconducting nanobridges under magnetic fields[END_REF][START_REF] Rodrigo | On the use of STM superconducting tips at very low temperatures[END_REF][START_REF] Guillamón | Scanning tunneling spectroscopy with superconducting tips of Al[END_REF][START_REF] Suderow | A nodeless superconducting gap in Sr 2 RuO 4 from tunneling spectroscopy[END_REF][START_REF] Pan | Vacuum tunneling of superconducting quasiparticles from atomically sharp scanning tunneling microscope tips[END_REF][START_REF] Naaman | Fluctuation Dominated Josephson Tunneling with a Scanning Tunneling Microscope[END_REF][START_REF] Bergeal | Scanning Tunneling Spectroscopy on the Novel Superconductor CaC 6[END_REF][START_REF] Noat | Signatures of multigap superconductivity in tunneling spectroscopy[END_REF]. Namely, the density of states at the center of the vortex core is high and leads to high conductance at 1mV when using a superconducting tip of Pb, and the characteristic star-shape found in NbSe 2 is observed in-between vortices. This observation is independent of the value of the tunneling conductance, as is shown in Fig. 2c.

This demonstrates that the localized electronic states inside the vortex cores can carry an Andreev current, which peaks at the vortex core. Note that Andreev reflection between a conventional s-wave superconductor and a metal with full spin polarization is not allowed. Thus, Scanning Andreev Spectroscopy can be developed in future as an effective tool to study local spin polarization of materials at very low temperatures.

Current drive scanning tunneling microscopy and spectroscopy.

Fig. 3. The pinned vortex lattice of NbSe 2 observed using conventional scanning tunneling spectroscopy with a normal tip under an applied current of 10 mA at a magnetic field of 0.5 T and at 4.2 K. To obtain the image, full I-V curves are taken at each position. The conductance at zero bias is plotted as a function of the position. At this temperature (4.2 K), the dependence of the I-V curves within vortex cores and in between vortices as a function of the applied current is mixed with the temperature smearing.

It is also important to image varying relevant thermodynamic and transport parameters, such as an applied current. Several STM/S experiments have been designed for topography measurements under an applied current. The arrangement requires to ground one side of the sample and apply a bias to the other side, with a current fixed by the resistance of the sample and the bias voltage [START_REF] Maldonado | Scanning tunneling spectroscopy under large current flow through the sample[END_REF][START_REF] Kirtley | Direct measurement of potential steps at grain boundaries in the presence of current flow[END_REF]. In order to study a superconductor, one requires knowledge of the full N S (E) dependence. Recently, we have developed new STM/S circuitry and methods to be able to make I-V measurements as a function of the position and the current using normal tips [START_REF] Maldonado | Scanning tunneling spectroscopy under large current flow through the sample[END_REF]. In Fig. 3 we show a vortex lattice image of NbSe 2 obtained by measuring at each position a full I-V curve, and applying a current of 10 mA through the sample, at 4.2 K. Corresponding current density is of 0.4 10 4 A/m 2 . Current flow can be expected to be homogeneous, because the London penetration depth λ is much larger than the coherence length ξ [START_REF] Guillamón | Intrinsic atomic-scale modulations of the superconducting gap of 2H-NbSe 2[END_REF]. Here we plot the normalized zero voltage conductance as a function of the position [START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF]. The vortex lattice is clearly viewed, so that the current is below the de-pinning value. We image therefore the pinned vortex lattice. Further measurements at lower temperatures, and as a function of the current and the magnetic field are under way.

5. Scanning tunneling microscopy and spectroscopy in a vector magnetic field.

76°70°6 0°F

ig. 4. Vortex lattice of NbSe 2 as a function of the angle of the applied magnetic field with respect to the surface. Images are taken at 0.5 T and 1.2K. Top panels show the real space images, and bottom panels their Fourier transforms. Red lines and points highlight the Bragg peaks of the vortex lattice. When increasing the angle, the hexagon elongates, and leaves practically a stripe like arrangement at 76 o . Grey lines and points show the position of Bragg peaks with smaller amplitude.

The control over the direction of the magnetic field is another important aspect which allows studying highly anisotropic samples. In particular, the vortex lattice in layered compounds is expected to show many peculiar features related to the modifications of intervortex potential when the magnetic field is turned from being perpendicular to the layers [START_REF] Brandt | Tilted and curved vortices in anisotropic superconducting films[END_REF][START_REF] Hess | Flux lattice and vortex structure in 2H-NbSe 2 in inclined fields[END_REF][START_REF] Buzdin | Crossover between magnetic vortex attraction and repulsion in thin films of layered superconductors[END_REF]. Recently, we have developed a dilution refrigerator three-axis vector magnet STM/S set-up, and could measure the angular dependence of the vortex lattice in NbSe 2 . The density of vortices decreases when the z-axis component of the magnetic field drops, following cos(θθ m ), with θ m being the misalignment of the normal to the surface of the sample with respect to the z component of the magnetic field (here θ m = 4 o ). As observed previously in Ref. [START_REF] Hess | Flux lattice and vortex structure in 2H-NbSe 2 in inclined fields[END_REF], the vortex lattice buckles, losing hexagonal symmetry, because it tries to orient one of the three high symmetry axis of the hexagon along the planar component of the magnetic field vector. Gradually, the hexagon is elongated and a zig-zag structure which ends up in stripe-like vortex arrangements is found. Although the vortices have been observed (Fig. 4), more precise and clear measurements are needed to show this interesting feature of the tilted vortex lattice.

Summary and outlook.

Scanning tunneling spectroscopy has evolved as a very efficient and complete microscopy of the superconducting state. Work in superconducting tips allow to increase considerably the precision in measuring the density of states of the sample, and provides for new modes of operation. Scanning Andreev Spectroscopy (SAS) appears as an efficient way to probe Andreev reflection at the very local level, and should lead to new imaging technique sensitive to the spin polarization of the tunneling current. Further developments in measurements as a function of an applied current (CD/STS), and in a vector magnetic field, will enable new imaging possibilities. The full potential of Materials Science, with anisotropies of single crystalline materials, and of engineered Nanoscience, with phenomena related to vortex flow in different geometries and arrangement of nanostructures in superconducting samples, come into the realm of the imaging possibilities of STM/S.

Fig. 2 .

 2 Fig.2. Scanning Andreev Spectroscopy of the vortex lattice of NbSe 2 using a tip of Pb at 0.3 K. In left panels we show experiments on the vortex lattice with a short tip-sample distance (conductance at 4 mV is of 17µS, Andreev reflection is observed), and in the right panels we show experiments made using a larger tip-sample distance (conductance at 4 mV is of 0.5µS, Andreev reflection is suppressed due to the high tunneling barrier). In a) we show the tunneling conductance at a vortex core (red points), and in between vortices (blue points). Higher conductance at the vortex cores is due to Andreev reflection between the superconducting tip and the NbSe 2 sample, only visible when tip-sample distance is short enough (here at 17µS). Violet and green lines show the voltages at which the spectroscopic images in b anc c are built of. The images built with the tunneling conductance at 0.5 mV (shown in b in violet frames), clearly show the vortex lattice if the tip-sample distance is short (left panel, 17µS) due to Andreev reflection between the superconducting tip and the normal vortex core. The image built with the tunneling conductance at the same voltage is featureless when the tunneling conductance is low (right panel, 0.5µS). Color code is shown as a bar at the center using the same scale as in the y axis of a, namely the tunneling conductance normalized to the value at high voltages. In c we show the images constructed from the data at 1 meV, using the color code from the bar at the center. Observed features (star shaped vortex core) do not depend on the tip-sample distance, and have been discussed in previous publications[START_REF] Rodrigo | Superconducting nanostructures fabricated with the scanning tunnelling microscope[END_REF][START_REF] Rodrigo | Superconducting nanobridges under magnetic fields[END_REF][START_REF] Rodrigo | On the use of STM superconducting tips at very low temperatures[END_REF][START_REF] Guillamón | Scanning tunneling spectroscopy with superconducting tips of Al[END_REF][START_REF] Suderow | A nodeless superconducting gap in Sr 2 RuO 4 from tunneling spectroscopy[END_REF][START_REF] Pan | Vacuum tunneling of superconducting quasiparticles from atomically sharp scanning tunneling microscope tips[END_REF][START_REF] Naaman | Fluctuation Dominated Josephson Tunneling with a Scanning Tunneling Microscope[END_REF][START_REF] Bergeal | Scanning Tunneling Spectroscopy on the Novel Superconductor CaC 6[END_REF][START_REF] Noat | Signatures of multigap superconductivity in tunneling spectroscopy[END_REF].

Acknowledgements

We specially acknowledge support from NES program. This work was also supported by the Spanish MEC (Consolider Ingenio Molecular Nanoscience CSD2007-00010 and FIS2008-00454 and ACI2009-0905 programs) and by the Comunidad de Madrid through program Nanobiomagnet. The Laboratorio de Bajas Temperaturas is associated to the ICMM of the CSIC.


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

Francis Brunet-Manquat
email: francis.brunet-manquat@imag.fr

Elena Chiocchetti
email: elena.chiocchetti@eurac.edu

Multilingual Legal Terminology on the Jibiki Platform: The LexALP Project

This paper presents the particular use of "Jibiki" (Papillon's web server development platform) for the LexALP 1 project. LexALP's goal is to harmonise the terminology on spatial planning and sustainable development used within the Alpine Convention 2 , so that the member states are able to cooperate and communicate efficiently in the four official languages (French, German, Italian and Slovene). To this purpose, LexALP uses the Jibiki platform to build a term bank for the contrastive analysis of the specialised terminology used in six different national legal systems and four different languages. In this paper we present how a generic platform like Jibiki can cope with a new kind of dictionary.

Introduction

One of the most time-consuming hindrances to supranational law drafting and convention negotiation is the lack of understanding among negotiators and technical writers. This is not only due to the fact that different languages are involved, but mainly to the inherent differences in the legal systems. Countries that speak the same language (like France and part of Switzerland) may use the same word to represent different legal concepts3 , as defined in their respective legal traditions. The same concept may be referred to in different ways according to the legal system4 . Also, terms that may superficially seem to be translations of each other can represent different legal notions 5 .

In order to concretely address these problems, several institutions representing translators, terminologists, legal experts and computational linguists joined in the LexALP project, co-funded by EU's INTERREG IIIb Alpine Space programme. The objective of the project is to compare the specialised terminology of six different national legal systems (Austria, France, Germany, Italy, Switzerland and Slovenia) and three supranational systems (EU law, international law and the particular framework of the Alpine Convention) in the four official languages of the Al-pine Convention, which is an international framework agreement signed by all countries of the Alpine arc and the EU. This contrastive analysis serves as a basis for the work of a group of experts (the Harmonising Group) who will determine translation equivalents in French, Italian, German and Slovene (one-toone correspondence) in the fields of spatial planning and sustainable development for use within the Convention, thus optimising the understanding between the Alpine states at supranational level.

The tools that are to be developed for these objectives comprise a corpus bank and a term bank. The corpus bank is developed by adapting the bistro system [START_REF] Streiter | BISTRO: Data structure, term tools and interface[END_REF][START_REF] Streiter | BISTRO, the online platform for terminology management: structuring terminology without entry structures[END_REF]. The term bank is based on the Jibiki plat-form [START_REF] Mangeot | Construction collaborative d'une base lexicale multilingue, le projet Papillon[END_REF][START_REF] Sérasset | A generic collaborative platform for multilingual lexical database development[END_REF].

This paper details the way the Jibiki platform is used in order to cope with a new dictionary structure. The platform provides dictionary access and edition services without any new and specific development.

After a brief overview of the Jibiki platform, we describe the choices made by the LexALP team for the structure and organisation of their term bank. Then, we show how this structure is described using Jibiki metadata description languages. Finally, we give some details on the resulting LexALP Information System.

2 Jibiki, The Papillon Dictionary Development Platform

Overview

The Jibiki platform has been designed to support the collaborative development of multilingual dictionaries. This platform is used as the basis of the Papillon project web site 6 . This platform offers several services to its users:

• access to many different dictionaries from a single easy to use query form,

• advance search for particular dictionary entries through an advanced search form,

• creation and edition of dictionary entries.

What makes the Jibiki platform quite unique is the fact that it provides these services regardless of the dictionary structure. In other words it may be used by any dictionary builder to give access and collaboratively edit any dictionary, provided that the resulting dictionary will be freely accessible online.

Jibiki Platform Architecture

The Jibiki platform is a framework used to set up a web server dedicated to the collaborative development of multilingual dictionaries. All services provided by the platform are organised as classical 3-tier architectures with a presentation layer (in charge of the interface with users), a business layer (which provides the services per se) and a data layer (in charge of the storage of persistent data).

In order to adapt the Jibiki platform to a new dictionary, the dictionary manager does not have 6 http://www.papillon-dictionary.org/ • a description of the dictionary volumes and their relations,

• a mapping between the envisaged dictionary structure and a simple hypothetical dictionary structure (called CDM) 7 ,

• the definition of the XML structure of each envisaged dictionary volume by way of XML schemas,

• the development of a specific edition interface as a standard xhtml form (that can be adapted from an automatically generated draft).

3 The LexALP Terminology Structure

Overview

The objective of the LexALP project is to compare the specialised terminology of six different national legal systems and three supranational systems in four different languages, and to harmonise it, thus optimising communication between the Alpine states at supranational level. To achieve this objective, the terminology of the Alpine Convention is described and compared to the equivalent terms used in national legislation. The resulting terminology entries feed a specific term bank that will support the harmonisation work.

As the project deals with legal terms, which refer to concepts that are proper of the considered national law or international convention, equivalence problems are the norm, given that concepts are not "stable" between the different national legislations. Standard terminology techniques for other fields can not be applied to the field of law, where the standardisation approach [START_REF] Felber | Manuel de terminologie[END_REF][START_REF] Felber | Terminology research: Its relation to the theory of science[END_REF] is not applicable. For this, we chose to use "acceptions" as they are defined in the Papillon dictionary [START_REF] Sérasset | Interlingual lexical organisation for multilingual lexical databases in nadia[END_REF] to represent the equivalence links between concepts of the different legal systems [START_REF] Arntz | Terminological equivalence and translation[END_REF]. The example given in figure 2 shows a concept defined in the Alpine Convention. This concept has the same definition in the four languages of the Alpine Convention but is expressed by different denominations. The Alpine Convention also uses the terms "circulation intra-alpine" or "transport intra-alpin" which are identified as synonyms by the terminologist.

This illustrates the first goal of the LexALP project. In different texts, the same concept may be realised by different terms in the same language. This may lead to inefficient communication. Hence, a single term has to be determined as part of a harmonised quadruplet of translation equivalents. The other denominations will be represented in the term bank as non-harmonised synonyms in order to direct drafting and translating within the Alpine Convention towards a more clear and consistent terminology use for interlingual and supranational communication.

In this example, the lexicographers and jurists did not identify any existing concept in the different national laws that could be considered close enough to the concept analysed. This is coherent with the minutes from the French National Assembly which clearly states that the term "trafic intraalpin" (among others) should be clarified by a declaration to be added to the Alpine Convention.

Figure 3 shows an analogous quadrilingual example where the Alpine Convention concept may be related to a legal term defined in the French laws. In this example the French term is distinguished from the Alpine Convention terms, because these concepts belong to different legal sys- This illustrates the second goal of the project, which is to help with the fine comprehension of the Alpine Convention and with the detailed knowledge necessary to evaluate the implementation and implementability of the convention in the different legal systems.

As a by-product of the project, one can see that there is an indirect relation between concepts from different national legal systems (by way of their respective relation to the concepts of the Alpine Convention). However, establishing these indirect relations is not one of the main objectives of the LexALP project and would require more direct contrastive analysis.

Macro-and Micro-Structures

The LexALP term bank consists in 5 volumes (for French, German, Italian, Slovene and English) containing all term descriptions (grammatical information, definition, contexts etc.). The translation links are established through a central acception volume. Figure 2 and3 show examples of terms extracted from the Alpine Convention, synonymy links in the French and Italian volumes, as well as inter-lingual relations by way of acceptions.

All language volumes share the same microstructure. This structure is stored in XML.

Figure 4 shows the xml structure of the French term "trafic intra-alpin", as defined in the Alpine Convention. The term entry is associated to a unique identifier used to establish relations between volume entries. Each term entry belongs to one (and only one) legal system. The example term belongs to the Alpine Convention legal <entry id="fra.trafic_intra-alpin.1010743.e" lang="fra" legalSystem="AC" process_status="FINALISED" status="HARMONISED"> <term>trafic intra-alpin</term> <grammar>n.m.</grammar> <domain>Transport</domain> <usage frequency="common" geographical-code="INT" technical="false"/> <relatedTerm isHarmonised="false" relationToTerm="Synonym" termref=""> transport intra-alpin </relatedTerm> <relatedTerm isHarmonised="false" relationToTerm="Synonym" termref=""> circulation intra-alpine system8 (code AC). The set of known legal systems includes of course countries belonging to the Alpine Space (Austria, France, Germany, Italy, Slovenia and Switzerland9 ) but also international treaties or conventions. The entry also bears the information on its status (harmonised or rejected) and its process status (to be processed, provisionally processed or finalised).

The term itself and its part of speech is also given, with the general domain to which the term belongs, along with some usage notes. In these usage notes, the attribute geographical-code allows for discrimination between terms defined in national (or federal) laws and terms defined in regional laws as in some of the countries involved legislative power is distributed at different levels.

Then the term may be related to other terms. These relations may lead to simple strings of texts (as in the given example) or to autonomous term entries in the dictionary by the use of the termref attribute. The relation itself is specified in the relationToTerm attribute. The current schema allows for the representation of relations between concepts (synonymy, hyponymy and hyperonymy), as well as relations between graphies (variant, abbreviation, acronym, etc.).

Then, a definition and a context may be given. Both should be extracted from legal texts, which must be identified in the source field.

An interlingual acception (or axie) is a place holder for relations. Each interlingual acception may be linked to several term entries in the language volumes through termref elements and to other interlingual acceptions through axieref elements, as illustrated in figure 5.

LexALP Information System

Overview

Building such a term bank can only be envisaged as a collaborative work involving terminologists, translators and legal experts from all the involved countries. Hence, the LexALP consortium has set up a centralised information system that is used to gather all textual and terminological data.

This information system is organized in two main parts. The first one is dedicated to corpus management. It allows the users to upload legal texts that will serve to bootstrap the terminology work (by way of candidate term extraction) and to let terminologists find occurrences of the term they are working on, in order for them to provide definitions or contexts.

The second part is dedicated to terminology work per se. It has been developed with the Jibiki platform described in section 2. In this section, we show the LexALP Information System functionality, along with the metadata required to implement it with Jibiki.

Dictionary Browsing

The first main service consists in browsing the currently developed dictionary. It consists in two different query interfaces (see figures 6 and 7) and a unique result presentation interface (see figure 10). In the provided examples, the user of the system specifies an entry (a term), or part of it, and a language in which the search is to be done. The expected behaviour may only be achieved if :

• the system knows in which volume the search is to be performed,

• the system knows where, in the volume entry, the headword is to be found,

• the system is able to produce a presentation for the retrieved XML structures.

However, as the Jibiki platform is entirely independent of the underlying dictionary structure <volume-metadata [...] dbname="lexalpfra" dictname="LexALP" name="LexALP_fra" source-language="fra"> <cdm-elements> <cdm-entry-id index="true" xpath="/volume/entry/@id"/> <cdm-headword d:lang="fra" index="true"

xpath="/volume/entry/term/text()"/> <cdm-pos d:lang="fra" index="true"

xpath="/volume/entry/grammar/text()"/> (which makes it highly adaptable), the expected result may only be achieved if additional metadata is added to the system.

These pieces of information are to be found in the mandatory dictionary descriptor. It consists in a structure defined in the Dictionary Metadata Language (DML), as set of metadata structures and a specific XML namespace defined in [START_REF] Mangeot | Environnements centralisés et distribués pour lexicographes et lexicologues en contexte multilingue[END_REF].

Figure 8 gives an excerpt of this descriptor. The metadata first identify the dictionary by giving it a name and a type. In this example the dictionary is a pivot dictionary (DML also defines monolingual and bilingual dictionary types). The descriptor also defines the set of source and target languages. Finally, the dictionary is defined as a set of volumes, each volume being described in another file. As the LexALP dictionary is a pivot dictionary, there should be a volume for the artificial language axi, which is the pivot volume.

Figure 9 shows an excerpt of the description of the French volume of the LexALP dictionary. After specifying the name of the dictionary, the descriptor provides a set of cdm-elements. These elements are used to identify standard dictionary elements (that can be found in several dictionaries) in the specific dictionary structure. For instance, the descriptor tells the system that the headword of the dictionary (cdm-headword) is to be found by applying the specified xpath10 to the dictionary structure.

With this set of metadata, the system knows that: • the requested headword will be found in the text of the term element of the volume entry element, Hence, the system can easily perform a request and retrieve the desired XML entries. The only remaining step is to produce a presentation for the user, based on the retrieved entries. This is achieved by way of a xsl 11 stylesheet. This stylesheet is specified either on the dictionary level (for common presentations) or on the volume level (for volume specific presentation).

In the given example, the dictionary administrator provided two presentations called LexALP (the default one, as shown in figure 10) and short-list, both of them defined in the dictionary descriptor.

This mechanism allows for the definition of presentation outputs in xhtml (for online browsing) or for presentation output in pdf (for dictionary export and print).

Dictionary Edition

The second main service provided by the Jibiki platform is to allow terminologists to collaboratively develop the envisaged dictionary. In this sense, Jibiki is quite unique as it federates, on the very same platform the construction and diffusion of a structured dictionary.

As before, Jibiki may be used to edit any dictionary. Hence, it needs some metadata information in order to work:

• the complete definition of the dictionary entry structures by way of an XML schema,

• a template describing an empty entry structure, 11 XSL is a standard way to transform an XML structure into another structure (XML or not). • a xhtml form used to edit a dictionary entry structure (which can be adapted from an automatically generated one).

When this information is known, the Jibiki platform provides a specific web page to edit a dictionary entry structure. As shown in figure 11, the XML structure is projected into the given empty XHTML form. This form is served as a standard web page on the client browser. After manual editing, the resulting form is sent back to the Jibiki platform as CGI 12 data. The Jibiki platform decodes this data and modifies the edited XML structure accordingly. Then the process iterates as long as necessary. Figure 12 shows an example of such a dynamically created web page.

After each update, the resulting XML structure is stored in the dictionary database. However, it is not available to other users until it is marked as finished by the contributor (by clicking on the save button). If the contributor leaves the web page without saving the entry, he will be able to retrieve it and finish his contribution later. At each step of the contribution (after each update) and at each step of dictionary editing (after each save), the previous state is saved and the contributor (or the dictionary administrator) is able to browse the history of changes and to revert the entry to a previous version.

Conclusion

In this article we give some details on the way the Jibiki platform allows the diffusion and the online editing of a dictionary, regardless of his structure (monolingual, bilingual (directed or not) or multilingual (multi-bilingual or pivot based)).

Initially developed to support the editing of the Papillon multilingual dictionary 13 , the Jibiki platform proved useful for the development of other very different dictionaries. It is currently used for the development of the GDEF (Grand Dictionnaire Estonien-Franc ¸ais) project 14 an Estonian French bilingual dictionary. This article also shows the use of the platform for the development of a European term bank for legal terms on spatial planning and sustainable development in the LexALP project.

Adapting the Jibiki platform to a new dictionary requires the definition of several metadata information, taking the form of several XML files. While not trivial, this metadata definition does not require any competence in computer development. This adaptation may therefore also be done by experimented linguists. Moreover, when the dictionary microstructure needs to evolve, this evolution does not require any programming. Hence the Jibiki platform gives linguists great liberty in their decisions.

Another positive aspect of Jibiki is that it integrates diffusion and editing services on the same platform. This allows for a tighter collaboration between linguists and users and also allows for the involvement of motivated users to the editing process.

The Jibiki platform is freely available for use by any willing team of lexicographer/terminologists, provided that the resulting dictionary data will be freely available for online browsing.

In this article, we also presented the choices made by the LexALP consortium to structure a term bank used for the description and harmonisation of legal terms in the domain of spacial plan-13 http://www.papillon-dictionary.org/ 14 http://estfra.ee/ ning and sustainable development of the Alpine Space. In such a domain, classical techniques used in multilingual terminology cannot be used as the term cannot be defined by reference to a stable/shared semantic level (each country having its own set of non-equivalent legal concepts).

Figure 1 :

 1 Figure 1: The Jibiki platform general architecture

Figure 2 :

 2 Figure 2: An Alpine Convention concept in four languages

Figure 3 :

 3 Figure 3: A quadrilingual term extracted from the Alpine Convention with reference to its equivalent at French national level

Figure 4 :

 4 Figure 4: XML form of the term "trafic intraalpin".

Figure 5 :

 5 Figure 5: XML form of the interlingual acception illustated in figure 2.

Figure 6 :

 6 Figure 6: Simple search interface present on all pages of the LexALP Information System

  Figure 9: Excerpt of a volume descriptor

Figure 7 :

 7 Figure 7: Advanced search interface

Figure 11 :

 11 Figure 11: Basic flow chart of the editing service

Figure 10 :

 10 Figure 10: Query result presentation interface

Legal Language Harmonisation System for Environment and Spatial Planning within the Multilingual Alps

http://www.convenzionedellealpi.org

E.g.: In the German-speaking province of Bolzano Italy the Landeshauptmann is the president of the provincial council, with much more limited competence that the Austrian Landeshauptmann, who is head of one of the states (Bundesland) that are part of the Austrian federation.

See for instance the European Union use of chien drogue while French legislation calls them chien renifleur.

For example, in Italy an elezione suppletiva is commonly held whenever an elected deputy or senator either resigns or dies. In Germany in such cases the first non-elected candidate is called to parliament. Ersatzwahlen are a rare phenomenon, foreseen in some very specific cases.

Strictly speaking, the Alpine Convention does not constitute a legal system per se.

9 Also Liechtenstein and Monaco are parties to the Alpine Convention, however, their legal systems are not terminologically processed within LexALP.

an xpath is a standard way to extract a sub-part of any XML structure


Verena Lyding

Elena Chiocchetti

Gilles Sérasset

Francis Brunet-Manquat

The LexALP Information System: Term Bank and Corpus for Multilingual Legal Terminology Consolidated

Standard techniques used in multilingual terminology management fail to describe legal terminologies as they are bound to different legal systems and terms do not share a common meaning. In the LexALP project, we use a technique defined for general lexical databases to achieve cross language interoperability between languages of the Alpine Convention. In this paper we present the methodology and tools developed for the collection, description and harmonisation of the legal terminology of spatial planning and sustainable development in the four languages of the countries of the Alpine Space.

Introduction

The aim of the LexALP project is to harmonise the terminology used by the Alpine Convention, both for internal purposes and for communication among the member states. The Alpine Convention is an international treaty signed by all states of the Alpine territory (France, Monaco, Switzerland Liechtenstein, Austria, Germany, Italy and Slovenia) for the protection of landscape and sustainable development of this mountain area 1 . The member states speak four different languages, namely French, German, Italian, and Slovene and have different legal systems and traditions.

Hence arises the need for a systematization and uniformation of terminology and clear translation equivalence in all four languages. For this reason, the project intends to provide all 1 cf. also http: www.alpenkonvention.org stakeholders and the wider public with an information system which combines three main components, a terminology data base, a multilingual corpus and the relative bibliographic data base. In this way the manually revised, elaborated and validated (harmonised) quadrilingual information on the legal terminology (i.e. complete terminological entries) will be closely interacting with a facility to dynamically search for additional contexts in a relevant set of legal texts in all languages and for all main legal systems involved.

Multilingual legal information system

The information system for the terminology of the Alpine Convention, with a specific focus on spatial planning and sustainable development, will give the possibility to search for relevant terms and their (harmonised or rejected) translations in all 4 official languages of the Alpine Convention in the first module, the term bank. Next to retrieving synonyms and translation equivalents within each legal system, the user will be provided with a representative context and a valid definition of the concept under consideration. Source information will be provided for each text field in the terminological entry.

Via a link from the terminological data base to the second module, the corpus facility, the information system will give the possibility to search the corpus for further contexts.

Finally, both term bank and corpus will be interacting with a third module, the bibliographic database, so as to allow retrieving full information on text excepts cited in the term bank and to store important meta data on corpus documents.

Terminological data

Data categories and motivations

The data categories present in the terminology database allow entering and organising relevant information on the concept under analysis. The term bank interface allows entering of the following terminological data categories: denomination/term, definition, context, note, sources (text fields), grammatical information to the term, harmonisation status, processing status, geographical usage, frequency and domain, according to the appositely elaborated domain classification structure 2 (pull down menus). Again by means of pull-down menus the terminologist will be able to signal to the users which terms are already processed (i.e. checked by legal experts), harmonised or rejected and -most important -to which legal system they belong (the menu geographical usage allows to specify this information). Furthermore it is possible to specify synonyms, short forms, abbreviations etc. in the terminological entry and, if necessary, link them to the relative full information already present in the term bank (however, no direct access to these linked data is possible, this must be done via the search interface). Finally, the terminologist is given the possibility of writing general comments to the entry. At the very end of one language entry the terminologist can decide whether to release the data to the public (by clicking on the button 'finish') or keep it for further finetuning (button 'update').

Each term is created in its 'language volume' and described by means of all necessary information. As soon as one or all equivalents in the other languages are available too, the single entries can be linked to each other with the help of an axie (see detailed description below).

Searches can be done for all languages or on a user-defined selection of source and target languages. Presently the database allows global searching in all text fields and filtering by source, author, date of creation, as well as by axie name and ids. Results can be displayed in full form, as a short list of terms only or in XML. Some export/import functions are granted.

As the term bank serves mainly the scope of diffusing harmonised terminology, the four translation equivalents (validated by a group of experts) are displayed together, whereas rejected synonyms are displayed separately for each search language. In this way the user may well 2 See also 4.1 look for a non validated synonym and find it in the database but be warned as to which is the preferred term and its harmonised equivalents in the other languages. Figure 1 shows such a situation where the French rejected term "transport intra-alpin" is linked to the harmonised term "trafic intra-alpin".

Monolingual data

The LexALP term bank consists in 5 volumes for French, German, Italian, Slovene and English (no data is being entered for this fifth language at the moment), which contain the term descriptions. The set of data categories is represented in an XML structure that follows a common schema.

<entry id="fra.trafic_intra-alpin.1010743.e" lang="fra" legalSystem="AC" process_status="FINALISED" status="HARMONISED"> <term>trafic intra-alpin</term> <grammar>n.m.</grammar> <domain>Transport</domain> <usage frequency="common" geographical-code="INT" technical="false"/> <relatedTerm isHarmonised="false" relationToTerm="Synonym" termref="fra.transport_intra-alpin…"/> <relatedTerm isHarmonised="false" relationToTerm="Synonym" termref="fra.circulation_intra-…"/> <definition> Each entry represents a unique term/meaning. Terms with the same denomination, but belong-ing to different legal systems have, de facto, different meanings. Hence, different entries are created. Terms with different denominations but conveying the same 'meaning' (concept) are also represented using different entries 3 . In this case, the entries are linked through a synonymy relation.

Figure 2 shows the XML structure of the French term "trafic intra-alpin", as defined in the Alpine Convention. The term entry is associated to a unique identifier used to establish relations between volume entries.

The example term belongs to the Alpine Convention legal system 4 (code AC). The entry also bears the information on its status (harmonised or rejected) and its processing status (to be processed, provisionally processed or finalised).

In addition, a definition (along with its source) and a context may be given. The definition and context should be extracted from a legal text, which must be identified in the source field.

Achieving language/legal system interoperability

As the project deals with several different legal terms, standard techniques used in multilingual terminology management need to be adapted to the peculiarities of the specialised language of the law. Indeed, terms in different languages are (generally) defined according to different legal systems and these legal systems cannot be changed. Hence, it is not possible to define a common 'meaning' that could be used as a pivot for language interoperability 5 . In this respect, legal terminology is closer to general lexicography than to standard terminology.

In order to achieve language/legal system interoperability we had several options that are used in general lexicography.

Using a set of bilingual dictionaries is not an option here, as we have to deal with at least 16 3 Variants, acronyms, etc. are not considered as different denominations. 4 Strictly speaking, the Alpine Convention does not constitute a legal system per se. 5 Consider for instance the difference between the Italian and the Austrian concepts of journalists' professional confidentiality. Whereas the heimnis underlines that the journalist can refuse to witness in court in order to keep the professional secret, in Italy the segreto giornalistico must obligatorily be lifted on a judge's request. The two concepts have overlapping meanings in the two states, however, they diverge greatly with respect to the behaviour in court. language/legal system couples (with alpine Convention and EU levels, but without taking into account regional levels). Moreover, such a solution will not reflect the multilingual aspect of the Alpine Convention or the Swiss legal system. Finally, building bilingual volumes between the French and Italian legal systems is far beyond the objectives of the LexALP project.

Another solution would be to use an "Eurowordnet like" approach [START_REF] Vossen | Introduction to EuroWordNet[END_REF] where a specific language/legal system is used as a pivot and elements of the other systems are linked by equivalent or near-equivalent links. As such an approach artificially puts a language in the pivot position, it generally leads to an "ethnocentric" view of the other languages. The advantage being that the architecture uses the bilingual competence of lexicographers to achieve multilingualism.

In this project, we chose to use 'interlingual acceptions' (a.k.a. axies) as defined in [START_REF] Sérasset | Interlingual Lexical Organisation for Multilingual Lexical Databases in NADIA[END_REF] to represent such complex contrastive phenomena as generally described in general lexicography work. In this approach, each 'term meaning' is associated to an interlingual acception (or axie). These axies are used to achieve interoperability as a pivot linking terms of different languages bearing the same meaning.

However, as we are dealing with legal terms (bound to different legal systems), it is generally not possible to find terms in different languages that bear the same meaning. In fact such terms can only be found in the Alpine Convention (which is considered as a legal system expressed in all the considered languages). Hence, we use these terms to achieve interoperability between languages. In this aspect, we are close to Eurowordnet's approach as we use a specific legal system as a pivot, but in our case the pivot itself is generally a quadrilingual set of entries.

These harmonised Alpine Convention terms are linked through an interlingual acception. An axie is a place holder for relations. Each interlingual acception may be linked to several term entries in the languages volumes through termref elements and to other interlingual acceptions through axieref elements, as illustrated in Figure 3. The termref relation establishes a direct translation relation between these harmonised equivalents. Then, national legal terms are indirectly linked to Alpine Convention terms through the axieref relation as illustrated in Figure 4.

Corpus

Corpus content

The corpus comprises around 3000 legal documents of eight legal systems (Germany, Italy, France, Switzerland, Austria, Slovenia, European law and international law with the specific framework of the Alpine Convention,) (see table 1). Documents of the supranational level are provided in up to four languages (subject to availability). National legislation is generally added in the national language (monolingual documents) and in case of Switzerland (multilingual documents) in the three official languages of that nation (French, German and Italian).

The documents are selected by legal experts of the respective legal systems following predefined criteria:

• entire documents (no single paragraphs or excerpts etc.);

•

strong relevance to the subjects 'spatial planning and sustainable development' as described in art. 9 of the relative Alpine Convention Protocol;

• primary sources of the law for every system at national and international/EU level, i.e. normative texts only (laws, codes etc.);

• latest amendments and versions of all legislation (at time of collection: June -August 2005);

• terminological relevance.
Each document is classified according to the following (bibliographical) categories: full title, short title, abbreviation, legal system, language, legal hierarchy, legal text type, subfield (1, 2 and 3), official date, official number, published in official journal (date, number, page), … The bibliographical information of all documents is stored in a database and can at any time be consulted by the user.

The subfields have been elaborated and selected by a team of legal experts, taking into account the classification specificities followed by the Alpine Convention and the need to classify texts from several different legal systems according to one common structure. For this reason, the legal experts have subdivided the fields spatial planning and sustainable development into 5 main areas, in accordance with the Alpine Convention Protocol dealing with these subjects and subsequently adopted an EU-based model for further subdividing the 5 main topics in such a way that all countries involved could classify their selected documents under a maximum of 3 main items, the first of which must be indicated obligatorily. This classification allows an easy selection of all subsets of documents according to subject field.

Structural organization of corpus data

Collected in raw text format (one file for each legal text) the documents are first transformed into XML-structured files and in a second step inserted into the database.

The XML-annotation is done in compliance with the Corpus Encoding Standard for XML (XCES) 6 . Slightly simplified, the provided schema 7 serves to add structural information to the documents. Each text is segmented into subsections like: preamble, chapter, section, para-6 http://www.cs.vassar.edu/XCES/ 7 http://www.cs.vassar.edu/XCES/schema/xcesDoc.xsd graph, title and sentence. Furthermore, a link to the classification data (bibliographic data base) is inserted and, in case of multilingual documents, alignment is done at sentence level.

The XML-annotated documents hold all the information needed for the insertion into the corpus database, such as structural mark-up and bibliographical information. The full text documents are transformed into sets of database entries, which can be imported into the database.

Technical organization of corpus data

Following the bistro approach as realized for the Corpus Ladin dl'Eurac (CLE) [START_REF] Streiter | CLE, an aligned Tri-lingual Ladin-Italian-German Corpus[END_REF]) the corpus data is stored in a relational database (PostgreSQL). The information present in the XML-annotated documents is distributed among four main tables: document_info, cor-pus_words, corpus_structure, corpus_alignment.

The four tables can be described as follows: document_info: This table holds the metainformation about the documents; each category (like full title, short title, abbreviation, legal system, language, etc.) is represented by a separate column. For each legal document one entry (one row) with unique identification number is added to the table. These identification numbers are cited in the XML-header of the corpus documents.

corpus_words: This table holds the actual text of the collected documents. Instead of storing entire paragraphs as it was done during the creation of CLE, for this corpus a different approach is being tested. Every annotated text is split into an indexed sequence of words, starting with counter one. Once inserted into the database a text is stored as a set of tuples composed of word, position in text and document id (as a reference to the document information).

corpus_structure: This table holds all information about the internal structure of the documents. Titles, sentences, paragraphs etc. are stored by indicating starting and ending point of the section. For each segment a tuple of segment type, segment id, starting point (indicated by the index of the first word), ending point (indicated by the index of the last word) and document id is added.

corpus_alignment: This table defines the alignment of multilingual documents. By providing one column for each language the texts are aligned via the document ids or via the ids of single segments.

The tables are interconnected by explicitly stated references. That means that the columns of one table refer to the values of a certain column of another table. As shown in figure 8 all tables hold a column document_id that refers to the document id of the table document_info. Furthermore, the table corpus_structure holds references to the column position of the table cor-pus_words. • by specifying a subset of corpus documents over which the search should be carried out (e.g. all documents of legal system CH with language French);

• by choosing the type of unit to be displayed (whole paragraphs <p>, sentences <s>, titles <title>, …);

• by searching for whole words only (exact match) or parts of words (fuzzy match);

• by restricting the number of hits to be displayed at a time.

For searches in multilingual documents it will be possible to search for aligned segments, specifying search word as well as target translation. For example, the user could search for all alignments of German-Italian sentences that contain the word Umweltschutz translated as tutela ambientale (and not with protezione dell'ambiente). Figure 9 shows a simple interface for searching monolingual documents. The interaction between corpus and term bank will concern in particular 1) corpus segments used as contexts and definitions in the terminological entries, 2) short source references in the term bank (and the associated sets of bibliographical information) and 3) legal terms.

Entering data into term bank

When adding citations to a term bank entry, the relative bibliographic information will automatically be counterchecked with the contents of the bibliographical database. In case the information about the cited document is already present in the DB, a link to the term bank can be added. Otherwise the terminologist is asked to provide all information about the new source to the bibliographic database and later create the link.

Next to static contexts and definitions present for each terminological entry, each entry will show a button for the dynamic creation of contexts. Hitting the button will start a context search in the corpus and return all sentences containing the term under consideration.

Searching the corpus

When searching the corpus the user will have the opportunity to highlight terms present in the term bank. In the same way standardised or rejected terms can be brought out. Via a link it will then be possible to directly access the term bank entry for the term found in the corpus.

In general each corpus segment is linked to the full set of bibliographic information of the document that the segment is part of. Accessing the source information will lead the user to a detailed overview as shown in figure 4.

Conclusion

In this paper, we have presented the LexALP information system, used to collect, describe and harmonise the terminology used by the Alpine Convention and to link it with national legal terminology of the alpine Convention's member states. Even if we currently give a specific focus on spatial planning and sustainable development, the project is not restricted to these fields and the methodology and tools developed can be adapted to legal terminology of other fields.

In this paper we also proposed a solution to the encoding of multilingual legal terminologies in a context where standard techniques used in multilingual terminology management usually fail.

The terminology developed and the corpus used for its development will be accessible online for the stakeholders and the wider public through the LexALP information system.

Figure 1 :

 1 Figure 1: A set of Alpine Convention terms and their relations

  Figure 2: XML form of the term 'trafic intraalpin'

Figure 3 :

 3 Figure 3: XML form of the interlingual acception illustrated Figure 1

Figure 4 :

 4 Figure 4: An example French term, linked to a quadrilingual Alpine Convention Term.

Figure 5 :

 5 Figure 5: Example of document classification

Figure 7 :

 7 Figure 7: XML-structure of corpus document

Figure 8 :

 8 Figure 8: Interconnection of tables 5 Searching the corpus Due to the fine-grained classification (see section 4.1) and the structural mark-up (see section 4.2) of all corpus documents, corpus searches can be restricted in the following ways:• by specifying a subset of corpus documents over which the search should be carried out (e.g. all documents of legal system CH with language French);

Figure 9 :

 9 Figure 9: Example search over monolingual documents 6 Interaction term bank and corpus Term bank and corpus are independent components which together form the LexALP Information System.The interaction between corpus and term bank will concern in particular 1) corpus segments used as contexts and definitions in the terminological entries, 2) short source references in the term bank (and the associated sets of bibliographical information) and 3) legal terms.

Table 1 : Corpus documents for each legal system

 1

	AT	CH	DE	FR	IT	SI	AC	EU	INT
	612	119	62	613	490	213	38	791	149

Acknowledgements

The LexALP research project started in January 2005 thanks to the funds granted by the IN-TERREG IIIB "Alpine Space" Programme, a Community Initiative Programme funded by the European Regional Development Fund.


Dániel Gerbner
email: gerbner.daniel@renyi.mta.hu.

The Magnus-Derek game in groups

Keywords:

The Magnus-Derek game (also called the maximal variant of the vector game), introduced by Nedev and Muthukrishnan is the following: a token is moved around a table with n positions. In each round of the game Magnus chooses an integer and then Derek chooses a direction (clockwise or counterclockwise), and the token moves that many positions into that direction. The goal of Magnus is to maximize the number of positions visited, the goal of Derek is the opposite. In the minimal variant of the game the goals of the two players are exchanged: Magnus wants to minimize the number of positions visited and Derek wants the opposite. Here we introduce a generalization of these games: the token is moved in a group, Magnus chooses an element of the group and Derek decides if the current position is multiplied or divided by that element.

Introduction

The Magnus-Derek game was introduced by Nedev and Muthukrishnan in [START_REF] Nedev | The Magnus-Derek game[END_REF]. The game is played by two players called Magnus (from magnitude) and Derek (from direction). The equipment used is a circular board with n positions labeled consecutively from 0 to n -1, and a token which moves in these positions. In each round Magnus chooses and announces an integer l (0 < l ≤ n/2 can be assumed) and then Derek chooses + or -. Suppose the token starts that round in the position i. Then the token is moved to the position i + l mod n or il mod n according to the choice of Derek. This ends the round. Then the game continues infinitely. Magnus aims to maximize the cardinality of the set S of the positions visited during the game, Derek aims to minimize the cardinality of S.

Nedev and Muthukrishnan ( [START_REF] Nedev | The Magnus-Derek game[END_REF]) determined what Magnus and Derek can achieve in this game. They showed that Magnus can make sure at least f * (n) and Derek can make sure at most f * (n) positions are visited, where f * (n) is the following:

f * (n) = n if n = 2 k p-1
p n if p is the smallest odd divisor of n.

Let us rewrite the description of the game. The token is moved on the elements of the cyclic group Z n . Magnus chooses an element of Z n and Derek decides if it should be added to the current position or subtracted from it. This definition can be obviously extended to any other group. Actually, most parts of the proof in [START_REF] Nedev | The Magnus-Derek game[END_REF] can be easily translated into this language. For example Derek always chooses a coset of a subgroup of size n/p, and his strategy is that he does not let the token visit any element of that coset. As we will see, he can follow the same strategy in any abelian group.

In general we will use multiplication as the operation in the group and denote it by simply writing the elements next to each other. The identity element will be denoted by 1 and the inverse of an element x will be denoted by x -1 . In some cases the group will be identified with Z or Z n ; in those cases addition is the operation in the group, 0 is the identity element and -x is the inverse of x. Only the following non-trivial group theoretic results will be used (see for example [START_REF] Aschbacher | Finite group theory[END_REF]).

Theorem 1.1 (Fundamental theorem of finite abelian groups) Any finite abelian group G can be written as a direct sum of cyclic groups in the following canonical way:

G = Z k1 ⊕ Z k2 ⊕ • • • ⊕ Z k l , where every k i (1 ≤ i ≤ l) is a prime power.
Corollary 1.2 If G is an abelian group of order n and n is divisible by m then there exists a subgroup of G with order m. Theorem 1.3 If G is a group of order p k where p is a prime and k is an integer, then for any integer l < k there exists a subgroup of G with order p l .

The Magnus-Derek game in groups

Here we give a more precise definition of the Magnus-Derek game in groups. Let G be a group. A token moves on the elements of the group. In each turn Magnus chooses an element x of the group. Suppose the token starts the round at the position y. Then Derek chooses its next position out of the following two: yx or yx -1 . Note that the current position is always multiplied from the right with Derek's choice. We suppose that the token is at the identity element in the beginning of the game. Let f (G) be the number of positions visited if both players play optimally. Proposition 2.1 If G is an infinite group, then f (G) is countably infinite, moreover Magnus has a nonadaptive strategy (i.e. he can make all his choices before Derek's first answer) that forces the token to visit a new position in every step.

Proof: Now we describe Magnus's strategy for choosing the nth element. No matter what elements he has chosen in the first n -1 rounds, Derek has at most 2 n-1 possible choices in the first n -1 rounds, and no matter what he chooses, at most n positions 1 = x 1 , x 2 , . . . , x n have been visited. Only

x -1 n x 1 , x -1 n x 2 , . . . , x -1 n
x n can bring back the token to one of them, hence Magnus should not choose any of them, nor their inverses. At most 2n choices are wrong for Magnus in the nth round. Of course, he does not know what they are at the beginning, when choosing an element for the nth round. But he knows the first n -1 elements he has chosen, hence he knows the 2 n-1 possibilities for the token's movement in the first n -1 round. Altogether at most 2n2 n-1 possibilities should be avoided, but there are infinitely many elements, Magnus can choose one of them. ✷ Theorem 2.2 If G is a group of order n = 2 k , then there is a non-adaptive strategy for Magnus which forces the token to visit all positions, hence f (G) = n. Moreover, the strategy needs only n -1 steps.

Proof: We use induction on k. The theorem is trivial for k = 1. Suppose the statement is true for every l < k and we prove it for k. At first we choose a subgroup H of order 2 k-1 . By the induction Magnus can force the token to visit every position in H in 2 k-1 -1 steps. Let h i denote the element of H which multiplies the position in the ith round (by Derek's decision it is either the element Magnus has chosen, or its inverse). Then the visited positions are 1, h 1 , h 1 h 2 , . . . , h 1 h 2 . . . h n/2-1 . These are all different. Magnus uses this strategy in the first 2 k-1 -1 steps. Then he chooses an element of G which is not in H, and after that he applies again the strategy which works for H. The token visits every element of H in the first 2 k-1 steps, then goes to an element x of the coset of H and moves there in the next 2 k-1 -1 steps (since only the elements of H are used, the token does not go back to H).

On the other hand no matter what Derek chooses, x is multiplied (from the right) by n/2 -1 different elements, hence the results are all different. It means every position in the coset is visited, hence the proof is done. ✷

The following lemma is a reformulation of Lemma 6 from [START_REF] Nedev | The Magnus-Derek game[END_REF]. Here we give only a sketch of the proof. Note that in [START_REF] Nedev | The Magnus-Derek game[END_REF] the numbers Magnus should choose are given exactly.

Lemma 2.3 If G = Z p , p > 2 is a prime, then f (G) = p -1.
Proof: The upper bound follows from a very simple strategy of Derek. He chooses any non-starting position, and makes sure the token does not visit that particular position. As no element has order 2, he always has a real choice; if x brings the point to that particular position, then x -1 does not.

For the lower bound, it is enough to show that if there are two elements a and b not yet visited, then Magnus can make sure the token visits one of them. There is a unique element Proof: We will show how Magnus (resp. Derek) can make sure that the token visits at least (resp. at most) f * (n) positions. Both in Derek's and Magnus's optimal strategy a subgroup H of order n/p will be chosen, where p is the smallest odd prime divisor of n (if there is no such p then the statement follows from Theorem 2.2). Clearly the factor group G/H is isomorphic to Z p . Thus we can denote the cosets of H by x 0 H, x 1 H, . . . , x p-1 H where x 0 = 1 and x i x j ∈ x i+j H, where the addition i + j is considered modulo p (i.e. x i = x i 1 ). We use the notation m(a, b) defined in the proof of Lemma 2.3.

m = m(a, b) with a -m = m -b (it is either (a + b)/2 or (a + b + p)/2 mod p).

Derek's Strategy

This strategy is a very simple extension of the strategy used in [START_REF] Nedev | The Magnus-Derek game[END_REF]. At the beginning of the game Derek chooses a coset x i H where x i ∈ H. We claim that Derek can prevent any position in x i H from being visited. In each round he can choose a position from the set {yz, yz -1 }, where y denotes the current position which is not in x i H.

Suppose y ∈ x j H and z ∈ x l H, then yz ∈ x j+l H and yz -1 ∈ x j-l H. At least one of them is not in xH, otherwise both j + l = i mod p and jl = i mod p and by adding the two equations we obtain the contradiction 2j = 2i mod p, hence i = j mod p, which would mean y is in x i H.

Magnus's Strategy

This strategy is a simple extension of the second strategy of Magnus from [START_REF] Nedev | The Magnus-Derek game[END_REF]. An induction on n is used and Magnus applies the following strategy recursively on the smaller groups. The strategy proceeds in two phases. In the first phase the token visits at least f * (n/p) positions in all but one cosets. In the second phase either f * (n/p) positions of the remaining coset, or all the positions from the other cosets are visited. One can easily see that the number of visited positions is either at least pf * (n/p), or at least (p -1)n/p, which will prove the theorem.

Phase 1. Phase 1 consists of the repetition of two main steps. In Step A the token visits at least f * (n/p) positions in a coset, and in Step B it moves to another coset.

Step A. The token is at a position x ∈ x i H. Magnus chooses elements of H, hence the token does not leave x i H. If n/p is a power of 2, then Magnus applies his strategy from Theorem 2.2. If not, then applies this two-phase algorithm recursively. In both cases the token visits at least f * (n/p) positions in x i H.

Step B. Magnus chooses two cosets of H never visited before, and moves the token into one of them. He uses the strategy from Lemma 2.3. It is easy to see that he can force the token into p -1 cosets.

Phase 2. The coset x j H has not been visited yet. In this phase the token goes either to a position in x j H, and then Step A is applied, or the token visits all the other positions. One can easily see that in both cases at least f * (n) positions are visited altogether. Suppose y ∈ x l H has not been visited yet. Then Magnus can, like in Step B of the previous phase, move the token either into x j H (which would finish the proof), or into an element z from x m(j,l) H. Then he chooses yz -1 . If Derek chooses to multiply z by this element, then the token goes to y, but if he chooses to divide, then the token goes to an element of the coset x m(j,l)-l+m(j,l) H, which is equal to x j H. ✷

Remarks. There is a quadratic upper bound given in [START_REF] Nedev | The Magnus-Derek game[END_REF] on the number of steps Magnus needs to visit f (n) positions. This was improved to O(n log n) in [START_REF] Hurkens | The Magnus-Derek game revisited[END_REF] and to 3n in [START_REF]An O(n)-Round Strategy for the Magnus-Derek Game[END_REF] and independently in [START_REF] Chen | More on the Magnus-Derek game[END_REF]. The same upper bounds hold here. Additionally, it is shown in [START_REF] Nedev | The Magnus-Derek game[END_REF] that Magnus and Derek both only need O(1) time to calculate their moves in each round. Here we cannot give such bounds in general. The difference is that simple calculations can take long time in some groups. However, if the players are allowed to find the subgroups and cosets they want before starting the game, and the computations in the groups (multiplying elements, finding the inverse) do not require too much time, then similar bounds can be given.

Here is an example showing how different the non-abelian case is [4].

Proposition 2.5 Let G be the symmetric group S n . Then f (G) = |S n | = n!.
Proof: The following well-known property of S n is used: any element of it can be written as a result of multiplications of transpositions. If there is a position

x not yet visited, and the token is at the position y, Magnus writes y -1 x = x 1 x 2 x 3 . . . x k , where x 1 , x 2 . . . x k are transpositions and says x 1 , x 2 . . . x k in this order. Then Derek does not have any choice, since

x i = x -1 i . ✷
One can easily see that the same argument holds for all groups generated by elements of order 2, for example for all non-abelian simple groups (by the Feit-Thompson theorem they contain at least one element of order 2, and those elements generate a normal subgroup, which has to be the group itself).

The Derek-Magnus game in groups

Nedev and Quas defined the minimal variant of the vector game in [START_REF] Nedev | Balanced sets and the vector game[END_REF]. In that variant all the equipment and rules are the same as in the Magnus-Derek game, with only one difference: the goals are exchanged.

Here we call it Derek-Magnus game. For sake of brevity we define and prove everything in the more general setting of groups.

To get a meaningful definition, we cannot let Magnus choose the identity element. The token starts at the identity element of G. In every round the token starts at a position x, Magnus chooses an element y of G which is not the identity element and Derek chooses the next position of the token from the set {xy, xy -1 }. The goal of Magnus is to visit as few positions as possible, the goal of Derek is the opposite. Let g(G) be the number of positions visited if both Magnus and Derek play optimally.

One can immediately see that if there is an element of G with order 2, then Magnus can repeat that element always, and the token will visit only 2 positions. More generally Magnus can choose any nontrivial subgroup and repeat an element of that always, the token will never leave that subgroup. This strategy is non-adaptive, i.e. Magnus does not wait for Derek's decisions, he chooses the sequence of elements and Derek knows them before starting the game. Let h(G) denote the number of positions visited if they both play optimally but Magnus has to play non-adaptively. Obviously h(G) ≥ g(G). Theorem 3.1 Let G be a finite abelian group. Then h(G) = p, where p is the smallest prime divisor of the order of the group.

Proof: Magnus can choose a non-identity element of the smallest non-trivial subgroup and repeat that. This proves h(G) ≤ p. If p = 2, the lower bound is also trivial. Otherwise we suppose Magnus chooses an infinite sequence of elements of G. At least one of the elements, say x appears infinitely many times.

We cut the sequence of Magnus into several parts, each ending with x. Let denote these parts by A 1 , A 2 , . . . . They cover every element in this order, and A i always contain i copies of x. Equivalently A 1 is the part of the sequence till the first appearance of x, and more generally A i is the part from the end of A i-1 till the ith x (that is included in A i and not in A i+1 , hence A i contains i copies of x).

Now we describe a strategy of Derek for i < p such that at the endpoints of A 1 , A 2 , . . . , A i the token will be at i different positions, also different from the identity element, which is the starting position. Obviously this is enough to prove the theorem. Suppose that this is true before starting at the endpoints of A 1 , A 2 , . . . , A i-1 (that is clearly the case if i = 1). The token is at the position z after the end of A i-1 .

Derek chooses a "direction" for the elements in A i not equal to x at first, arbitrarily. Those would move the token into z ′ altogether (it is possible that the token never actually moves to z ′ , since there are also xs in the sequence). Then Derek decides how many of the i copies of x should be used for multiplying and how many for dividing. This way he chooses one element among x i , x i-2 , . . . , x -i . These are all different since the rank of x is odd and at least p > i. The position of the token at the endpoint of A i will be one of z ′ x i , z ′ x i-2 , . . . , z ′ x -i , these are all different, hence at least one of them is different from all the earlier endpoints and the identity element. ✷

One can easily see that the size of the smallest subgroup is an upper bound even if G infinite and/or non-abelian.

Let us turn our attention to the adaptive case. Surprisingly Magnus can do much better. Nedev and Quas examined this version for Z n in [START_REF] Nedev | Balanced sets and the vector game[END_REF]. They showed that g(Z n ) is equal to the size of the smallest balanced set in Z n , where a set S is balanced if for any x ∈ S there is an element y = 0 of Z n such that xy and x + y are both in S.

One can easily see that the same is true in any finite group. Let S be a balanced set in G if for any x ∈ S there exists a y = 1 in G such that xy and xy -1 are both in S. Magnus obviously can choose the smallest balanced set and force the token to stay there. On the other hand Derek can easily make sure that the set of positions visited infinitely many times is balanced. He can use the following simple strategy: if the token is in position x and Magnus chooses y, Derek checks if this has happened before. If it has, then he checks his answer and now answers differently. If x is visited infinitely many times, at least one y chosen by Magnus also appears infinitely many times, and then both xy and xy -1 are visited infinitely many times.

Using this Nedev and Quas proved the following theorem.

Theorem 3.2 [ [START_REF] Nedev | Balanced sets and the vector game[END_REF]] Let n be an integer. Then g(Z n ) = min p|n g(Z p ) where the minimum is taken over all primes dividing n. For a prime p the following is true:

1 + log 2 p ≤ g(Z p ) ≤ (2 + o(1)) log 3 p.
The upper bound was improved to 1 + o(1) log 2 p in [START_REF] Nedev | An algorithm for finding a nearly minimal balanced set in Fp[END_REF]. Here we prove that it is enough to examine the subgroups of prime order in an abelian group, and since they are isomorphic to Z p , g(G) only depends on the order of G.

Let G = G 1 ⊕ G 2 . For a set S let S 1 = {g 1 ∈ G 1 :
there exists a g 2 such that(g 1 , g 2 ) ∈ S}. S 2 is defined in a similar way. For an element x its first coordinate is simply denoted by x 1 . Lemma 3.3 If S is balanced and minimal under inclusion in G, then S 1 is either balanced in G 1 or contains only one element.

Proof: We define a directed graph on S. A vertex x is connected to xy and xy -1 if they are both in S. If xy = xy -1 , then {x, xy} is balanced, hence S does not contain any other elements, and it is easy to see that the statement holds. Otherwise every out-degree is at least 2, and the graph is strongly connected, i.e. for every pair of vertices x, x ′ there is a directed path going from x to x ′ . If not, then there is a proper subset U of the vertices such that all edges leaving the vertices of U go to vertices in U , but then U is balanced.

For every vertex x ∈ S there is a vertex z ∈ S and an edge from x to z. It means there is a y ∈ G such that z = xy and xy -1 ∈ S. But then x 1 y 1 and x 1 y -1 1 are both in S 1 . This makes S 1 balanced, unless y 1 is the identity element in G 1 . In that case z and x differ only in the second coordinate. Now suppose S 1 is not a singleton. One can easily see that the strong connectivity of the graph defined in the first paragraph implies that there is an edge from a vertex u with u 1 = x 1 to a vertex v with v 1 = x 1 . Then v = uw, and uw -1 is also in S. It is easy to see that v 1 = x 1 w 1 and (uw -1 ) 1 = x 1 (w -1 ) 1 , and w 1 is not the identity element in G 1 . ✷ Theorem 3.4 Let G be an abelian group of order n. Then g(G) = g(Z n ) = min p|n g(Z p ) where the minimum is taken over all primes dividing n.

Proof: Obviously g(G) ≤ g(Z p ) if p|n, since there is a subgroup of G isomorphic to Z p . Let S be a balanced set in G. Consider the canonical form of G given in Theorem 1.1. S is not a singleton, hence there are two elements of it which differ in a coordinate i. We consider G as the direct sum of Z ki and all the other members of the canonical direct sum. Then S i is a balanced set in Z ki . Hence g(G) ≥ g(Z ki ). Clearly k i is a power of a prime p where p|n, hence by Theorem 3.2 g(Z ki ) ≥ g(Z p ). This finishes the proof. ✷

4 Magnus-Derek game in Z

One group is of special interest: the group of integers. Proposition 2.1 implies that Magnus has a nonadaptive strategy to ensure there are infinitely many positions visited. One could think this solves the problem, if both players play optimally, the number of positions visited is infinity. But we can change Derek's goal a bit: now he wants to maximize the number of unvisited positions. In the case of finite groups, these were equivalent. Derek can always choose that the token goes to the right, hence there are infinitely many positions never visited. (In case of other infinite groups this strategy is not well-defined. Moreover, one can easily see that if every element has order 2, and the group is countably infinite, Magnus can force the token to visit every position). Again, one could think this finishes the case of Z. But the strategy given in Proposition 2.1 results in a very sparse set of visited positions. In some sense Magnus could do much better. Hence we change the definition again.

For a set S let

d n (S) = |[-n, n] ∩ S| 2n + 1 and Den(S) = lim n→∞ d n (S) if exists.
The goal of Magnus is to maximize the density of the positions visited, the goal of Derek is to minimize it. The previously mentioned strategy of Magnus gives 0 density, but Derek's strategy shows at most 1/2 can be achieved. Proof: We have already shown Derek's strategy (he always makes the token move to the right), now we give the strategy of Magnus. We show a little bit more: he can make sure that before the token first leaves [-n, n], either there have been at least n + 1 positions visited, and the token goes to one of -n -1 and n + 1, or there have been at least n + 2 positions visited and the token goes to one of -n -2 and n + 2, or there have been at least n + 3 positions visited and the token goes to one of -n -3 and n + 3. We prove it by induction on n, the cases n ≤ 6 can be easily checked.

Suppose it is true for every positive integer less than n, but Derek has a strategy that does not allow this for n. It is true for n -1, which means when the token left [-n + 1, n -1], there was n -1 + i positions visited and the token went to n -1 + i or -n + 1i, where 1 ≤ i ≤ 3. For i = 2 and i = 3 this proves the statement, hence we can suppose there were at least n -1 + 1 positions visited, and the token went n or -n. If Magnus can move the token into n + 1 or -n -1, the proof is done, hence we can assume the token does not move there.

In the next part of the game Magnus chooses numbers such a way that no matter what Derek chooses, the token does not leave [-n -1, n + 1]. We show that for a set S with -n -

1, n + 1 ∈ S ⊂ [-n -1, +1],
if the token starts from [-n-1, n+1], Magnus can make sure a position of S is visited unless S is a subset of an arithmetic progression with difference at least 3. Obviously is a, b ∈ S, it is enough for Magnus to arrive to (a + b)/2. And it is enough to arrive to (a + (a + b)/2)/2, and so on, like in Lemma 2.3. Let S be the smallest set containing S which is closed under this operation (among integers), it is enough for Magnus to arrive into any position in S. But S is an arithmetic progression with odd difference, as for three consecutive elements x, y, z there is at least one even difference among them, but then the average of those two numbers have to be among then. This only possible if zy = yx and it is an odd number.

If the difference is 1, then S = [-n -1, n + 1], hence it contains the current position of the token, which leads to a contradiction. Now Magnus at first visits as many unvisited positions in [-n -1, n + 1], as possible. If there are more than ⌊ 2n+1 3 ⌋ unvisited positions, including -n -1 and n + 1, then he can make sure the token visits a new position. Thus at least ⌈(4n + 1)/3⌉ ≥ n + 3 positions can be visited. Let S = {-n -1, 0, 1, n + 1}. After visiting n + 3 positions, Magnus can force the token to visit a position in S. If it is -n -1 or n + 1, we are done. If it is 0, Magnus chooses n + 1, if it is 1, Magnus chooses n + 2, and in both cases we are done. ✷

Let us consider the Derek-Magnus game now. Strangely the best for Derek is to use the same strategy as in the case when his goal was the opposite: he always chooses that the token goes to the right. This way he makes sure infinitely many positions are visited. He cannot achieve anything more even if the density is considered, as the following statement shows. Proposition 4.2 Magnus has a non-adaptive strategy such that if S is the set of visited positions after all the rounds, Den(S) = 0. Moreover, for any monotone increasing sequence (a n ) of positive integers he has a non-adaptive strategy which makes sure d an (S) ≤ n/a n for every n.

Proof: One can easily see that the second part of the proposition implies that the density is 0 if for example a n = n 2 .

Magnus says b n in the nth round, where b n is defined recursively the following way: b n = 1 + a n + n-1 i=1 b i . Then no matter what Derek answers, the token is not in [-a n , a n ] after the nth round. It is true for every n, hence the token never goes back to [-a n , a n ], thus there are at most n positions visited in that interval. This finishes the proof. ✷

Theorem 2 . 4

 24 Obviously if the token visits m(a, b), Magnus can choose am and then the token goes to a or b. Hence Derek cannot let the token visit m(a, b), and then similarly cannot let the token visit m(a, m(a, b)) and m(b, m(a, b)). In general, the set of positions which Derek cannot let be visited is closed under the operation m. But it is easy to see that such sets have p or at most 1 elements, and these both lead to contradiction.✷ If G is an abelian group of order n, then f (G) = f * (n).

Theorem 4 . 1

 41 If both players play optimally, the density of the positions visited is 1/2.

Acknowledgements

I would like to thank László Pyber for helping with the group theoretic questions and Péter Csorba for communicating the original problem to me.

Research supported by the Hungarian NSF, grant number PD-109537 and grant number NK 78439 1365-8050 c 2013