Franck Cassez
email: franck.cassez@irccyn.ec-nantes.fr

⋆,⋆⋆ Alexandre David
email: adavid@cs.aau.dk

Kim G Larsen

Didier Lime
email: didier.lime@irccyn.ec-nantes.fr

Jean-François Raskin
email: jraskin@ulb.ac.be

Timed Control with Observation Based and Stuttering Invariant Strategies

In this paper we consider the problem of controller synthesis for timed games under imperfect information. Novel to our approach is the requirements to strategies: they should be based on a finite collection of observations and must be stuttering invariant in the sense that repeated identical observations will not change the strategy. We provide a constructive transformation to equivalent finite games with perfect information, giving decidability as well as allowing for an efficient on-the-fly forward algorithm. We report on application of an initial experimental implementation.

Introduction

Timed automata introduced by Alur and Dill [START_REF] Alur | A theory of timed automata[END_REF] is by now a well-established formalism for representing the behaviour of real-time systems. Since their definition several contributions have been made towards the theoretical and algorithmic characterization of this formalism. In particular, industrial mature tools supporting model-checking for timed automata now exist [START_REF] Behrmann | Uppaal 4.0[END_REF][START_REF] Behrmann | A tutorial on uppaal[END_REF].

More recently the problem of controller synthesis for timed automata based models have been considered: i.e. given a timed game automaton modelling the possible moves of an environment as well as the possible moves of a control program, the problem consists in synthesizing a strategy for the control program in order that a given control objective is met no matter how the environment behaves [START_REF] Maler | On the synthesis of discrete controllers for timed systems[END_REF]. Controller synthesis and time-optimal controller synthesis for timed games was shown decidable in [START_REF] Asarin | Controller Synthesis for Timed Automata[END_REF] and [START_REF] Asarin | As Soon as Possible: Time Optimal Control for Timed Automata[END_REF]. First steps towards efficient synthesis algorithms were taken in [START_REF] Altisen | Tools for controller synthesis of timed systems[END_REF][START_REF] Tripakis | On-the-Fly Controller Synthesis for Discrete and Timed Systems[END_REF]. In [START_REF] Cassez | Efficient on-the-fly algorithms for the analysis of timed games[END_REF] a truly on-the-fly algorithm based on a mixture of forward search and backwards propagation was proposed and later used as the basis for an efficient implemention in the tool Uppaal Tiga [START_REF] Behrmann | Uppaaltiga: Time for playing games![END_REF].

In all of the papers cited above it has been assumed that the controller has perfect information about the plant: at any time, the controller knows precisely in what state the environment is. In general however -e.g. due to limited sensors -a controller will only have imperfect (or partial) information about the state of the environment. In the discrete case it is well known how to handle partial observability, however for the timed case it has been shown in [START_REF] Bouyer | Timed control with partial observability[END_REF] that the controller synthesis problem under partial observability is in general undecidable. Fixing the resources of the controller (i.e. a maximum number of clocks and maximum allowed constants in guards) regains decidability [START_REF] Bouyer | Timed control with partial observability[END_REF], a result which also follows from the quotient and model construction results of [START_REF] Laroussinie | CMC: A tool for compositional model-checking of real-time systems[END_REF][START_REF] Laroussinie | From timed automata to logic -and back[END_REF].

In this paper we also deal with the problem of controller synthesis for timed games under imperfect information following the approach of [START_REF] Chatterjee | Algorithms for omegaregular games with imperfect information[END_REF][START_REF] Wulf | A lattice theory for solving games of imperfect information[END_REF]. That is, the imperfect information is given in terms of (a finite number of possible) observations to be made on the system configurations, providing the sole basis for the strategy of the controller. However, in contrast to [START_REF] Chatterjee | Algorithms for omegaregular games with imperfect information[END_REF][START_REF] Wulf | A lattice theory for solving games of imperfect information[END_REF], which is essentially turn-based in the untimed setting, we will here consider a more general framework, where in each step the controller and environment are competing. In particular, the strategy of the controller is supposed to be stuttering invariant, i.e. the strategy will not be affected by a sequence of environment or time steps unless changes in the observations occur. x := 0 x ≥ 0

x ≥ 8

x := 0

x ≥ 8

x := 0

x ≥ 8 kick?

Fig. 1. Timed Game with Imperfect Information.

To illustrate the concepts of imperfect information and stuttering invariance consider the timed game automaton in Figure 1 modelling a production system for painting a box moving on a conveyor belt. The various locations indicate the position of the box in the system: in Sensor a sensor is assumed to reveal the presence of the box, in Sensed the box is moving along the belt towards the painting area, in Paint the actual painting of the box takes place, in Piston the box may be kick?'ed off the belt leading to Off; if the box is not kicked off it ends in End. All phases are assumed to last between 8 and 10 seconds, except for the phase Sensor, which is instantaneous. The uncontrollability of this timing uncertainty is indicated by the dashed transitions between phases. The controller should now issue a single kick?'command at the appropriate moment in order to guarantee that the box will -regardless of the above timing uncertainybe kicked off the belt. However the controller has imperfect information of the position of the box in the system. In particular, the controller cannot directly observe whether the box is in the Sensed, Paint or in the Piston phase nor can the value of the clock x be observed. Still equipping the controller with its own clock y -which it may reset and test (against a finite number of predicates)it might be possible to synthesize a control strategy despite having only partial information: in fact it may be deduced that the box will definitely be in the Piston area within 20-24 seconds after being sensed. In contrast, an increased timing uncertainty where a phase may last between 6 and 10 seconds will make a single-kick? strategy impossible.

The main contributions of this paper are: (i) we show how a variant of the subset construction of [START_REF] Chatterjee | Algorithms for omegaregular games with imperfect information[END_REF][START_REF] Wulf | A lattice theory for solving games of imperfect information[END_REF] allows us to transform a timed game H with imperfect information into an equivalent game G(H) of perfect information; (ii) we show that G(H) can be effectively and symbolically computed and this implies that the control problem under imperfect information is decidable; this allows us to apply the efficient on-the-fly forward algorithm from [START_REF] Cassez | Efficient on-the-fly algorithms for the analysis of timed games[END_REF] and (iii) we report on application of an initial experimental implementation of this algorithm and a number of heuristics for minimizing the explored state-space as well as the size of the finally synthesized strategy.

The detailed proofs can be found in the extended version available from the authors web pages.

Timed Games and Observation Based Strategies

In this section, we define the timed game structures, the notion of strategies that we are interested in, and useful vocabulary for the rest of the paper. We denote R ≥0 the set of non-negative reals and R >0 = R ≥0 \ {0} and A B the set of mappings from B to A.

Timed game structures (TGS) will be defined using a timed automaton like notation. The semantics of the notation will be defined by a two-player labeled timed transition system (2-LTTS), and the games will be played on this 2-LTTS.

Definition 1 (2-LTSS).

A 2-player labeled timed transition system (2-LTTS) is a tuple (S, s 0 , Σ 1 , Σ 2 , →) where S is a (infinite) set of states, s 0 is the initial state, Σ 1 and Σ 2 are the two disjoint alphabets of actions for Player 1 and Player 2 respectively, and →⊆ S × Σ 1 ∪ Σ 2 ∪ R >0 × S is the transition relation. Given a state s ∈ S, we define enable(s) as the set of σ ∈ Σ 1 ∪ Σ 2 ∪ R >0 such that there exists s ′ and (s, σ, s ′ ) ∈→.

Let X be a finite set of real-valued variables called clocks. Let M be a natural number. We note C(X, M ) the set of constraints ϕ generated by the grammar:

ϕ ::= x ∼ k | x -y ∼ k | ϕ ∧ ϕ where k ∈ Z ∩ [0, M ],
x, y ∈ X and ∼∈ {<, ≤, =, >, ≥}. B(X, M ) is the subset of C(X, M ) generated by the following grammar:

ϕ ::= ⊤ | k 1 ≤ x < k 2 | ϕ ∧ ϕ where k, k 1 , k 2 ∈ Z ∩ [0, M ], k 1 < k 2 ,
x ∈ X, and ⊤ is the boolean constant true. In the sequel, we will restrict our attention to bounded timed automata where clock values are all bounded by a natural number M ; this does not reduce the expressive power of timed automata. Given a natural number M , an M -valuation of the variables in X is a mapping X → R ≥0 ∩ [0, M ]. We also use the notation [X → [0, M ]] for valuations and 0 for the valuation that assigns 0 to each clock. For Y ⊆ X, we denote by v[Y ] the valuation assigning 0 (resp. v(x)) for any x ∈ Y (resp. x ∈ X \ Y ). Let t ∈ R ≥0 , v be an M -valuation for the set of clocks X, if for all x ∈ X, v(x)

+ t ≤ M then v + t is the M -valuation defined by (v + t)(x) = v(x) + t for all x ∈ X. For g ∈ C(X, M ) and v ∈ (R ≥0 ∩ [0, M ]) X , we write v |= g if v satisfies g and [[g]] denotes the set of valuations {v ∈ (R ≥0 ∩ [0, M ]) X | v |= g}. An M -zone Z is a subset of (R ≥0 ∩ [0, M ]) X s.t. Z = [[g]] for some g ∈ C(X, M ).
Definition 2 (Timed Game Structure). Let M be a natural number, an Mtimed game structure (M -TGS) is a tuple H = (L, ι, X, δ, Σ 1 , Σ 2 , inv, P) where:

-L is a finite set of locations, ι ∈ L is the initial location, -X is a finite set of real-valued clocks, -Σ 1 , Σ 2 are two disjoint alphabets of actions, Σ 1 is the set of actions of Player 1 and Σ 2 the set of actions of Player 2,

-δ ⊆ (L×B(X, M )×Σ 1 ×2 X ×L)∪(L×C(X, M )×Σ 2 ×2 X ×L) is partitioned
into transitions1 of Player 1 and transitions of Player 2. inv : L → B(X, M ) associates to each location its invariant.

-P is a finite set of pairs (K, ϕ) where K ⊆ L and ϕ ∈ B(X, M ), called observable predicates.

In the definition above, each observable predicate (K, ϕ) ∈ P is a predicate over the state space of the TGS, i.e. the set L × [X → [0, M ]]. For l ∈ L and v an M -valuation of the clocks in X, we write (l, v) |= (K, ϕ) iff l ∈ K and v |= ϕ. Two pairs (l 1 , v 1 ), (l 2 , v 2 ) that satisfy the same observable predicates from P have the same observation (they can not be distinguished by our controllers). So, an observation is a function o : P → {0, 1}, or equivalently, a class of equivalent states w.r.t P. We note O the set of functions [P → {0, 1}], it is called the set of observations of the system. With each TGS H with set of observable predicates P, we associate the function γ that maps observations to classes of equivalent states, i.e. γ : O → 2 L×[X→[0,M]] , and it is defined as follows:

γ(o) =    (l, v) | (K,ϕ) | o(K,ϕ)=1 (l, v) |= (K, ϕ) ∧ (K,ϕ) | o(K,ϕ)=0 (l, v) |= (K, ϕ)    Note that the set of observations O defines a partition of the state space of the M -TGS, i.e. o∈O γ(o) = L × [X → [0, M ]], and for all o 1 , o 2 ∈ O, if o 1 = o 2 , then γ(o 1 ) ∩ γ(o 2 ) = ∅. Given (l, v) we write γ -1 (l, v) for the observation o of state (l, v), i.e. γ -1 (l, v) is the function o : P → {0, 1} s.t. ∀p ∈ P, o(p) = 1 ⇐⇒ (l, v) |= p.
We associate with any M -TGS H a semantics in the form of a (infinite state) 2-LTTS. The state space of the 2-LTTS will be composed of elements of the form (l, v) where l is a location of the TGS and v is a valuation of the clocks. In order to avoid deadlocks in the 2-LTTS, we require that our TGS are deadlock-free2 , that is, for every state (l, v) such that v |= inv(l), there exists σ ∈ Σ 2 ∪ R >0 , such that either there is a transition (l, g, σ, Y, l

′ ) ∈ δ such that v |= g and v[Y ] |= inv(l ′ ), or for all t ′ , 0 ≤ t ′ ≤ σ, v + t ′ |= inv(l).

