Bruno Mery
email: bruno.mery@u-bordeaux.fr

Lessons Learned from a Prototype Implementation of Montagovian Lexical Semantics

Keywords: Lexical Semantics, Prototype Software, Montagovian Generative Lexicon, Knowledge Representation for Natural Language Semantics

We present a general-purpose implementation of the process of lexical semantics analysis theorised in the Montagovian Generative Lexicon Λ TY n (hereafter MGL). The prototype software itself serves as a proof of concept of the MGL theory. The implementation process, the data structures and algorithms, also provide valuable results as to the expressive power required by MGL. While the implementation of terms and types for the purpose of meaning assembly assumed by MGL is in itself straightforward, some lexical phenomena imply additional mechanisms in order to process the logical representation using implicit knowledge. We therefore also present a minimal architecture for knowledge representation, and how it can be applied to different phenomena.

Theories and Implementations of Lexical Semantics

Formal lexical semantics theories aim to integrate to the toolbox of compositional analysis of natural language developed since Montague considerations of (logical) polysemy. Based on original studies such as [START_REF] Bierwisch | Wördliche Bedeutung -eine pragmatische Gretchenfrag[END_REF][START_REF] Cruse | Lexical Semantics[END_REF], then on a theory thoroughly developed in [START_REF] Pustejovsky | The Generative Lexicon[END_REF], there have been many formulations that build upon powerful type-theoretic foundations, with a generative, dynamic account of the lexicon at their heart. Such recent type-theoretic accounts of lexical meaning include Type Composition Logic (TCL) presented in [START_REF] Asher | Lexical Meaning in Context: A Web of Words[END_REF], Dynamic Type Semantics (DTS) presented in [START_REF] Bekki | Dependent Type Semantics: An Introduction[END_REF], Type Theory with Records (TTR) presented in [START_REF] Cooper | Copredication, dynamic generalized quantification and lexical innovation by coercion[END_REF], Unified Type Theory (UTT) presented in [START_REF] Luo | Contextual analysis of word meanings in type-theoretical semantics[END_REF], and the Montagovian Generative Lexicon (MGL) presented in [START_REF] Retoré | The Montagovian Generative Lexicon Lambda Ty n : a Type Theoretical Framework for Natural Language Semantics[END_REF].

Several partial or complete implementations of those theories have been provided for demonstration purposes, using logical or functional programming, or theorem provers such as Coq ( [START_REF] Chatzikyriakidis | Natural language inference in coq[END_REF] is an example among many). Concerning MGL, however, one of the stated goals was (paraphrasing slightly [START_REF] Retoré | The Montagovian Generative Lexicon Lambda Ty n : a Type Theoretical Framework for Natural Language Semantics[END_REF]) to provide an integrated treatment from syntax to semantics extending existing analysers based on Montagovian semantics such as [START_REF] Moot | Wide-coverage French syntax and semantics using Grail[END_REF] with mechanisms for lexical semantics that are easily implemented in a typed functional programming language like Haskell. Our goal in this publication is to present an actual prototype implementation (using functional and object programming in Scala) of the lexical semantics of that framework.

We detail some of the necessary data structures and algorithms used, what we learned from this implementation on the underlying logic properties of MGL, and sketch an architecture for simple knowledge representation that is necessary for the representation of certain lexical phenomena. The demonstrably functioning prototype illustrates both the validity of type-theoretic formulations of lexical meaning, and the deep interaction of lexical meaning with at least some sort of knowledge representation already evoked in [START_REF] Bosch | The bermuda triangle: Natural language semantics between linguistics, knowledge representation, and knowledge processing[END_REF].

A MGL Prototype 2.1 The Montagovian Generative Lexicon

MGL makes use of Λ TY n (an adaptation of the many-sorted logic TY n proposed in [START_REF] Muskens | Meaning and Partiality[END_REF] in second-order λ -calculus, given in the syntax of System-F). The idea is to perform an usual Montague analysis (performing syntax analysis via proof-search and substituting semantic main λ -terms to syntactic categories). Lexical mechanisms are then implemented in the meaning-assembly phase via a rich system of types based on ontologically different sorts and optional λ -terms that model lexical adaptation. The mechanisms, given in Fig. 1, can be summarised as follows:

-First, the input utterance is super-tagged and analysed using categorial-grammar mechanisms, which is the only step of proof-search of the process, yielding a syntactic term whose components are syntactic categories. The lexicon is then used in standard Montagovian fashion to substitute λ -terms, yielding a main semantic term, typed with many sorts and the type t for propositions. -Second, as a many-sorted logic is used, some type mismatches might (and should) occur, allowing mechanisms of lexical semantics to disambiguate between terms.

The lexicon provides optional λ -terms that are used as lexical transformations. These optional terms are inserted depending on their typing and yield a λ -term with no type mismatches. -Finally, β -reduction yields a normal, η-long λ -term of type t (the type of propositions), i. e. a logical formula that can be used in any usual semantics, such as model-theoretic or game-theoretic semantics.

As the first step is already well-studied and implemented, the object of concern is the second step: given a term reflecting the syntactic structure of an utterance, to construct a semantic λ -term in a many-sorted logic, making use of available transformations, and yielding a suitable formula. This is the object of our prototype implementation.

Modelling Types and Terms

The data structures and algorithms responsible for implementing the terms and types of Λ TY n are the core mechanisms of the software. They are given as two Scala sealed abstract classes, TermW and TypeW, with a flat hierarchy of case classes implementing the various possible terms and types; this simple categorisation allows us to easily construct and detect patterns of objects. Terms and types are constructed as binary trees (abstractions and applications of more than one argument to a given term/type can be easily curryied).

For terms, leaves are AtomicTerms (constants), TermVarIds (variables) with an identifier and type, or specific Transformations and Slots, while inner nodes are TermBindings (λ -abstracted terms), or TermApplications of a predicate and argument. For types, leaves are constant Sorts, pre-defined objects such as PropositionType for t, or second-order variable identifiers TypeVarIds, while nodes are TypeFunctions between two types A and B modelling A → B, or TypeApplications modelling A {B}.

A simplified UML class diagram presents this straightforward architecture in Fig. 2. Several algorithms are provided in order to work with types and terms; they are mostly simple recursive tree-walking algorithms, making the most of memoisation when possible (e. g., lists of available ressources are incrementally built as terms and types are constructed in order to minimise computations). Algorithms include the typechecking of applications, comparison between types, automated α-conversion of variables in order to prevent issues of scope, replacement of term and type variables, βreduction, and the automated specialisation of types for polymorphic terms (i. e., a predicate with a type containing one or several type variables will be specialised to the correct types if applied to an argument with a compatible but specified type).

Most are linear in complexity (with exceptions in the adaptative mechanisms below); all algorithms are at most polynomial in time.

Explicit Adaptation

The core of MGL is to provide transformations as optional terms, on top of the main λ -term associated to each lexeme. A canonical example is the book is heavy and interesting. Supposing three basic sorts:

-R for readable materials, ϕ for physical objects, -I for informational contents; the book can be modelled as the book R , heavy as heavy ϕ→t , interesting as interesting I→t . The example utterance is a case of co-predication, as two predicates are simultaneously asserted on two different facets (with different, incompatible sorts) of a same object, and MGL will resolve this by having the lexicon provide two optional terms associated with book in order to access these two facets:

f R→ϕ phys and f R→I in f o . A polymorphic conjunction & Π = Λ αΛ β λ P α→t λ Q β →t Λ ξ λ x ξ λ f ξ →α λ g ξ →β .(and t→t→t (P ( f x))(Q (g x))
) is needed for the co-predication. This yields, after suitable substitutions, application, and reduction, the term (and (heavy( f phys book)) (interesting ( f in f o book))), which is normal and of type t.

In our implementation, there are several important differences with the theory outlined above. As we distinguish between type constants and variables, there is no need to explicitly abstract types. This is because the only second-order operation ever used in Λ TY n is specialisation (i. e., the replacement -or instantiation -of type variables). Moreover, second-order (type) variables are all introduced by λ -bound firstorder (term) variables.

We also distinguish between term variables that are necessary for the definition of an abstracted term (such as P, Q and x, the two predicates and the argument of the conjonction above) and adaptation slots, the places where optional λ -terms (such as f and g above) can be inserted. This is because the optional terms can be provided by various different mechanisms, and might not be provided at all if the term is wellformed (there is no lexical adaptation taking place in utterances such as heavy and black rock; in that case, MGL provides an useful, if slightly redundant, id optional polymorphic term that can be inserted in order to get the identity on any type).

We provide optional terms as Transforms, which are distinguished from other terms. Each term has a list of available transformations, constructed recursively from the leaves (the transformations available to atomic terms should be given in the lexicon). We also distinguish Slots for explicit adaptations; the list of slots is maintained during the construction of the terms. Our polymorphic and conjunction then becomes:

lambda p^(B->t).lambda q^(G->t).lambda x^A.((And^{(t->(t->t))} (p^(B->t) (f^{(A->B)} x^A))) (q^(G->t) (g^{(A->G)} x^A)))
During the attempted resolution of the application of the conjunction to terms for heavy and interesting, the polymorphic and is specialised to sorts representing ϕ and I, and cannot be reduced further with the application of the argument book. A further algorithm is provided in order to model the choice of transformations, trying to match all available transformations to the adaptation slots. As all permutations are considered, this is potentially the most costly computation taking place. The result is a list of possible interpretations (given as term applications with slots filled by transformations): there might be zero, one, or finitely many. A further check on the list of terms obtained will filter those, if any, with a suitable typing, that will form the desired result(s). In the tests conduced with the input of the example, four interpretations where produced, with only the correct one of a resolvable type (t):

((And^{(t->(t->t))} (heavy^{(P->t)} (morph_R->Phy^{(R->P)} book^{R}))) (interesting^{(I->t)} (morph_R->I^{(R->I)} book^{R})))

Implicit Adaptation

