Dominique Cansell
email: cansell@loria.fr

Dominique Méry
email: mery@loria.fr

Joris Rehm
email: rehm@loria.fr

Time constraint patterns for event B development

Keywords: event B, pattern, distributed systems, refinement

Distributed applications are based on algorithms which should be able to deal with time constraints. It is mandatory to express time constraints in (mathematical) models and the current work intends to integrate time constraints in the modelling process based on event B models and refinement. The starting point of our work is the event B development of the IEEE 1394 leader election protocol; from standard documents, we derive temporal requirements to solve the contention problem and we propose a method for introducing time constraints using a pattern. The pattern captures time constraints in a generic event B development and it is applied to the IEEE 1394 case study.

Introduction

Overview

In this article, we present work in progress on the modelling of time in event B using patterns. The concept of time is not predefined in B but using set theory we can effectively model it. Generally most formal models "implement" time in the first abstraction and they explicitly express time constraints in models of computations or automata; several notations propose solutions for expressing time and time constraints (timed automata of Alur and Dill [START_REF] Alur | A theory of timed automata[END_REF]). We think that it is not a good idea to introduce time too early in the development process, because invariants on time (using natural numbers and arithmetic) introduce too much noise for proof assistants and consequently most proof obligations need interaction. Using abstraction without time we can solve and prove more easily important properties of the system and obtain a first scheduling of events. For us, time can be introduced later in a specific refinement where time is a global variable.

Motivations for integrating time constraints in event B development

Needs for integrating time constraints in event B development are motivated by observations on a case study developed by Jean-Raymond Abrial, D. Cansell and D. Méry [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF] and the goal was to redevelop the leader election protocol and to provide a proof simpler and easier to understand than Devillers et al [START_REF] Marco Devillers | Verification of a leader election protocol: Formal methods applied to ieee 1394[END_REF].

The IEEE 1394 leader election protocol works properly provided the network is acyclic; but it is sensitive to time constraints [START_REF] Romijn | A timed verification of the ieee 1394 leader election protocol[END_REF], since it may loop forever if no time constraint is taken into account. In fact, the problem appears when the algorithm is executed and leads to a situation where two nodes of a finite network a and b are in contention. Let us recall the problem using events. Node a sends a message to b and asks him to be its child, while node b is asking to a to be its child. The two nodes a and b have sent messages to each other and the messages were sent independently. No one wants to be the leader but no other one can be the leader, since they are the last nodes in the election process: the others nodes have already asked to be children or grand-children of a or b. This problem is called the contention problem. This problem can occur with only two nodes of the network (this can be proved using our models). In the "real" protocol the problem is "solved" by means of timers. As soon as a node a discovers a contention with node b, it waits for a very short delay in order to be sure that the other node b has also discovered the problem. The very short delay in question is at least equal to the message transfer time between nodes (such a time is supposed to be bounded ). After this, each node randomly chooses (with probability 1/2) to wait for either a "short" or a "large" delay (the difference between the two is at least twice the message transfer time). After the chosen delay has passed each node sends a new request to the other if it is in the situation to do so. Clearly, if both nodes choose the same delay, the contention situation will reappear. However if they do not choose the same delay, then the one with the largest delay becomes the father of the other: when it wakes up, it discovers the request from the other while it has not itself already sent its own request, it can therefore send an acknowledgement and thus become the father. According to the law of large numbers, the probability for both nodes indefinitely choosing the same delay is zero. Thus, at some point, they will (in probability) choose different delays and one of them will thus becomes the father of the other. Abrial et al. [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF] present a partial formalisation of the contention problem and the idea is to introduce a virtual channel which is used to resolve the contention. Recently, J-R. Abrial et al propose a simpler (without acknowledgement and confirmation) algorithm [START_REF] Abrial | A new IEEE 1394 leader election protocol[END_REF]. In both models, the contention is solved abstractly and no time reference is used. The real algorithm uses time constraints to solve this contention. Our starting questions were:

can we add time constraints in previous abstract models to facilitate more realistic refinement? -can we do this in a systematic way using something similar to design patterns in object-oriented software development [START_REF] Gamma | Design patterns: Abstraction and reuse of object-oriented design[END_REF]?

The questions will be partly addressed in the next sections. However, the introduction of time is not the main issue and the next sub-section motivates the introduction of patterns in the B methodology.

B patterns

Designing models of a complex system using refinement and proofs are very hard and often not very well used. This proof-based modelling technique is not automatically done, since we need to extract some knowledge from the system in an incremental and clever way. The event B method allows one such development and many case studies have been developed, including sequential algorithms [START_REF] Abrial | Formal derivation of spanning trees algorithms[END_REF], distributed algorithms [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF][START_REF] Cansell | Formal and Incremental Construction of Distributed Algorithms: On the Distributed Reference Counting Algorithm[END_REF], parallel algorithms [START_REF] Abrial | Formal Construction of a Nonblocking Concurrent Queue Algorithm (a Case Study in Atomicity)[END_REF] or embedded systems for controlling train like METEOR [START_REF] Behm | METEOR : A successful application of B in a large project[END_REF] or Roissy Val [START_REF] Badeau | Using B as a high level programming language in an industrial project: Roissy val[END_REF]. The last example was developed faster because previous models were reused and a specific automatic refining tool -Edit B developed by Matra (now Siemens)-was utilised. EditB provides automatic refinement from an abstract B model, which can be proved more quickly and automatically using or adding specific rules in the B prover; EditB is a "private" tool and only Siemens uses it to develop systems. The interesting thing is that the engineer activity (typing model) is very much simplified. This tool seems to apply a similar technique to those used in design patterns. It is the application of well-engineered patterns for a specific domain.

Three years ago Jean-Raymond Abrial, D. Cansell and D. Méry worked on using genericity in event B [START_REF] Cansell | Assistance au développement incrémental et à sa preuve[END_REF][START_REF] Abrial | B # : Toward a synthesis between z and b[END_REF]. When a designer develops a generic development (a list of models related by refinement) both modelling and proof are easily done. Models are more abstract and consequently the set of proof obligations can be discharged more automatically or in an interactive way (it is less noisy for the prover). The generic development can be reused by instantiation of the carrier sets and constants of the development (list of models). We obtain a new development (list of models) which is correct, if all instantiated sets and constants satisfy properties of the generic development. An interesting point is that we do not prove the proof obligation of the instantiated development. This technique is well known by mathematicians who prove abstract theorems and reuse these on specific cases reproving the instantiated axioms of the theorem to obtain (for free or without proof) the instantiated goal of the theorem.

Recently, Jean-Raymond Abrial has presented [START_REF]Using Design Patterns in Formal Devlopments -Example: A Mechanical Press Controler[END_REF] patterns for the action/reaction paradigm to systematically develop the mechanical press controller.

These contributions follows the same direction leading to reuse previous proof-based developments, to give guidelines for mechanical refinement in daily software development. In our opinion, a B pattern is an event B development which is proved, sufficiently generic and can be partially reused in another specific B development to produce automatically new refinement models: proofs are (partly) inherited from the B pattern.

Summary

Our paper proposes initial and partial answers to these questions. We do not give an exact definition of B patterns. It is too early to propose a standard definition as many works are converging to this B pattern concept. We describe a pattern with regard to time and how we can use it to produce other patterns or to solve a specific problem. The next section introduces the time constraint pattern and its construction. Section 3 presents an application of our pattern for a message passing system. Section 4 concludes the paper by the IEEE 1394 case study and future works.

Time constraint pattern

In order to express time and time constraints we introduce a new pattern. This pattern demonstrates our modelling choice and gives a general background to reason about things like time progression, clock or timer. The main idea is to guard events with a time constraint, therefore those events can be observed only when the system reaches a specific time. The time progress is also an event, so there is no modification of the underlying language of B. It is only a modelling technique instead of a specialised formal system. The variable time is in N but time constraints can be written in terms involving unknown constants or expressions between different times. Finally, the timed event observations can be constrained by other events which determine future activations.

Defining the pattern