Definition 3 (Semantics of a TGS). The semantics of an

M -TGS H = (L, ι, X, δ, Σ 1 , Σ 2 , inv, P) is a 2-LTTS S H = (S, s 0 , Σ 1 , Σ 2 , →) where: -S = {(l, v) | l ∈ L ∧ v ∈ (R ≥0 ∩ [0, M ]) X ∧ v |= inv(l)}; -s 0 = (ι, 0); -the transition relation is composed of (i) discrete transitions. For all (l 1 , v 1 ), (l 2 , v 2 ) ∈ S, for all σ ∈ Σ 1 ∪ Σ 2 , ((l 1 , v 1 ), σ, (l 2 , v 2 )) ∈→ iff there exists a transition (ℓ, g, a, Y, ℓ ′ ) ∈ δ such that ℓ = l 1 , ℓ ′ = l 2 , v 1 |= g, and v 2 = v 1 [Y ]; (ii) time transitions. For all (l 1 , v 1 ), (l 2 , v 2 ) ∈ S, for all t ∈ R >0 , there is a transition ((l 1 , v 1 ), t, (l 2 , v 2 )) ∈→ iff l 1 = l 2 , v 2 = v 1 + t, and for all t ′ , 0 ≤ t ′ < t, (l 1 , v 1 + t ′ ) ∈ S and γ -1 (l 1 , v 1 + t ′ ) = γ -1 (l 1 , v 1 ).
Remark 1. This semantics has the following important property: changes of observations can occur only during a discrete transition, or at the last point of a time delay. This is consistent with our definition of observations using constraints in B(X, M ): the form of the constraints implies that either for all t ≥ 0, (l, v)

t -→ (l, v + t), and γ -1 (l, v + t) = γ -1 (l, v), or there is a first instant t 0 > 0 s.t. (l, v) t0 -→ (l, v + t 0 ) and γ -1 (l, v + t 0 ) = γ -1 (l, v), and for all 0 ≤ t ′ < t 0 , γ -1 (l, v + t ′ ) = γ -1 (l, v).
The 2-LTTS of a TGS has no deadlock because a TGS is deadlock-free. This also implies that any state of the 2-LTTS is the source of an infinite path. As a TGS is bounded, these infinite paths contain infinitely many discrete steps and in the sequel we will consider only these type of infinite paths.

Playing with Observation Based Stuttering Invariant Strategies. In the remainder of this section, we will define the rules of the timed games that we want to consider. We start by an informal presentation and then turn to the formalization.

Player 1 and Player 2 play on the underlying 2-LTTS of a TGS as follows. Player 1 has to play according to observation based stuttering invariant strategies (OBSI strategies for short). Initially and whenever the current observation of the system state changes, Player 1 either proposes an action σ 1 ∈ Σ 1 , or the special action delay. When Player 1 proposes σ 1 , this intuitively means that he wants to play the action σ 1 whenever this action is enabled in the system. When Player 1 proposes delay, this means that he does not want to play discrete actions until the next change of observation, he is simply waiting for the next observation. Thus, in the two cases, Player 1 sticks to his choice until the observation of the system changes: in this sense he is playing with an observation based stuttering invariant strategy. Once Player 1 has committed to a choice, Player 2 decides of the evolution of the system until the next observation but respects the following rules:

1. if the choice of Player 1 is a discrete action σ 1 ∈ Σ 1 then Player 2 can choose to play, as long as the observation does not change, either (i) a discrete actions in Σ 2 ∪ {σ 1 } or (ii) let time elapse as long as σ 1 is not enabled. This entails that σ 1 is urgent, 2. if the choice of Player 1 is the special action delay then Player 2 can choose to play, as long as the observation does not change, any of its discrete actions in Σ 2 or let time pass, 3. the turn is back to Player 1 as soon as the next observation is reached.

Plays. In the following, we define plays of a game where choices of Player 1 are explicitly mentioned. A play in H is an infinite sequence of transitions in

S H , ρ H = (l 0 , v 0 )c 0 σ 0 (l 1 , v 1 )c 1 σ 1 . . . (l n , v n )c n σ n . . . , such that for all i ≥ 0, (l i , v i ) σi -→ (l i+1 , v i+1 ) and -either σ i ∈ {c i } ∪ Σ 2 , or -σ i ∈ R X >0 and ∀0 ≤ t < σ i , c i ∈ enable(l i , v i + t) (time elapses only when the choice of Player 1 is not enabled). 3 -if σ i and σ i+1 are in R X >0 then γ -1 (l i , v i ) = γ -1 (l i+1 , v i+1 ).
We write Play((l, v), H) for the set of plays in H that start at state (l, v). We write Play(H) for the initial plays that start at the initial state of H, that is the set Play((ι, 0), H).

Prefixes, Strategies, and Outcomes. A prefix of H is a prefix of a play in H that ends in a state of H. We note Pref((l, v), H) for the set of prefixes of plays in H that starts in (l, v), i.e. plays in Play((l, v), H). We note Pref(H), for prefixes of initial plays in H, i.e. prefixes of plays in Play(H).

Let ρ H = (l 0 , v 0 )c 0 σ 0 • • • (l n , v n )c n σ n • •
• be a play or a prefix of a play, ρ H (n) denotes the prefix up to (l n , v n ). In the sequel, we measure the length of a prefix by counting the number of states that appear in the prefix. For example, ρ H (n) has a length equal to n + 1. A strategy for Player 1 in H is a function λ H :

Pref(H) → Σ 1 ∪ {delay}. The outcome of a strategy λ H in H is the set of plays ρ H = (l 0 , v 0 )c 0 σ 0 (l 1 , v 1 )c 1 σ 1 . . . (l n , v n )c n σ n . . . such that l 0 = ι, v 0 = 0 and for all i ≥ 0, c i = λ H (ρ H (i))
. We note Outcome H (λ H ) this set of plays.

Consistent Plays, Choice Points and OBSI Strategies in H. We are interested in strategies for Player 1 where the choice of action can only change if the observation of the state of the system changes. Such a strategy is called an observation based stuttering invariant strategy as presented before. When Player 1 plays such a strategy, the resulting plays have the property of being consistent. This notion is defined as follows. A play

ρ H = (l 0 , v 0 )c 0 σ 0 • • • (l n , v n )c n σ n • • • is consistent iff for all i ≥ 0: γ -1 (ℓ i+1 , v i+1 ) = γ -1 (ℓ i , v i ) =⇒ c i+1 = c i .
We note Play co (H) the set of consistent plays of H, and Pref co (H) the set of prefixes of consistent plays of

H. Let ρ H = (l 0 , v 0 )c 0 σ 0 • • • (l n-1 , v n-1 )c n-1 σ n-1 (l n , v n ) ∈ Pref co (H). ρ H is a choice point if either n = 0, or n > 0 and γ -1 (l n-1 , v n-1 ) = γ -1 (l n , v n ). Note that we have that ChoicePoint(H) ⊆ Pref co (H) ⊆ Pref(H) and Play co (H) ⊆ Play(H). Let ρ H = (l 0 , v 0 )c 0 σ 0 • • • (l n , v n )c n σ n • • • be a consistent play in H. Let I = {m | ρ H (m) ∈ ChoicePoint(H)}.
The stuttering free observation Obs(ρ H ) of ρ H is the sequence in (O.Σ 1 ) ω defined by:

-if I = {n 0 , n 1 , • • • , n k } is finite, Obs(ρ H ) = γ -1 (l n0 , v n0 )c n0 • • • γ -1 (l n k , v n k )c n k (γ -1 (l n k , v n k )c n k ) ω -if I = {n 0 , n 1 , • • • , n k , • • • } is infinite, Obs(ρ H ) = γ -1 (l n0 , v n0 )c n0 γ -1 (l n1 , v n1 )c n1 • • • γ -1 (l n k , v n k )c n k • • • We call it "stuttering free" as, for all i ∈ I, γ -1 (l ni , v ni ) = γ -1 (l ni+1 , v ni+1 ) except when I is finite, but in this case, only the last observation is repeated infinitely. Let ρ H ∈ ChoicePoint(H), let I = {n 0 , n 1 , • • • , n k } be the set of indices n i such that ρ H (n i ) ∈ ChoicePoint(H). The (finite) observation of ρ H , noted Obs * (ρ H ), is γ -1 (l n0 , v n0 )c n0 • • • γ -1 (l n k , v n k )c n k γ -1 (l n k , v n k )c n k . We
(λ H ) • Obs(ρ) ↓ O ∈ W.
To conclude this section, we define the control problem OBSI-CP we are interested in: let H be a TGS with observations O, W be a stuttering closed subset of O ω , is there an OBSI winning strategy in H for W?

(OBSI-CP)

In case there is such a strategy, we would like to synthesize one. The problem of constructing a winning strategy is called the synthesis problem.

Subset Construction for Timed Games

In this section, we show how to transform a timed game of imperfect information into an equivalent game of perfect information. Let H = (L, ι, X, δ, Σ 1 , Σ 2 , inv, P) be an M -TGS and let S H = (S, s 0 , Σ 1 , Σ 2 , →) be its semantics. In this section we assume delay ∈ Σ 1 but H has no transition labeled delay.

Useful functions. Let σ ∈ Σ 1 . We define the relation σ -→ nobs by: (l, v)

σ -→ nobs (l ′ , v ′ ) if there is a prefix ρ = (ℓ 0 , v 0 )c 0 σ 0 (ℓ 1 , v 1 )c 1 σ 1 • • • (l k , v k )c k σ k (ℓ k+1 , v k+1 ) in Pref((l, v), H) with (ℓ 0 , v 0 ) = (l, v), (ℓ k+1 , v k+1 ) = (l ′ , v ′ ), ∀0 ≤ i ≤ k, c i = σ, γ -1 (ℓ i , v i ) = γ -1 (ℓ 0 , v 0 ), and γ -1 (ℓ k+1 , v k+1 ) = γ -1 (ℓ 0 , v 0 ). Notice that because of the definition of time transitions in Definition 3, if σ i ∈ R >0 and 0 ≤ i < k then γ -1 (ℓ i , v i ) = γ -1 (ℓ i+1 , v i+1 ) and if σ i ∈ R >0 and i = k, γ -1 (ℓ i , v i ) = γ -1 (ℓ i , v i + t) for all 0 ≤ t < σ i , γ -1 (ℓ i , v i ) = γ -1 (ℓ i , v i + t) and (ℓ i+1 , v i+1 ) = (ℓ i , v i + σ i ) (i.
e. σ i is the first instant at which the observation changes). By the constraints imposed by B(X, M ) this first instant always exists. We define the function Next σ (l, v) by:

Next σ (l, v) = {(l ′ , v ′ ) | (l, v) σ -→ nobs (l ′ , v ′ )} (1)
This function computes the first next states after (l, v) which have an observation different from γ -1 (l, v) when Player 1 continuously plays σ. Next is extended to sets of states as usual.

We also define the function Sink σ (•) :