Polymorphic operators such as and, with explicit adaptation slots, are needed for co-predications. However, most lexical adaptations can take place implicitly, simply by reacting to a type mismatch such as (p A→B a C ) and applying any suitable transformation to resolve the type mismatch. In order to do this automatically, there are two possibilities to resolve such type mismatches: by adapting the predicate, yielding (( f (A→B)→(C→B) ) p) a), or the argument, resulting in (p ( f C→A a)). There is also a third situation to consider, that of a partial application (λ x A .τ a C ), in which the argument can be adapted as above, but the typing of the predicate might be as not be determined at the moment of the adaptation.

A procedure analyses such applications with type mismatches and no explicit adaptation slots, and inserts suitable, automatically generated adaptation slots, then proceeds as with explicit adaptations. For example, a simple term application such as (P^{(e->t)} a^{A}), with a transformation f_{A->e} available to the atomic term a yields the straightforward (and only felicitous) interpretation (lambda x^A.(P^{(e->t)} (f_{A->e}^{(A->e)} x^A)) a^{A}), that reduces to (P^{(e->t)} (f_{A->e}^{(A->e)} a^{A}).

Implicit adaptations are necessarily reduced to those simple cases. Trying to account automatically for co-predications would imply to try any possible permutation of types and transformations at all nodes of a term, which would be exponential in complexity; thus, the need for explicit operators such as the polymorphic and.

Lexicalisation

In addition to the core mechanisms, a tecto package provides support for a tectogrammatical/syntactic structure in the form of an unannotated binary tree of lexemes ; this serves as a factory for the input of already analysed text, and as a more streamlined form of output for adapted terms.

A lexicon package enables the storage of lexical entries that associate lexemes (as strings) to terms, complete with typing, transformations and ambiguities. Lexica can be merged, in order to have combine the treatment of different phenomena, treated as standalone modules, for complex sentences. Lexica also provide automated translations from a syntactic structure (a tecto term) to a semantic one (a TermW term, initially not adapted, reduced or even type-checked). Semantic terms can be presented either by a straightforward translation to syntactic terms, or printed to a string in the usual fullyparenthesed prefix notation with apparent typing (as in the examples of this article).

Phenomena Coverage

Many lexical phenomena discussed in [START_REF] Pustejovsky | The Generative Lexicon[END_REF][START_REF] Mery | Modélisation de la Sémantique Lexicale dans le cadre de la Théorie des Types[END_REF] can be modelled using the simple mechanisms of Λ TY n in their prototypal implementation given above; some others require additional mechanisms.

Lexical adaptations, including alternations, meaning transfers, grinding, qualiaexploitation and "Dot-type"-exploitation are all supported by the adaptation mechanisms, as given previously. Simple predications only require to have suitable transformations available, and to use the implicit adaptation mechanisms ; copredications require explicit adaptation using polymorphic operators. Theoretical grounds have been laid in [START_REF] Bassac | Towards a Type-Theoretical Account of Lexical Semantics[END_REF][START_REF] Retoré | The Montagovian Generative Lexicon Lambda Ty n : a Type Theoretical Framework for Natural Language Semantics[END_REF]. Constraints of application are required in order to perform co-predications correctly.

As explained in [START_REF] Mery | Recent advances in the logical representation of lexical semantics[END_REF], the simultaneous reference to different facets of a same entity can be infelicitous in some circumstances, such as the use of destructive transformations (grinding, packing) or metaphorical use of some words. Thus, the following co-predications are infelicitous to some degree : *The salmon was lighting-fast and delicious, ? Birmingham won the championship and was split in the Brexit vote. In order to block such co-predications, we have proposed to place constraints on transformations in order to block their usage depending on the other transformations that have been used on the same term. The first version of this system given in, e. g., [START_REF] Bassac | Towards a Type-Theoretical Account of Lexical Semantics[END_REF], distinguishes between flexible (allowing all other facets) and rigid (blocking all other facets) transformations. The latest version, given in [START_REF] Mery | Lexical Semantics with Linear Types[END_REF], proposes a Λ TY n , a system with terms of the linear intuitionistic logic as types, that (among other things) allow any arbitrary type-driven predicate to act as a constraint on the use of transformations.

In this prototype implementation, all transformations come with a member function that can be defined as a constraint, and a compatibility check of all transformations can be performed using every constraint, the default constraint being the boolean constant true (that simply models flexible transformations). As the constraint can effectively be any function, the precision is the same as in [START_REF] Mery | Lexical Semantics with Linear Types[END_REF]. Ontological inclusion, called type accommodation in [START_REF] Pustejovsky | The Generative Lexicon[END_REF] and modelling the lexical relation of hyponymy, can be supported by tweaking the system of sorts. The theoretical and empirical basis for doing so are discussed in [START_REF] Mery | Are books events ? Ontological Inclusions as Coercive Sub-Typing, Lexical Transfers as Entailment[END_REF], in which we argue that coercive sub-typing is an accurate and helpful mechanism for resolving ontological inclusion, but no other lexical phenomena.

In order to support sub-typing, each sort can be defined with an optional parent sort. A careful review of the typing comparison mechanism will then be enough, together with a rewriting of the equality method for sorts, in order to support subtyping. This is not implemented yet, but does not require (much) additional processing power. Performative lexical adaptations, such as quantification, Hilbert operators for determiners, and the alternate readings of plurals and mass nouns, are supported as far as the meaning assembly phase is concerned. However, in order to be useful, this category of lexical phenomena (as well as hypostasis and several others) require additional mechanisms in order to incorporate the knowledge gathered from the analysis of the sentence into the logical representation. The basic architecture is supported, but mechanisms of resolution remain preliminary and will be discussed next, especially in Section 3.3.

3 Layers of Lexica and Knowledge Representation

The Additional Layers

Theories of semantics deriving from [START_REF] Pustejovsky | The Generative Lexicon[END_REF] generally encompass some degree of common sense world knowledge: it is considered known that a committee (and other such group nouns) is made of several people and is a felicitous argument of predicates requiring a plural argument, and that engines are part of cars and thus that predicates such as powerful or fuel-guzzling can apply to cars via their constitutive quale. It has been argued (e. g. in [START_REF] Fodor | The emptiness of the lexicon : Reflections on James Pustejovsky's The Generative Lexicon[END_REF]) that such complex knowledge does not belong in a semantic lexicon; we will paraphrase Im and Lee from [START_REF] Im | A developed analysis of type coercion based on type theory and conventionality[END_REF], defining semantics to be the meaning conveyed by an utterance to a competent speaker of the language in itself, excluding, for instance, the specific situation in which the utterance is made, but including any previous discourse. Thus, the full contents of a given fairy tales should be able to be described within semantics, while a political essay will probably require additional knowledge about the position of the author and the specifics of the period of writing.

From our point of view, designing a complete tool for type-theoretic lexical semantics imply the careful definition of various lexica that can convey the necessary, elementary world-knowledge for each word. A lexicon for general use will associate to all relevant lexemes their semantics (in the form of main and optional λ -terms) as can be given in a dictionary of a language. However, there are two common cases in which the general lexicon is not sufficient.

First are the specific lexica: vocabularies relevant only to a community (professional jargons, local dialects, and other linguistic constructs specific to small groups of people), and/or to a specific literary universe (fairy tales, space opera, mythology, politic speeches, etc.). Such lexica are activated on an as-needed basis, switched often, and are more specific than the general-use lexicon.

Lexical semantics also requires a lexicon used for the current enunciation. A competent speaker of any language is able to use generative mechanisms in order to introduce new lexical concepts, either by hypostasis (the use of a new word, the meaning of which can be inferred from context and morphology), or by creative use (giving a new, contextually evident meaning to an existing word).

In our view, the lexicon of the enunciation starts empty and can be augmented when the analysis of the discourse encounters words that are not present in the current active lexica. We think that such mechanisms can enable the learning of lexical semantic data. In addition to these lexical layers of meaning, we tend to implement different lexical phenomena using different lexica for simplicity's sake, and create a merged lexicon from every relevant one when processing text.

Individuals, Facts and Contexts

To summarise our argument in Section 3.1 above, in addition to mostly static lexical data, some sort of knowledge representation is needed to process even simple lexical phenomena such as collective and distributive readings for plurals. Namely, we need to keep track of the individuals mentioned in a given discourse, and of the facts asserted of those individuals. To be complete, we would also need to keep track of agents, in order to model dialogues or multiple points of view in which certain agents assert certain facts. Our implementation prototype currently supports individuals, as atomic terms of type A (for named entities: human agents, towns. . . ) or A → t (for common nouns, that can be resolved to a specific individual of type A by the means of an Hilbert-based determiner) for any sort A. We also account for facts, as predicates (TermBindings or atomic terms) of type α → t for any arbitrarily complex type α, that are used in a term application, and apply to an individual. In the analysis of a term, individuals and types are extracted and added to the context of enunciation. The hierarchy of lexical layers given above can be implemented as a hierarchy of contexts, some containing initial individuals and facts relevant to each lexicon; in a such complete system, the context of the real world would, to resolve the paradox mentioned in [START_REF] Russell | On denoting[END_REF], include the fact that there is no King of France (and therefore that The king of France is bald, while grammatical, is not felicitous because there are no qualifying referents for the entities described, and thus cannot be assigned a truth value). Such contexts are specific objects (aggregating individuals, facts and a related lexicon) in our implementation.

The Parsing-Knowledge Loop

We use a specific lexicon to list some common semantic terms for quantifiers, counting terms, logical and Hilbert operators (detailed in e. g. [START_REF] Retoré | Sémantique des déterminants dans un cadre richement typé[END_REF], more recently in [START_REF] Mery | Typed Hilbert Operators for the Lexical Semantics of Singular and Plural Determiner Phrases[END_REF]). Other lexica can make use of these terms in order to construct, for instance, Link-based semantics for plurals (originally given in [START_REF] Link | The logical analysis of plurals and mass terms: A lattice-theoretic approach[END_REF]), using lexical transformations as suggested by [START_REF] Moot | Second order lambda calculus for meaning assembly: on the logical syntax of plurals[END_REF] and detailed in [START_REF] Mery | Computing the Semantics of Plurals and Massive Entities using Many-Sorted Types[END_REF]. Some functions associated to the logical lexicon then resolve the operators, given a term and a context. This updated process of analysis is given in Fig. 3.

To explain what the analysis of plural readings in MGL entail, consider the following example from [START_REF] Mery | Computing the Semantics of Plurals and Massive Entities using Many-Sorted Types[END_REF] : Jimi and Dusty met is analysed as |λ y e .(y = j) ∨ (y = d)| > 1 ∧ meet(λ y e .(y = j) ∨ (y = d)). One elementary issue is that the predicate met applies to group individuals (such as a committee) and constructions made of more than one individuals (such as Jimi and Dusty) but not to singular individuals (such as a student). Thus, the lexical entry for the predicate is λ P e→t .|P| > 1 ∧ meet(P) -a logical conjunction with a cardinality operator. Those two simple elements can be defined in System-F (the calculus in which Λ TY n , the logic of MGL, is implemented). The issue is that, in order for our system to infer correctly that Jimi and Dusty are two different individuals, and thus that the above term resolves to meet(λ y e .(y = j) ∨ (y = d)), we must use processing power beyond the simple construction and reduction of terms: a minimal system of knowledge representation and logical inference. Within our architecture encompassing individuals and facts, and with a functional lexicon for logical connectives (including the logical and operator of that example), as well as quantification and counting (including the cardinality operator), this example can be treated.

However, this requires a given term to be parsed at twice: the first time, the syntactic structure is converted into a semantic term and lexical transformations are applied, the second, facts that emerge from the transformations are added to the lexicon, and the logical lexicon can be used in order to process the operators that have been introduced. Our prototype implementation does not incorporate such feedback yet, as the first step can result in several different interpretations; this remains a work in progress. As a result, straightforward composition for plurals are tentatively supported (such as in the previous example), but ambiguous covering readings for plurals are not yet available.

Hypostasis and Quantificational Puzzles

An enunciation-context lexicon that is filled with individuals and facts inferred from the primary semantic analysis can serve, in a limited way, to account for hypostasis. Words absent from the lexicon, but syntactically placed in the position occupied by individuals, will be added as primary entities to the lexicon, and their precise typing inferred from the predicates they are applied to. An elementary mechanism should be enough to have a correct representation from Lewis Carroll's Jabberwocky. Of course, most competent human speakers also use morphosyntactic inference to attach at least some degree of connotative meaning to the words being proposed (e. g., Star Wars's plasteel can be inferred as a fictive material somehow combining the characteristics of plastics and steel by any English speaker). This is completely beyond the power of our early software. Rather, we can have the process of meaning assembly outline which lexemes are not in the lexicon, and use human input for correcting the precise types and terms associated.

The process of counting, quantifying and selecting entities using Hilbert operators can also shed some light on the quantificational puzzles mentioned in [START_REF] Asher | Lexical Meaning in Context: A Web of Words[END_REF] and several other related works. The issue with having universal quantification used together with co-predication on multi-faceted entities can be seen in examples such as There are five copies of War and Peace and a copy of an anthology of Tolstoï's complete works on the shelf (what is the answer to questions such as How many books. . . ?, and what exactly is the type of book in such questions ?), or I read, then burnt, every book in the attic (the entities being predicated form two different sets). In order to resolve such quantificational puzzles satisfactorily, the methods for counting and quantifying must be adapted to each predicate, and only apply to individuals of the appropriate type. For our purpose, this implies a close monitoring of the entities introduced by lexical transformations and their context of appearance. This is also a work in progress.

Results

A Fragment of Second-Order

We have proven that MGL can actually be computationally implemented. This was not really in doubt, but the way that the combination of types and terms are implemented illustrates that the time and space complexity of most of the process is limited: the algorithms used are mostly linear tree walks, with a few quadratic worst-case operations. The most complex step is the choice of optional terms for adaptation slots, of complexity |t| × |s| × n at worst (the product of the number of optional terms available, adaptation slots, and length of the term); the hypothesis behind MGL is that the number of available optional terms at any point remains manageable. Thus, the step not actually implemented in this prototype (but for which many implementations exist), syntactic analysis, is the costliest of the process detailed in Fig. 1 and the complete process of parsing is polynomial in time.

MGL accounts such as [START_REF] Retoré | The Montagovian Generative Lexicon Lambda Ty n : a Type Theoretical Framework for Natural Language Semantics[END_REF] point out that the whole expressive power of secondorder λ -calculus is not used, and that all could be implemented using first-order terms if all possible adaptations were listed at each step (which is syntactically much longer to write). Indeed, our implementation only supports the single second-order operation of type specialisation (by distinguishing type variables from other types and using pattern matching to recognise and rewrite types), which is required for having polymorphic terms. There are no features of Λ TY n that require additional power: sub-typing can be implemented by an optional parent field in Sorts, arbitrary complex on copredications are supported by including a check on transformations that can be any arbitrary function, quantification, counting and Hilbert operators can be included. . .

Minimal Processing Architecture

Our prototype implementation includes the skeleton of an architecture that represents the individuals, facts and agents appearing during the semantic analysis. This goes beyond the straightforward process of producing a logical representation for an utterance, as some of the terms of that logical representation might be analysed differently depending on the context; we argue that that process is still part of a semantic analysis. The individuals, facts and agents are stored in objects called contexts, organised in a hierarchy that includes the most specific context (modelling the analysis of the current discourse), universe-specific contexts (describing whether the discourse is part of a fictional, historical or activity-specific setting), dialect-and language-specific contexts, each associated to an appropriate lexicon. A complete analysis would minimally involve the construction of the logical representation of an utterance, the update of the enunciation context with individuals and facts introduced by that utterance, and a re-interpretation of the logical representation in the active contexts. This minimal processing architecture can be completed with no difficulties; our implementation includes relevant data structures and algorithms, but requires significant work on examples of performative lexica in order to be thoroughly tested.

Perspectives

This prototype implementation has already served its primary purpose: to illustrate that MGL can be computationally implemented, and that the examples usually given with the theory actually work. As it is, however, this implementation is more of a proof of concept than useful software.

To be actively used by the community, more work would be required to give it an helpful interface, both for the user and for existing analysers; we also would like to convert from and to representations of the other most active type-theoretic accounts of lexical semantics. The knowledge-representation architecture remains a work in progress, and requires solid efforts in order to correspond to our ambitions. However, what MGL really requires in order to be useful is a large-cover library of types and terms; our hope is that this prototype will help to build software that can learn those features from corpora.

Fig. 1 .

 1 Fig. 1. MGL Process Summary

Fig. 2 .

 2 Fig. 2. Class diagram of the core package for terms and types.

Fig. 3 .

 3 Fig. 3. Parsing-Knowledge Representation Feedback


Philippe Pernelle
email: philippe.pernelle@univ-lyon1.fr

Thibault Carron
email: thibault.carron@lip6.fr

Jean-Charles Marty
email: jean-charles.marty@liris.cnrs.fr

Stéphane Talbot

Stephane Talbot
email: stephane.talbot@univ-savoie.fr

Learning PLM system with a Serious Game

Keywords: Game Base Learning, Serious Game, PLM

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Teaching production engineering is dicult, and particularly for PLM systems. There are many reasons for this. The rst reason is that students learn CAD systems without management constraints. When they nd out PLM systems, constraints are more visible than the benets. The second and probably more important, reason is that it is very expensive (in terms of nancial cost and human resources) for an educational establishment : Installation, conguration, collaborative projects management...

In this paper, we propose a new approach for learning PLM system: learning a unit with Serious Game. This unit has been produced as part of a research project (PEGASE) that was initially intended to improve the change management. Noting the fact that resistance to change were the same for enterprises and students, we developed a learning scenario using the playful aspects of the video games. In the rst part, we present the concept of this Serious Game, then we present the experiment results that was achieved with students.

2 New learning for PLM systems 2.1 About the Games Learning Bases Since a few years, Learning Management Systems (LMS) oer functionalities that are recognized as being valuable from dierent points of view [START_REF] Dillenbourg | The evolution of research on collaborative learning[END_REF]. For instance, students can learn at their own speed. These environments also allow the teacher to evaluate specic activities in a uniform way [START_REF] Hijon | E-learning platforms analysis and development of students tracking functionality[END_REF]. LMS allow to structure and to develop distance training. However they have not enough impact on the motivation and the attractiveness. Some students tend to consider LMS as unexciting [START_REF] Prensky | Digital Game-Based Learning[END_REF]. So, Game-Based Learning Management System is based on that the way of acquiring knowledge during a learning session is similar to following an adventure in a Role-Playing Game (RPG) [START_REF] Squire | Videogames in education[END_REF]. The combination of the two styles is called MMORPG (Massively Multiplayer Online RPG) and oers a good potential for learning reformulated as MMOLE (Massively Multiplayer Online Learning Environment) [START_REF] Yu | Learning in the virtual world : the pedagogical potentials of massively multiplayer online role playing games[END_REF]. Nevertheless, although the students appreciate this approach and that Games-based Learning can signicantly enhance learning, there is an obvious need for realistic information about students: skills, actions or behaviors especially for the teacher [START_REF] Galarneau | Online Game for 21st Century Skills[END_REF].

The diculties that teachers face in teaching PLM System to students incited us to nd additional motivation thanks to Game-Based Learning (GBL). Although the project below was not initially intended for this, we have conducted experiments to test this.

PEGASE : a Serious Game for PLM

PEGASE project [START_REF] Bissay | Pegase : a platform tool to help change management support during the implementation of a plm system in an industrial company[END_REF] [8] is a Serious Game based on Learning Adventure ("LA") [START_REF] Carron | Teaching with game based learning management systems: Exploring and observing a pedagogical dungeon[END_REF]. LA is a Game-Based Learning Management System representing a 3D environment where the learning session takes place (see Fig. 1). The environment is generic in the sense that it is not dedicated to a particular teaching domain. With the help from a pedagogical engineer, the teacher adapts the environment before the session by setting pre-requisites between sub-activities and by providing dierent resources (documents, videos, quizzes) linked to the course. Experiments have already been set up for learning Operating Systems as well as Project Management or Object Oriented Concepts in Computer Science. LA is thus a platform allowing one to describe, generate and enact dierent learning environments. The following items dene the main characteristics of LA: A 2D or 3D multiplayer world, split into activity areas; Artefacts populating this world: objects, individual or collaborative tools, non-player characters (NPC), players represented by their avatars; Possibility to characterize the players / learners through a learner/user model and also through group models; Enacting facilities Avatar personalisation Tracing facilities of players' actions Tools for designing scenarios Scenario or quest editor, evaluation tools Possibility to modify dynamically the environment. In the PEGASE project, the gaming environment is associated to a content platform (Audros). This content platform is a PLM system very used in SME/SMI. Moreover, a Trace-Based System (TBS) captures the behavioral traces and activity traces. These traces are essential to monitor the progress the users in the scenario. Thus, after several steps (collection, selection, transformation, aggregation of dierent traces), we are able to provide specic indicators [START_REF] Gendron | Towards a structured approach to the denition of indicators for collaborative activities in engineering design[END_REF] giving meaningful information to the teacher (see Fig. 2). Moreover, some of these indicators may also be used to update the user model of each student and to present accurate information for the teacher. The interoperability issues have been resolved by relying on a service-oriented architecture [START_REF] Zrouki | Caracterisation de services metiers plm : Un exemple d integration dans le cadre du projet pegase[END_REF] (see Fig. 2) Fig. 2. PEGASE architecture 3 An example of a pedagogical scenario for PLM In order to design a pedagogical scenario for PLM, we looked for an industrial process that was suciently generic to be used by any student. This process referred to a case study the plastic industry. The transformation of an industrial process into a pedagogical scenario was achieved thanks to research work concerning gamication [START_REF] Mayer | he gaming of policy and the politics of gaming: A review[END_REF].

This architecture is generic in sense that it can design any pedagogical scenario. We chose to conceive a rst scenario for discovering the main functions of PLM. In the design stage, this classication enables the trainer to build his scenario from a descriptive guide. Initially, the proposed scenario was structured around a simple industrial process (purchase order) described in Figure 3. Without a PLM system, this process is achieved through traditional activities where the risk of error, as well as the tedious tasks involved, should be considered.

In a rst part, this process is carried out in the PEGASE Serious Game without any PLM system. The following items and gures describe the corresponding actions:

Discussion with colleagues and watching a training presentation (see Figure 4); Collecting documents in order to complete and visualize the tasks in the process; Visualization of the order form, retrieval of information from the archives; Fig. 3. Purchase order management process with and without PLM Summary of time-consuming steps (see Figure 5); Explanation for creating a purchase order with Audros platform(see Figure 6); Once the process is carried out without a PLM system, a collective and individual balance of mistakes made by the player is presented. A mini training session on possible solutions to resolve their mistakes with the Audros PLM system is then proposed. The process is therefore performed with a connection to the Audros platform.

Experiment of this scenario.

An experiment was carried out from September 2011 to December 2011 in the Technical Institute (Lyon -France) with 224 students. During the experiment, Fig. 4. PEGASE screenshot: a player interacting with the game environment Fig. 5. PEGASE screenshot: reminder for the player's tedious tasks Fig. 6. PEGASE screenshot: a player interacting with Audros system each group of twelve students with their teacher was present in the classroom equipped with 12 computers. Each student accessed the virtual environment through his/her workstation, and had a personal (adapted) view on the world. They were explicitly allowed to communicate through the chat tool provided with the system and were warned that they would be observed regarding the use of the system.

As explained before, the course was dedicated to the understanding of the PLM problematic. The learning content dealt with PLM elementary concepts: the session was split into two parts: experimenting without (long and tedious) and with a PLM system. The solution (nal document) had to be approved by a PLM system expert who was online via the PLM business tool (Audros) and was receiving each document produced. The aim of the session was to assess the knowledge and know-how of the students about the objectives of a PLM system. A story guided the knowledge quest thanks to metaphors. Indeed, the challenge is encouraged through NPC who propose a coherent contest. Immersion is reinforced when the users' actions have a direct impact on the objects of the world. Finally, the teacher was also present in the game via an avatar: it was possible to chat with him, to ask for help for example.

Looking at the experiment results with regard to previous years when this module was done without SG, we observed two improvements. The rst is a very slight increase in overall average. However, there is a signicant reduction of the standard deviation. This is conrmed by a survey showing that there were fewer unmotivated students than usual.

Conclusion

In this article, we have illustrated an example of new learning technologies for PLM system. Using a serious game has shown very positive eects. This allows to more easily accept the PLM system constraints. Furthermore, students' motivational level for deepening such systems, is greatly increased.

Naturally, some drawbacks persist: we must recognize that it is very dicult for the teacher to be both present in the game, help the students and regulate the session even with these specic tools. We currently think that we can develop some specic indicators only dedicated to some classical elds of a domain. An interesting perspective could be to develop and propose directly within the indicators some basic regulation actions such as play specic PLM video , propose new activity or enable/disable such facility/ies for this student in order to improve and adapt the learning progression.

The LA environment is collaborative, multiplayer and fully observable thanks to traces left by the users during the game. These traces allow us to elaborate collaborative indicators. Moreover, thanks to the feedback collected from these experiments (questionnaires and debrieng sessions directly after the game), we are able to imagine new factual indicators of collaboration exploiting traces left by the users. Future experiments will be done around collaborative activities in the PLM systems. In this brand new scenario (context : futuristic enterprise, multi-role player, handling quality non-conformance process), we want to test some advanced functionalities (ECR, ECO, co-design, ...) around the conception of some complex products.

Fig. 1 .

 1 Fig. 1. Screenshots of the Learning Adventure (LA) environnement

Acknowledgement

We would like to thank the French Ministry for the Economy, Industry and Employment (DGCIS) for the support in the PEGASE project. We would like also to thank G. Dalla Costa, A. Bissay, J. Depoil, L. Kepka, S. El Kadiri, L. Michea and M. Zrouki for their great help in developing this platform.


A Casteigts
email: acasteig@labri.fr

Y Métivier
email: metivier@labri.fr

J M Robson
email: robson@labri.fr

A Zemmari
email: zemmari@labri.fr

Deterministic Leader Election in O(D + log n) Time with Messages of Size O(1)

This paper presents a distributed algorithm, called ST T , for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size O(log n), where n is the number of processors. It elects a leader in O(D + log n) rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of O(D + log n). This substantially improves upon the best known algorithm whose bit round complexity is O(D log n). In fact, using the lower bound by Kutten et al. [13] and a result of Dinitz and Solomon [8], we show that the bit round complexity of ST T is optimal (up to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D.

Introduction

The election problem in a network consists of distinguishing a unique node, the leader, which can subsequently act as coordinator, initiator, and more generally performs some special role in the network (see [START_REF] Tanenbaum | Distributed Systems -Principles and Paradigms[END_REF] p. 262). Once a leader is established, many problems become simpler. For this reason, election algorithms are often considered as building blocks for other distributed algorithms and election, together with consensus, is probably the most studied task in distributed computing literature [START_REF] Dinitz | Bit complexity of breaking and achieving symmetry in chains and rings[END_REF], starting with the works of Le Lann [START_REF] Lelann | Distributed systems: Towards a formal approach[END_REF] and Gallager [START_REF] Gallager | Finding a leader in a network with o(e+n log n) messages[END_REF] in the late 70's.

A distributed algorithm solves the election problem if it always terminates and in the final configuration exactly one process (or node) is in the elected state and all others are in the non-elected state. It is also required that once a process becomes elected or non-elected, it remains so for the rest of the execution. The vast body of literature on election (see [START_REF] Attiya | Distributed computing: fundamentals, simulations, and advanced topics[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Santoro | Design and analysis of distributed algorithm[END_REF][START_REF] Tel | Introduction to distributed algorithms[END_REF] and references therein) actually covers a number of different topics. They include the feasibility of deterministic election in anonymous networks, starting with the seminal paper of Angluin [START_REF] Angluin | Local and global properties in networks of processors[END_REF]

and the key role

A full version of this paper can be found on arXiv (http://arxiv.org/abs/1605.01903) of coverings; the complexity of deterministic election in networks with identifiers; and the complexity of probabilistic election in anonymous (or sometimes identified) networks.

The present work is in the second category. We assume that each node has a unique identifier which is a positive integer of size O(log n), and the nodes exchange messages with their neighbours in synchronous rounds. The exact complexity of deterministic leader election in this setting has proven elusive for decades and even some simple questions remain open [START_REF] Kutten | On the complexity of universal leader election[END_REF]. Assuming the size of messages is logarithmic (i.e. messages of size O(log n)), we know since Peleg [START_REF] Peleg | Time-optimal leader election in general networks[END_REF] that O(D) rounds are sufficient to elect a leader in arbitrary networks. This was recently proven optimal by Kutten et al. [START_REF] Kutten | On the complexity of universal leader election[END_REF] using a very general Ω(D) lower bound (that applies even in the probabilistic setting). Independently, Fusco and Pelc [START_REF] Fusco | Knowledge, level of symmetry, and time of leader election[END_REF] showed that the time complexity of leader election is Ω(D + λ) where λ is the smallest depth at which some node has a unique view, called the level of symmetry of the network. (The view at depth t from a node is the tree of all paths of length t originating at this node.) If nodes have unique identifiers, then λ = 0, which implies the same Ω(D) bound as in [START_REF] Kutten | On the complexity of universal leader election[END_REF].

Regarding message complexity, Gallager [START_REF] Gallager | Finding a leader in a network with o(e+n log n) messages[END_REF] presents the first election algorithm for general graphs with O(m+n log n) messages, where m is the number of edges, and a running time of O(n log n). Santoro [START_REF] Santoro | On the message complexity of distributed problems[END_REF] proves a matching Ω(m + n log n) lower bound for the number of messages. A few years later, Awerbuch [START_REF] Awerbuch | Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary)[END_REF] presents an algorithm whose message complexity is again O(m + n log n), but time complexity is taken down to O(n).

A number of questions remain open for election. Peleg asks in [START_REF] Peleg | Time-optimal leader election in general networks[END_REF] whether an algorithm could be both optimal in time and in number of messages. The answer depends on the setting, but remains essentially open [START_REF] Kutten | On the complexity of universal leader election[END_REF]. In the conclusion of their paper, Fusco and Pelc [START_REF] Fusco | Knowledge, level of symmetry, and time of leader election[END_REF] also observe that it would be interesting to investigate other complexity measures for the leader election problem, such as bit complexity. This measure can be viewed as a natural extension of communication complexity (introduced by Yao [START_REF] Yao | Some complexity questions related to distributed computing[END_REF]) to the analysis of tasks in a distributed setting.

Following [START_REF] Kothapalli | Distributed coloring in O( √ log n) bit rounds[END_REF], the bit round complexity of an algorithm A is the total number of bit rounds it takes for A to terminate, where a bit round is a round with single bit messages. This measure has become popular recently, as it captures into a single quantity aspects that relate both to time and to the amount of information exchanged. In this framework, the time-optimal algorithm of Peleg [START_REF] Peleg | Time-optimal leader election in general networks[END_REF] results in a bit round complexity of O(D log n) (i.e. O(D) rounds with O(log n) message size), and the message-optimal algorithm of [START_REF] Awerbuch | Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary)[END_REF] results in a O(n log n) bit round complexity (i.e. O(n) time with O(log n) message size).

In this paper, we present a bit round complexity optimal leader election algorithm for arbitrary synchronous networks. Our algorithm requires O(D + log n) bit rounds, and we show this is optimal by combining a lower bound from [START_REF] Kutten | On the complexity of universal leader election[END_REF] and a recent communication complexity result by Dinitz and Solomon [8]. This work is thus a step forward in understanding election, and a partial answer to whether optimality can be achived both in time and in the amount of information exchanged. (As opposed to measuring time on the one hand, and the number of messages of a given size on the other hand.) In this respect, our result illustrates the benefits of studying optimality under the unified lenses of bit complexity.

Contributions

We present an election algorithm ST T , having time complexity of O(D + log n) with messages of size O(1), where D is the diameter of the network. Algorithm ST T solves the explicit (i.e. strong) variant of the problem defined in [START_REF] Kutten | On the complexity of universal leader election[END_REF], namely, the identifier of the elected node is eventually known to all the nodes. It also fulfills requirements from [START_REF] Dinitz | Two absolute bounds for distributed bit complexity[END_REF], such as ensuring that every non-leader node knows which local link is in direction of the leader, and these nodes learn the maximal id network-wide (MaxF), as a by-product of electing this specific node in the explicit variant.

The architecture of our algorithm follows the same principle as many election algorithms, such as those of Gallager [START_REF] Gallager | Finding a leader in a network with o(e+n log n) messages[END_REF] or Peleg [START_REF] Peleg | Time-optimal leader election in general networks[END_REF]. It relies on a competition of spanning tree constructions that works by extinction of those trees originating at nodes with lower identifiers (see Algorithm 4 in [START_REF] Attiya | Distributed computing: fundamentals, simulations, and advanced topics[END_REF] and discussion therein). Eventually, a single spanning tree survives, whose root is the node with highest identifier. This node becomes elected when it detects termination (recursively from the leaves up the root). Difficulty arises from designing such algorithms with the extra constraint that only constant size messages must be used. Of course, one might simulate O(log n)-size messages in the obvious way paying O(log n) bit rounds for each message. But then, the bit round complexity would remain O(D log n). Our algorithm takes it down to O(D + log n).

For ease of exposition, we split the ST T algorithm into three components described below, whose execution is joint in a specific way.

1. A spreading algorithm S which pipelines the maximal identifier bitwise to each node, in a mix of battles (comparisons), conquests (progress of locally higher prefixes), and correction waves of bounded amplitude;

2. A spanning tree algorithm that executes in parallel of S and whose union with S is denoted ST . It consists in updating the tree relations based on what neighbour brought the highest prefix so far; 3. A termination detection algorithm that executes in parallel of ST and whose union with ST is denoted ST T . This component enables the node with highest identifier (and only this one) to detect termination of the spanning tree construction rooted whose root it is.

An extra component can be added to broadcast a (constant size) termination signal from the root down the tree, once election is complete. This component is trivial and therefore not described here.

Lower Bound: Dinitz and Solomon [START_REF] Dinitz | Two absolute bounds for distributed bit complexity[END_REF] prove a lower bound (Theorem 1 below) on the leader election problem among two nodes.

Theorem 1 ([8]

). Let M be an integer such that M ≥ 2. Let G be the graph with two nodes linked by an edge each node has a unique identifier taken from the set Z M = {0, • • • , M }. The bit round complexity of the Leader task and of the MaxF version is exactly 2 log 2 ((M + 2)/3.5) . This theorem implies that the time complexity of an election algorithm with messages of size O(1) is Ω(log n), and thus the bit round complexity of Algorithm ST T is Ω(log n).

On the other hand, the lower bound by Kutten et al. in [START_REF] Kutten | On the complexity of universal leader election[END_REF], establishing that Ω(D) time is required with logarithmic size messages, obviously extends to constant size messages. Put together, these results imply that the bit complexity of leader election with messages of size O(1) and identifiers of size O(log n) is Ω(D + log n), which makes our algorithm bit-optimal (up to a constant factor).

In fact, the lower bound holds for arbitrary sizes |id| of identifiers (necessarily larger than log n, though, since they are unique). Likewise, the complexity of our algorithm is expressed relative to identifiers of arbitrary sizes (see Theorem 25). Hence, the bit round complexity of the election problem is in fact Θ(D + |id|). Table 1.1 summarises these elements.

Outline: After general definitions in Section 2, we present the three components of the algorithm: the spreading algorithm S (Sections 3), its joint use with the spanning tree algorithm (ST , Section 4), and the adjunction of termination detection (ST T , Section 5). We conclude in Section 6 with some remarks.

Time Number of messages Message size Bit round complexity Awerbuch

[3] O(n) Θ(m + n log n) O(log n) O(n log n) Peleg [16] Θ(D) O(D m) O(log n) O(D log n) This paper O(D + log n) O((D + log n)m) O(1) Θ(D + log n)
Table 1. Best known solutions in terms of time and number of messages, compared to our algorithm.

2 Model and definitions

The Network

We consider a failure-free message passing model for distributed computing. The communication model consists of a point-to-point communication network described by a connected graph G = (V, E) where the nodes V represent network processes (or nodes) and the edges E represent bidirectional communication channels. Processes communicate by message passing: a process sends a message to another by depositing the message in the corresponding channel.

Let n be the size of V . We assume that each node u is identified by a unique positive integer of O(log n) bits, called identifier and denoted Id u (in fact, Id u denotes both the identifier and its binary representation). We do not assume any global knowledge on the network, not even the size or an upper bound on the size, neither do the nodes require position or distance information. Every node is equipped with a port numbering function (i.e. a bijection between the set of incident edges I u and the integers in [1, |I u |]), which allows it to identify which channel a message was received from, or must be sent to. Two nodes u and v are said to be neighbours if they can communicate through a port.

Finally, we assume the system is fully synchronous, namely, all processes start at the same time and time proceeds in synchronised rounds composed of the following three steps:

1. Send messages to (some of) the neighbours, 2. Receive messages from (some of) the neighbours, 3. Perform local computation.

The time complexity of an algorithm is the number of such rounds needed to complete the execution in the worst case.

Further definitions

The paper uses a number of definitions from graph theory and formal language theory. Although most readers may be familiar with them, we remind the most important ones. Next we define the bit round complexity.

Definitions on graphs: These definitions are selected from [START_REF]Handbook of discrete and combinatorial mathematics[END_REF] (Chapter 8). A tree is a connected acyclic graph. A rooted tree is a tree with one distinguished node, called the root, in which all edges are implicitly directed away from the root. A spanning tree of a connected graph G = (V, E) is a tree T = (V, E ) such that E ⊆ E. A forest is an acyclic graph. A spanning forest of a graph G = (V, E) is a forest whose node set is V and edge set is a subset of E. A rooted forest is a forest such that each tree of the forest is rooted. A child of a node u in a rooted tree is an immediate successor of u on a path from the root. A descendant of a node u in a rooted tree is u itself or any node that is a successor of u on a path from the root. The parent of a node u in a rooted tree is a node that is the immediate predecessor of u on a path to u from the root.

Definitions on languages: These definitions are selected from [START_REF]Handbook of discrete and combinatorial mathematics[END_REF] (Chapter 16). Let A be an alphabet, A * is the set of all words over A, the empty word is denoted by . If x is a non empty word over the alphabet A of length p then x can be written as the concatenation of p letters, i.e.,

x = x[1]x[2] • • • x[p] with each x[i] in A. If a ∈ A
and i is a positive integer then a i is the concatenation i times of the letter a. Let x and y be two words over alphabet A, x is said to be a prefix (resp. proper prefix) of y if there exists a word (resp. non-empty word) z such that y = xz.

Bit round complexity:

The bit complexity in general may be viewed as a natural extension of communication complexity (introduced by Yao [START_REF] Yao | Some complexity questions related to distributed computing[END_REF]) to the analysis of tasks in a distributed setting. An introduction to the area can be found in Kushilevitz and Nisan [START_REF] Kushilevitz | Communication complexity[END_REF]. In this paper, we follow the definition from [START_REF] Kothapalli | Distributed coloring in O( √ log n) bit rounds[END_REF], that is, the bit round complexity of an algorithm A is the total number of bit rounds it takes for A to terminate, where a bit round is a synchronous round with single bit messages. This measure captures into a single quantity aspects that relate both to time and to the amount of information exchanged. Other definitions are considered in the literature, in [START_REF] Bar-Noy | One-bit algorithms[END_REF][START_REF] Bodlaender | The distributed bit complexity of the ring: from the anonymous case to the non-anonymous case[END_REF][START_REF] Bodlaender | Bit-optimal election in synchronous rings[END_REF][START_REF] Dinitz | Bit complexity of breaking and achieving symmetry in chains and rings[END_REF] the bit complexity is the total number of bits sent until global termination. In [START_REF] Schneider | Trading bit, message, and time complexity of distributed algorithms[END_REF], it is the maximum number of bits sent through a same channel. In both variants, silences may convey much information, which is why we consider the definition from [START_REF] Kothapalli | Distributed coloring in O( √ log n) bit rounds[END_REF] in terms of round complexity as more comprehensive.

A spreading algorithm

This section presents a distributed spreading algorithm using only messages of size O(1) which allows each node to know the highest identifier among the set of all identifiers with a time complexity of O(D + log n), where D is the diameter of G.

Preamble

Given a node u and the binary representation Id u of its identifier. We define α(Id u ) as the word

α(Id u ) = 1 |Idu| 0Id u .
For instance, if u has identifier 23, then Id u = 10111 and α(Id u ) = 11111010111. This encoding has the nice property that it extends the natural order < of integers into a lexicographic order ≺ on their α-encoding.

Remark 2. Let u and v be two nodes with identifiers Id u and Id v . Then:

Id u < Id v ⇔ α(Id u ) ≺ α(Id v ).
As a result, the order between two identifiers Id u and Id v is the order induced by the first letter which differs in α(Id u ) and α(Id v ). This property is key to our algorithm, in which the spreading of identifiers progresses bitwise and comparisons occur consistently.

The algorithm S

Variables: Each node can be active or f ollower, depending on whether it is still a candidate for becoming the leader (i.e. no higher identifier was detected so far). Each node u also has variables Y u , Z u and Z v u (one for each neighbour v of u) which are words over the alphabet {0, 1}. Y u is a shorthand for α(Id u ), it is set initially and never changes afterwards. Z u is a prefix of Y w , for some node w (possibly u itself). It indicates the highest prefix known so far by u. On each node, this variable will eventually converge to the α-encoding of the highest identifier. Finally, for each neighbour v of u, Z v u is the lastest value of Z v known to u.

Initialisation: Initially every node u is active, all the Z u 's are set to the empty word , and the Z v u 's are accordingly set to the empty word (wlog, we assume that a preliminary round made it possible for all nodes to know what neighbours they have).

ST ; furthermore, as it is the only one, when it detects the termination it becomes elected. Our solution is a bitwise adaptation of the propagation process with feedback introduced in [START_REF] Segall | Distributed network protocols[END_REF] and further formalised and studied in Chapter 6 and 7 of [START_REF] Tel | Introduction to distributed algorithms[END_REF].

Definition 19. Let v be a node. Let t be a round number of the spreading algorithm. The variable Z t v is said to be well-formed if there exists an identifier Id such that Z t v = α(Id).

Each node v is equipped with a boolean variable T erm v which is true iff v and all of its subtree have terminated. Whenever a rule of the spreading algorithm is applied to node v, the variable T erm v is set to f alse, and a signal is sent to its neighbours to indicate that T erm v = f alse. Indeed, this variable can be updated several times for a same node before stabilizing to true.

We describe an extra rule to be added to the ST algorithm in order to allow the node with highest identifier to learn that it is so by detecting termination of the spanning tree algorithm. This rule is considered after those of algorithm ST in each round. Let us denote by N v the set of neighbours of v, and by Ch v ⊆ N v those which are v's children. Also recall that we omit the round number in the expression on variables when it is non ambiguous.

The rule: Given a node v, if (v is follower) and (T erm v = f alse) and (Z v is well-formed) and (∀w ∈ N v Z w = Z v ) and (∀w ∈ Ch v T erm w = true) then T erm v := true. Furthermore v sends to his parent a signal indicating that T erm v = true.

We denote by ST T the algorithm obtained by putting together the rules of Algorithm ST and this extra rule for termination detection.

Remark 20. Let v be a node, if T erm v = true then Z v has the same value it had when T erm v became true the last time.

Remark 21. If Ch v = ∅, i.e., v is a leaf, and Z v is well-formed and for each neighbour w of v Z w = Z v then v sets T erm v to true right away (and v sends to his parent a signal indicating that T erm v = true).

Remark 22. Let u be the node with highest identifier. Let v be a node. If Z v = α(Id u ) then Z v will never change.

Theorem 10 and Proposition 18 imply: Proposition 23. Let G be a graph such that each node has a unique (integer) identifier. Algorithm ST T terminates. Furthermore, if the node u has the highest identifier then, after a run of algorithm ST T , for each neighbour v of u Z v = α(Id u ) and T erm v = true and the node u receives from each node v in Ch u the signal indicating that T erm v = true.

The next proposition established that only the node with highest identifier can receive a termination signal from all neighbors.

Proposition 24. Let G be a graph such that each node has a unique identifier. Let v be a node which has not the highest identifier and such that Z v = α(Id v ) and for each neighbour w of v Z w = Z v . Then there exists a neighbour v of v such that T erm v = f alse.

Proof. The proof relies on transitive relations between T erm v values within the tree (detailed proof in the long version).

If the node u with highest identifier, becomes elected as soon as, for each neighbour v of u, Z v = α(Id u ) and T erm v = true and it receives from each child v the signal indicating that T erm v = true we deduce:

Theorem 25. Let G be a graph such that each node has a unique identifier which is an integer. Let u be the node with the highest identifier. There exists an election algorithm for G with messages of size O(1) which terminates after at most |α(Id u )| + 6D rounds.

Conclusion

Concerning deterministic election algorithms with identifiers, we may consider three complexity measures: time complexity, message complexity, and bit (round) complexity. Santoro [START_REF] Santoro | On the message complexity of distributed problems[END_REF] proved that Ω(|E| + n log n) is a lower bound for the number of messages and Awerbuch [START_REF] Awerbuch | Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary)[END_REF] presented an algorithm that matches this bound. Kutten et al. [START_REF] Kutten | On the complexity of universal leader election[END_REF] shows that concerning the time complexity Ω(D) is a lower bound and [START_REF] Peleg | Time-optimal leader election in general networks[END_REF] implies that O(D) is a tight upper bound. For bit (round) complexity, we deduced from [START_REF] Kutten | On the complexity of universal leader election[END_REF] and [START_REF] Dinitz | Two absolute bounds for distributed bit complexity[END_REF] that Ω(D + log n) is a lower bound and we presented an algorithm that matches this bound with a running time of O(D + log n) bit rounds. Our algorithm requires no knowledge on the graph such as the size or the diameter.

Main loop: In each round, the algorithm executes the following actions.

1. update Z u , 2. send to all neighbours a signal indicating how Z u was updated, 3. receive such signals from neighbours, 4. update all the Z v u accordingly. The main action is the update of Z u (step 1). It depends on the values of Z v u for all neighbours v and Z u itself at the end of the previous round. This update is done according to a number of rules. For instance, as long as u remains active and Z u is a proper prefix of Y u , the update consists in appending the next bit of Y u to Z u . Most updates are more complex and detailed further below. The three other actions (step 2, 3, and 4 above) only serve the purpose of informing the neighbours as to how Z u was updated, so that all Z v u are correctly updated. In fact, Z u can only be updated in seven possible ways, each causing the sending of a particular signal among {append0, append1, delete1, delete2, delete3, change, null}, with following meaning:

-append0 or append1: Z u was updated by appending a single 0 or a single 1; -delete1, delete2, or delete3: Z u was updated by deleting one, two or three letters from the end; change: Z u was updated by changing the last letter from 0 to 1; null: Z u was not modified.

Each node updates its variables Z v u based on these signals (step 4). Remark 3. By the end of each round, it holds that Z v u = Z v for any neighbour v of u. Thus from now on, Z v u is simply written Z v . We now describe the way Z u is updated by each node u. One property that the update guarantees is that by the end of each round, if u and v are two neighbours, then Z u and Z v must have a common prefix followed, in each case, by at most six letters. This fact is later used for analysis.

Update of Z u in each round: Let us denote the state of some variable X at the end of round t by X t . For instance, we write Z 0 u = , where round 0 corresponds to initialisation. The computation of Z u at round t results from u being active or follower, and the values of Z t-1 u and Z t-1 v for all neighbours v of u. It is done according to the following rules given in order of priority, i.e., R 1.1 has a higher priority than R 1.2 , having itself a higher priority than R 2 , etc. Whenever a rule is applied, the subsequent rules are ignored.

-R 1 (delete). The relationship between Z t-1 u and Z t-1 v for any neighbour v of u may mean that a delete operation is possible. If any delete is possible, one will be carried out; if more than one is possible, the greatest will be carried out.

u ; If none of these actions apply, then Z u remains unchanged and a null signal is sent. Otherwise, a signal corresponding to the resulting action is sent. We now prove some properties on Algorithm S. Lemma 4. Whenever a node u carries out a delete operation at round t, u's operation at round t + 1 must be another delete operation or a change operation.

Proof. The proof proceeds by induction on t (details in the long version).

Lemma 4 induces immediately:

Corollary 5. A sequence of delete operations on a node u ends with a change operation on u.

Remark 7. Let u be a node. If there exists a neighbour v of u and a round t such that |Z t u | < |Z t v | then u becomes f ollower.

Lemma 8. Let u and v be two neighbours. Let t be a round number. The words Z t u and Z t v will always take one of the following forms (up to renaming of u and v) where p and w are words and a is 1 or 0:

4. Z t u = p1 and Z t v = p0w and |w| ≤ 3, 5. Z t u = p and Z t v = pw and 3 ≤ |w| ≤ 6 and u has performed a delete.

Proof. The proof proceeds by examination of all possible cases (detailed proof in the long version).

The application of rule R 1.2 corresponds to item 4, thus:

2 is applied then 0 < |x| ≤ 3 and y = .

Lemma 8 implies:

Theorem 10. Let G be a graph of size n and diameter D such that each node u is endowed with a unique identifier Id u which is a non negative integer. Let X be the highest identifier. After at most |α(X)|+6D rounds, algorithm S terminates and for each node u, Z u = α(X).

Proof. The proof proceeds by induction on the distance of a node from the highest node (detailed proof the long version).

A Spanning Tree Algorithm

This section explains how the computation of a spanning tree may be associated to the spreading algorithm S by selecting for each node u the edge through which Z u was modified.

Let u be a node, we add for each neighbour v, a variable status v u whose possible values are in {child, parent, other}: it indicates the status of v for u; initially status v u = other. The computation of the spanning tree occurs concurently with the spreading algorithm S as follows. If R 2 , R 3 , or R 4 is applied at round t relative to neighbor v, then u choses v as parent (if not already the case). Then, in addition to the signals of the spreading algorithm (indicating how Z u was updated), u sends a signal parent to v and a signal other to its previous parent (if different from v).

After receiving signals from neighbours, in addition to the computation of the new value of Z v for each neighbour v by Algorithm S, u updates status v u . Algorithm ST denotes the algorithm obtained with Rules of the spreading algorithm S and actions described just above.

Remark 11. A node has no parent if and only if it is active. Remark 12. A node has at most one parent.

The next definition introduces for each node u a word T u that is used to prove that the graph induced by all the parent relations has no cycle.

Proof. Let t be a round, and let u 1 be a node. Let (u i ) 1≤i≤p be nodes of G such that, at round t, for 2 ≤ i ≤ p u i is parent of u i-1 . The previous lemma implies that (T t u i ) 1≤i≤p is increasing. Considering a couple (u j , u j+1 ) where R 2 , or R 3 , or R 4 has been applied for the last time before t, we obtain the result.

Corollary 16. Let t be a round number. Let u 1 be a node. Then either u 1 is active or there exist (u i ) 1≤i≤p nodes of G such that: for 2 ≤ i ≤ p u i is parent of u i-1 and u p is active. Definition 17. We denote by ST (G) the subgraph of G = (V, E) having V as node set and there is an edge between the node u and the node v if u is the parent of v or v is the parent of u when algorithm ST terminates.

When Algorithm ST terminates there is exactly one active node: the node with highest identifier. Now, from Remark 12 and Corollary 16: Proposition 18. Let G be a connected graph such that each node has a unique identifier. Let u be the node with the highest identifier. When algorithm ST terminates, the graph ST (G) is a spanning tree of G.

Termination Detection of Algorithm ST

This section presents some actions which, added to algorithm ST , enable the node with the highest identifier to detect termination of algorithm


Almost-sure asymptotic for the number of heaps inside a random sequence

Keywords: MSC 2010 Classification: 60F15, 60G55, 60K35 Hammersley's process, Heap sorting, Patience sorting, Longest increasing subsequences, Interacting particles systems, Almost-sure convergence

We study the minimum number of heaps required to sort a random sequence using a generalization of Istrate and Bonchis's algorithm (2015). In a previous paper, the authors proved that the expected number of heaps grows logarithmically. In this note, we improve on the previous result by establishing the almost-sure and L 1 convergence.

Introduction

The so-called Ulam's problem consists in estimating the length of the longest decreasing subsequence in a uniform random permutation σ of {1, . . . , n}. By duality, this question is equivalent to computing the minimal number of disjoint increasing sub-sequences of σ required to partition {1, . . . , n}. In [START_REF] Byers | Heapable sequences and subsequences[END_REF], Byers et al proposed variations on this problem where the question of finding increasing subsequences in a permutation is replaced by that of finding heapable subsequences. Subsequently, Istrate and Bonchis [START_REF] Istrate | Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley's Process[END_REF] introduced a modification of the classical patience sorting algorithm called heap sorting algorithm which now computes the minimal number of binary heaps required to partition {1, . . . , n}.

In [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF], we study a generalization of the algorithm which also allows for the heaps to be random. More precisely, let µ be a fixed offspring distribution on {1, 2, . . . , }. Let (U i , ν i ) be an i.i.d. sequence where U i and ν i are independent, U i is uniform on [0, 1] and ν i is distributed as µ. We use the following streaming algorithm to sort this sequence into Galton-Watson heaps i.e. labeled Galton-Watson trees with the condition that the label of each vertex is larger than that its ancestors.

Heap sorting algorithm for (U i , ν i ).

• We start at time 1 with a single tree containing a unique vertex (U 1 , ν 1 ) and set R(1) = 1.

• At time n, we have R(n) trees. To each vertex of these trees is associated a pair (U, ν).

The variable U represents the label of the vertex whereas ν prescribes the maximum number of offsprings that the vertex may have. A vertex (U, ν) is said to be alive if it has strictly less than ν children. This algorithm sorts the sequence (U i , ν i ), in their order of arrival, and in such way that 1. All the trees have the heap property.

2. The trees are asymptotically Galton-Watson distributed with offspring distribution µ and, at all time, the vertex with label U i has at most ν i children.

See Figure 1 for an illustration of the procedure. It is easy to verify that, remarkably, this greedy algorithm is optimal in minimizing the number of trees at all time. In [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF], we proved that, for any offspring distribution µ which is not the Dirac mass in 1 (i.e. we exclude Ulam's problem), then the expectation of the number of trees grows logarithmically as it was predicted in [START_REF] Istrate | Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley's Process[END_REF]:

there exists c µ ∈ (1, ∞) s.t. lim n→∞ E[R(n)] log n = c µ . (1)
The aim of this note is to bootstrap the result above, proving that the limit of R(n)/ log n also holds almost surely and in L 1 .

Theorem 1.1. For any offspring distribution µ = δ 1 , there exists c µ ∈ (1, ∞) such that

lim n→∞ R(n) log n = c µ a.s. and in L 1 .
As explained in [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] (and briefly recalled in the next section), we can associate to the heap sorting algorithm a particle system which plays the same role as Hammersley's line particle system for Ulam's problem. One of the main result of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] states that this particle system, while initially defined on compact intervals, can be extended to an infinite particle system on the whole line. Thus, the strategy to prove Theorem 1.1 is to first establish the almost sure convergence for an analog of R(n) associated with this infinite system on R and then transfer the result back to the discrete case. In this study, the key ingredients are the remarkable scaling properties of the infinite volume system together with monotonicity arguments.

2 Almost-sure convergence for the process on the half-plane

We start by recalling the construction of the Hammersley's tree process associated with the heap sorting algorithm introduced in [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF]. Let H denote the upper half-plane R × (0, ∞). Consider a point Poisson process (PPP)

Ξ = (U i , T i , ν i )
on H × N with intensity du × dt × µ. For any a < b, we consider the following particle system H on (a, b) × N constructed from the atoms of Ξ inside the strip (a, b) × (0, ∞).

H(t)

Figure 2: An example of the graphical representation G0,1 (which is, in fact, an embedding of the sequence of Figure 1). Crosses represent the atoms of Ξ. At time t, H(t) has four particles located at position 0.3, 0.4, 0.7, 0.8 with respective number of lives 1, 3, 1, 1.

• There is no particle at time t = 0.

• Given H(t -), an atom (u, t, ν) of Ξ with u ∈ (a, b) creates in H(t) a new particle at position u with ν lives. Furthermore, the particle in H(t -) with the largest label smaller than u loses one life (if such a particle exists) and is removed from the system if it was its last life.

We can represent the genealogy of the particles using a set of vertical and horizontal lines. Here, vertical lines denote the positions of particles through time and horizontal lines connect particles to their father on their left (or to the vertical axis if they have no father). We denote G a,b this graphical representation of the process. See Figure 2 for an illustration.

For a = 0 and b = 1, this particle system may be seen as a continuous time embedding of the heap sorting algorithm where new labels now arrive with Poissonian rate instead of integer time. Therefore, the heaps created by the algorithm are exactly the trees "drawn" by the graphical representation. In particular, the number of trees (equiv. heaps) created between time s and t is equal to the number of horizontal lines in G 0,1 intersecting the vertical segment {0} × [s, t].

Since incoming particles do not affect particles already present on their right, it is clear that the graphical representations G a,b are compatible for different values of the left boundary i.e.

for a < a the restriction of G a ,b to (a, b) × (0, ∞) coincides with G a,b .
Thus, there is no problem to define G -∞,b . Clearly, this compatibility relation does not hold anymore when it is the right boundary that extends since new particle may "kill" their left neighbour. However, Theorem 4.4 of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] states that the graphical representation G -∞,b still converges locally, almost surely, as b tends to infinity, to a random graphical representation G ∞ on H. This limiting graphical representation is such that there is only finitely many horizontal and vertical lines crossing any compact set inside H. On the other hand, there is an accumulation of horizontal lines at the bottom of the half plane i.e. near the X-axis. See Figure 3 for a picture showing how this graphical representation G ∞ looks like.