We can explain our method through an example event-B model. Later this model can be used like a pattern to refine another model adding time considerations. As you can see below, the pattern has two variables:

model m0 variables time, / * current time * / at/ * Active Times * / invariant time ∈ N ∧ at ⊆ N ∧ (at = ∅ =⇒ time ≤ min(at)) initialisation time := 0 || at := ∅ events ...
time in N models the current time value. The incrementation of this value denotes the time progression.

at ⊆ N is the known future active times of the system. Each active time stands for a future event activation. For example, a simple clock will have a set of active times like {time + 1, time + 2, ...}.

Since this pattern is very general, the invariant is simple and we have only to satisfy at = ∅ ⇒ time ≤ min(at). This means that active times are in the future.

As a consequence of this fact the time can not be moved beyond the first active time, this is intuitively correct because if time goes beyond one event activation, then we miss the right moment for observing it.

The three events represent three different temporal aspects. The first event is the creation of a new active time. In real system this can be the initialisation of a timer or the setting of a new time constraint. We denote this by "posting" new active times in the event "post time". This event is needed when the activation of the system is dynamic. For our example of a regular clock the active times are known for every system so we have only to initialise the set at with N. In this case, the event post time is not required. For more complex cases like message passing in a network, the active times are determined by the message arrival so we need an event like post time observed when a message is sent to constrain the system to receiving them some time later. The event takes a new active time tm which is indeterminate in the most general case but it can be more specific like time + delay with a constant delay in N and greater than 0.

The second aspect is time progression. In this modelling approach, in a system state the time is frozen and it can go with an observation of the tick tock event.

time at1 at2 at3

As we have already said, time progress is nondeterministic, the new value tm should only satisfy the invariant with tm ≤ min(at), if at = ∅. Otherwise time can take place everywhere and let the system trigger any event potentially. But as time is a natural and tm > time we are sure that the system will reach the next active time if tick tock is activated enough. Thanks to the set at, which is very general, this event can be copied without modification when we use the time constraint pattern. Now we can look at the last aspect which is the goal of our work. With this event "process time" we can consider events with time constraints. process time = when time ∈ at then at := at -{time} end

The guard time ∈ at and the invariant implies that time has reached the first active time. The time can have made one or more step with one or more activation on tick tock and other temporised events may have occurred.

time = at2 at3

X at1

The current active time is deleted from at therefore an active time can be used once and only once. After this removal the time and the system can continue to change.

Applying the time constraint pattern

This model can be used as a pattern, but it is very general and the invariant is limited. The pattern can be fit to time-sensitive systems in order to introduce time behaviour and prove invariants. Consequently such B patterns can be used as a systematic help to refine systems.

As this pattern represents a way to write time arguments it can not be used directly but needs to be adapted to a specific system (except for tick tock which can be used directly).

At first, events of the system involving time must be present and written in a proved model. The idea is to use refinement and make an abstract model where time is implicitly controlled by events as usual. One can already reason about a model without time and prove general or abstract properties on the system. Next, the pattern should be adapted except tick tock. The two aspects involved in post time and process time need to be identified from the modelled system. For instance, the beginning of a timer, sending of message or other initiation of non-instantaneous actions match the posting time event. Connected to that timer ending, message reception or finalisation of non-instantaneous actions match the processing time event. The result will be a set of adapted and renamed instances of post time and process time events.

When this aspect of events has been identified we can use it to refine the abstract model with a superposition of modified events; we refine the abstract model; for instance, we can substitute an abstract guard model by concrete time expression; in this way, we can prove that the time constraints implements required behaviour.

Some specific adaptation or improvement may be used:

-The two ideas of posting and processing active times have been presented separately for getting the essence of the concept. However they are often mixed in the same event. One can make a chain of reactions with time constraints between events. -There is no contradiction to consider more than one time posting in an event which refines post time. We can add a number of active times in one shot. Using the same idea, an infinite number of times can be posted using generalised substitution: for example, on the initialisation of the system. -In addition to the set at we can add variables to express in a more specialised and meaningful way active times. These variables have common elements with at. For example, we can store sending time of messages. All these added variables allow one to write more specialised time constraints and give different categories of active times inside at. -With the last remark, we can have different categories but we can not simply trigger more than one event at the same time because at is a set and it can not contain several identical values like in a multiset. To resolve this we can take several sets like at or take a function to index different sets. This index will represent different processes which can run at the same time. Of course this modification needs to be done in the same way for the rest of the model: invariant and other events. With this adaptation we can represent different local clocks or several processes.

Comparisons with other methods

Our solution does not require a language with explicit time expression. Consequently it is difficult to compare this work with other solutions. A big part of other work uses timed automata [START_REF] Alur | A theory of timed automata[END_REF] with model checkers such as Uppaal [START_REF] Bengtsson | UPPAAL -a tool suite for automatic verification of real-time systems[END_REF] or Kronos [START_REF] Daws | The tool KRONOS[END_REF]. These automata allows one to write transition systems with time.

Transitions between states are instantaneous and time can progress inside a state. One can use several clocks (variables in R). Time constraints are comparisons of clocks with numeric constants and can be set both on state and transition. Automata can only stay in a state, if clock does not exceed time constraints. In the same way system can transit, if constraints are valid. One can reset clock to zero on transition, so the time may be cyclic. We can point out fundamental differences with our time model using connections between event B models and automata. In our model it is a transition (event) which makes time progress under some condition instead of a state such that time can grow under a limit. For this reason we can have several event activations which are instantaneous. Usually we do not reset time to zero because we can infinitely add active times in the future.

The main difference comes with the use of the active times set which are not explicit in timed automata theory. The word "clock" does not fit very well with our approach because the variable time denotes the general time passing. For us a clock is a relation between time progression and known future active times. This set is also the main difference with the explicit-time description in [START_REF] Abadi | An old-fashioned recipe for real time[END_REF] and [START_REF] Lamport | Real time is really simple[END_REF] by L. Lamport et al. As a result our tick tock event is more general because it only refers to elements of this set.

Properties certification for timed automata is done by a model-checker. The infinite number of states (because of time) is reduced to a finite set of partitions over vector space make by clocks. In our case, proof are made as usual with first order classical logic and set theory inside B tools. Some other works related to real-time systems can be found in [START_REF] Fidge | An action-based formal model for concurrent real-time systems[END_REF] by C.J. Fidge and A.J. Wellings, their approach is different than ours because they do not use instantaneous actions.

Message passing using the time constraint pattern

This section presents an application of our pattern. We design a system of two devices a and b. Device a can send a message to b. We prove that a timer triggered after sending ensure to a the effective reception of message by b (we do not take into account loss of message). The system is described by two models. The first model has basic elements and events sequencing. The second model refines the previous sequencing of events by time constraints.

Abstract model

As a first step we introduce the problem with an abstract model. The model consists of two constants a and b for the devices, four variables A, S, B and AB, and three events :

-sendA : a sends its message to b using connection AB -recB : b receives it from the connection AB -quA : when a knows that the message is received by b, it modifies one of its local variable S.

The invariant of the model is:

A ⊆ { a } ∧ B ⊆ { b } ∧ AB ⊆ { a } ∧ S ⊆ { a } ∧ (A = ∅ =⇒ AB = ∅)
According to a distributed system, we consider that A and S are local variables for device a, B is a local variable for device b and AB is a global variable for the channel between the two devices. Similarly events sendA and quA are local to device a and event recB is local to device b. A denotes sending of the message if and only if A is not empty, similarly B denotes its reception and S denotes the state after execution of quA. All variables are booleans (empty or not). Next we define the three events:

sendA = when A = ∅ then A := { a } || AB := { a } end recB = when AB = { a } then B := { b } || AB := ∅ end
Using A to express the sending of the message and B its reception, these events implicitly denote a delay between the execution of sendA and recB. After this delay, we make an action (the reception of the message) as a requirement. To specify this we explicitly ask the message to be received, in the guard of quA.

quA = when B = { b } then S := { a } end
In the abstract model we are "cheating" because event quaA is intended to be local to device a but it can see the variable B which is intended to be local to device b. It is as if device a can see local information of device b. In order to enforce the localisation property as we are moving towards implementation we refine this specification with the time constraint pattern.