L × R X ≥0 → L × R X ≥0 for σ ∈ Σ 1 : (l ′ , v ′ ) ∈ Sink σ (l, v) iff there is an (infinite) play 5 ρ = (ℓ 0 , v 0 )c 0 σ 0 (ℓ 1 , v 1 )c 1 σ 1 • • • (l k , v k ) c k σ k (ℓ k+1 , v k+1 ) • • • in S H such that: (ℓ 0 , v 0 ) = (l, v), (ℓ k+1 , v k+1 ) = (l, ′ v ′ ), ∀0 ≤ i, c i = σ, and ∀0 ≤ i, γ -1 (l i , v i ) = γ -1 (l 0 , v 0 ).
Non-Deterministic Game (of Perfect Information). The games of perfect information that we consider here are (untimed) non-deterministic games, and they are defined as follows: in each state s Player 1 chooses an action σ and Player 2 chooses the next state among the σ-successors of s. Definition 4 (Non-Deterministic Game). We define a non-deterministic game (NDG) to be a tuple G = (S, µ, Σ 1 , ∆, O, Γ ) where:

-S = S 0 ∪ S 1 is a set of states; µ ∈ S 0 is the initial state of the game; -Σ 1 is a finite alphabet modeling choices for Player 1;

-∆ ⊆ S 0 × Σ 1 × S is the transition relation;
-O is a finite set of observations; -Γ : O → 2 S \ ∅ maps an observation to the set of states it represents, we assume Γ partitions S (Γ -1 (s) = o ⇐⇒ s ∈ Γ (o)).

Definition 5 (Plays in NDG).

A play in G from s 0 is either an infinite sequence s 0 a 0 s 1 a 1 . . . s n a n . . . such that for all i ≥ 0, s i ∈ S 0 , a i ∈ Σ 1 , and (s i , a i , s n+1 ) ∈ ∆ or a finite sequence s 0 a 0 s 1 a 1 . . . s n such that all i, 0 ≤ i < n, s i ∈ S 0 , (s i , a i , s i+1 ) ∈ ∆, and s n ∈ S 1 . We note Play(s 0 , G) the set of plays starting in s 0 in G and let Play(G) = Play(µ, G). The observation of an infinite play ρ G = s 0 a 0 s 1 a 1 . . . s n a n . . . is defined by

Obs(ρ G ) = Γ -1 (s 0 )a 0 Γ -1 (s 1 )a 1 . . . Γ -1 (s n )a n . . . . If ρ G = s 0 a 0 s 1 a 1 s n-1 a n-1 . . . s n a n s n+1 is finite then Obs(ρ G ) = Γ -1 (s 0 )a 0 Γ -1 (s 1 )a 1 . . . Γ -1 (s n )a n (Γ -1 (s n+1 )a n ) ω .
A prefix in G is a finite sequence s 0 a 0 s 1 a 1 . . . s n ending in s n ∈ S 0 , such that for all i, 0 ≤ i < n, (s i , a i , s i+1 ) ∈ ∆. We let Pref(G) be the set of prefixes of G. The observation of a prefix is

Obs(ρ G ) = Γ -1 (s 0 )a 0 Γ -1 (s 1 )a 1 . . . a n Γ -1 (s n ). For any ρ G ∈ Play(G), ρ G (n) = s 0 a 0 • • • s n is the prefix up to state s n and we let |ρ G | = n to be the length of ρ G .
Remark 2. S 0 is the set of states where Player 1 has to make a choice of action. In S 1 -states, Player 1 does not have any choice. A prefix ends in an S 0 -state. Finite sequences ending in S 1 -states are not prefixes but finite plays.

Strategies and Winning Conditions for

NDG. A strategy in G is a func- tion 6 λ G : Pref(G) → Σ 1 . The outcome, Outcome G (λ G ), of a strategy λ G is the set of (finite or infinite) plays ρ G = s 0 a 0 • • • s n a n • • • s.t. s 0 = µ, ∀i ≥ 0, a i = λ G (ρ G (i)). Let ρ G be a play of G. We let Obs(ρ G ) ↓ O be the projection of Obs(ρ G ) on O. A winning condition W for G is a subset of O ω . A strategy λ G is winning for W in G iff ∀ρ G ∈ Outcome G (λ G ), Obs(ρ G ) ∈ W.
Remark 3. Strategies in NDG are based on the history of the game since the beginning: in this sense, this is a perfect information game.

Knowledge Based Subset Construction. Definition 6. Given a game H = (L, ι, X, δ, Σ 1 , Σ 2 , inv, O, γ), we construct a NDG G(H) = (S, µ, Σ 1 , ∆, O, Γ ) as follows:

-let V = {W ∈ 2 L×R X ≥0 \ ∅ | γ -1 (l, v) = γ -1 (l ′ , v ′ ) for all (l, v), (l ′ , v ′ ) ∈ W }, -S = V × {0, 1}, and we note S 0 the set V × {0} and S 1 the set V × {1}, -µ = ({(ι, 0)}, 0), -∆ ⊆ S × Σ 1 × S is the smallest relation that satisfies: ((V 1 , i), σ, (V 2 , j)) ∈ ∆ if • i = 0. A consequence is that if i = 1 (a state in S 1
) there are no outgoing transitions.

• j = 0 and

V 2 = Next σ (V 1 )∩o for some o ∈ O such that Next σ (V 1 )∩o = ∅, or • j = 1 if Sink σ (s) = ∅ for some s ∈ V 1 and V 2 = ∪ s∈V1 Sink σ (s), -Γ -1 : S → O, and Γ -1 ((W, i)) = γ -1 (v) for v ∈ W . Note that this is
well-defined as W is a set of states of H that all share the same observation.

Notice that the game G(H) is non-deterministic as there may be many transitions labeled by σ and leaving a state s to many different states with different observations. G(H) is total for S 0 states: ∀(V, 0) ∈ S 0 , ∀σ ∈ Σ 1 , σ ∈ Enabled(V ), because either there is an infinite path from some s ∈ V with the same observation or there is an infinite path with a new observation (remember that time can elapse or Player 2 can do a discrete action from any state in H). Although non-deterministic G(H) enjoys a weaker notion of determinism formalized by the following proposition:

Proposition 1. Let (V, i) be a state of G(H), σ ∈ Σ 1 and o ∈ O. There is at most one (V ′ , j) with V ′ ⊆ γ(o) s.t. ((V, i), σ, (V ′ , j)) ∈ ∆. Note also that if ((V, 0), σ, (V ′ , 0)) ∈ ∆ then Γ -1 ((V, 0)) = Γ -1 ((V ′ , 0)).
We can relate the consistent plays in H and plays in G. For that, we define the function Abs : Play co (H) → Play(G) as follows.

Definition 7 (Abs for Plays of H

). Let ρ H = (l 0 , v 0 )c 0 σ 0 (l 1 , v 1 ) . . . (l m , v m ) c m σ m . . . be in Play co (H). Let I = {j ∈ N | ρ H (j) ∈ ChoicePoint(H)}. Then Abs(ρ H ) is defined by: -if I is a finite set, let I = {j 0 , j 1 , • • • , j n }. Define Abs(ρ H ) = s 0 a 0 s 1 a 1 . . . s n
a n s n+1 by induction as follows:

1. s 0 = ({(l 0 , v 0 )}, 0), a 0 = c j0 (and j 0 = 0), 2. and for all i,

0 < i ≤ n, if s i-1 = (V, 0) then let V ′ = Next ai-1 (V ) ∩ γ -1 (v ji ), s i = (V ′ , 0) and a i = c ji . 3.
As ρ H has a finite number of choice points, it must be the case that

∀k ≥ j n , γ -1 (l k , v k ) = γ -1 (l jn , v jn ); moreover, because ρ H is consistent, ∀k ≥ j n , c k = c jn . If s n = (V, 0) we let V ′ = ∪ v∈V Sink cj n (v). V ′ must
be non empty and we define s n+1 = (V ′ , 1).

-if I is an infinite set, let I = {j 0 , j 1 , • • • , j n , • • • }. We define Abs(ρ H ) =
s 0 a 0 s 1 a 1 . . . s n a n s n+1 • • • by induction as follows:

1. s 0 = ({(l 0 , v 0 )}, 0), a 0 = c j0 (and j 0 = 0),

and for all

i ≥ 1, if s i-1 = (V, 0) then let V ′ = Next ai-1 (V ) ∩ γ -1 (v ji ), s i = (V ′ , 0) and a i = c ji .
Definition 8 (Abs for consistent prefixes). Let ρ H = (l 0 , v 0 ) . . .

(l n-1 , v n-1 ) c n-1 σ n-1 (l n , v n ) ∈ Pref co (
H) and, I = {j 0 , j 1 , • • • , j m } be the set of choice points of ρ H . Then Abs(ρ H ) = s 0 a 0 . . . s m-1 a m-1 s m with:

s 0 = ({(l 0 , v 0 )}, 0), -and for all i,

0 < i ≤ m, if s i-1 = (V i-1 , 0) then s i = (V i , 0) where V i = Next ai-1 (V i-1 ) ∩ o i , -∀0 ≤ i < m, a i = c ji .
It can be checked that Abs(ρ H ) is well-defined for consistent plays as well for prefixes. The following theorem states the correctness of our construction: Theorem 1. Let Φ be a stuttering closed subset of O ω . Player 1 has a winning strategy in G(H) for Φ iff Player 1 has an observation based stuttering invariant winning strategy in H for Φ.

Symbolic Algorithms

In this section, we show that the game G(H) is a finite game and design an efficient symbolic algorithm for reachability and safety objectives.

Given a set of states S represented as a finite union of zones, and an action c ∈ Σ 1 we can compute the sets s∈S Next c (s) and s∈S Sink c (s) as finite unions of zones. Since the clocks are bounded in our M -TGS, only a finite number of zones are computed during the computation of those operators. As a consequence, the game G(H) is finite.

To implement efficiently the computations, we use Difference Bound Matrices (DBMs), which allow efficient realisation of most set operations (inclusion, interesection, future, reset. . . ) [START_REF] Dill | Timing Assumptions and Verification of Finite-State Concurrent Systems[END_REF][START_REF] Larsen | Model-checking for real-time systems[END_REF].

Since G(H) is finite, we can apply standard control algorithms to compute the set of winning states. In particular, for reachability or safety objectives, we can use the efficient on-the-fly forward algorithm of [START_REF] Cassez | Efficient on-the-fly algorithms for the analysis of timed games[END_REF] that has been implemented in Uppaal-Tiga [START_REF] Behrmann | Uppaaltiga: Time for playing games![END_REF].

The algorithm for finite games given in [START_REF] Cassez | Efficient on-the-fly algorithms for the analysis of timed games[END_REF] can easily be tailored to solve NDGs of type G = (S, s 0 , Σ 1 , ∆, O, Γ ) with reachability objective Goal s.t. Goal ∈ O. Then, to obtain an algorithm for games of imperfect information, we replace the transition relation of G(H) in this algorithm with the definition (see Definition 6) of the transition relation of G(H) using the Next and Sink operators. This way we obtain the algorithm OTFPOR for TGS which is given Figure 2.

An important feature added to the algorithm is the propagation of losing state-sets, that is state-sets for which the reachability objective can be directly concluded not to be achievable. For reachability games, a state-set W may declared to be losing provided it is not among the Goal sets and is a deadlock. Safety games are dual to reachability games in the sense that if the algorithm concludes that the initial state is not losing it is possible to extract a strategy to avoid losing states.

Example and Experiments

In this section we report on an application of a prototype implementation of the OTFPOR algorithm. Similar to the Box Painting Production System (BPPS) from the Introduction, we want to control a system consisting of a moving belt and an ejection piston at the end of the belt. However, a complicating feature compared with BPPS is that the system can receive both light and heavy boxes. we want to avoid); those transitions are not depicted in the figure. The control objective is to avoid entering location l 7 .