The following result is the counterpart of Theorem 1.1 for the infinite volume system.

lim t→∞ R ∞ [1, t] log t = E(R ∞ [1, e
]) a.s. and in expectation.

Let us point out that this result does not assert the finitness of E(R ∞ [1, e]) (otherwise, the limit above is simply infinite). However, E(R ∞ [1, e]) is indeed always finite as we shall see later.

Proof. We decompose the number of horizontal lines crossing the vertical axis during the time interval [1, e n ] in the following way:

R ∞ [1, e n ] = n-1 i=0 R ∞ [e i , e i+1 ].
For any i > 0, the invariance of the Poisson measure under the mapping

H → H (u, t) → (e i u, t e i )
implies that the law of G ∞ is also invariant under this transformation. Thus, it follows that the sequence (R ∞ [e i , e i+1 ], i ≥ 0) is stationary. In particular, for any i ≥ 0, the r.v. R ∞ [e i , e i+1 ] has the same law as R ∞ [1, e]. This already proves that

E[R ∞ [1, e n ]] n = E(R ∞ [1, e]).
The sequence (R ∞ [e i , e i+1 ], i ≥ 0) is clearly not i.i.d. Yet, we will show that it is ergodic since it is mixing. Thus, the ergodic theorem will implies that

lim n→∞ R ∞ [1, e n ] n = E(R ∞ [1, e]) a.s. (2)
Finally, from (2) and using the monotony of R ∞ [1, t] with respect to t, we will conclude that