-(A = ∅ =⇒ stm + prop < slp):

This invariant uses the fact that prop < st because event sendA provides the following proof obligation: {a} = ∅ =⇒ time + prop < time + st. This fact is a property on constants st and prop which expresses that the propagation time is less than the sleep time.

The abstract event quA is cheating, since it looks the variable B in its guard (B = {b}); the refined version is no more cheating, since the guard is local (A = ∅ it has sent the message) and the temporal guard time = slp. Only time is a global variable shared by each participant of the global system: it is local for each participant and everyone has the same time. We assume that the time is the same of everyone.

Concluding remarks and perspectives

On the contention problem

This work began with the time constraint problems inside the firewire protocol. The protocol, namely IEEE 1394, can be found in computers and devices like cameras or external hard-disks and is used to connect them together in a local network. When one or several devices are connected or disconnected, they are able to reconfigure themselves. The reconfiguration consists of the election of a network leader. The network is a symmetric acyclic graph, the algorithm of election orients edges to obtain a spanning tree rooted by a leader.

At each step of this distributed algorithm a device is submitted to another. The submitted device is a leaf node among non-submitted devices. The submission of the device is done by sending a message to the device next to it.

But, at the end of the process, a contention problem may occur with the last two devices (and only in this case). Since both devices are leaves, they can send submission almost at the same time. In this case, the two messages cross in the bi-directional channel between the last devices. The election can not be done because both devices are in a submission state.

We can see in the figure 1 an example of contention. X and Y devices are sending messages together with the arrow "1". After the first sending there is a period "a", in this period the other node can send a second message because the first is not received. The protocol has a special case for this problem, the chosen solution deletes the two submission messages and tries to choose a leader with a new message. Messages are not structured packets but constant signals, so a message can be put on or removed from the channel. To give a chance for resolving contention each device chooses a delay between a long and a short time. Then they sleep for the chosen delay. We can see a example below in figure 2 with the two delays "b" and "c" and the deletion of message with the arrow "2".

When the device awakes, there are two possibilities:

-No message has arrived during the sleeping time, so the device can send a submission message. This contention solving succeeds only if the chosen times are different, in this case only one message is re-sent and the receiver becomes the leader. We can see this discriminatory message labelled "3" in the figure 2. On the other hand if sleeping times are the same the contention problem occurs again and the same process begin.

As we have seen there are a lot of time issues in this part of the protocol. Time is needed to quantify the two different sleeping times and to represent the progression of the message signals over the channel.

Conclusion

The starting point of our work is the proof-based development of the IEEE 1394 leader election protocol and the observation of the partiality of the resulting proved solution [START_REF] Abrial | A mechanically proved and incremental development of IEEE 1394 tree identify protocol[END_REF]: the development does not take into account time constraints. Moreover, we paid attention to capture our modelling experience in a pattern called time constraint pattern. We give a light definition of patterns which are planned to give a systematic help for specialised refinement. Our work illustrates the use of a general and global time which interacts with a number of actives times. The time progression is abstract and nondeterministic; the concept of active times can be fit to various situations like simple clocks, timers or delays for messages. We have used our pattern on a realistic problem involving messages on channels and we have studied time constraints in contention problem of the IEEE 1394 protocol.

The contention problem is not yet completely solved. But we have enough elements and tools to solve the contention problem in the event B framework. With the help of refinement we can introduce time constraints that satisfies a sequence of events. If a concrete system refines another system with time constraints we can prove the timing validity of the concrete system. For future work, we can enrich the library of patterns and we can study the applicability of such a process on others case studies.

  post time = any tm where tm ∈ N ∧ tm > time then at := at ∪ {tm} end time tm

  tick tock = any tm where tm ∈ N ∧ tm > time ∧ (at = ∅ =⇒ tm ≤ min(at)) then time := tm end This event simply takes a new value of time in the future and assigns it at the current time.

Figure 1 .

 1 Figure 1. Example for the contention problem

Figure 2 .

 2 Figure 2. Example for the contention problem

Introducing time by the time constraint pattern

With the method already described we need to adapt the pattern and anchor events in time. For this we need two constants : prop is the propagation time needed for the message to transit from a to b and st is the sleeping time used in the timer. As an adaptation we need two new variables: stm is the "send time message" and slp the time when a will stop sleeping at the end of the timer. The tick tock event can be copied as before and we have the two aspects of the pattern:

-Only event sendA posts two active times : time + prop and time + st (with the hypothesis prop < st). -Events recB and quA are processing an active time.

Next we can write temporal aspects with a refinement of the abstract model. For these two events the refinement is just a superposition, i.e. some lines have been added without changing existing expressions. On sendA we can see the two new active times time + prop and time + st which are the future arrival time of messages and the awake time ending the timer. On the same event the informative variables stm and slp are set up. The second event is triggered by stm + prop which is equal to the posted value time + prop, this active time is deleted from at, as in the pattern. Now the most interesting event: Here the refinement is not just a superposition: the abstract guard was B = {b} and is changed to a more concrete A = ∅ ∧ time = slp. The use of the non local variable B has disappeared with the use of the local variable A and of the variable time. Variable time is universal and global so we can use it to get more information from the local state of distributed devices. In order to prove the refinement we need the following invariant:

We give explanations on the most interesting part of this invariant and a derived theorem:

This part of the invariant is important to prove the refinement of quA. In this expression if time is beyond stm+prop and if the time constraint stm+prop has already been processed then we are sure of the reception (B = {b}).

If active times set is only {slp} and message is gone then current time is after the message reception.

This predicate is interesting if the message has already been sent (A = ∅) and if there is no more time constraints on process (at = ∅), in other words once all the events were observed. In this case, one can affirm that the current time exceeded the moment when a was awaken.


Aritz Irurtzun

Strategies for argument and adjunct focalization in Basque

Keywords: focus, Wh-movement, left periphery, wh in situ