To control the system, the controller can use a clock y that it can reset at any moment. The controller can also issue the order Eject! or propose to play delay, which allows for the time to elapse. The controller has an imperfect information about the state of the system and the value of the clock y. The controller gets information throughout the following observations: E: the control of the automaton is in location l 0 , l 2 , l 3 , l 5 , or l 6 ; H: the control of the automaton is in location l 1 ; L: the control of the automaton is in location l 4 ; B: the control of the automaton is in location l 7 ; 0 ≤ y < M : the value of clock y is in the interval [0, M [, M being a parameter. The observations E, H, L, and B are mutually exclusive and cover all the states of the automaton but they can be combined with the observation 0 ≤ y < M on the clock but also with its complement y ≥ M . So formally, the set of observations that the controller can receive at any time is O = {(E, 0 ≤ y < M ), (E, y ≥ M ), (H, 0 ≤ y < M ), (H, y ≥ M ), (L, 0 ≤ y < M ), (L, y ≥ M ), (B, 0 ≤ y < M ), (B, y ≥ M )}. The set of actions that the controller can choose from is Σ c = {Reset y , Eject!, delay}.

We modelled this example in our prototype and checked for controllability of the safety property A ¬B. Controllability as well as the synthesized strategy heavily depend on the choice of the parameter M , i.e. the granularity at which the clock y may be set and tested. Table 1 gives the experimental results for M ∈ {1, 0.5, 0.25, 0.2}7 . It turns out that the system is not controllabe for M = 1: a granularity of 1 is simply too coarse to determine (up to that granularity) with certainty when, say, a light box will be in l 6 and should be Eject?'ed. The differences between the guards and invariants in l 5 , l 6 and l 7 are simply too small. As can be seen from Table 1 the finer granularities yield controllability.

We report on the number of explored state-sets (state-set ) and the number of state-sets that are part of the strategy (strat ). To get an impression of the complexity of the problem of controller synthesis under partial observability we note that the the model in Figure 3 as a regular timed automaton. Table 1 reports on experiments exploiting an additional inclusion checking option in various ways: (notfi ) without on-the-fly inclusion checking, and (otfi ) with on-the-fly inclusion checking. In addition, we apply the post-processing step of inclusion checking (+post ) on the strategy and a filtering of the strategy (+filter ) on top to output only the reachable state-sets under the identified strategy. The results show that on-the-fly inclusion checking gives a substantial reduction in the number of explored state-sets -and is hence substantially faster. Both (notfi ) and (otfi ) shows that post processing and filtering reduces the size of the control strategy with a factor of approximately 100. It can also be seen that the size of the final strategy grows when granularity is refined; this is to be expected as the strategies synthesized can be seen to involve counting modulo the given granularity. More suprising is the observation that the final strategies in (notfi +post +filter ) are uniformly smaller than the final strategies in (otfi ): not performing on-the-fly inclusion checking explores more state-sets, thus having the potential for a better reduction overall.

Conclusions and Future Works

During the last five years a number of very promissing algorithmic techniques has been introduced for controller synthesis in general and controller synthesis for timed systems in particular. The contribution of this paper to the decidability and algorithmic support for timed controller synthesis under imperfect information is an important new step within this line of research. Future research includes more experimental investigation as well as search for additional techniques for minimizing the size of the produced strategies (e.g. using minimization wrt. (bi)simulation or alternating simulation). For safety objectives, we need methods to insure that the synthesized strategies do not obtain their objective simply by introducing zeno behaviour. Finally, a rewrite of the prototype as extension of Uppaal-Tiga is planned.

On x ≤ 10 Sensor

 10

Fig. 3 .

 3 Fig. 3. Timed Game for Sorting Bricks. Edges to l7 with action Eject? are omitted.

  say that a strategy λ H is an observation based stuttering invariant (OBSI) strategy if the following property holds: for all ρ H

1 , ρ H 2 ∈ Pref co (H), let n 1 be the maximal value such that ρ H 1 (n 1 ) ∈ ChoicePoint(H), let n 2 be the maximal value such that ρ H 2 (n 2 ) ∈ ChoicePoint(H), if Obs * (ρ H 1 (n 1 )) = Obs * (ρ H 2 (n 2 )) then λ H (ρ H 1 ) = λ H (ρ H 2 ). Winning Conditions and Winning Strategies. Let ρ H ∈ Play(H) s.t. Obs(ρ H ) = o 0 c 0 o 1 c 1 . . . o n c n . . . . The projection Obs(ρ H ) ↓ O over O of Obs(ρ H ) is the sequence o 0 o 1 . . . o n . . . . A winning condition W is a stuttering closed 4 subset of O ω . A strategy λ H for Player 1 is winning in H for W, if and only if, ∀ρ ∈ Outcome H

Table 1 .

 1 has 115 reachable symbolic states when viewed Number of state-sets and size of strategy obtained for different heuristics for observations 0 ≤ y < M of the clock y with M ∈ {1, 0.5, 0.25, 0.2}. The case M = 1 is not controllable.

			notfi				otfi
		state-set strat +post +filter state-set strat +post +filter
	[0, 0.2[	110953 36169 1244	70	52615 16372 841	176
	[0, 0.25[ 72829 23750 1014	60	35050 11016 697	146
	[0, 0.5[	20527 6706 561	41	10586 3460 407	88
	[0, 1[	2284	-	-	-	1651	-	-	-

Note that we impose that guards of Player 1's transitions are left closed. This ensures that, when a guard becomes true for an action owned by Player 1, there is always a first instant where it becomes true.

And more precisely, either time can elapse or Player 2 can do a discrete action from any state: thus Player 1 cannot block the game by refusing to take its actions.

Remember that delay is never enabled and if Player 1 wants to let time elapse he plays delay.

A language is stutter closed, if for any word w in the language, the word w ′ obtained from w by either adding a stuttering step (repeating a letter), or erasing a stuttering step, is also in the language.

With an infinite number of discrete transitions because of the boundedness assumption. If needed we can add the requirement that this path is non-zeno if we want to rule out zeno-runs.

Notice that S1-states have no outgoing transitions and we do not need to define a strategy for these states.

Fractional values of M are dealt with by multiplying all constants in the timed game automaton with 1 M .

⋆ Work supported by the French National Research Agency ANR-06-SETI-DOTS. ⋆⋆ Author supported by the Fonds National de la Recherche Scientifique, Belgium. ⋆ ⋆ ⋆ Author supported by the Belgian FNRS grant 2.4530.02 of the FRFC project "Centre Fédéré en Vérification" and by the project "MoVES", an Interuniversity Attraction Poles Programme of the Belgian Federal Government.

Initialization:

P assed ← {{s0}}; When receiving a light box, its speed is high and the box takes between 4 to 6 seconds to reach the zone where it can be Eject?'ed with a piston. When receiving a heavy box, the speed of the belt is slower and the box takes between 9 and 11 seconds to reach the zone where it can be Eject?'ed by the piston. The controller should command the piston so that the order to Eject? a box is given only when the box is in the right region. The system is modeled by the timed game automaton of Figure 3. The initial location of the automaton is l 0 . The system receives boxes when it is in location l 0 , if it receives a heavy box then it branches to l 1 , if it receives a light box then it branches to l 4 . The only event that is shared with the controller is the Eject? event. This event should be issued when the control of the automaton is in l 3 or l 6 (which has the effect of ejecting the box at the end of the belt), in all other locations, if this event is received then the control of the automaton evolves to location l 7 (the bad location that


Lan Gao
email: lan.gao@esiee.fr

Elyes Nefzaoui

Martine Gnambodoe-Capochichi

Yamin Leprince-Wang

Tarik Bourouina

Enhanced steam generation based on a bilayer water and light absorber Modelling and optimization of capillary imbibition and water evaporation

Bilayer modelling

Heat and mass transfer in the bilayer structure during the steam generation process.

Energy balance in the enhanced steam generation process.

Introduction

Enhanced steam generation is a robust and promising process for water purification. This is a method of increasing the evaporation efficiency by localizing the heat at the water-air interface using a black absorber. It is worth mentioning at this stage that the two functions of localized heating and water imbibition are different functions that can be separated in their implementation. However, one can note that a vast majority of state-of-the-art implementations show that both functions are integrated together, which is typically a black and porous medium, hence providing simultaneous light absorption and water absorption capabilities. In addition, there is a concern about thermal conductivity so as to minimize loss of the surface-localized generated heat into the surrounding water bulk. As of late, bilayer structure black absorbers have been developed in different combinations of photothermal materials and porous media aiming to achieve efficient steam generation.

First layer modelling : heat transfer

v 𝑞 𝑒𝑣𝑎𝑝,𝑤𝑎𝑡𝑒𝑟 = 𝑞 𝑠𝑜𝑙𝑎𝑟 • 𝛼 𝑒𝑣𝑎𝑝 + 𝑞 𝑟𝑎𝑑,𝑎𝑏𝑠 -𝑞 𝑠𝑜𝑙𝑎𝑟 • 𝛼 𝑎𝑏𝑠 -𝑞 𝑐𝑜𝑛𝑣,𝑤𝑎𝑡𝑒𝑟 -𝑞 𝑟𝑎𝑑,𝑤𝑎𝑡𝑒𝑟 + 𝑞 𝑠𝑜𝑙𝑎𝑟 • 𝛼 𝑎𝑏𝑠 -𝑞 𝑟𝑎𝑑,𝑎𝑏𝑠 -𝑞 𝑠𝑒𝑐𝑜𝑛𝑑-𝑙𝑎𝑦𝑒𝑟 𝐹
In the first layer modelling: the smaller the F, which means the smaller the total surface area of the pores, the larger the heat flux for evaporation, and the more evident the evaporation.

Second layer structure

v open pore ( for water imbibition) Close pore (low thermal conductivity)

Water flow due to capillary effect

Different pore function integrated in one porous media.

In the second layer, we propose two kinds of pore for different functional uses. One is with the "open pores" to obtain water sustainable water imbibition. The other one is the "closed pores" in order to have low thermal conductivity 𝑘 𝑐𝑜𝑛𝑑 and the self-flowing ability. In a perforated pore, the capillary phenomenon can be obtained from the following differential equation:

• 𝜎 is the surface tension of water.

• 𝜃 is the contact angle.

• 𝑟 𝑝𝑜𝑟𝑒 is the radius of the perforated pore.

• 𝑔 is the gravity constant.

• 𝜌 is the density of water.

• 𝜇 is the water viscosity.

• 𝐻 𝑐 is the capillary height.

Capillary imbibition in steady state

We assumed that the water only gets vaporized at the surface, which means there is no evaporation happened during the capillary imbibition. While in the steady state, we can get :

𝑝 𝑐 = ∆𝑝 1 + 𝜌𝑔𝐿
• N is the number of perforated pores.

• Q is the Darcy's flow rate in steady state.

• L is the thickness of porous media.

Conclusion

• The theoretical results have a good agreement with simulation results in water imbibition phenomenon. • When giving a certain water imbibition flow rate, with the help of this modelling, we can determine the geometry from the perforate pore size, the number of pores and the thickness of absorber. • The modelling of thermal conductivity and density in close pores need to be added to the current model in the following study. • 𝑞 is the heat flux.

Theoretical results & Simulation results

• 𝜀 is absorptivity.

• 𝑘 is thermal conductivity.

• 𝜎 is Stefan-Boltzmann constant.

For the reason that the flow rate increases monotonically with the number of pores N, so in the modelling of open pores, the radius of the hole and the thickness of the hole are more noticeable.

Ideal model

Bilayer model

( a )

 a Capillary height versus time (with a given value pore radius). (b) Capillaryvelocity versus height (with a given value pore radius). is the capillary pressure (or Laplace pressure) while ∆𝑝 1 is the pressure due to the water motion in the porous media.By combining the hydraulic conductivity with Darcy's law, the flow rate through the perforated pores is:(C) Flow rate versus the radius of pore and the thickness of absorber.𝑞 𝑐𝑜𝑛𝑣 = ℎ 𝑐𝑜𝑛𝑣 (𝑇 𝑙𝑎𝑦𝑒𝑟1 -𝑇 𝑎𝑚𝑏𝑖𝑒𝑛𝑡 )𝑞 𝑟𝑎𝑑,𝑤𝑎𝑡𝑒𝑟 = 𝜀 𝑤𝑎𝑡𝑒𝑟 𝜎(𝑇 𝑙𝑎𝑦𝑒𝑟1 4 𝑙𝑎𝑦𝑒𝑟 = 𝑘 𝑐𝑜𝑛𝑑 𝑇 𝑙𝑎𝑦𝑒𝑟1 -𝑇 𝑤𝑎𝑡𝑒𝑟

layer modelling :perforated open pore Capillary imbibition in transit state

	2𝜎 cos 𝜃 𝑟 𝑝𝑜𝑟𝑒	𝜋𝑟 𝑝𝑜𝑟𝑒	2 -𝜌𝑔𝐻 𝑐 𝜋𝑟 𝑝𝑜𝑟𝑒	2 -	8𝜇 𝑟 𝑝𝑜𝑟𝑒	2 𝐻 𝑐	𝑑𝐻 𝑐 𝑑𝑡	𝜋𝑟 𝑝𝑜𝑟𝑒	2 =	𝑑 𝑑𝑡	(𝜌𝜋𝑟 2 𝐻 𝑐	𝑑𝐻 𝑐 𝑑𝑡	)

v Second


Mickael Pihain
email: mickael.pihain@ut.ee

Pille Gerhold
email: pille.gerhold@ut.ee

Alexis Ducousso
email: alexis.ducousso@inra.fr

Andreas Prinzing
email: andreas.prinzing@univ-rennes1.fr

Evolutionary response to coexistence with close relatives: increased resistance against specialist herbivores without cost for climatic-stress resistance

Keywords: adaptation, associational resistance, climatic-stress resistance, eco-evolutionary feedback, ecomorphology and chemical ecology, galls, ectophages and miners, phylogenetic diversity, multifunctional resistance, Sessile Oak (Quercus petraea), temperate forests

published or not. The documents may come

Evolutionary response to coexistence with close relatives: increased resistance against specialist herbivores without cost for climatic-stress resistance

Introduction

Coexistence among conspecific or phylogenetically proximate plants ("phylogenetically proximate" from here on) has been suggested to be difficult due to increased herbivore pressure, but plant populations might respond to such coexistence by evolving increased herbivore resistance. Specifically, individuals of phylogenetically proximate plant species tend to share similar traits [START_REF] Burns | More closely related species are more ecologically similar in an experimental test[END_REF][START_REF] Peterson | Ecological niche conservatism: a time-structured review of evidence[END_REF]Violle et al. 2011) and can be attacked by the same herbivore species [START_REF] Brändle | Is the composition of phytophagous insects and parasitic fungi among trees predictable?[END_REF]. This effect of phylogenetic proximity on herbivory is likely to be strongest in highly specialized herbivores [START_REF] Nyman | Larval habits, host-plant associations, and speciation in nematine sawflies (Hymenoptera: Tenthredinidae)[END_REF], Vialatte et al. 2010). Consequently, in phylogenetically proximate neighbourhoods, a focal host plant could be attacked by the herbivores of its neighbours, increasing herbivory on the focal plant [START_REF] Yguel | Phytophagy on phylogenetically isolated trees: why hosts should escape their relatives[END_REF]. It has been suggested that such increased herbivore pressure prevents coexistence of phylogenetically proximate individuals and leads to coexistence among phylogenetically distant species [START_REF] Janzen | Herbivores and the number of tree species in tropical forests[END_REF][START_REF] Liu | Experimental evidence for a phylogenetic Janzen-Connell effect in a subtropical forest[END_REF]; we use the term "coexistence" sensu largo, i.e. including coexistence with conspecifics, [START_REF] Jiang | A computational-experimental framework for mapping plant coexistence[END_REF]. However, such neighbourhoods might also select for increased herbivore resistance. In phylogenetically proximate neighbourhoods, more resistant plants will survive better, have more chances to reach maturity and reproduce more, leading to a higher fitness than non-resistant plants.

Plant resistances are often genetically determined and hence heritable, e.g. levels of flavonoids or anthocyanins or leaf morphology (e.g. Stevens & Lindroth 2005;[START_REF] Johnson | Heritability, covariation and natural selection on 24 traits of common evening primrose (Oenothera biennis) from a field experiment[END_REF]. Overall, a phylogenetically proximate neighbourhood should select for genotypes that are resistant against herbivores, in particular against specialist herbivores. These selection pressures are particularly powerful in trees [START_REF] Ersoz | Evolution of disease response genes in Loblolly pine: Insights from candidate genes[END_REF], where natural selection can shift frequencies of traits across a population within a fraction of a generation time (even if selection pressures might change even more rapidly, [START_REF] Rellstab | Signatures of local adaptation in candidate genes of oaks (Quercus spp.) with respect to present and future climatic conditions[END_REF]. This rapid shift of the frequencies of traits is possible due to large population sizes (seeds and seedlings included), 99.9999 % mortality depending on heritable resistance traits, and a very high genetic variability among trees and among seeds of each tree [START_REF] Shaw | Factors affecting the natural regeneration of sessile oak (Quercus petraea) in North Wales[END_REF][START_REF] Zanetto | Geographical structure of gene diversity in Quercus petraea (Matt.) Liebl. I. Monolocus patterns of variation[END_REF][START_REF] Klaper | Heritability of phenolics in Quercus laevis inferred using molecular markers[END_REF][START_REF] Petit | Some evolutionary consequences of being a tree[END_REF]. Overall, our first hypothesis A c c e p t e d m a n u s c r i p t is that tree species are not passively suffering from increased pressure by specialist herbivores in a phylogenetically proximate neighbourhood, but rather local populations are adapting to herbivory as a result of selection for herbivore resistance (Fig. 1).

If phylogenetically proximate neighbourhoods select for higher herbivore resistances they might indirectly select against capacities that are traded off against herbivore resistances such as the resistance to extreme climatic conditions. Specifically, resistance against herbivores might invoke multiple types of costs for the tree [START_REF] Baldwin | Jasmonate-induced responses of Nicotiana sylvestris results in fitness costs due to impaired competitive ability for nitrogen[END_REF][START_REF] Koricheva | Meta-analysis of sources of variation in fitness costs of plant antiherbivore defenses[END_REF][START_REF] Siemens | Plant chemical defence allocation constrains evolution of local range[END_REF].

Investment in resistance against herbivores might hence be traded off against other capacities of trees. For instance, genotypes with increased energy investment into traits conferring herbivore resistance might have less energy available to invest into traits conferring other functions including competitiveness or climatic-stress resistance [START_REF] Siemens | Water deficiency induces evolutionary tradeoff between stress tolerance and chemical defense allocation that may help explain range limits in plants[END_REF][START_REF] Alsdurf | Drought-induced trans-generational tradeoff between stress tolerance and defence: consequences for range limits?[END_REF]. Our second hypothesis is hence that phylogenetically proximate neighbourhoods indirectly select for reduced climatic-stress resistance due to a combination of two mechanisms: direct selection for genotypes of increased herbivore resistance (above hypothesis), and a trade-off between herbivore resistance and climatic-stress resistance of genotypes (Fig. 1). We expect this indirect selection to involve particular resistance traits that are energetically costly to a tree because they are produced in high quantities, such as anthocyanins or flavonols or morphological resistance traits [START_REF] Feeny | Plant apparency and chemical defense[END_REF].

Alternatively, the same traits might confer resistance against herbivores and climatic-stress and selection for these traits by a phylogenetically proximate neighbourhood might either prevent or reinforce selection by climatic-stress. Anthocyanins and flavonols, for instance, have been shown to increase under both herbivore attack and climatic-stress due to frost or drought (Treutter 2006;[START_REF] Korn | Heterosis in the freezing tolerance, and sugar and flavonoid contents of crosses between Arabidopsis thaliana accessions of widely varying freezing tolerance[END_REF]. Also tough, thick leaves rich in dry matter might resist both herbivores and climatic-stress. In such a case, two scenarios are possible. First, the double benefits from such multifunctional traits might reduce the costs of adaptation to climatic-stress in a neighbourhood that increases herbivore pressure, i.e. a phylogenetically proximate neighbourhood (Fig. 1). Second, the A c c e p t e d m a n u s c r i p t signal of selection by climatic-stress might be obscured by selection of the same traits by herbivore pressure, i.e. in a phylogenetically proximate neighbourhood. Simply, climatic-stress is not needed for the evolution of such traits in a phylogenetically proximate neighbourhood, and herbivores from phylogenetically proximate neighbours are not needed in a stressful climate. To our knowledge, it has been little studied how selection due to climatic-stress interacts with selection due to herbivore pressure (Suzuki et al. 2014), or even conditions favouring herbivory. Our third hypothesis is hence that a phylogenetically proximate neighbourhood either prevents or reinforces the selection by climatic-stress for traits promoting climatic-stress resistance.

We tested the above hypotheses for sessile oak (Quercus petraea), one of the major forest trees across much of Europe, often growing with phylogenetically proximate neighbours, and suffering from climatic-stress [START_REF] Cheaib | Climate change impacts on tree ranges: model intercomparison facilitates understanding and quantification of uncertainty[END_REF]. We used a 25-year common garden experiment from provenances of different phylogenetic neighbourhoods and climates (Appendix S1), permitting us to identify selection of genotypes in the provenances by characterising phenotypes of descendants in the common garden. Specifically, our hypotheses predict: (1) Descendants from provenances dominated by phylogenetically proximate neighbours experience little attack from specialist herbivores due to high levels of herbivore resistances (Fig. 1). (2) Provenances whose descendants have high levels of such herbivore resistances tend to have particularly low climatic-stress resistance, and these are the provenances dominated by phylogenetically proximate neighbours (Fig. 1). (3) Descendants from provenances of particularly harsh climates have tough and thick leaves rich in chemical resistance compounds -and the strength of this relationship is modified in provenances dominated by phylogenetically proximate neighbours (Fig. 1).

A c c e p t e d m a n u s c r i p t

Methods

Sessile oak (Quercus petraea)

Sessile oaks are among the dominant late-successional tree species in forests across temperate Europe, often forming monospecific stands or growing together with other Fagaceae species [START_REF] Ellenberg | Vegetation Ecology of Central Europe, 4 th edition[END_REF]. Sessile oaks suffer from a diverse and abundant herbivore fauna [START_REF] Brändle | Species richness of insects and mites on trees: expanding Southwood[END_REF], including both specialist species, such as miners and galls, and less specialised species such as ectophageous lepidoptera often capable of using multiple plant genera or even families [START_REF] Gaston | Intimacy and fidelity: internal and external feeding by British microlepidoptera[END_REF][START_REF] Giffard | Influcence of surrounding vegetation on insect herbivory: A matter of spatial scale and herbivore specialisation[END_REF]. [START_REF] Southwood | Seasonality, abundance, species richness and specificity of phytophagous guild of insects on oak (Quercus) canopies[END_REF] show that all three groups are abundant on oaks, the ectophages mainly in May, galls and mines in August to October. Moreover, sessile oak is predicted to strongly suffer from future climate change towards the hot and dry range edge [START_REF] Cheaib | Climate change impacts on tree ranges: model intercomparison facilitates understanding and quantification of uncertainty[END_REF], while towards its continental and northern limit, it appears to be limited by cold and long winters [START_REF] Sáenz-Romero | Adaptative and plastic responses of Quercus petraea populations to climate across Europe[END_REF]. Vulnerability of a genotype to herbivores should be visible from increased damage, vulnerability to cold and long winters or hot and dry summers from a late bud burst, or from bud burst or growth that strongly responds to changes in ambient climate, as detailed below. Traits that may confer protection from herbivores, frost, heat or drought include leaves that are thick or tough, or rich in dry matter, in anthocyanins, flavonols, or tannins (Thomas et al. 2002;[START_REF] Cornelissen | Herbivory by leaf miners on Florida scrub oaks[END_REF][START_REF] Korn | Heterosis in the freezing tolerance, and sugar and flavonoid contents of crosses between Arabidopsis thaliana accessions of widely varying freezing tolerance[END_REF][START_REF] Nakabayashi | Enhancement of oxidative and drought tolerance in Arabidopsis by overaccumulation of antioxidant flavonoids[END_REF].

The provenance experiment

We profited from a common garden experiment created by the French National Institute for Agricultural Research (INRA) in 1990 [START_REF] Ducousso | Latitudinal and altitudinal variation of bud burst in western populations of sessile oak (Quercus petraea (Matt) Liebl)[END_REF][START_REF] Sinclair | Impacts of local adaptation of forest trees on associations with herbivorous insects: implications for adaptive forest management[END_REF] and described in Appendix S2. We used phylogenetic distances in Yguel et al. (2011, details in We note that phylogenetic distance to Q. petraea does not always equal to phylogenetic diversity of the forest. For instance, a forest composed of 90% of Q. petraea and 10% Fagus sylvatica has identical phylogenetic diversity but much lower phylogenetic distance to Q. petraea than a forest of the inverse composition. We also characterised provenances by annual minimum and maximum temperatures and summer hydric deficit (Appendix S2).We selected 25 provenances, maximizing the variation in phylogenetic distance, while minimizing the geographic distance, hence mostly choosing pairs of provenances with contrasting phylogenetic distance that were geographically close. Also, in the common garden, we sampled trees from different provenances in spatial proximity. Each provenance is a replicate along a gradient of phylogenetic distances of parental neighbourhoods and parental climate, and trees were averaged within provenances to avoid pseudoreplication.

Sampling

In the common garden we sampled leaves from two trees from each of 21 provenances, and one tree from each of the remaining 4 provenances. Sampling was done in October 2015. We harvested leaves from branches of intermediate height of about 7-9 m. From each tree, we stored 40 leaves in a freezer at minus 18°C, and dried 50 flat leaves at ambient room temperature.

Measurements of herbivory

We assessed herbivory, using frozen leaves out of which we randomly selected 15 to 30 (variation imposed by technical constraints). As in [START_REF] Giffard | Influcence of surrounding vegetation on insect herbivory: A matter of spatial scale and herbivore specialisation[END_REF], we discriminated three types of herbivory based on the feeding guild: (i) galls (ii) mines, i.e. galleries formed between the upper and the lower epidermis by insect larvae, and (iii) ectophagy, i.e. the partial or complete loss of leaf including epidermis. To quantify herbivory we first approximately quantified the surface of the leaf prior to damage by reconstructing the initial leaf shape before herbivory on a photocopy of the leaf.

A c c e p t e d m a n u s c r i p t

We traced the drawing on a grid of points of 1x1cm² [START_REF] Yguel | Phytophagy on phylogenetically isolated trees: why hosts should escape their relatives[END_REF]. Then, we laid the grid on the leaf to quantify the area lost through ectophagy or leaf mines. Throughout, "area" was the number of points covering a given damaged or undamaged part of the leaf. We also counted the number of galls and leaf mines. For each leaf we calculated (i) the density of galls per cm² (ii) the proportion of area damaged by leaf mines, and (iii) the proportion of area damaged by ectophagy (we note that relationships observed for proportion of mined surface were consistent with numbers of mines per surface and average size of mines -the mined proportion of leaf surface integrates mine abundance and mine growth, appendix S3).

Proxies of climatic resistance

Climate is widely considered as a major control of the budburst of trees [START_REF] Menzel | Trends in phenological phases in Europe between 1951 and 1996[END_REF][START_REF] Morin | Changes in leaf phenology of three European oak species in response to experimental climate change[END_REF]. Genotypes that are more resistant to cold winter temperatures burst buds earlier. Moreover, such resistant genotypes should also burst buds more independently of the ambient climate, resulting in low variation of budburst across the four common gardens. We thus used the budburst advancement, and coefficient of variation (CV) of budburst advancement across the four common gardens, as proxies of climatic-stress resistance. Budburst was recorded on a 0-5 ordinal scale where 0 is a dormant bud and 5 is a fully open bud (details in [START_REF] Sinclair | Impacts of local adaptation of forest trees on associations with herbivorous insects: implications for adaptive forest management[END_REF], similar approaches in [START_REF] Crawley | Individual variation in the phenology of oak trees and its consequences for herbivorous insects[END_REF]Tack et al. 2010). Budburst was surveyed already in 1995, but results were still applicable as relative budburst-rank of individual oak trees remains constant across years [START_REF] Koenig | Stabilizing selection for within-season flowering phenology confirms pollen limitation in a wind-pollinated tree[END_REF]. We calculated the CV of budburst for each provenance as the standard deviation of the budburst among the four common gardens divided by the mean. Climate is also considered to affect growth. Genotypes that are more resistant to climate grow independently of the ambient regional climate (Thomas et al. 2002). Growth was recorded as the height of trees after 10 years (starting from seeds) within each common garden in 2001, and we calculated the CV of growth across common gardens.

A c c e p t e d m a n u s c r i p t

Measurements of leaf traits

We measured leaf chemical traits in the field. We measured an index of anthocyanins, flavonols and nitrogen status with an optical sensor based on the absorbance proprieties contained in the epidermis (Dualex 4 Force A; [START_REF] Louis | Seasonal changes in optically assessed epidermal phenolic compounds and chlorophyll content in leaves of sessile oak (Quercus petraea): towards signatures of phenological stage[END_REF][START_REF] Cerovic | A new optical leaf-clip meter for simultaneous non-destructive assessment of leaf chlorophyll and epidermal flavonoids[END_REF]. These measures are nondestructive and much more rapid than quantifying the within-leaf concentrations, but nevertheless strongly correlated to within-leaf concentrations [START_REF] Goulas | Dualex: a new instrument for field measurements of epidermal ultraviolet absorbance by chlorophyll fluorescence[END_REF]). Moreover, anthocyanins and flavonols reflect well overall polyphenol concentrations under comparable conditions [START_REF] Scogings | Calibration of a hand-held instrument for measuring condensed tannin based of UV-and red-excited fluorescence[END_REF]). We measured three leaves per tree, between leaf veins on both leaf faces.

We measured leaf morphological traits in the laboratory. We assessed leaf thickness on four randomly selected leaves among the leaves studied for herbivory, i.e. using material that had been deep-frozen. We used a precision calliper (Thickness gauge glorythai, model number: BY01, Shantou, China). For each leaf, we measured the thickness at eight points between the main veins as recommended by [START_REF] Pérez-Harguindeguy | New handbook for standardised measurement of plant functional traits worldwide[END_REF]. We averaged values per leaf, per tree and per provenance.

To assess leaf toughness we randomly selected five leaves per tree. Because Pérez-Harguindeguy et al. ( 2013) discourage the use of frozen leaves we used dried leaves which we rehydrated by letting them soak for 24 hours in tap water. Once rehydrated, we used a durometer to measure the resistance to punching (ATG-50 Dial Tension Gauge Gram Force Meter Dual point 50 g, Wenzhou, China) at eight points per leaf between the main ribs. Again, we averaged values per leaf, tree, and provenance.

To asses leaf dry matter content (LDMC) we used the five rehydrated leaves per tree having served for toughness measurements. We weighed them together, dried to weight-constancy during 48 hours in an oven at a temperature of 65 ° C and then reweighted to obtain dry weight (Pérez-

Statistical analyses

Throughout our analyses, information on descendants in the common garden was averaged within provenances. For our analyses, except for the exploratory analyses, we did corrections for multiple comparisons using the method of the false discovery rate, following [START_REF] Benjamini | Controlling the false discovery rate: a pratical and powerful approach to multiple testing[END_REF], applied to each of the four groups of dependent variables (pressure by specialist herbivores, pressure by generalist enemies, morphological resistances, or chemical resistances).

Exploratory analyses

Soil types in provenances might influence phylogenetic distance of neighbourhoods, and select for different capacities of nitrogen acquisition. We therefore checked if the soil type of the provenances had an effect on leaf nitrogen status of the descendants or on the phylogenetic distance of the provenance neighbourhood. As there was no effect of soil type and as soil types were only known for 19 provenances we did not integrate soil type into our below models (Appendix S4).

Our measure of phylogenetic distance of the provenance neighbourhood is dependent on the abundance of different tree taxa in the provenances. We therefore checked with simple regressions the effect of abundances of individual taxa in the provenances on each variable of herbivory or herbivore resistances. We found that taxon abundances were always less significant than phylogenetic distance (Appendix S5). We hence used only phylogenetic distances in our models.

A c c e p t e d m a n u s c r i p t

Relationships between the phylogenetic distance of provenance neighbourhoods and the herbivory or resistances against herbivores of descendants from these provenances

We performed multiple regressions to study the effect of phylogenetic distance of neighbourhood on herbivory or traits related to herbivore resistances (leaf toughness, leaf thickness, LDMC, anthocyanins and flavonols). We took into account multiple co-variables that might relate to phylogenetic distance in the provenance or nutritional quality of the descendants for herbivores: annual minimum and maximum temperatures, and summer hydric deficit in the provenances, budburst and the leaf nitrogen status of the descendants [START_REF] Crawley | Individual variation in the phenology of oak trees and its consequences for herbivorous insects[END_REF][START_REF] Minkenberg | Effect of leaf nitrogen content of tomato plants on preference and performance of a leafmining fly[END_REF].

Relationships between resistance against herbivores and climatic-stress resistance

We performed multiple regressions to study the effect of herbivore resistance (low proportion of ectophagy, low gall density, low proportion of leaf mines, leaf toughness, leaf thickness, LDMC, anthocyanins and flavonols) on climatic-stress resistance (bud-burst advancement, CVs of bud-burst and growth). We used leaf nitrogen status as a co-variable to avoid bias due to differences of nutrient availability for descendants from different provenances, as suggested by [START_REF] Koricheva | Meta-analysis of sources of variation in fitness costs of plant antiherbivore defenses[END_REF].

Relationships between phylogenetic distance of provenance neighbourhoods and climatic-stress resistance or resistance-related traits

We performed multiple regressions to study the effect of phylogenetic neighbourhood on climaticstress resistance of descendants. We took into account the annual minimum and maximum temperature, summer hydric deficit in the provenances, and leaf nitrogen status of the descendants in the common garden as co-variables as explained before.

A c c e p t e d m a n u s c r i p t in the provenances, and the interaction between both, on traits potentially increasing climatic-stress resistance (anthocyanins, flavonols, leaf toughness, leaf thickness and LDMC), using the advancement of budburst and leaf nitrogen status as a co-variables as before. Again, we included all three climatic variables into the model, together with corresponding interaction term. In order to not overload the model we applied a selection of the variables using the R function "step()". This function uses a stepwise selection procedure, based on Akaike Information Criterion [START_REF] Burnham | Model selection and multimodel inference[END_REF]. A positive interaction means that descendants from climatically stressful provenances have higher levels of a resistance-trait if neighbourhoods in these provenances are phylogenetically distant. Finally, we explored the indirect effect of phylogenetic neighbourhood on climatic-stress resistance mediated by resistance traits, using techniques from pathway analyses. This indirect effect is a compound path composed of two direct paths. Direct paths are usually characterised by standardized regression coefficients but these coefficients are inflated in models with interaction terms due to inevitable multicollinearity [START_REF] Fletcher | QuantPsyc: Quantitative Psychology Tools. R package version 1[END_REF]). As t-values are not inflated [START_REF] Friedrich | In defense of multiplicative terms in multiple regression equations[END_REF] we used them to quantify for each direct path its explained variance Pearson R² (as in [START_REF] Rosenthal | Meta-analytic procedures for social research[END_REF], and the compound paths as the product of the R² of the two direct paths. We applied the same procedure for the indirect effects of the interactions between phylogenetic neighbourhood and provenance climate on climatic-stress resistance mediated by resistance traits.

We focused on explaining the climatic-stress resistance that was most strongly related to resistance traits, the coefficient of variation of budburst.

All statistical analyses were performed using R version 3.4.1. We verified assumptions of normality and variance homogeneity as follows. We identified residual outliers graphically checking for the normality of the residuals with the QQ plots and the weight of the residuals with the Cook's distance. A maximum of three outliers were excluded per analysis.

A c c e p t e d m a n u s c r i p t

Results

Descendants from phylogenetically proximate neighbourhoods had increased resistances against leaf miners Proportion of leaf-mines was highest in descendants from provenances with phylogenetically distant neighbourhoods but independent of climate. Attack by galls was independent of parental neighbourhood but highest in descendants from warm climates. Proportion of ectophagy was independent of parental environment (Tab. 1 and Fig. 2A). Leaves were softest in descendants from phylogenetically distant neighbourhoods and mildest temperatures (Tab. 1 and Fig. 2B).

Consistently, soft leaves had particularly high proportion of leaf mines (T=-2.146, p=0.0466, adjustedR²=0.20, df=17, same co-variables as in above models). Leaves tended to be thinnest and poorest in dry matter in descendants from mildest temperatures. Anthocyanins or flavonols did not depend on parental environment (Tab. 1). Note that the effect of phylogenetic distance on proportion of leaf-mines might be driven by the phylogenetic distance of the heterospecifics: this effect was maintained after including conspecific abundance into the model (which only had a weak effect; Appendix S6). In contrast, the effect of phylogenetic distance on leaf toughness might be driven by both heterospecific distance and conspecific abundance: taken into account together these variables showed roughly similar, non-significant, effects (Appendix S6).

Resistances against leaf miners did not relate to climatic-stress resistance

Descendants with advanced budburst within the studied common garden, or with constant budburst across common gardens, had low gall density (Tab. 2, Fig. S7A andB). No relationships were observed for climatic-stress resistance as inferred from among-common-garden CV of growth of descendants, or for physical or chemical resistances, or the proportion of leaf mines (Tab. 2).

A c c e p t e d m a n u s c r i p t

Descendants from phylogenetically proximate neighbourhood were no less resistant to climatic-stress than descendants from other neighbourhoods

The phylogenetic distance of the parental neighbourhood had no effect on the budburst advancement (T=0.598, p=0.557, adjusted R²=0.08, df=18), the CV of budburst (T=-0.178, p=0.861, adjusted R²=0.47, df=17) or the CV of growth (T=0.417, p=0.682, adjusted R²=-0.08, df=18), nor did it change the relationship between temperature extremes in provenances and proxies of climaticstress resistance (interaction terms in Appendix S8).

A phylogenetically proximate neighbourhood reinforces the selection by harsh climates on anthocyanins, flavonols and leaf thickness.

We observed significant interactions between phylogenetic distance of the parental neighbourhood and the parental climate on anthocyanins, flavonols and leaf thickness (Tab. 3). Specifically, stress due to high summer hydric deficit corresponded to an increase of anthocyanins concentration and leaf thickness of descendants from phylogenetically proximate but not distant neighbourhoods (Tab.

3, Fig. 3A andC). Stress due to low minimum annual temperatures corresponded to a strong increase of flavonols concentration and leaf thickness of descendants from phylogenetically proximate but not distant neighbourhoods (Tab. 3, Fig. 3B andD), albeit the effect on flavonols became marginally significant after correction for false discovery rate. Compound paths never exceeded R²=0.018 suggesting no mediation by resistance traits between provenance neighbourhoods and climatic-stress resistance of descendants. (Note that direct effects of provenance climate on climatic-stress resistance did exist, Appendix S8).

A c c e p t e d m a n u s c r i p t Discussion

Overall, we found that descendants from phylogenetically proximate neighbourhoods differ from descendants from phylogenetically distant neighbourhoods in multiple ways. We acknowledge that our study has a number of limitations. First, there were no gymnosperms in the provenances used for this study. [START_REF] Castagneyrol | Effects of plants phylogenetic diversity on herbivory depend on herbivore specialization[END_REF] show that specialist-herbivore abundance on angiosperms starts to decrease when the phylogenetic distance of the neighbourhood differs from zero, while generalist abundance remains constant until the phylogenetic neighbourhood includes gymnosperms. Our results are hence appropriate mainly for specialist herbivores. Secondly, we do not have information about the pressure of herbivores in the provenances. Explaining herbivore resistances of a genotype from a phylogenetically proximate neighbourhood by herbivore pressure remains an interpretation. Such interpretation is a plausible one given that herbivore pressure does reflect phylogenetic composition of a forest [START_REF] Brändle | Is the composition of phytophagous insects and parasitic fungi among trees predictable?[END_REF][START_REF] Nyman | Larval habits, host-plant associations, and speciation in nematine sawflies (Hymenoptera: Tenthredinidae)[END_REF][START_REF] Yguel | Phytophagy on phylogenetically isolated trees: why hosts should escape their relatives[END_REF]. Moreover, we inferred climatic-stress resistance from a limited number of proxies, i.e. budburst and growth and their coefficients of variation, proxies that certainly do not reflect all aspects of climatic-stress resistance. Nevertheless, budburst and growth are sensitive to factors limiting the distributional range of our study species, i.e. extreme winter and summer temperatures and drought [START_REF] Menzel | Trends in phenological phases in Europe between 1951 and 1996[END_REF][START_REF] Morin | Changes in leaf phenology of three European oak species in response to experimental climate change[END_REF]. Finally, a trade-off between resistance against climatic-stress and against herbivores might be masked by other trade-offs such as between resistance to climatic-stress and pathogens. However, in our study, visible fungal pathogens covered only less than one percent of the leaves. A trade-off between resistance against bacteria and against climatic-stress cannot be excluded but should hide a trade-off between herbivore resistances and climatic-stress resistance only if bacteria attack oaks mainly in a phylogenetically distant neighbourhood, which should be tested in future studies.

Coexistence with phylogenetically proximate neighbours selects for genotypes that are morphologically resistant against one type of specialist herbivore. We had hypothesized that plants A c c e p t e d m a n u s c r i p t from phylogenetically proximate neighbourhoods have evolved increased herbivore resistance because of the increased pressure of herbivores in such neighbourhood [START_REF] Yguel | Phytophagy on phylogenetically isolated trees: why hosts should escape their relatives[END_REF].

Consistent with the hypothesis we found that genotypes from such neighbourhoods are particularly resistant against leaf miners. [START_REF] Gaston | Intimacy and fidelity: internal and external feeding by British microlepidoptera[END_REF] show that leaf miners are mostly specialists, probably because they are internal feeders and hence have to adapt to the specific leaf morphology and chemistry of their host plant [START_REF] Cornell | Endophage-ectophage ratios and plant defense[END_REF]. A major resistance against several miner species are tough leaves: tough leaves prevent adult females from piercing the leaf epidermis to oviposit their egg inside the leaf, or they prevent larvae that hatch on the leaf surface from entering inside the leaf. [START_REF] Cornelissen | Herbivory by leaf miners on Florida scrub oaks[END_REF] indeed shows that tougher leaves exhibited lower density of leaf miners.

Consistently, we found that genotypes from phylogenetically proximate neighbourhoods have tougher leaves and that tough leaves are particularly little attacked by leaf miners. Equally consistently, we found that genotypes from phylogenetically proximate neighbourhoods are not particularly strongly resistant against ectophages, being usually less specialized due to their external feeding mode [START_REF] Gaston | Intimacy and fidelity: internal and external feeding by British microlepidoptera[END_REF]. Low specialization permits the use of relatively distantly related host plants across Angiosperms, and consistent with that, [START_REF] Grandez-Rios | The effect of host-plant phylogenetic isolation on species richness, composition and specialization of insect herbivores: A comparison between native and exotic hosts[END_REF] show that ectophages are not affected by the phylogenetic neighbourhood. Selection for plant defences against ectophages should hence not differ among phylogenetic neighbourhoods. Inconsistent with the hypothesis we found that genotypes from phylogenetically proximate neighbourhoods are not particularly resistant against another type of specialist enemies: galls (itself consistent with [START_REF] Yguel | Enemy release of insect herbivores on phylogenetically isolated trees: why phytophages should follow plants escaping their relatives?[END_REF] showing that gall abundance does not depend on host phylogenetic isolation). Possibly, any effect of parental neighbourhood is overridden by the observed effect of parental temperatures on gall resistance. Finally, inconsistent with the hypothesis we found that genotypes from phylogenetically proximate neighbourhoods are not particularly resistant in terms of chemical compounds. [START_REF] Neilson | Plant chemical defense: at what cost?[END_REF] have suggested that chemical compounds are multifunctional -in the absence of herbivores they might serve other purposes than herbivore resistance. Herbivory in a A c c e p t e d m a n u s c r i p t phylogenetically proximate neighbourhood hence might not increase selection for the chemical compounds.

Coexistence with phylogenetically proximate neighbours does not indirectly select against climaticstress resistance because resistances against specialist herbivores are not traded off against climaticstress resistance. We had hypothesized that if phylogenetically proximate neighbourhoods select for higher herbivore resistances they might indirectly select against capacities that are traded off against herbivore resistances such as climatic-stress resistance. The first part of this hypothesis, on selection of herbivore resistances, is equal to hypothesis 1 and has been treated before. We will here discuss the second and third part, i.e. a trade-off between resistances against herbivores and climatic-stress, and an indirect selection against climatic-stress resistance by phylogenetically proximate neighbourhoods. Consistent with the trade-off part of the hypothesis we found a tendency of delayed budburst in trees that are more resistant against ectophages, albeit other proxies of climate resistance did not respond. Delayed budburst represents an opportunity cost by delaying photosynthesis [START_REF] Koricheva | Meta-analysis of sources of variation in fitness costs of plant antiherbivore defenses[END_REF]. However, this trade-off might not lead to an indirect selection against climatic-stress resistance in a phylogenetically proximate neighbourhood as such neighbourhood did not select for increased resistance against ectophages. Inconsistent with the trade-off part of the hypothesis we found no negative relationships between resistances against leaf miners, including leaf toughness, and climatic-stress resistance. There might be no trade-off because resistance to leaf miners and to climatic-stress occur at different moments: Leaf toughness -a resistance against leaf miners -develops in a climatically favourable period for oaks in spring and in early summer. In contrast, climatic-stress limiting budburst operates in late winter. Oaks might therefore invest into the resistance against leaf miners in spring and summer and later on invest in climatic-stress resistance, without any direct trade-off among them. In addition, inconsistent with the trade-off part of the hypothesis we found no trade-off between chemical compounds and climatic-stress resistance. [START_REF] Neilson | Plant chemical defense: at what cost?[END_REF] have suggested that the multifunctionality of chemical resistances such as anthocyanins can offset the cost of plant chemical resistance. Also, A c c e p t e d m a n u s c r i p t opposite to the trade-off part of the hypothesis, we found a positive relationship between resistances against galls and against climatic-stress in terms of early budburst. [START_REF] Crawley | Individual variation in the phenology of oak trees and its consequences for herbivorous insects[END_REF] have shown that some gall species prefer oaks that burst buds late, possibly because such oaks are more favourable for adult female gall wasps. Finally, we found no evidence in favour of the third part of the hypothesis, i.e. an indirect selection against climatic-stress resistance in phylogenetically proximate neighbourhoods. This is consistent with the absence of trade-offs between resistances against miners and against climatic-stress, and with the absence of selection for resistance against ectophages in such neighbourhoods.

Coexistence in phylogenetically proximate neighbours can reinforce the selection by climate for biochemical compounds and one morphological trait, possibly reflecting increased pressure from herbivores. We had hypothesized that in phylogenetically proximate neighbourhoods, the increased herbivore pressure can reinforce or prevent the selection pressure by climatic-stress on particular traits conferring multiple resistances. As mentioned above, we found no supporting results for the "prevent" version of the hypothesis. Consistent with the "reinforce" version of the hypothesis we found that genotypes from cold-winter provenances have high levels of flavonols and thick leaves (known to increase frost resistance, [START_REF] Korn | Heterosis in the freezing tolerance, and sugar and flavonoid contents of crosses between Arabidopsis thaliana accessions of widely varying freezing tolerance[END_REF][START_REF] González-Zurdo | Costs of leaf reinforcement in response to winter cold in evergreen species[END_REF]) -provided that the neighbourhood in the provenances was phylogenetically proximate. We found that genotypes from dry summer provenances had high levels of anthocyanins and thick leaves (known to increase water stress resistance, Chalker-Scott 1999; [START_REF] Ennajeh | Comparative impacts of water stress on the leaf anatomy of a drought-resistant and a drought-sensitive olive cultivar[END_REF]) -provided that the neighbourhood in the provenances was phylogenetically proximate. White (1984) suggests that climatic-stress increases the availability of nitrogen in leaves of stressed plants, which will increase herbivory and reinforce their selection pressure on plants. Resistance traits against cold stress and drought stress should hence be particularly important in plants exposed to high enemy pressure in a phylogenetically proximate neighbourhood.

A c c e p t e d m a n u s c r i p t

Our results may have implications for understanding coexistence among phylogenetically proximate individuals [START_REF] Prinzing | Benefits From Living Together? Clades Whose Species Use Similar Habitats May Persist as a Result of Eco-Evolutionary Feedbacks[END_REF][START_REF] Gerhold | The deep past controls the phylogenetic structure of present, local communities[END_REF]. It has been suggested that coexistence of phylogenetically proximate individuals is prevented by increased herbivore pressure and competition, leading to coexistence among phylogenetically distant species [START_REF] Janzen | Herbivores and the number of tree species in tropical forests[END_REF]Webb et al. 2002;[START_REF] Liu | Experimental evidence for a phylogenetic Janzen-Connell effect in a subtropical forest[END_REF]. Our study shows that another response to coexistence among phylogenetically proximate individuals might be an adaptation to increased herbivore pressure. This adaptation to neighbourhoods seems to be no less important than adaptation to climates (Tab. 1), and seems to come without costs, at least in terms of climatic tolerance. We might hence hypothesize that adaptation to phylogenetically proximate neighbours facilitates their coexistence. Table 1. Effect of phylogenetic distance of parental neighbourhood and of climate (annual minimum and maximum temperatures, summer hydric deficit) in provenances on herbivory and herbivore resistances of oak descendants in the common garden. Linear regressions with co-variables (advancement of budburst and leaf nitrogen status of the descendants in the common garden). LDMC= leaf dry matter content. Significant values are in bold (an asterisk indicates the p value that stay significant after correction using the false discovery rate). "Proportion" refers to the proportion of the entire leaf surface affected by a type of herbivory. Data points are means across descendants within provenances. focal tree (broadleaf tree). Hypothesis 1 states that such neighbourhood selects for increased investment into resistance against specialist herbivores (thick arrows towards caterpillars).

Hypotheses 2 states that traits conferring resistance to herbivores are distinct (red arrows) from those conferring resistance to climate (blue arrows), resulting in a trade-off between both (arrow size) and an indirect selection against resistance to climatic-stress in a conspecific or phylogenetically proximate neighbourhood (bottom graph). Hypothesis 3 suggest that traits are multifunctional and confer resistance against both, herbivory and climatic-stress (yellow arrows). In the illustrated case, resistance to climatic-stress is less costly in a conspecific or phylogenetically proximate neighbourhood as here the resistance trait also serves to resist herbivore pressure, facilitating selection by climatic-stress for this multifunctional resistance trait (bottom graph).

  Appendix S2) multiplied by the relative abundance of each trees species in each provenance (equivalent to abundance weighting in phylogenetic diversity measures) resulting in a gradient from zero to 48 million years.

  A c c e p t e d m a n u s c r i p t five leaves. Then we averaged the LDMC across trees within provenances.

  Future studies should try to identify the importance of multifunctionality of chemical compounds possibly enabling plants to be jacks-of-all-trades and to coexist among phylogenetically proximate individuals. Our results also imply that while the response to coexisting close relatives has no costs for climatic-stress resistance, it might change the evolutionary response of one trait to climate.Future studies should identify what exactly causes this change, e.g. whether rather the action of enemies or of mutualists changes the selection pressure by climate.

Figure 1 .

 1 Figure legends Figure 1. Our hypotheses. A conspecific or phylogenetically proximate neighbourhood (broadleaf

Figure 2 .

 2 Figure 2. Effect of phylogenetic distance of parental neighbourhood in provenances on (A) the

Figure 3 .

 3 Figure 3. Interaction between the phylogenetic distance of the parental neighbourhood and the

  Figure 2

  Figure 3

Table 2 .

 2 Effect of herbivory or herbivore resistances of the descendants on their climatic-stress resistance. Climatic-stress resistance is represented by advancement of budburst of descendants in the Petite Charnie common garden, coefficient of variation (CV) of budburst advancement and CV of growth across four commons gardens. Multiple linear regression analyses accounting for leaf nitrogen status of the descendants in the common garden. LDMC= leaf dry matter content. Significant values are in bold (an asterisk indicates the p value that stay significant after correction using the false discovery rate). "Proportion" refers to the proportion of the entire leaf surface affected by a type of herbivory. Data points are means across descendants within provenances.

	Phylogenetic distance of parental neighbourhood	Tmin	Tmax	Summer hydric deficit

Table 3 .

 3 Effect of phylogenetic distance of parental neighbourhood, the parental climate (summer hydric deficit, annual minimum and maximum temperature), and the interaction between them on traits of the descendants conferring resistance against climatic-stress, accounting for the advancement of budburst and leaf nitrogen status of the descendants in the common garden. Multiple linear regression analyses across data points that are means across descendants within provenances. The variables of the models have been selected by multiple-step AIC procedure. Significant values are in bold (an asterisk indicates the p values that stay significant after correction using false discovery rate with α=0.05 and a cross for α=0.1).

	Phylo dist	Summer hydric deficit	Summer hydric deficit:phylo dist	Tmax	Tmax:phylo dist	Tmin	Tmin:phylo dist

Acknowledgements:

We thank Julie Jaquiéry, Jean-Pierre Caudal and Fouad Nassur for their help in sampling. We thank the PlantaComp project and in particular Antoine Kremer. We thank Julie Jacquiéry for extensive discussion and improving the manuscript. We thank the two anonymous referees for improving the

data supporting the results are archived in HAL https://hal.archives-ouvertes.fr/hal-02062599.

manuscript and their comments on this manuscript. This work was support by an Estonian Research Council (grant PUT1006). MP and PG thank the Estonian Government for continuously keeping up our hopes about raising research funding to 1% of GDP.


est destinée au dépôt

ZnO nanowires-on-quartz for efficient water purification:

The issue of Volatile organic compounds (VOCs) degradation using solar energy

Lan Gao, Martine Gnambodoe-Capochichi, E. Nefzaoui, Frederic Marty, Tarik

ZnO nanowires-on-quartz for efficient water purification

The issue of volatile organic compounds (VOCs) degradation using solar energy

Conclusion

The photocatalysis is proved to be the most efficient way for the degradation process of organic pollutants. ZnO and TiO 2 are supposed to be the most common photocatalysts due to their high performance in degradation by producing the oxidative free radical after being illuminated by UV light. Taking the advantages of these chemical properties, the environmental applications were developed by many research groups using micro-nano technologies. Furthermore, ZnO has biocompatibility advantage, and easy to obtain the high aspect ratio nanowires (NWs) via low-cost synthesis method with the further advantage of being firmly anchored to the substrate, leading to more sustainable applications.

Introduction Photocatalysis principle

Diagram of photocatalysis principle

Degradation of toluene

Using UV-Vis spectrum approach, the degradation effect can be obviously observed according to absorbance from analyses results. Due to the chemical property of toluene, 3 controlled experiments were conducted to compare as a blank reference to indicate the impact of UV light and the surrounding atmosphere.

Diagram of experiment setup.

• A homogeneous ZnO NWs has been successfully grown on the quartz surface via SEM observation, with a band gap of ~ 3.15 eV.

• The best performance of toluene degradation in water can be observed under UV light with ZnO NWs. The blank comparison experiments offset the volatile effect, which illustrates a further verification of ZnO NWs degradation effect with UV light.

The polluted water sample was prepared with toluene (volatile organic compounds) with the concertation of 530 ppm. The macro water film flow was controlled with a given flow rate, which sited above the ZnO NWs on the quartz surface. Contact Email : lan.gao@esiee.fr

Characterization of ZnO NWs

  Bourouina, Yamin Leprince-WangTo cite this version:Lan Gao, Martine Gnambodoe-Capochichi, E. Nefzaoui, Frederic Marty, Tarik Bourouina, et al.. ZnO nanowires-on-quartz for efficient water purification: The issue of Volatile organic compounds (VOCs) degradation using solar energy. The 9th International Multidisciplinary Conference on Optofluidics (IMCO2019), Jun 2019, Hong Kong, China. hal-02183395

  (a) Quartz substrate & sample photos. (b) (c) (d) SEM pictures of ZnO NWs indicating homogeneous growth. (e) ZnO NWs band gap measurement. pass, the absorption spectrum of the treated water sample showed that the best degradation effect of toluene in water was with UV light and ZnO NWs; while the UV light also has a significant effect on toluene degradation. Degradation effect of toluene in different conditions. Absorption spectrum of treated water sample after two-pass.

( 1 )

 1 Seedlayer deposition (At room temperature via spin-coating) 𝑃𝑉𝐴 + Zn(Ac) 2 200𝜇𝐿 /𝑐𝑚 2 (2) ZnO nanowires growth (At 90 ℃ for 2 hours) 25𝑚𝑀 𝑍𝑛(𝑁𝑂 3 ) 2 + 12.5 𝑚𝑀 𝐻𝑀𝑇𝐴 Two steps hydrothermal synthesis diagram Elyes NEFZAOUI 1 , Martine GNAMBODOE-CAPOCHICHI 2 , Yamin LEPRINCE-WANG 2 , Tarik BOUROUINA 1 1 Université Paris-Est, ESYCOM CNRS FRE2028, ESIEE PARIS-93162, Noisy le Grand, France 2 Université Paris-Est, ESYCOM CNRS FRE2028, UPEM-77420, Champs sur Marne, France