lim t→∞ R ∞ [1, t] log t = E(R ∞ [1, e]) a.s.
Thus, it remains to prove that the sequence (X i := R ∞ [e i , e i+1 ], i ≥ 0) is mixing i.e. that for any n, m and any bounded functions f : R n+1 → R and g : R m+1 → R,

lim k→∞ E [f (X 0 , . . . , X n )g(X k , . . . , X k+m )] = E [f (X 0 , . . . , X n )] E [g(X 0 , . . . , X m )] . (3)
Fix n, m ≥ 0 and k > n + 1. Let Xk denote the number of horizontal lines crossing the segment {0} × [e k , e k+1 ] when we remove all the atoms of Ξ below height e n+1 . By construction, G ∞ ∩ (R × (0, t)) is determined by the atoms of Ξ below height t. In particular, this implies that (X 0 , . . . , X n ) is independent of ( Xk , . . . , Xk+m ). Moreover, up to a translation, the graphical representation obtained by removing all atoms below a given height as the same law as G ∞ . Thus, the vector ( Xk , . . . , Xk+m ) has the same distribution as the vector (R ∞ [e ke n+1 , e k+1e n+1 ], . . . , R ∞ [e k+me n+1 , e k+m+1e n+1 ]), which is also equal, using the scaling property, to the law of (R ∞ [1e n+1-k , ee n+1-k ], . . . , R ∞ [e me n+1-k , e m+1e n+1-k ]). Therefore, we obtain the limit in law lim k→∞ ( Xk , . . . , Xk+m )