In this chapter, I provide an overview of the different strategies employed for Wh-questions and focalizations across Basque dialects. I argue that a core property of Basque syntax is the fact that both Wh-and focus phrases undergo syntactic (A'-type) displacements, and that they exhibit the main characteristics of syntactic displacements (locality, successive cyclicity, sensitivity to islands, etc.).

After analysing the "standard strategy", which is available across all dialects, I provide an overview of the new in situ Wh-question strategy of the young speakers of Navarro-Labourdin and two different strategies that are employed across different dialects to generate reinforced foci: the highly contrastive rightward focus constructions (specific to Southern dialects, and particularly common in High Navarrese), and the 'reinforced movement' strategy of Navarro-Labourdin (a Northern variety). I finish with a brief description of some other constructions involving foci: the mirative focus constructions of substandard Basque, and the dialectal distribution of different types of split interrogatives.

Introduction: The 'Standard Strategy' 1

Basque has been characterized as a S-IO-DO-V language given that, even if the order of constituents in this language is not a fixed one, this is the pattern appearing in an out-of-the-blue or all-new statement (cf., i.a., Ortiz de Urbina, 1989 et seq.; [START_REF] Elordieta | Verb Movement and Constituent Permutation in Basque[END_REF][START_REF] Etxepare | Focalization[END_REF][START_REF] Irurtzun | The Grammar of Focus at the Interfaces[END_REF][START_REF] Erdocia | Syntactic complexity and ambiguity resolution in a free word order language: Behavioral and electrophysiological evidences from Basque[END_REF]. However, information-structure affects the order of constituents in Basque and it is, therefore, a 'discourse-configurational' language (in the sense of Kiss (1995)). In this chapter, I provide an overview of the main syntactic and semantic properties of different question and focalization strategies in Basque. The discussion will concentrate on Whquestions and argument and adjunct focalization -what is known as "term-focus"-, see Elordieta & Haddican (this volume) for an analysis of verb-focalization and [START_REF] Elordieta | The relationship between meaning and intonation in non-exhaustive answers: evidence from Basque[END_REF] for a study involving verum focus. 1 My deepest thanks to B. Fernández and J. Ortiz de Urbina for their editorial support and to two anonymous reviewers for their insightful comments. This work benefited from the projects IT769-13 (Eusko Jaurlaritza), FFI2013-43823-P, FFI2013-41509-P, FFI2014-53675-P (MINECO), and EC FP7/SSH-2013-1 AThEME 613465 (European Commission).

To begin with, there is in Basque a common Wh-movement and focalization strategy that we could term the 'standard strategy', for it is available across all dialects of this language. This strategy is exemplified in (1b) for a Wh-question and (1c) for a subject-focalization, where we can observe that the basic S-O-V word order of an out-of-the-blue statement (1a) is altered and the verb appears immediately following the Wh-(1b) or focal (1c) phrase:

(1) a.

Jonek ura edan du.

Jon water drink AUX 'Jon drank water' b.

Nork edan du ura?

who drink AUX water 'Who drank water?' c.

[Jonek]F edan du ura.

Jon drink AUX water '[Jon]F drank water'

Actually, a long-standing observation in Basque linguistics (cf. i.a. Altube (1923), de Rijk (1978), [START_REF] Mitxelena | Galdegaia eta mintzagaia euskaraz[END_REF], [START_REF] Eguzkitza | Topics on the Syntax of Basque and Romance[END_REF], Ortiz de Urbina (1989), [START_REF] Rebuschi | A Note on Focalization in Basque[END_REF], [START_REF] Artiagoitia | Hatsarreak eta Parametroak Lantzen[END_REF]) is that if this change in word order does not take place, the result is ungrammatical, as illustrated in the examples in (2a-b):

(2) Authors like Ortiz de Urbina (1989, et seq.) or [START_REF] Irurtzun | The Grammar of Focus at the Interfaces[END_REF] have analysed these constructions as involving an A'-displacement of the relevant phrase (a Wh-phrase or a focal phrase) to the specifier of some functional projection at the left periphery of the clause (traditionally, taken to be Cº or Focº).2 This displacement in turn would be followed by a T-to-C movement, as represented in (3), which, in order to avoid repeating the same tree twice, combines the structure under the subjectquestion in (1b) and the subject-focalization in (1c) (for simplicity, I am omitting the movement of the subject DP from Spec-vP to Spec-TP, and the movement of V-to-v-to-T): In both (4b) and (4c) we have a Wh-question over the subject of the embedded clause; the only difference between both clauses is that in (4b) we observe OV inversion in the embedded clause (along with the SV inversion of the matrix clause), but in (4c) we do not, resulting in ungrammaticality. Likewise for the focalization constructions in (4d) and (4e). The necessity of verb-movement in the embedded clause has been taken as an indication that the extracted element moves trough the specifier of the embedded CP in its way to the specifier of the matrix CP, this cyclic movement being the catalyst of the verb-movement in the embedded clause.5 Therefore, the derivation corresponding to (4b)-( 4d) would be the one in (5):

( (1989,1993), [START_REF] Arregi | Clausal pied-piping[END_REF], [START_REF] Irurtzun | The Grammar of Focus at the Interfaces[END_REF]). Consider the data in (6) for Wh-questions and (7) for focalizations. In (6a)-(7a) we observe that the whole embedded clause is fronted to the left periphery of the matrix CP, and that there is OV inversion in Thus, the analysis of the derivation of clausal pied-piping structures is very similar to that of long distance extractions. As a first step, the Wh-phrase/focus phrase is moved to the specifier of the embedded clause, attracting its verbal complex, and then, instead of extracting it to the specifier of the matrix CP (as in the long distance extraction in ( 5)), it is the whole embedded CP that is moved to the specifier of the matrix CP, generating T-to-C movement in the matrix clause, as represented in (8), which corresponds to examples (6a) and ( 7a):

(8) Step1: CP1 wo C' wo C TP wo Jonek T' wo vP [V+v+T] ei tDP v' 3 VP t[V+v] 2 CP2 tV wo Nork/[Mirenek]F C' wo edan duela TP wo tDP T' wo vP t[V+v+T] ei tDP v' 3 VP t[V+v] 2 ura tV Step2: CP1 wo [Nork/[Mirenek]F edan duela ura]CP2 C' wo esan du TP wo Jonek T' wo vP t[V+v+T] ei tDP v' 3 VP t[V+v] 2 tCP2 tV
Finally, let me note that the parasitic movement of the verb with respect to the Whmovement can serve as a disambiguator of scope for extractions that could be potentially ambiguous. This is, for instance, the case of modifiers like noiz (when) that could, potentially, be first-merged in either the matrix or the embedded clause, as in the examples in (9):

(9) a.

Noiz pentsatzen duzu [gerra bukatuko dela]?

when think aux war finish AUX.C

'When is it that you think that the war will finish?' (Whenthink) b.

Noiz pentsatzen duzu [bukatuko dela gerra]?

when think aux finish AUX.C war 'According to you, when will the war finish?' (Whenfinish)

A direct consequence of the parasitic nature of verb-movement is that a focus or interrogative displacement of an element in the matrix clause generates no inversion in the embedded clause (9a), but on the contrary, extraction from the embedded clause is accompanied by T-to-C movement in both embedded and matrix clauses (9b). As a consequence, the scopal properties of the interrogative have a direct mapping in the syntactic structure of the clause. As a matter of fact, a plausible answer to question (9a) could be something like "Whenever I see the occupation troops leaving the city" (i.e. that's when I think that the war will come to an end), and a plausible answer to question (9b) something like "When the last city will be liberated" (i.e. I think that when such an event will be accomplished, the war will come to an end). Now, let us give a look at some of the syntactic restrictions that are inherent to the displacement operations in questions and focalizations.

Islandhood restrictions

We just saw that the displacements underlying questions and focalizations in Basque observe some locality and cyclicity restrictions which are shown with the movement of the verbal complex.

However, these are not the only characteristic restrictions of Wh-questions and foci. In fact, given that they involve A'-displacements, Wh-questions and focalizations are also sensitive to various sorts of syntactic islands. For instance, extraction out of a coordination phrase results in plain ungrammaticality. This is illustrated in (10b-c):

(10) a. Jonek [salda eta legatza] nahi ditu. So, as we said, all these restrictions constitute evidence that both Wh-questions and focalizations in Basque have a very similar syntax. In a nutshell, they both involve:

(i) A'-movement of the focus/Wh-phrase to Spec-CP. 6

(ii) T-to-C movement, which renders adjacency between the verbal complex (V+v+T) and the moved phrase.

(iii) Cyclicity in the focus/Wh-movement, which can be observed in the cyclic movement of the verbal complex of each clause.

(iv) A ban on extraction out of islands.

(v) Possible clausal pied-piping. This is the panoramic picture regarding the standard constructions. 7 In the next sections, I will present the microparametric variability observed in the Wh-question and focalization strategies employed across Basque dialects. Section 2 will briefly present the emergent Wh in situ strategy of Labourdin Basque, section 3 will be devoted to two 'reinforced focus' constructions ((i) the "rightward" focalization trategy of Southern dialects and (ii) the "movement+AUX" construction of Northern dialects), and section 4 will briefly present some other focus constructions attested in Basque dialects: a substandard mirative focus construction, and two different split interrogatives, which vary in their geographic distribution. Again, it should be emphasized that even if I will be dealing with some strategies that are restricted to some varieties, all varieties of Basque have the standard strategy that we just saw, and that the alternative strategies that I will comment on in the 6 Or Spec-FocP in "split CP" analyses (see, e.g. Ortiz de Urbina (1999), Irurtzun ( 2007)). 7 An anonimous reviewer reminds me that Elordieta (2001) mentions a potential point of variation between focalizations and Wh-constructions with respect to "weak crossover" effects (focalizations would generate a weaker agrammaticality effect than Wh-constructions). Nevertheless, the phenomenon and judgments are not clear, and unfortunately we still have no in-depth study of this important issue.

next sections are employed along with the standard ones (in fact, they are typically employed to convey different semantic nuances).

The new wh in situ strategy of Navarro-Labourdin Basque

Recently, [START_REF] Duguine | From obligatory Wh-movement to optional Wh in situ in Labourdin Basque[END_REF] have discovered that young speakers of Navarro-Labourdin Basque also have another type of Wh-question construction, which is unavailable to older speakers of this dialect, and to the speakers of other dialects in Southern Basque Country (in the Spanish territory). This strategy is illustrated in examples ( 15) and ( 16):

( In these constructions, we do not observe the typical adjacency between the Wh-phrase and the verb, characteristic of standard strategies (in ( 15) the DO appears between the interrogative subject and the verb, and in ( 16) the adverb 'fite' (quickly) is sandwiched between the interrogative DO and the verb). [START_REF] Duguine | From obligatory Wh-movement to optional Wh in situ in Labourdin Basque[END_REF] analysis is that underlying these examples there is an in situ Wh-strategy. In fact, in these constructions no interrogative displacement seems to take place (no Wh-movement and, as a consequence, no residual V2 effect), but furthermore, these constructions of Navarro-Labourdin Basque also share a range of properties with French wh in situ. In particular, they display intervention effects with negation: Wh in situ constructions are ungrammatical when the Wh-phrase is c-commanded by negation ( 17), the only way of asking a question with negation on the matrix clause being the Wh-movement strategy (18) (see [START_REF] Bošković | LF movement and the Minimalist Program[END_REF][START_REF] Bošković | Sometimes in [Spec, CP], sometimes in situ[END_REF] or [START_REF] Mathieu | Wh in situ and intervention effects[END_REF][START_REF] Mathieu | The mapping of form and interpretation: The case of optional WH-movement in French[END_REF] for French data and analysis):

( Lit. 'They lit people's anger when they took the house to who?'

The syntactic and semantic similarity of these constructions with respect to the French Wh in situ has led [START_REF] Duguine | From obligatory Wh-movement to optional Wh in situ in Labourdin Basque[END_REF] to the hypothesis that a catalyst for its emergence in Labourdin Basque is a transfer from French (which would be made possible by other 3 rd factor effects like an innate bias for preferring movementless operations).

In the next section I will briefly present two strategies that are employed for 'reinforced focalizations' across Basque dialects: the "rightward focalization" of Southern dialects (3.1), and the 'displacement+auxiliary' constructions of Navarro-Labourdin (3.2).

Reinforced focus strategies

In this section I give an overview of some 'reinforced' focalization strategies observed across Basque dialects. Generally these strategies are termed 'reinforced' because they have a marked focus semantics associated to them; they are generally more contrastive and more presuppositional than the regular focalization constructions (to the point that they could be taken as semantic equivalents of cleft sentences (see below)). The two strategies that I will focus on are the 'rightward focalizations' of Southern dialects, and the 'movement+auxiliary' constructions of the Northern dialects (in particular, Navarro-Labourdin).

The 'rightward' focalization strategy of Southern dialects

We saw that the standard focalization strategy available to all dialects comprises a leftwarddislocation of the focal element. Now, Southern dialects also have a different construction where the focus appears at the right edge of the clause, preceded by the rest of the sentence where the order of constituents tends to be the same as in out-of-the-blue sentences (although, it can certainly vary).

For instance, the example in ( 23) would be a 'marked' variant of ( 24), with a enhanced degree of exhaustivity and a clear topic-focus (rising-falling) intonation:

( One of the virtues of an analysis along these lines is that it immediately explains the sentence-final position of the focus (given that it directly follows from the fact that the rest of the clause is remnant-moved to a position higher than Spec-Foc). Besides, it follows naturally that a topiccomment intonational contour accompanies them, and the highly contrastive nature of their interpretation is also explained as deriving from the Topic position of the clause. Furthermore, this analysis can also explain some scopal relations that would otherwise be hard to explain. Consider the rightward focus construction of ( 26), where the focal XP takes scope over negation, linear order notwithstanding:

(26) Ez da etorri [horregatik]F.

not AUX come because.of.that 'He has not come [because of that]F' (=[That]F, and not (the) other one, is the reason why he has not come).

On this approach, we expect negation not to take scope over the focal 'horregatik', for Negº is contained within the remnant-moved phrase and from there it cannot c-command the purpose-clause 'horregatik'. The availability of the remnant movement operation (25b) would be restricted to Southern varieties of Basque, which would account for the restricted distribution of these constructions. 8 8 It should be noted that the speakers of these varieties of Basque (all Spanish-Basque bilinguals) also have a very similar construction in Spanish, namely, the non-echoic sentence-final Wh-questions (cf. Uribe-Etxebarria (2002),

Etxepare & Uribe-Etxebarria ( 2004)).

The 'movement+AUX' strategy of Navarro-Labourdin

The Navarro-Labourdin dialect does not generally display the rightward focalization This is a construction that is restricted to main clauses, and according to the analysis in [START_REF] Duguine | Opérateurs d'exclusivité dans les questions et réponses en basque[END_REF], the reinforced nature of these constructions is clearly observed in their semantic interpretation regarding the parameters of presuppositionality and exhaustivity. 10 For instance, even if all Wh-questions take as granted that the eventuality described in the question takes place, the presupposition of reinforced constructions is stronger, and a discourse clash or clear incongruence is generated when the presupposition is refuted. Consider the data in ( 28) and (29). In (28) we observe that the presupposition of the Wh-question in (28A) is directly refuted in the answer in (28B), but there is no sharp discourse clash. On the contrary, the refutation in (29B) clashes directly with the presupposition expressed in the reinforced Wh-question in (29A), as it would do with a clefted question in English:

(28) A:

Zer jan duzu?

  Lit. 'What does Jon want and hake?' And the same happens with extraction out of adjuncts (12b-c), left branch phrases (13b-c) or complex NPs (14b-c); Wh-or focus movement out of these islands derives in ungrammaticality:

		stock want AUX Jon what hear AUX Jon	and hake write AUX.C.P rumour
		Lit. 'What did you hear the rumour that Jon wrote?'
	c.	*[Liburu bat]F entzun dut [Jonek t idatzi duelako zurrumurrua].
		book one hear AUX Jon	write AUX.C.P rumour
	(12) a.	Jon [abestia entzun duelako] 'I heard the rumour that Jon wrote [a book]F' poztu da.
		Jon song hear AUX.because get.happy AUX
		'Jon got happy because he heard the song'
	b.	*Zer poztu	da Jon [t entzun duelako]?
		what get.happy AUX Jon hear AUX.because
		Lit. 'What did Jon got happy because he heard?'
	c.	*[Abestia]F poztu	da Jon [t entzun duelako]?
		Jon stock and hake want AUX Song get.happy Miren Jon's book read AUX
		'Jon wants stock and hake' 'Miren read Jon's book'
	b. b.	*Zer nahi ditu Jonek [salda eta t ]? *Noren irakurri du Mirenek [t liburua]?
		what want AUX Jon stock and whose read AUX Miren book
		Lit. 'What does Jon want stock and?' 'Whose book did Miren read?'
	c. c.	*Zer nahi ditu Jonek [ t eta legatza]? *[Jonen]F irakurri du Mirenek [t liburua]?
		what want AUX Jon Jon's read AUX Miren and hake book
		Lit. 'What does Jon want and hake?' 'Miren read [Jon's]F book'
	(11) a. (14) a.	*[Legatza]F nahi du Jonek [salda eta t ]. [Jonek liburu bat idatzi duelako zurrumurrua] entzun duzu.
		hake Jon book one write AUX.C.P rumour want AUX Jon stock and	hear aux
		'Jon wants stock and [hake]F'
	b.

*[Salda]F nahi du Jonek [t eta legatza ]. AUX Jon hear AUX.because Lit. 'Jon got happy because he heard [the song]F' (13) a. Mirenek [Jonen liburua] irakurri du. 'You heard the rumour that Jon wrote a book' b. *Zer entzun duzu [Jonek t idatzi duelako zurrumurrua]?

  This rightward focus constructions, as I said, are common to all Southern dialects (see, e.g., the dialectal study in[START_REF] Hualde | The Basque dialect of Lekeitio[END_REF]). Ortiz de[START_REF] Ortiz De Urbina | Focus of Correction and Remnant Movement in Basque[END_REF] argues that in this type of constructions we have the regular focus movement of the [+F] marked XP illustrated in

	'It's [Jon]F that broke the table'
	(25a), followed by "remnant movement" of the rest of the clause to a higher TopP (25b):
	(25) a.	FocP [ XP[+F] [Focº CP [...tXP...]]]]
	b.	TopP[ CP [Topº FocP [ XP[+F] [Focº tCP ]]]]
	23) [Jonek]F hautsi du mahaia.	[Standard Construction]
	Jon	break AUX table
	'[Jon]F broke the table'
	(24) Mahaia hautsi du [Jonek]F.	[Reinforced Construction]
	table break AUX Jon

  I translate example (27b) with a cleft in order to express the reinforced nature of these constructions. Actually,Lafitte (1944: 48) when commenting in these constructions says that 'pour le traduire, le français ce que est obligatoire' [in order to translate it, French ce que is necessary]. See[START_REF] Duguine | Opérateurs d'exclusivité dans les questions et réponses en basque[END_REF] for discussion.10 The restriction to main clauses makes that extraction out of embedded clauses using this strategy renders ungrammaticality, as represented in (i), with the reinforced strategy only in the embedded clause, and (ii), with the embedded strategy in both clauses:(i) *[Mirenek]F erran dut [t duela Jon ikusi]. Miren say AUX AUX.C Jon see "I said that Jon saw [Miren]F" (ii) *[Mirenek]F dut erran [t duela Jon ikusi]. Miren AUX say AUX.C Jon see "I said that Jon saw [Miren]F"

9

  Likewise, reinforced interrogative and focus constructions always require a strongly exhaustive or complete answer interpretation (cf.[START_REF] Duguine | Opérateurs d'exclusivité dans les questions et réponses en basque[END_REF]). Thus, contrary to standard constructions, they cannot appear with additive particles (30), and they cannot be

					[Standard Wh-construction]
		what eat AUX
		'What did you eat?'
	B:	Deus	ez.
		nothing not
		'I ate [nothing]F'
	(29) A:	Zer duzu jan?	[Reinforced Wh-construction]
		what AUX eat
		'What is it that you ate?'
	B:	#Deus ez.
		nothing not
		'It's [nothing]F that I ate'
	employed in a pair-list answer (31):
	(30) a.	Nor besterik jinen	da?	[Standard Wh-construction]
		who else	come.FUT AUX

'Who else will come?' b.

*Nor besterik da jinen?

[Reinforced Wh-construction]

See also[START_REF] Elordieta | Verb Movement and Constituent Permutation in Basque[END_REF] and[START_REF] Arregi | Focus on Basque movements[END_REF] for alternative proposals and[START_REF] Artiagoitia | Hatsarreak eta Parametroak Lantzen[END_REF] and[START_REF] Etxepare | Focalization[END_REF] for a general overview of the syntax of these constructions.

See also[START_REF] Laka | Barriers for Basque and vice-versa[END_REF] and[START_REF] Uriagereka | Minimal restrictions on Basque movements[END_REF] among others.

A reviewer wonders whether all speakers find these examples ungrammatical. The literature converges in this direction and the speakers I have consulted tend to associate the word order in (4c) not with the interpretation in (4c) but with a reading where extraction does not take place from the embedded clause but from the matrix clause ('Who said that John drank water?'). Unfortunately, we still lack any formal experimental test on acceptability judgements for this type of data.

See Ortiz de Urbina (1995) for an analysis.

Jon AUX come.FUT Peio AUX come.FUT It's Jon that will come, it's Peio that will come...

The availability of this strategy, as I said, is restricted to Northern dialects, and it may be correlated with a range of other phenomena involving participial periphrases (cf. [START_REF] Etxepare | The microparameter in Basque participial periphrases[END_REF] for a recent microparametric analysis).

Having briefly analysed the reinforced constructions, in section 4 I will overview two other focus constructions; a substandard mirative construction of Southern Basque, and two split interrogative (Wh-question+focus) constructions, one of them available to all speakers across Basque dialects, the other one restricted to Southern dialects.

Other Constructions

Along with the standard and reinforced constructions of each dialect, there are also some other constructions which, even though not evenly spread across the population deserve a brief mention here, given that they also have characteristic correspondences between their syntactic form and their semantic interpretation. Here I would like to briefly comment on two of these constructions; the mirative focus (section 4.1), and the split interrogative constructions (section 4.2.).

Mirative focus constructions

Mirativivity in Basque has not got an in-depth treatment in the literature. And its grammatical status is not very clear. However, [START_REF] Etxepare | A Case for Two Types of Focus in Basque[END_REF] discusses some constructions that, even though they are not fully grammaticalised nor evenly spread across the population, can be taken as instances of "mirative focus" constructions. [START_REF] Etxepare | A Case for Two Types of Focus in Basque[END_REF] concentrates on the differences between the type of focus constructions like (32) that we have seen in section 1, and mirative focus constructions like (33) which would involve some sort of exclamation: 11,12 (32) [Jonek]F ekarri du ardoa. 11 Actually, the terminology employed in Etxepare ( 1998) is a bit different; he terms "Emphatic Focus" what we have analysed as (normal) "focus" (basically, the constructions in section 1), and he terms "Contrastive Focus" the constructions that we analyse here as "mirative". At the risk of confusing the reader (sorry!), I think that the terminology employed in this chapter is more accurate and, furthermore, it better matches the crosslinguistic use of those terms in the literature, so I will keep to the distinction between "focus" and "mirative focus" when I talk about what Etxepare (1998) calls "emphatic focus" and "contrastive focus". The reader should be aware of the difference in terminology.

12 A reviewer rightly points out that the examples I use to illustrate mirative focus only involve subjects. I do so because thus we can assess the lack of linear continuity between the focus and the verb. Evidence with other syntactic objects would require a longer argumentation (involving an explanation of the properties of scrambling of nonfocal material and speech act modifiers) and it would take us too far from our expository purposes. The reader is referred to Etxepare (1998) for discussion.

Split interrogatives

The last construction that I would like to comment on is the "split interrogative" construction, which is a confirmatory construction combining a Wh-question and a focal phrase.

The Wh-phrase appears to be in its canonical left-peripheric position and the focus (the potential answer) in sentence-final position. This is illustrated in ( 34 According to [START_REF] Irurtzun | Euskarazko galdera erdibituak: analisi bitar baterantz[END_REF], matching type split interrogatives are derived from a simple bi-clausal construction: a regular Wh-question followed by a leftward focalization which undergoes sluicing (following the analysis of Spanish matching constructions proposed by [START_REF] Arregi | Ellipsis in Split Questions[END_REF]).

Therefore, the fact that all dialects of Basque have this type of constructions is just something to be expected, given that all dialects have both Wh-movement and sluicing constructions.

Regarding what type constructions, the analysis put forth in [START_REF] Irurtzun | Euskarazko galdera erdibituak: analisi bitar baterantz[END_REF] Northern dialects, on the contrary, cannot make what-type split interrogatives.

Summary

In conclusion, in this chapter I have provided an overview of the different question and focalization strategies available across Basque dialects. We have seen that a core property of Basque syntax is that it treats in a very similar way Wh-questions and their answers (focus constructions).

The standard strategy (available to all varieties) involves an A'-movement of the focal item to Spec-CP (which is accompanied by movement of the verb) but there are also a range of other alternative strategies employed across Basque varieties. These alternative strategies are generally employed in order to gain some semantic nuance (stronger presuppositionality, exhaustivity, etc.) with respect to the standard strategy.


B Eynard

N Orantin
email: orantin@cea.fr

Weil-Petersson volume of moduli spaces, Mirzakhani's recursion and matrix models

We prove that Mirzakhani's recursions for the volumes of moduli space of Riemann surfaces are a special case of random matrix recursion relations, and therefore we confirm again that Kontsevich's integral is a generating function for those volumes. As an application, we propose a formula for the Weil-Petersson volume Vol(M g,0 ).

1 Introduction Let V g,n (L 1 , . . . , L n ) = Vol(M g,n ) = d 0 +...+dn=3g-3+n n i=0 1 d i ! κ d 0 1 τ d 1 . . . τ dn g,n L 2d 1 1 . . . L 2dn n (1 -1)
denote the volume of the moduli space of curves of genus g, with n geodesic boundaries of lengths L 1 , . . . , L n , measured with the Weil-Petersson metrics. Using Teichmuller pants decomposition and hyperbolic geometry, M. Mirzakhani [START_REF] Mirzakhani | Simple geodesics and Weil-Petersson volumes of moduli spaces of bordered Riemann surfaces[END_REF] has found a recursion relation among the V g,n 's, which allows to compute all of them in a recursive manner. It was then observed [START_REF] Mulase | Mirzakhani's recursion relations, Virasoro constraints and the KdV hierarchy[END_REF] that this recursion relation is equivalent to Virasoro constraints.

In fact, Mirzakhani's recursion relation takes a form [START_REF] Liu | A simple proof of Mirzakhani's recursion formula of Weil-Petersson volumes[END_REF] which is amazingly similar to the recursion relation obeyed by matrix models correlation functions ( [START_REF] Eynard | Topological expansion for the 1-hermitian matrix model correlation functions[END_REF][START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF]) and which were indeed initialy derived from loop equations [START_REF] Eynard | Topological expansion for the 1-hermitian matrix model correlation functions[END_REF], i.e. Virasoro constraints.

Here we make this observation more precise, and we prove that after Laplace transform, Mirzakhani's recursion is identical to the recursion of [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF] for the Kontsevich integral with times (Kontsevich's integral depends only on odd times):

Z(t k ) = dM e -N Tr [ M 3 3 +ΛM 2 ] , t 2k+3 = 1 N Tr Λ -(2k+3) = (2π) 2k (-1) k (2k + 1)! + 2δ k,0 .
(1-2)

Laplace transform

Define the Laplace transforms of the V g,n 's:

W g n (z 1 , . . . , z n ) = 2 -mg,n ∞ 0 dL 1 . . . dL n e -i z i L i n i=1 L i V g,n (L 1 , . . . , L n ) = 2 -mg,n d 0 +...+dn=3g-3+n n i=0 1 d i ! κ d 0 1 τ d 1 . . . τ dn g,n (2d 1 + 1)! z 2d 1 +2 1 . . . (2d n + 1)! z 2dn+2 n (2 -1)
where (see [START_REF] Mirzakhani | Simple geodesics and Weil-Petersson volumes of moduli spaces of bordered Riemann surfaces[END_REF]) m g,n = δ g,1 δ n,1 .

Since the V g,n 's are even polynomials of the L i 's, of degree 2d g,n where

d g,n = dim M g,n = 3g -3 + n (2-2)
the W g n 's are even polynomials of the 1/z i 's of degree 2d g,n + 2. Let us also define:

W 0 1 = 0 (2-3) W 0 2 (z 1 , z 2 ) = 1 (z 1 -z 2 ) 2 (2-4)
and

dE u (z) = 1 2 1 z -u - 1 z + u . (2-5)
We prove the following theorems:

Theorem 2.1 For any 2g -2 + n + 1 > 0, the W g n+1 satisfy the recursion relation

W g n+1 (z, K) = Res u→0 πdEu(z) u sin 2πu g h=0 J⊂K W h 1+|J| (u, J)W g-h 1+n-|J| (-u, K/J) +W g-1 n+2 (u, -u, K) (2-6)
where the RHS includes all possible W h k , including W 0 1 = 0 and W 0 2 , and where

K = {z 1 , . . . , z n } (2-7)
is a set of n variables.

proof:

This relation is merely the Laplace transform of Mirzakhani's recursion. See the appendix for a detailed proof.

Corollary 2.1 W g n are the invariants defined in [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF] for the curve:

x(z) = z 2 -2y(z) = sin (2πz) 2π = z -2 π 2 3 z 3 + 2π 4 15 z 5 -4π 6 315 z 7 + 2π 8 2835 z 9 + . . . (2-8)
which is a special case of Kontsevich's curve:

Z(t k ) = dM e -N Tr [ M 3 3 +ΛM 2 ] , t k = 1 N Tr Λ -k = (2π) k-3 sin (πk/2) (k -2)! (2-9)
For instance we have:

ln Z(t k ) = ∞ g=0 N 2-2g W g 0 (2-10) (W g 0 is often noted -F g in the litterature).
proof: Eq. 2-6 is precisely the definiton of the invariants of [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF] for the curve

x(z) = z 2 -2y(z) = sin (2πz) 2π = z -2 π 2 3 z 3 + 2π 4 15 z 5 -4π 6 315 z 7 + 2π 8 2835 z 9 + . . . (2-11)
And it was proved in [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF] that this curve is a special case of Kontsevich's curve:

x(z) = z 2 y(z) = z -1 2 ∞ j=0 t j+2 z j (2-12)
which corresponds to the computation of the topological expansion of the Kontsevich integral:

Z(t k ) = dM e -N Tr [ M 3 3 +ΛM 2 ] , t k = 1 N Tr Λ -k (2-13) ln Z(t k ) = - ∞ g=0 N 2-2g F g (2-14)
Theorem 2.2 For any 2g -2 + n > 0 we have:

(2g -2 + n) W g n (K) = 1 4π 2 Res u→0 u cos (2πu) - 1 2π sin (2πu) W g n+1 (u, K) (2-15)
or in inverse Laplace transform:

(2g -2 + n) V g,n (K) = 1 2iπ V ′ g,n+1 (K, 2iπ) (2-16)
where ′ means the derivative with respect to the n + 1 th variable.

proof: This is a mere application of theorem 4.7. in [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF], as well as its Laplace transform.

In particular with n = 0 we get:

V g,0 = Vol(M g,0 ) = 1 2g -2 V ′ g,1 (2iπ) 2iπ (2-17)
for instance for g = 2:

V 2,0 = 43π 6 2160 .

(2-18)

Examples

From [START_REF] Mirzakhani | Simple geodesics and Weil-Petersson volumes of moduli spaces of bordered Riemann surfaces[END_REF] we get:

W 0 3 = 1 z 2 1 z 2 2 z 2 3 (2-19) W 1 1 = 1 8z 4 1 + π 2 12z 2 1
(2-20)

W 0 4 = 1 z 2 1 z 2 2 z 2 3 z 2 4 2π 2 + 3( 1 z 2 1 + 1 z 2 2 + 1 z 2 3 + 1 z 2 4 ) (2-21) W 1 2 = 1 z 2 1 z 2 2 π 4 4 + π 2 2 ( 1 z 2 1 + 1 z 2 2 ) + 5 8z 4 1 + 5 8z 4 2 + 3 8z 2 1 z 2 2 (2-22) W 0 5 = 1 z 2 1 z 2 2 z 2 3 z 2 4 z 2 5 10π 4 + 18π 2 i 1 z 2 i + 15 i 1 z 4 i + 18 i<j 1 z 2 i z 2 j (2-23) W 2 1 = 1 192z 2 1 29π 8 + 338π 6 5z 2 1 + 139π 4 z 4 1 + 203π 2 z 6 1 + 315 2z 8 1 (2-24)
Those functions are the same as those which appear in section 10.4.1 of [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF], for the Kontsevich curve with times: i.e. the rational curve:

t 3 -2 = 1, t 5 = - 2π 2
E K = x(z) = z 2 -2y(z) = sin (2πz) 2π = z -2 π 2 3 z 3 + 2π 4 15 z 5 -4π 6 315 z 7 + 2π 8 2835 z 9 + . . . (2-26)
It is to be noted that those t k 's are closely related to the β k 's of [START_REF] Mulase | Mirzakhani's recursion relations, Virasoro constraints and the KdV hierarchy[END_REF][START_REF] Liu | A simple proof of Mirzakhani's recursion formula of Weil-Petersson volumes[END_REF].

Conclusion

We have shown that, after Laplace transform, Mirzakhani's recursions are nothing but the solution of loop equations (i.e. Virasoro constraints) for the Kontsevich integral with some given set of times. It would be interesting to understand what the invariants of [START_REF] Eynard | Invariants of algebraic curves and topological expansion[END_REF] compute for an arbitrary spectral curve (for instance for other Kontsevich times).

Mirzakhani's recursion reads:

2LV g,n+1 (L, L K ) = L 0 dt ∞ 0 dx ∞ 0 dyK(x + y, t)H g n (x, y, L K ) + n m=1 L 0 dt ∞ 0 dx(K(x, t + L m ) + K(x, t -L m ))xV g,n-1 (x, Lm ) (1-4) where K(x, t) = 1 1 + e ( x+t 2 )
+ 1

1 + e ( x-t 2 )

(1-5)

and Lm = L K /{L m }. Let Hg n be the Laplace transform of H g n with respect to x and y. The Laplace transform of the first term in eq.1-4 is:

ǫ=±1 ∞ 0 dL e -zL L 0 dt ∞ 0 dx ∞ 0 dy 1 1 + e x+y+ǫt 2 H g n (x, y, L K ) = ǫ=±1 ∞ 0 dt ∞ t dL e -zL ∞ 0 dx ∞ 0 dy 1 1 + e x+y+ǫt 2 H g n (x, y, L K ) = ǫ=±1 1 z ∞ 0 dt e -zt ∞ 0 dx ∞ 0 dy 1 1 + e x+y+ǫt 2 H g n (x, y, L K ) = - ∞ j=1 1 z ∞ 0 dt e -zt ∞ 0 dx ∞ 0 dy(-1) j e -j 2 (x+y+t) H g n (x, y, L K ) + ∞ j=0 1 z ∞ 0 dx ∞ 0 dy ∞ x+y dt e -zt (-1) j e j 2 (x+y-t) H g n (x, y, L K ) - ∞ j=1 1 z ∞ 0 dx ∞ 0 dy x+y 0 dt e -zt (-1) j e -j 2 (x+y-t) H g n (x, y, L K ) = - ∞ j=1 1 z ∞ 0 dx ∞ 0 dy (-1) j z + j 2 e -j 2 (x+y) H g n (x, y, L K ) + ∞ j=0 1 z ∞ 0 dx ∞ 0 dy (-1) j z + j 2 e -z(x+y) H g n (x, y, L K ) - ∞ j=1 1 z ∞ 0 dx ∞ 0 dy (-1) j z -j 2 (1 -e -(z-j 2 )(x+y) )e -j 2 (x+y) H g n (x, y, L K ) = -2 ∞ j=1 (-1) j z 2 -j 2 2 Hg n ( j 2 , j 2 , L K ) + 1 z 2 Hg n (z, z, L K ) +2 ∞ j=1 (-1) j z 2 -j 2 2 Hg n (z, z, L K ) = -2 ∞ j=1 (-1) j z 2 -j 2 2 Hg n ( j 2 , j 2 , L K ) + 2π z sin 2πz Hg n (z, z, L K ) = Res u→z + ∞ j=1 Res u→± j 2 du u -z 2π u sin (2πu) Hg n (u, u, L K ) = Res u→0 du z -u 2π u sin (2πu) Hg n (u, u, L K ) = Res u→0 2π du u sin (2πu) dE u (z) Hg n (u, u, L K ) (1 -6) Using the notation R(x, t, L m ) := (K(x, t + L m ) + K(x, t -L m )), (1-7)
the Laplace transform of the second term in eq.1-4 is:

∞ 0 dL m e -zmLm ∞ 0 dL e -zL L 0 dt ∞ 0 dxR(x, t, L m )xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dL m e -zmLm ∞ 0 dt e -zt R(x, t, L m )xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dL m e -zmLm ∞ Lm dt e -z(t-Lm) K(x, t)xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx ∞ 0 dL m e -zmLm ∞ -Lm dt e -z(t+Lm) K(x, t)xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dt e -zt t 0 dL m e -(zm-z)Lm K(x, t)xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx ∞ 0 dt e -zt ∞ 0 dL m e -(zm+z)Lm K(x, t)xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx 0 -∞ dt e -zt ∞ -t dL m e -(zm+z)Lm K(x, t)xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dt e -zt -e -zmt z m -z K(x, t)xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx ∞ 0 dt e -zt + e zmt z m + z K(x, t)xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx ∞ 0 dt e -zmt z m + z K(x, t)xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dt e -zt -e -zmt z m -z + e -zt + e -zmt z m + z K(x, t)xV g,n-1 (x, Lm ) = 1 z ∞ 0 dx ∞ 0 dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) 1 1 + e x+t 2 xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx x 0 dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) 1 1 + e x-t 2 xV g,n-1 (x, Lm ) + 1 z ∞ 0 dx ∞ x dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) 1 1 + e x-t 2 xV g,n-1 (x, Lm ) = - ∞ j=1 (-1) j z ∞ 0 dx ∞ 0 dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) e -j 2 (x+t) xV g,n-1 (x, Lm ) - ∞ j=1 (-1) j z ∞ 0 dx x 0 dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) e -j 2 (x-t) xV g,n-1 (x, Lm ) + ∞ j=0 (-1) j z ∞ 0 dx ∞ x dt 2z m e -zt -2ze -zmt (z 2 m -z 2 ) e j 2 (x-t) xV g,n-1 (x, Lm ) = - ∞ j=1 (-1) j z ∞ 0 dx 2zm z+ j 2 -2z zm+ j 2 (z 2 m -z 2 ) e -j 2 x xV g,n-1 (x, Lm ) - ∞ j=1 (-1) j z ∞ 0 dx x 0 dt 2z m e -j 2 x -e -zx z-j 2 -2z e -j 2 x -e -zmx zm-j 2 (z 2 m -z 2 ) xV g,n-1 (x, Lm ) + ∞ j=0 (-1) j z ∞ 0 dx ∞ x dt 2zme -zx z+ j 2 -2ze -zmx zm+ j 2 (z 2 m -z 2 ) xV g,n-1 (x, Lm ) = -2 ∞ j=1 (-1) j z z + z m + j 2 (z m + z)(z + j 2 )(z m + j 2 ) W g,n-1 ( j 2 , Lm ) -2 ∞ j=1 (-1) j z z + z m -j 2 (z m + z)(z -j 2 )(z m -j 2 ) W g,n-1 ( j 2 , Lm ) +2 ∞ j=1 (-1) j z z m (z -j 2 )(z 2 m -z 2 )
W g,n-1 (z, Lm )