L = (X 0 , . . . , X m ). (4)
On the other hand, adding atoms below a given height s can only decrease the number of horizontal lines crossing the segment {0} × [s, t] (see for instance Equation ( 12) of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] for more details). This monotonicity result implies that, for any k > n + 1,

X k ≤ Xk . (5)
We can now write E [f (X 0 , . . . , X n )g(X k , . . . , X k+m )] = E f (X 0 , . . . , X n )g( Xk , . . . , Xk+m ) + E f (X 0 , . . . , X n )(g( Xk , . . . , Xk+m )g(X k , . . . , X k+m ))

= E [f (X 0 , . . . , X n )] E g( Xk , . . . , Xk+m ) + E f (X 0 , . . . , X n )(g( Xk , . . . , Xk+m )g(X k , . . . , X k+m )) .

The first term of the r.h.s. of the last equality tends to E [f (X 0 , . . . , X n )] E [g(X 0 , . . . , X m )] according to (4). Concerning the second term, we write

E f (X 0 , . . . , X n )(g( Xk , . . . , Xk+m ) -g(X k , . . . , X k+m )) ≤ 2||f || ∞ ||g|| ∞ P{∃i ≤ m, Xk+i = X k+i } ≤ 2(m + 1)||f || ∞ ||g|| ∞ sup i≥k P{ Xi = X i }.
Finally, the following easy lemma ascertains that sup i≥k P{ Xi = X i } tends to 0 which concludes the proof of (3).

Lemma 2.2. Let (U k ) and (V k ) be two sequences of integer-valued random variables such that

(i) U k ≤ V k for all k.
(ii) The sequence (U k ) is tight.

(iii) lim k→∞ P{U k = a} -P{V k = a} = 0 for every a.

Then, lim

k→∞

P{U k = V k } = 0.
Proof. We first show by induction on i that

lim k→∞ P{V k = i, U k = i} = 0.
Indeed, we find, using (i), that

P{V k = 0, U k = 0} = P{U k = 0} -P{V k = 0, U k = 0} (6) = P{U k = 0} -P{V k = 0}, (7)
which, according to (iii), tends to 0 as k tends to infinity. Now, for i ≥ 1, we write

P{V k = i, U k = i} = P{U k = i} -P{V k = i, U k = i} = P{U k = i} -P{V k = i} + P{V k = i, U k < i} ≤ P{U k = i} -P{V k = i} + j<i P{V k = j, U k = j}.
The induction hypothesis combined with (iii) implies that the r.h.s. of the last equation tends to 0 as k tends to infinity. Hence, (6) holds for all i. Finally, writing that, for any A > 0,

P{V k = U k } ≤ P{U k ≥ A} + i<A P{V k = i, U k = i},
and using the tightness of the sequence (U k ), we deduce that P(V k = U k ) tends to 0 as k tends to infinity. Proposition 3.1. Assume that µ = δ 1 . We have