+ j 2 )(z 2 m -z 2 )-u 2 )(z 2 -u 2 ) 1 z

 2222221 W g,n-1 (z m , Lm ) + z m + u (z m + z)(z + u)(z m + u) W g,n-1 (u, Lm ) +4 z m π z sin (2πz) (z 2 m -z 2 ) W g,n-1 (z, Lm ) -4 π sin (2πz m ) (z 2 m -z 2 ) W g,n-1 (z m , Lm ) (z 2 -u 2 )(z 2 m -u 2 ) W g,n-1 (u, Lm ) m -u + 1 z m + u W g,n-1 (u, Lm )

Acknowledgements

This work is partly supported by the Enigma European network MRT-CT-2004-5652, by the ANR project Géométrie et intégrabilité en physique mathématique ANR-05-BLAN-0029-01, by the Enrage European network MRTN-CT-2004-005616, by the European Science foundation through the Misgam program, by the French and Japaneese governments through PAI Sakura, by the Quebec government with the FQRNT.

Appendix A Laplace transform of the equations

Let us write:

where all the V h,k terms in the RHS are such that 2h + k -2 > 0 (i.e. stable curves only), as well as their laplace transform:

After taking the derivative with respect to z m that gives the expected term:

and therefore the Laplace transform of Eq. (1-4) gives the relation Eq. (2-6).