lim t→∞ R [0,1] [0, t] log t = E [R ∞ [1, e]]
a.s. and in L 1 .

Proof. As we already noticed, G 0,1 coincides with G -∞,1 restricted to the strip [0, 1] × (0, ∞). Furthermore, taking into account the atoms inside (1, +∞) × (0, ∞) can create new horizontal lines inside [0, 1] × (0, ∞) but cannot remove those already present (see Section 2.3.1 of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] for details). Thus, the horizontal lines of G 0,1 are a subset of the horizontal lines of G ∞ . This domination implies in particular that

R [0,1] [s, t] ≤ R ∞ [s, t].
In particular, we get

R [0,1] [0, t] ≤ R [0,1] [0, 1] + R ∞ [1, t]
(we need this splitting since R ∞ [0, 1] is infinite). The quantity R [0,1] [0, 1] is bounded by the number of atoms in the box [0, 1] 2 . Thus, in view of Proposition 2.1, we find that

lim sup t→∞ R [0,1] [0, t] log t ≤ E(R ∞ [1, e
]) a.s. and in expectation.

Let us now prove the matching lower bound. Fix some N ≥ 0. For n ≥ N , we decompose R [0,1] [0, e n ] in the following way

R [0,1] [0, e n ] = R [0,1] [0, e N ] + n-1 i=N R [0,1] [e i , e i+1 ].
For i ≥ N , let X N i := R [0,e N -i ] [e i , e i+1 ] be the number of horizontal lines attached to the Y-axis between heights e i and e i+1 when we consider only the atoms of Ξ with absciss in the interval [0, e N -i ]. Using the same monotonicity argument as above, we have, for any i ≥ N ,

R [0,1] [e i , e i+1 ] ≥ X N i .
Thus, for n ≥ N , we get

R [0,1] [0, e n ] ≥ R [0,1] [0, e N ] + n-1 i=N X N i .
Using again the invariance of the law of Ξ under the mappings

H → H (u, t) → (e i u, t e i )
we deduce that the sequence (X N i , i ≥ N ) is stationary. In particular, for any i ≥ N , X N i has the same law as R [0,e N ] [1, e]. Again, we prove that the sequence is mixing i.e. for any n, m and any bounded functions f : R n+1 → R and g : R m+1 → R,

lim k→∞ E f (X N N , . . . , X N N +n )g(X N k , . . . , X N k+m ) = E f (X N N , . . . , X N N +n ) E g(X N N , . . . , X N N +m ) .
The argument is the same as in the previous section. Indeed, consider, for k > N + n, the number XN k of horizontal lines crossing the Y-axis between height e k and e k+1 when we only take into account the atoms of Ξ in the domain [0, e N -k ] × [e N +n+1 , ∞). It is easily checked that the following holds

1. X N k ≤ XN k . 2. ( XN k , . . . , XN k+m ) is independent of (X N N , . . . , X N N +n ). 3. lim k→∞ ( XN k , . . . , XN k+m ) L = (X N N , . . . , X N N +m ).
These three properties imply, just as for Proposition 2.1, that the sequence is mixing. Thus, the ergodic theorem implies the almost sure limit

lim inf n→∞ R [0,1] [0, e n ] n ≥ lim n→∞ n-1 i=N X N i n = E X N N = E R [0,e N ] [1, e] .
On the other hand, the sequence (R [0,e N ] [1, e], N ≥ 0) increases to R ∞ [1, e] as N tends to infinity. Thus, the monotone convergence theorem yields lim

N →∞ E[X N N ] = E R ∞ [1, e]
which proves the convergence of R [0,1] [0, t]/ log t towards E R ∞ [1, e] almost surely and in expectation.

It remains to prove the L 1 convergence. Let us first recall that Theorem 2.1 of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] states that the limit in Proposition 3.1

c µ := lim t→∞ E R [0,1] [0, t] log t is finite for any µ = δ 1 . We write E R [0,1] [0, t] log t -c µ = E R [0,1] [0, t] log t -c µ + 2E c µ - R [0,1] [0, t] log t + .
The random variable c µ -R [0,1] [0,t] log t + converges a.s. to 0 and is bounded by c µ . Thus, the previous convergence in expectation combined with the dominated convergence theorem yield the L 1 convergence of R [0,1] [0, t]/ log t. Remark 3.2. In a previous paper [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF], it was shown that the infinite graphical representation exists, which is the same as saying that R ∞ (s, t) is finite for any 0 < s < t. However, it was not proved that the expectation of R ∞ (s, t) is also finite. This is now a consequence of the previous proposition combined with the main result of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF] stating that c µ is always finite. Still, we point out that the arguments presented here do not allow, by themselves, to recover that c µ is finite.

We now have all the tools needed to prove Theorem 1.1. Furthermore, using the convergence in expectation of R(n) log n towards the same limit (see Theorem 2.1 of [START_REF] Basdevant | From Hammersley's lines to Hammersley's trees[END_REF]), we also deduce the L 1 convergence.

Figure 3 :

 3 Figure 3: Simulation of the full half plane representation G∞ in the case of binary heaps (µ = δ2). The box displayed is [0, 40] × (0, 15]. There is an accumulation of horizontal lines at y = 0 and of vertical lines at y = +∞.

3 1 ]

 1 Almost-sure convergence for the process on [0, We now translate Proposition 2.1 for the Hammersley process defined on the finite interval [0, 1]. We use the notation R [a,b] [s, t] for the number of horizontal lines crossing the segment {0}×[s, t] in the graphical representation G a,b obtained by using only the atoms of Ξ in the strip [a, b]×(0, ∞).

Proof of Theorem 1 . 1 .

 11 Recall that the processes R and R [0,1] are time changed of each other:R(n) = R [0,1] [0, t(n)],wheret(n) := {t ≥ 0, card(Ξ ∩ [0, 1] × [0, t] × N) = n}counts the number of atoms of Ξ inside the box [0, 1] × [0, t]. Since t(n)/n tends a.s. to 1 as n tends to infinity, we get from Proposition 3.1 thatlim n→∞ R(n) log n = lim n→∞ R [0,1] [0, t(n)] log t(n) log t(n) log n = E [R ∞ [1, e]] = c µ a.s.

  n+1 , ν n+1 ) as the children of the vertex which is still alive and which has the largest label smaller than U n+1 . If no such vertex exists, we create a new tree with root (U n+1 , ν n+1 ).

							.8		.8
			.7	.7		.7	.4	.7	.4	.7	.4	.3
	(.1; 1)	(.7; 2)	(.2; 2)		(.4; 3)		(.8; 1)		(.3; 1)
	∅	.1	.1	.1	.2	.1	.2	.1	.2	.1	.2
	Figure 1: Example of heap sorting algorithm for the sequence (.1, 1), (.7, 2), (.2, 2), (.4, 3), (.8, 1), (.3, 1), . . .

• At time n + 1, we add (U