Cédric Eichler

Thierry Monteil

Patricia Stolf

Modelling Constrained Dynamic Software Architecture with Attributed Graph Rewriting Systems

Keywords: Dynamic software architectures, Graph rewriting systems, Constrained and attributed rewriting systems

Dynamic software architectures are studied for handling adaptation in distributed systems, coping with new requirements, new environments, and failures. Graph rewriting systems have shown their appropriateness to model such architectures, particularly while considering the consistency of theirs reconfigurations. They provide generic formal means to specify structural properties, but imply a poor description of specific issues like behavioural properties. This paper lifts this limitation by proposing a formal approach for integrating the consideration of constraints, non-trivial attributes, and their propagation within the framework of graph rewriting systems.

Introduction

Dynamic software architectures are studied for handling adaptation in autonomic distributed systems, coping with new requirements, new environments, and failures. The description of evolving architectures cannot be limited to the specification of a unique static topology but must cover the scope of all the correct configurations. This scope characterize an architectural style, qualifying what is correct and what is not. Naturally, once this distinction made, the question of the specification of the modifications themselves arises, alongside with theirs properties with regard to consistency preservation. These concerns motivate the need for suitable description languages and formalisms avoiding ambiguities for correct architectural design, management and analysis.

Several approaches have been proposed in the past adopting a language-based view of this problem. Many architecture description languages (ADLs) were introduced providing rigorous syntax and semantic to define architectural entities and relations [START_REF] Oquendo | π-method: a model-driven formal method for architecture-centric software engineering[END_REF][START_REF] Luckham | Specification and analysis of system architecture using rapide[END_REF][START_REF] Allen | A formal basis for architectural connection[END_REF][START_REF] Garlan | Acme: Architectural description of componentbased systems[END_REF][START_REF] Magee | Dynamic structure in software architectures[END_REF]. Such languages are adequate to describe the structural and behavioural properties and constraints of a system. However, ADLs suffer from several insufficiencies for modelling and analysing dynamic software architecture [START_REF] Kacem | Evaluation and comparison of adl based approaches for the description of dynamic of software architectures[END_REF]. The majority of ADLs are concentrated on the structural description of architecture whereas their dynamic aspects are not well supported. Darwin [START_REF] Magee | Dynamic structure in software architectures[END_REF] only allows component replication whereas ACME [START_REF] Garlan | Acme: Architectural description of componentbased systems[END_REF] only allows optional components and connections. Dynamic-Wright [START_REF] Allen | Specifying and analyzing dynamic software architectures[END_REF] describes dynamic architecture in Wright [START_REF] Allen | A formal basis for architectural connection[END_REF], limiting itself to predefined dynamics, meaning that the system should have a finite number of configurations and reconfiguration policies known in advance.

Model-based approaches, proposing general-purpose modelling languages, allows to handle dynamism and particularly the definition of reconfiguration rules managing the evolution of an application in run-time. They provide very intuitive and visual formal or semi-formal description of structural properties [START_REF] Bradbury | A survey of selfmanagement in dynamic software architecture specifications[END_REF]. For example, designing and describing software models using UML [START_REF]OMG: Unified Modeling Language Specification 2[END_REF] is a common practice in the software industry, providing a standardized definition of system structure and terminology, as well as facilitating a more consistent and broader understanding of the architecture [START_REF] Selonen | Validating uml models against architectural profiles[END_REF]. Nevertheless the generic fitness of model-based approaches implies poor means of describing specific issues like behavioural properties. Therefore they are often coupled with description using ADLs [START_REF] Roh | Architecture modeling language based on uml2.0[END_REF][START_REF] Medvidovic | Modeling software architectures in the unified modeling language[END_REF][START_REF] Broto | Autonomic management policy specification in tune[END_REF], mapping the concepts of ADLs into the visual notation of UML, or other formalisms [START_REF] Loulou | Towards a unified graph-based framework for dynamic component-based architectures description in z[END_REF][START_REF] Kandé | Towards a uml profile for software architecture descriptions[END_REF]. In spite of its wide acceptance, UML-based descriptions appears to lack expressiveness and formal tools for guaranteeing consistency. In fact, consistency checking in run-time may lead to combinatorial explosions. To tackle efficiently consistency preservation in the scope of dynamic reconfiguration, correct by design formal approaches have emerged. Based on formal proofs and reasoning in design-time, they guarantee the correctness of a dynamic application, requiring little or no verifications in run-time.

Graph-based methods for software modelling are appropriate for conceiving correct by design frameworks, as theoretical work on this field provides formal means to specify and check structural constraints and properties [START_REF]Handbook of Graph Grammars and Computing by Graph Transformations[END_REF][START_REF] Ehrig | Graph Grammars and Their Application to Computer Science: 4th International Workshop[END_REF]. Within this kind of approaches, some methods are restricted to the use of type graphs alone [START_REF] Wermelinger | A graph transformation approach to software architecture reconfiguration[END_REF] and suffer from the same lack of expressiveness as UML-based methods. Other works [START_REF] Hirsch | Modeling Software Architectures and Styles with Graph Grammars and Constraint Solving[END_REF][START_REF] Métayer | Describing software architecture styles using graph grammars[END_REF] are based on graph grammar, or graph rewriting system, techniques. Graph grammars are appropriate for formal modelling dynamic structures and software architectures, and are used to specify architectural style where a graph represents a configuration. Graph rewriting rules have two distinct values. They intervene in both the characterisation of an architectural style as part of a rewriting system and in the specification of consistency preserving reconfiguration rules [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF]. The very first thing to consider is the definition of attributes for which two approaches prevail. The most simple one is to assign to each elements, vertices and edges, of a graph a list of couples representing constant or variable attributes along with theirs domains of definition [START_REF] Chassot | Towards autonomous management of qos through model-driven adaptability in communication-centric systems[END_REF]. The main drawback is that it does not allow to conduct any operation on said attributes or to fully propagate them. The second one is to define domains of definitions and operators in the form of a many sorted algebraic signature [START_REF] Ehrig | Fundamentals of algebraic specification[END_REF] SIG and to integrate attributes as vertices of the graph, elements of a SIG-algebra [START_REF] Berthold | Attributed graph transformation with partial attribution[END_REF][START_REF] Ehrig | Fundamental theory for typed attributed graphs and graph transformation based on adhesive hlr categories[END_REF]. A direct implication is a natural manipulation of attributes using operators and their addition or deletion as regular vertices of the graph. This modularity does not come without drawbacks. Graph rewriting rules relies on finding graph homomorphisms, a NP-complete problem. As a consequence, increasing the size of the input graphs seems inefficient, as well as multiplying the application of graph rewriting rules to modify attributes whenever a domino effect is implied.

The motivation of this paper comes from two simple statements. First, classical grammar theory allows complex propagation of attributes and the specification of elaborated semantic predicates on production rules. Propagation of attributes in graph grammars is very limited and often restricted to inheritance [START_REF] Chassot | Towards autonomous management of qos through model-driven adaptability in communication-centric systems[END_REF], restraining the means to model the impact of an event, such as a reconfiguration, on the attributes of an application. Semantic predicate are mostly present in the form of implicit system of simple equalities between attributes [START_REF] Chassot | Towards autonomous management of qos through model-driven adaptability in communication-centric systems[END_REF][START_REF] Berthold | Attributed graph transformation with partial attribution[END_REF][START_REF] Ehrig | Fundamental theory for typed attributed graphs and graph transformation based on adhesive hlr categories[END_REF]. Secondly, these approaches focused on attributes and structural transformation, but disregard the appropriateness of a configuration. Yet constraints linked to such consideration are closely related to the architecture and its components. As a consequence, we wish, while constructing, deploying, or reconfiguring a configuration, to construct a set of constraints easy to evaluate. These lasts model some basic, more or less important, requirements of the application. As a result, their violation could be detected and automatically handled by a manager without requiring complex decision and without analysing the actual performances of the whole application.

A motivating example further enlightening the problems tackled by this article is presented in the next section. Section 3 introduces our formal model overcoming said obstacles. The characterisation of the motivating example is presented in Section 4, before discussing optimisation and evaluation issues. Finally, Section 5 is dedicated to conclusion and perspectives.

2 Problem Statement throughout a Motivating Example.

Motivating Example

In order to illustrate the issues addressed in this article, we introduce DIET 4 [6], a hierarchical load balancer for dispatching computational jobs over a distributed infrastructure, like a grid or a cloud. Its architecture consists of a set of agents: some Master Agents (MA) manage pools of computational SErver Deamons (SED) through none, one or several layers of Layer Agents (LA). These servers can achieve specialized computational services. Communications between agents are driven by the omniORB system (OMNI). MAs listen to client requests and dispatch them through the architecture to the best SED that can carry out the required service. We stated previously that UML-based modelling suffers from a lake of expressiveness. This application has been described using class diagrams [START_REF] Sharrock | Non-intrusive autonomic approach with self-management policies applied to legacy infrastructures for performance improvements[END_REF], but the fact that a LA can manage another LA could not be taken into consideration. It will be shown later that graph grammars do not exhibit such limitations.

A simplified architecture with a single MA and a single OMNI will be considered here. The main characteristics of the application are as follow :

1. While being deployed, each component record itself to the OMNI. 2. Each LA and each SED has a hierarchical superior. 3. The MA and each LA manage at least one LA or one SED and at maximum ten of them -these conditions could be trivially extended to any number of minimum and maximum managed entities, as seen later in this paper.

All instances of an architectural style are NOT created equals. At a given time, even though a configuration meet all the requirements of the application, another configuration may meet them in a "better way". In particular, we considered the following criteria : the energy consumption, the robustness, the fault-tolerance w.r.t. the breakdown of machine or a software component, and the quality of service. A very restricted view will be adopted here, with simple -simplistic, even -models as they still put the addressed problem under the spotlight. Assume that the energy consumption depends only on the number of used machines and of the software components deployed on them. Robustness is a little bit trickier. The first intuition is to exploit redundancy by deploying SEDs not having a disjoint set of carried out services. However, if every SED offering a particular service are deployed on the same machine, the application is still vulnerable to a machine breakdown. In a similar fashion, SEDs offering very close sets of services should not be managed by the same LA or LAs deployed on the same machine. A single aspect of quality of service is studied : the balance of the managed entities over the set of LAs sharing the same depth, i.e. the number of intermediate LAs between a LA and the MA. Let LA(d) be the set of LA of depth d, and M(c) be the number of entities managed by the component c. An entity can be deployed and directly managed by a LA ∈ LA(d) if it does not make the standard deviation of la∈LA(d) M(la) become greater than an arbitrary value. An interesting point here is that robustness and energy consumption are concurrent, in the sense that deploying more software components or using more machines will, while ameliorating the first, impact badly on the second.

To value these three conditions, it is crucial to keep track of some attributes of the software components :

1. the machine on which each entity is deployed, 2. the number of entities managed by each LA and the MA, 3. the depth of each LA, 4. the set of services carried out by each SED or by at least a SED managed directly or indirectly by each LA.

By misuse of language the set of services carried out by at least a SED managed directly or indirectly by an LA will sometimes be referred to as the set of services carried out by the LA.

Problem Statement

How is modelling such an architecture an issue? This seemingly simple problem still raises some interesting points underlining limitations of classical attributed graph grammars.

-Interdependency of attributes; the attributes of an entity depends on attributes of other entities. In classical attributed grammars, attributes are classified according to the fact that those other entities are parents or siblings of the first one , it is then said to be inherited, or not, in the case of a synthesized attribute. Similarly, those dependencies have to be handled in a very different way whether they rely on existing attributes or attributes of entities that has yet to be deployed. The first scenario, including the evaluation of the depth of an LA, which depends on the depth of the entity managing it, have been addressed with attributes inheritance in graph grammars. On the other hand, evaluating the set of services offered by at least a SED managed directly or indirectly by an LA can not be treated in the same fashion. -Modification of an existing attribute; the option of considering attributes as nodes has been discarded due to its high implementation complexity. Consequently, graph rewriting rules cannot be used to modify attributes, and their modification are therefore not possible within the framework of classical graph grammars. -Conditional deployment ; whenever trying to deploy a LA or a SED, we should verify that it does not violate the maximal cardinality condition and the balancing condition. The first one could be handled in a structural, syntactic way using negative application conditions, implying other search for homomorphisms and thus a high computational complexity. The balancing condition, however, is too complex to be reasonably managed using pattern matching. -Evaluating a configuration; we have seen that the constraints reflecting the appropriateness of a configuration are intimately related to attributes of the graph and do not weight on the same levels or components. Particularly, components of the same nature have close requirements that arise or evolve as components are deployed or as the context evolve, so that integrating such constraints in the model as any attributes is relevant. In addition, the entity managing the evolution of the architecture could then react quickly to their violation, without requiring much reasoning.

These four points put under the spotlight the limits of the formalism presented in [START_REF] Rodriguez | A rule driven approach for architectural self adaptation in collaborative activities using graph grammars[END_REF] and the need for its expansion described in this paper.

Introducing Constraints and Mutators within Graph

Rewriting Systems

Attributes, Constraints and Attributes Rewriting

Before introducing graph rewriting systems and how they may be used to model a dynamic software architecture, a certain number of concepts have to be defined. First of all, let us consider what an attribute shall be. We adopt an hybrid formalism conserving the simplicity and the computational efficiency of "listing" attributes as labels while granting the possibility of applying any operator.

Informally, an attribute is represented as a constant, a variable or the result of any function on other attributes, as long as the signature of the function is respected, coupled with its domain of definition. The expression of the function may includes quantifiers. We assume the canonic notation where Y X is the set of function from X to Y. An attributed structure is a couple composed of the structure and a set of indexed attributes or sequence of attributes. The first member of an attribute will be noted within quotation marks if and only if it is constant. The fact that the first member of an attribute is constant does not implies that it can not change any further, but rather that at a given time the attribute is equals to a member of its domain of definition.

Remark 1. In the approach presented here the attributes can be a regular combination of any other attributes, not necessary the attributes of the same structure. For example, considering an attributed structure (A, ATT A ) of attributed structures (B i , ATT Bi ) of attributed elements

(C i j , ATT C i j ). Let ATT = AT T A ∪ i AT T Bi ∪ (i,j) AT T C i j . ∀ Att ∈ ATT, ∀N ∈ N, ∀ (Att k ) k∈[|1,N |] ∈ AT T N , Att can be a regular combination of (Att k ) k∈[|1,N |]
. From now on, we adopt the definition Remark 2. Note that this notation is related to the approach considering manysorted signatures and algebras as elements are attributed over an implicit SIGalgebra. Informally, the sorts of SIG are every defined domains of definition and its operations are every functions from any combination of sorts to any sort. For any attributed structure (str, ATT str ), let ATT be the set of attributes resulting of the union of any attribute defined in the framework of str, which is not empty as at least ATT str ⊆ ATT. Let S = { s |∃ Att, (Att, s) ∈ ATT} and

OP = { f | ∃N ∈ N, ∃(Att i ) i∈[|0,N |] , f ∈ Att Att1×Att2ו••×AttN 0 }. str is attributed over a (S,OP)-algebra.
Attributes are entirely aimed at providing informations on an algebraic structure. It is very natural to desire to exploit these bits of information by expressing any property over a structure or its attributes. Those having been defined in a very generic way, constraints can be seen as a specific kind of attributes taking values in a ternary predicate logic system. Definition 2. (Constraint) A constraint Cons = (C, D) is an attribute (C, D) and D = {"true", "false", "unknown"}.

To simplify the notation, considering that constraints share the same domain of definition, a constraint Cons = (C, D) may be referred to as C, and the domain of definition be implicit. In the following we adopt the principles of Kleene's strong logic [START_REF] Kleene | On notation for ordinal number[END_REF] [19], in particular its basic logic operations (∨, ∧, ¬, =⇒ ) and the fact that the only truth value is "true". The uniqueness of this truth value means that evaluations are pessimistic, i.e. "unknown" is supposed to be false. Remark 3. A constraint, as a regular combination of attributes, can be seen as a classical expression of a predicate ternary logic. Considering a ternary logic rather than a binary one implies that unlike attributes, constraints can be evaluated, i.e. associated with a constant, at any time. The idea here is to associate any minimal logic expression that can not be evaluated, due for example to an attribute implied in its expression being un-evaluable or variable, with "unknown".

Example 1. Let S be any mathematical structure along with the set of attributes ATT = {Att 1 , Att 2 , Att 3 } = {(A 1 , Mach), (A 2 , Mach), (A 3 , {"true", "false", "unknown"})} where A 1 = m, A 2 = " m", and A 3 = "true" and the set of

constraints CONS = {C 1 , C 2 } = { (A 1 = A 2 ), (C 1 ∨ A 3 ) }.
Even though Att 1 can not be evaluated to a constant, C 1 can be evaluated to "unknown". C 2 is then equals to "unknown" ∨ "true", which is "true".

In order to lighten the notation, an attributed system with constraints, i.e. a triple composed by the system, a set of indexed attributes or sequence of attributes, and a set of indexed constraints or sequence of constraints, is noted an AC-system. Whenever defining an AC-system with AC-elements, rather than separating each sets of attributes (resp. constraints), a single family of sequence of attributes indexed by the sets of attributed elements is considered.

One of the issues evoked in section 2 is the fact that attributes are prone to evolve. A reconfiguration may thus impact the attribute of the system. Classical string rewriting theory [START_REF] Parr | Ll(*): the foundation of the antlr parser generator[END_REF] tackles this issue by using mutators. A similar approach is adopted here. Definition 3. (A mutator on an AC-system) A mutator on an AC-system is an arbitrary algorithm updating the value(s) of none, one or some attributes of the AC-system.

According to this definition, the scope of mutators remains limited to the modification of values. They can not be used neither to add or suppress an attribute nor to modify the domain of definition of an attribute.

Attributed Constrained Graph Modelling a Configuration

Tools to manipulate and analyse attributes having been introduced, the structures of interest can be presented. An AC-graph, modelling a software snapshot or configuration at a given time, consists in an AC-couple of two AC-sets of vertices and edges where an edge is a couple of vertices (source, destination). Following the commonly used conventions for standard graphical descriptions, one considers that vertices represent services or architectural components and edges correspond to their related interdependencies. Note that vertices, edges and the graph itself are AC-structures. According to remark 1, elements are attributed over the same algebra, i.e. an attribute or a constraint of the graph, a vertex or an edge may consist in any regular combination of attributes of the graph, any vertex and any edge. For any set S, the cardinality of S is represented as |S|.

Definition 4. (AC-graph) An AC-graph is defined by the system G = (V, E, ATT, CONS) where -V and E ⊆ V 2 correspond respectively to the set of vertices and edges of the graph, -ATT (resp. CONS) is a family of sets ATT el (resp. CONS el ), indexed by a subset of V ∪ E ∪ {G}. ATT el is a set of attributes (resp. constraints) of arbitrary length and containing the sequence of attributes

(ATT i el = (A i el , D i el )) i∈[|1,|AT T el || (resp. (CONS i el = (C i el , D i el ) ) i∈[|1,|CON S el || ) of the element el.
ATT and CONS are indexed by a subset of V ∪ E ∪ {G}, so as not to impose an empty set of attributes or constraint if an element is wished not to be attributed or constrained. Consequently, 0 ≤ |ATT| ≤ |V|+ |E| +1 and 0 ≤ |CONS| ≤ |V|+ |E| +1. Now that AC-graphs are defined, it is possible to represent a configuration of DIET as presented in section 2. The notations used in Fig. 1 are as follow; Mach is the set of available machines, on which a software component may be deployed, Nat the set of possible nature of a software component, {"OMNI", "MA", "LA", "SED"} in the case of a DIET architecture, Link the set of possible relationships {"ma2la", "ma2sed", "la2sed", "registered"}, and Serv the power set of S, the set of services that could be carried out by a SED. At this time, the software architecture is composed by eight components symbolized by eight vertices and theirs corresponding relations modelled by some edges both with theirs attributes. A notable fact is that components of the same nature have the same number of attributes, theirs attributes being the one identified in Sect. 2. This stem from the definition of the rewriting system that will be presented later in this paper. Attributes have similar meanings, be it the number of managed entities, the depth of a LA... In addition, some components as well as the graph itself are constrained to reflect the concerns stated in the same section. Graphically, a dot line between a constraint and a vertex illustrates the target of said constraint. The MA should manage strictly less than eleven entities, underlining a fundamental property of the architectural style. Even though the maximum number of entities managed by the LAs could be expressed in the same way, an other technique will be used and presented later. To cope with robustness, it is specified that a LA should not be deployed on the same machine as a component managed by the same entity as itself or that they should have disjoint set of carried services. The graph is constraints by two clauses Loc and Red, described in Appendix A, taking into account the needs for redundancy and multiple localisations over the offered services. This is how a DIET configuration should look like. From now on, our aim is to introduce the notions allowing to characterize the corresponding architectural style, ensuring in particular that attributes are correctly updated and that components have the required constraints.

Graph Rewriting Rules and Systems

As stated in the introduction, an architectural style can be formalised using a graph rewriting system. The production rules of such systems require to identify sub-structures by the means of homomorphisms. An unattributed graph homomorphism between two graphs is defined as an homomorphism from the set of vertices of the first one to the set of vertices of the second graph so that if there is an edge between two vertices of the first one there is an edge between their image in the second one. Based on [START_REF] Rodriguez | A rule driven approach for architectural self adaptation in collaborative activities using graph grammars[END_REF], we define an attributed graph homomorphism as follow.

Definition 5. (AC-graph homomorphism) Two AC-graphs G = (V, E, ATT, CONS) and G' = (V', E', ATT', CONS') are homomorph -noted G → G'-if and only if there is a graph-homomorphism h from (V, E) to (V', E') such as

1. ∀ v ∈ V (resp. ∀ e = (v, ṽ) ∈ E), |ATT v | = |ATT h(v) | (resp. |ATT e | = |ATT (h(v),h(ṽ) |), 2. ∀ v ∈ V (resp. ∀ e = (v, ṽ) ∈ E), ∀ i ∈ [|1, |ATT v |], D i v = D i h(v) , 3. The system of equations S = { A = A' | (∃ v ∈ V, ∃ i ∈ [|1, |ATT v |], A = A i v ∧ A' = A i h(v) ) ∨ (∃ e = (v, ṽ) ∈ E, ∃ i ∈ [|1, |ATT e |], A = A i e ∧ A' = A i (h(v,h(ṽ))
) } has at least one solution.

Remark 4. -Constraints do not impact on the definition of an homomorphism.

It will be shown that they intervene in the rewriting process in a different way. Similarly, attributes on vertices and edges are the only one that are considered whereas attributes on the graph itself are not. -We underline the fact that the existence of an AC-homomorphism is conditioned by the resolvability of a system of equations on attributes. As stated in the introduction, in [START_REF] Berthold | Attributed graph transformation with partial attribution[END_REF][START_REF] Loulou | Towards a unified graph-based framework for dynamic component-based architectures description in z[END_REF][START_REF] Hirsch | Modeling Software Architectures and Styles with Graph Grammars and Constraint Solving[END_REF][START_REF] Métayer | Describing software architecture styles using graph grammars[END_REF] and most of the research on attributed graphs, the existence of a morphism is also conditioned by equalities between attributes, potentially through morphism between attributes spaces. However, this is often the only clause relying on attributes that impact the applicability of a graph rewriting rule. -AC-graph isomorphism and AC-vertex morphism can be trivially deduced from the definition of AC-graph homomorphism.

Solving the system of equation S result in identifying the value of some attributes with some constants in theirs domains of definition and/or with some other attributes. Integrating the affectation obtained by solving this system refers to the update of the value of the attribute to reflect these identifications. Intuitively, such an integration is nothing more than a dimension reduction of the space formed by the potential values of the attributes. For more information see [START_REF] Rodriguez | A rule driven approach for architectural self adaptation in collaborative activities using graph grammars[END_REF].

There exists a vast number of approaches handling graph rewriting based on attributed graphs [START_REF]Handbook of Graph Grammars and Computing by Graph Transformations[END_REF][START_REF] Ehrig | Tutorial introduction to the algebraic approach of graph grammars[END_REF]. Their applicability depends on various factors, suspension condition, negative application condition(s), always including the existence of an homomorphism between an element of the graph rewriting rule and the graph to rewrite. Inspired by string grammar theory [START_REF] Parr | Ll(*): the foundation of the antlr parser generator[END_REF], we include in these factors the satisfaction of a, potentially empty, set of constraints on attributes, namely the set of constraints of the AC-rewriting rule. Consequently, the set of constraints on a graph rewriting rule can be seen as a set of semantic predicates.

Applying a rewriting rule on a graph consists in suppressing a part of the graph and extending it by adding some vertices and edges. In addition to classical modifications induced by the application of a rule, a set of actions is performed at the end of said application.

Virtually, any attributed graph rewriting formalism could be extended to include semantic predicates, constraints and mutators. In order to fix the idea, we chose the classical double push out formalism defined in [START_REF]Handbook of Graph Grammars and Computing by Graph Transformations[END_REF] alongside with the attribute management considered previously and used in [START_REF] Rodriguez | A rule driven approach for architectural self adaptation in collaborative activities using graph grammars[END_REF]. Definition 6. (AC-graph AC-rewriting rule) An AC-graph AC-rewriting rule is a 5-tuple (L, K, R, ATT, CONS, ACT) where -ATT = ATT L ∪ ATT R is a set of attributes, ATT rule being the set of attributes of the graph rewriting rule itself, -CONS = CONS rule ∪ CONS R\K is a set of constraints, CONS rule being the set of constraints of the graph rewriting rule itself and CONS R\K the set of constraints of R\K,

-(L = (V L , E L ), ATT L , ∅) and (R = (V R , E R ), ATT R , CONS R\K ) are AC-graphs, -K = (V K , E K ) is a sub-graph of both L and R, -ACT is a set of actions.
L\K is called the Del zone and R\K is called the Add zone, while K is called the Inv zone.

Furthermore, graph rewriting rules are illustrated here using the delta representation, where only one graph is considered. This graph is visually partitioned into three zones, from left to right the Del, Inv and Add zones. This graphical representation is illustrated in Fig. 2.

A rule is applicable on a AC-graph G if :

1. there is an AC-homomorphism h : (L, ATT L , CONS L ) → G, implying in particular that the system of equations S

= { A = A' | (∃ v ∈ V L , ∃ i ∈ [|1, |ATT v ||], A = A i v ∧ A' = A i h(v) ) ∨ (∃ e = (v, ṽ) ∈ E, ∃ i ∈ [|1, |ATT e ||], A = A i e ∧ A' = A i (h(v,h(ṽ)) ) } has at least a solution,
2. the application of the rule would not lead to the apparition of any dangling edge, 3. each Cons ∈ CONS rule is evaluated to "true" by integrating the affectations obtained by solving S and by evaluating each elementary logic expression containing variable attributes to "unknown" as stated in remark 3.

Its application consists in :

1. erasing h(L\K), 2. integrating the affectations obtained by solving S to the remaining graph, 3. adding an isomorph copy of R\K integrating the affectations obtained by solving S, 4. performing each action Act ∈ ACT.

Inspired from Chomsky's generative grammars [START_REF] Chomsky | Three models for the description of language. Information Theory[END_REF], graph grammars are defined as a classical rewriting system and formally characterize an architectural style.

Definition 7. (Graph Grammar)A graph grammar is defined by the 4-tuple (AX, N T, T, P ) where -AX is the axiom, an AC-graph with a single vertex AX -N T is the sets of non-terminal archetypes of AC-vertices, -T is the set of terminal archetypes of AC-vertices, -P is the set of AC-graph AC-rewriting rules, or production rules, belonging to the graph grammar.

Each vertex occurring in a graph rewriting rule in P or in a graph obtained by applying a sequence of productions ∈ P to the axiom is then isomorph to at least one arch-vertex in N T or T .

Remark 5. Semantic predicates allow to easily guarantee the finition of such rewriting systems, by imposing, for example, a limited number of deployed components.

Definition 8. (Instance belonging to the graph grammar) An instance belonging to the graph grammar (AX, N T, T, P ) is a graph whose vertices and edges have only constant attributes and obtained by applying a sequence of productions in P to AX. If an instance does not contain any vertex isomorph to an arch-vertex from N T it is said to be consistent.

Graph rewriting systems are illustrated in the next section, where they are used to characterize the example presented in Sect. 2.

Characterisation of the Motivating Example.

By characterising the motivating example using the formalism presented in the previous section, it appears undoubtedly that it addresses the problems identified in Sect. 2.

Components arch-types : Terms of the Grammar

Firstly, let us consider what the axiom shall be. Considering the definition of graph rewriting rules and systems, instances of the such systems are graphs that inherit the attributes and constraints of the axiomatic graph. We wish to expressed the redundancy and localisation constraints on instances of the architectural style, as described in appendix A, as well as the maximum number of entities that a MA or a LA may manage and the arbitrary value intervening in the balancing condition. Therefore, let AX DIET be (v AX , ATT AX = ((maxSon-sLA, N), (maxSonsMA, N), (maxσ, R + )), CONS AX = (L(S,2),R(S,3))), where here maxSonsMA = maxSonsLA = 10. Throughout this section the graph, on which production rules will be attempted to be applied to, is noted G = (V, E, ATT, CONS). Note that as stated in this paragraph, if G is an instance of the architectural style defined here, ATT = ATT AX and CONS G = CONS AX .

Secondly, terminal terms of the graph rewriting system characterizing DIET have to be defined. As they are AC-vertices, defining their attributes and constraints is sufficient. Remember that these term are arch-vertices and defined a pattern of attributes and constraints for the vertices of each instance. The first ones have already been listed in Sect. 2, while constraints stem from considerations exposed in the same section. The naming system itself is not constrained and is quite simple, let T Omni be (v Omni , ATT Omni = (("Omni", Nat), (m, Mach)), ∅). Similarly, let T SeD = (v SeD , ATT SeD = (("SeD", Nat), (s, Serv), (m, Mach)), ∅). The MA shall not manage more than 10 entities. Accordingly, let T MA be (v MA , ATT MA = (("MA", Nat), (Nsons, N), (m, Mach)), CONS MA = ((A 2 < ATT 2 AX ))). Finally, we stated before that LAs of the same layer should not be deployed on the same machine or have disjoint set of carried out services. Hence, let T LA be (v LA , ATT LA = (("LA", Nat), (depth, N), (Nsons, N), (m, Mach), (s, Serv)), CONS LA = c(v LA )), where c(v) = (c(v

) i ) i∈[|1,|LA((AT TG) 2 v )|-1|] and ∀ṽ ∈ LA((ATT G ) 2 v )\{v}, !∃ i ∈ [|1, |LA((AT T G ) 2 v )| -1|], c(v) i = ((ATT G ) 4 v = (ATT G ) 4 ṽ ) ∨ ((ATT G ) 5 v ∩ (ATT G ) 5 ṽ = ∅).

Productions of the Rewriting System

Production rules of the graph grammar formalize the construction of instances by defining when and how an entity may be deployed and the consequences of such a deployment. The first rule to define is the initialisation consuming the axiomatic vertex (Del). The naming service and the MA are deployed, as well as a non-terminal vertex granting that the MA manages at least an entity (Add). This vertex will be later on instantiated into a LA or a SeD. Finally, the MA register to the naming service through the action register. Let p 1 = (L p1 , K p1 , R p1 , ∅, µ registering (pv2)), where L p1 , K p1 , R p1 and pv2 are defined in Fig. 2 and µ registering (v) is the action of registering the object represented by the vertex v to the naming service. Productions rules p 2 and p 3 model the addition of a non-terminal vertex, that will later on be instantiated into a LA or a SeD, and manage respectively by the MA or a LA. To deploy a new entity under a LA, the balancing condition and the maximal number of managed entities should be respected. The application of one of these productions leads to the incrementation of the number of sons of the entity on which the terminal vertex is added.

Let p 2 = (L p2 , K p2 , R p2 , ∅, µ inc (pv2MA,2)) and p 3 = (L p3 , K p3 , R p3 , (balancing(pv2LA), Nsons < ATT 1 AX ), µ inc (pv2LA, 3
)) where L p2 , K p2 , R p2 , pv2LA, L p3 , K p3 , R p3 , and pv2MA are defined in Fig. 3, while µ inc (v, i) is described below and balancing The instantiation of a temporary vertex into a SeD is described by p 4 and p 5 if it is managed by respectively the MA or a LA. After deploying the SeD, it has to register to the naming service and, if it is managed by a LA, an update of carrying out services must be conducted. Let p 4 = (L p4 , K p4 , R p4 , ∅, µ registering (pv4)) and p 5 = (L p5 , K p5 , R p5 , ∅, (µ registering (pv4), µ updateServ (pv2,pv4)), where L p4 , K p4 , R p4 , L p5 , K p5 , R p5 , pv2, and pv4 are defined in Fig. 4, and µ updateServ (v, ṽ) is as follows. The two last productions of the grammar, p 6 and p 7 , describe the instantiation of non-terminal term into a LA managed respectively by the MA or a LA. Let p 6 = (L p6 , K p6 , R p6 , ∅, µ registering (pv4)) and p 7 = (L p7 , K p7 , R p7 , ∅, µ registering (pv4)), where L p6 , K p6 , R p6 , L p7 , K p7 , R p7 , and pv4 are defined in Fig. 5.

(v) = σ(((ATT G ) 3 la ) la∈LA(d)\{v} , (ATT G ) 3 v +1) < ATT 3 AX , where σ(s) is the standard deviation of the sequence s. µ inc (v, i) Att i v ← Att i v + 1
µ updateServ (v, ṽ) oldServ ← (Att G ) 5 v ind ← 5 if (A G ) 1 ṽ = "SeD" ind ← 2 (Att G ) 5 v ← oldServ ∪ (Att G ) ind ṽ if (Att G ) 5 v = oldServ v ← v ′ ∈ V G , (v ′ , v) ∈ V E µ updateServ (v, v)

The Constrained Attributed Graph Rewriting System Characterizing the Motivating Example

Considering the definition introduced in this section, GRS DIET , the graph rewriting system formally characterizing the motivating example introduced in Sect. 2, is defined as GRS DIET =(AX D IET , NT DIET , T DIET , P DIET ), where NT DIET = (v temp , ATT temp = ("temp", {"temp"}), CONS temp = ∅), Remark 6. Efficiently representing evolving attributes. An interesting feature of this formalism is that it offers several options for the characterization of problematic attributes or constraints. Let us consider the set of services that may be carried out by at least a SeD managed directly or indirectly by a LA, for example. Intuitively, this attribute depends on other ones and could be expressed as a regular combination of the graph attributes. However, this combination should have been evaluated whenever its value is required, for example to evaluate the constraints of a LA. To avoid frequent evaluations, the graph representing the configuration can be seen as an augmented data structure and the attribute be updated whenever it has to be using mutators. The choice between these two options rely on the complexity and frequency of updates and evaluations.

This model allows to express each limitation identified in Sect. 2, interdependency between attributes, modification of existing attributes and non-trivial requirements for conditional deployments. Furthermore, components of the architecture are constrained to reflect the appropriateness of a configuration. These constraints are inherited from arch-vertices as a component is deployed, and may evolve like any attribute to reflect context changes.

Evaluation of a configuration can be done in several ways. The most straightforward would be to assign a, potentially infinite, weight to the violation of constraints to define management policies through heuristics. However, constraints on an architecture and their satisfaction can be seen as a way of granting some desirable properties rather than looking for an optimum. Considering that finding a "good" configuration as a classical multi-criteria optimisation problem, it could be solved by restraining it to a single-criteria, here energy consumption, problem over the space of consistent configurations that does not violate any constraint.

Conclusion

This article lift limitations of formal approaches for the characterisation of dynamic software architectures using graph rewriting systems. Said limitations are put under the spotlight using an example of hierarchical dynamic software architecture that previous approaches have failed to characterize, and that later on serve as an illustration for our model. In particular, interdependency of attributes is handled using regular combination of attributes, and mutators are introduced to modify existing attributes. Consequently, non-trivial attributes related to structural and behavioural properties of the architecture may be handily represented, as shown in the example. Based on such attributes, dynamic constraints are included in the formal model, reflecting the appropriateness of a configuration, arising or evolving as components are deployed or as the context change. Moreover, further properties can be guaranteed as the formalism presented in this paper tackles non-trivial conditional deployments using semantic predicates.

Constraints and attributes facilitate the evaluation of a configuration, a basis for the definition and the enforcement of reconfiguration policies. We plan on developing the mechanisms evoked in this paper to achieve these aims, as well as extending existing tools to realise management using this formalism and validate its time efficiency with regard to other graph-based approaches.

Definition 1 .

 1 (Attribute) An attribute is a couple Att = (Att A , Att D ) where -Att A is called value and is either • a variable, • a constant or • an expression, a regular combination of attributes : ∀n ∈ N, ∀ sequence of sets (D u ) u∈[|1,n|] , ∀ f ∈ D D1×D2ו••×Dn , a couple Att = (f(A 1 ,..,A n ), Att D ) is a regular combination of attributes of (A i , D Ai ) i∈[|1,n|] if and only if Att D ⊆ D and ∀i ∈ [|1, n|], (A i , D Ai ) is a (defined) attribute and D Ai ⊆ D i . -and Att D its domain of definition.

Fig. 1 .

 1 Fig. 1. An AC-graph modelling a configuration of DIET

Figure 1

 1 represents an AC-graph modelling some configuration of DIET, where the naming server has been omitted for clarity concerns. The graph is formally defined in Appendix A.

Fig. 2 .

 2 Fig. 2. Initialisation

Fig. 3 .

 3 Fig. 3. Addition of a non-terminal term

Fig. 4 .

 4 Fig. 4. Instantiation of a non-terminal term into a SeD

Fig. 5 .

 5 Fig. 5. Instantiation of a non-terminal term into a LA

Acknowledgement

The work presented in this paper has been funded by the ANR in the context of the project SOP, ANR-11-INFR-001.

A Formal definition of the graph presented in Fig 1

The graph in the Fig. 1 is defined as follow. G = (V, E, ATT, CONS) where

The architecture is composed by some software component, the first one being v 1 , a MA managing 2 entities and deployed on a machine noted m 1 ATT v1 = {("MA", Nat), ("2", N), (m 1 ,Mach)}.

Three LAs are deployed, respectively of depth 1, 1 and 2, managing 2, 1 and 2 entities, placed on machine m 2 , m 3 and m 4 . The first one managed directly or indirectly SEDs providing the set of services s 1 ∪ s 2 ∪ s 3 , the second one s 4 and the third one s 1 ∪ s 2 . ATT v2 = {("LA", Nat), ("1", N), ("2", N), (m 2 , Mach), (s 1 ∪ s 2 ∪ s 3 , Serv)}, ATT v3 = {("LA", Nat), ("1", N), ("1", N), (m 3 , Mach), (s 4 , Serv)}, ATT v4 = {("LA", Nat), ("2", N), ("2", N), (m 4 , Mach), (s 1 ∪ s 2 , Serv)}.

Finally, four SEDs deployed on m 5 , m 6 , m 7 and m 8 carry out the services s 1 , s 2 , s 3 and s 4 . ATT v5 = {("SED",Nat), (s 1 , Serv), (m 5 , Mach)}, ATT v6 = {("SED",Nat), (s 2 , Serv), (m 6 , Mach)}, ATT v7 = {("SED",Nat), (s 3 , Serv), (m 7 , Mach)}, ATT v8 = {("SED",Nat), (s 4 , Serv), (m 8 , Mach)}.

The graph itself is constraints by L(S,2) and R(S,3), where R and L are as follows. ∀S ′ ⊆ S, ∀x s ∈ N , let the redundancy constraint R(S',x s ) be "There are at least x s SeDs carrying each service s in S'".

V k . ∀s ∈ S, ∀x s ∈ N , let the localisation constraint L(S',x s ) be "For each service in S', there are at least x s different machines on which at least a SeD carrying out the service s is deployed".

This means that each service should be carried out by at least 3 SEDs located on at least two different machine. The MA has a constraints on the number of entities it manages. The two LA of depth 1 are constrained not to be deployed on the same machine or to offer disjoint sets of services. The last LA has a similar constraint.


Eva Löcherbach
email: locherbach@univ-paris12.fr

Dasha Loukianova
email: dasha.loukianova@univ-evry.fr

On Nummelin splitting for continuous time Harris recurrent Markov processes and application to kernel estimation for multi-dimensional diffusions

Keywords: Harris recurrence, Nummelin splitting, continuous time Markov processes, resolvents, special functions, additive functionals, Chacon-Ornstein theorem, diffusion process, Nadaraya-Watson estimator

We introduce a sequence of stopping times that allow to study an analogue of a life-cycle decomposition for a continuous time Markov process, which is an extension of the well-known splitting technique of Nummelin to the time-continuous case. As a consequence, we are able to give deterministic equivalents of additive functionals of the process and to state a generalisation of Chen's inequality. We apply our results to the problem of non-parametric kernel estimation of the drift of multi-dimensional recurrent, but not necessarily ergodic, diffusion processes.

Introduction

Consider a Harris recurrent strong Markov process X = (X t ) t≥0 with invariant measure µ. If such a process has a recurrent point x 0 (or more generally a recurrent atom), then it is possible to introduce a sequence of stopping times R n , called life-cycle decomposition, such that 1. For all n, R n < ∞, R n+1 = R n + R 1 • θ Rn . (Here, θ denotes the shift operator.) 2. X Rn = x 0 .

3. For all n, the process (X Rn+t ) t≥0 is independent of F Rn .

In this case, paths of the process can be decomposed into i.i.d. excursions [R i , R i+1 [, i = 1, 2, . . . , plus an initial segment [0, R 1 ], and then limit theorems such as the ratio limit theorem for additive functionals of the process follow immediately as a direct application of the strong law of large numbers, in both the ergodic and the null recurrent case.

For general Harris processes, at least without further assumptions, recurrent atoms do not exist. However, for discrete time Harris chains, Athreya and Ney, see [START_REF] Athreya | A new approach to the limit theory of recurrent Markov chains[END_REF], and Nummelin, see [START_REF] Nummelin | A splitting technique for Harris recurrent Markov chains[END_REF], give a way of constructing a recurrent atom on an extended probability space, provided the transition operator of the chain satisfies a certain minorization condition. This construction is called "splitting". A well-known idea, see for instance Meyn and Tweedie, [START_REF] Meyn | Proceedings of the Doeblin conference '50 years after Doeblin: development in the theory of Markov chains, Markov processes, and sums of random variables[END_REF] and [START_REF] Meyn | A survey of Foster-Lyapunov techniques for general state space Markov processes[END_REF], is to consider the discrete chain X = ( Xn ) n , called resolvent chain or R-chain, instead of the process in continuous time X. This resolvent chain is obtained when observing the process at independent exponential times. We propose to apply the splitting technique to this resolvent chain which is always possible. Hence, we use splitting at random times when sampling the process after independant exponential times. We then fill in the original process in between two successive exponential times. In other words, we construct bridges of the process X between exponential times such that at the exponential times, the splitting is satisfied. This construction is not evident since we want to preserve the Markov property of the process. It is for that reason that we have to change the structure of "history" of the process. Actually, we construct a process Z t taking values in E × [0, 1] × E together with a sequence of jump times T n for this process such that at any time T n , we know the present state of the process X Tn , but also the future state X T n+1 . Moreover, the following properties are fulfilled :

1. The first co-ordinate Z 1 t of Z t has the same dynamics as the original process X t starting from X 0 = x if we fix the initial condition Z 1 0 = x, but not Z 2 0 and Z 3 0 .

2. On each interval [T n , T n+1 [, Z 2 t and Z 3 t are constant, and the third co-ordinate Z 3

Tn represents a choice of X T n+1 according to the splitting technique which has to be attained by the bridge (the process) between T n and T n+1 .

3. The second co-ordinate is used only in order to model the splitting. It is not of further importance.

Then it is possible to define a sequence of stopping times (S n , R n ) for this process which is a generalised life-cycle decomposition in the following sense :

1. For all n, S n < R n < ∞, S n+1 = S n + S 1 • θ Sn , R n = inf{T m : T m > S n }.

2. For every n, X Rn is independent of σ{X s : s ≤ S n } and L(X Rn ) = ν for some fixed probability measure ν.

3. For all µ-integrable functions f and for any initial measure π, E π ( R n+1 Rn f (X s )ds) = µ(f ) (up to a multiplicative constant). Note that it is not possible to divide the path of the process into real i.i.d. excursions. We obtain the independence only after the waiting time R n after S n . Some special attention has to be payed to the initial segment R 1 0 f (X s )ds -and it is for that sake that we have to introduce and to investigate functions that are called special functions.

As a consequence, we establish a generalization of Chen's inequality (compare also to [START_REF] Chen | The law of the iterated logarithm for functionals of Harris recurrent Markov chains: Self Normalization[END_REF], lemma 1, (2.4)) for additive functionals of the Markov process (see theorem 2.18) and get in particular the existence of a deterministic equivalent of any integrable additive functional A of the process (see corollary 2.19):

There exists a deterministic function t → v t such that v t → ∞ as t → ∞ such that for any µ-integrable additive functional A of X and any initial measure π,

lim M →∞ lim inf t→∞ P π (1/M ≤ A t /v t ≤ M ) = 1. (1.1)
Here, the rate of convergence of v t to infinity is determined by the asymptotic behaviour of the process, and is given by v t = t in the ergodic case.

Under some additional regularity assumptions, (1.1) can be strengthened to obtain weak convergence of martingales and additive functionals as indicated in [START_REF] Chen | How often does a Harris recurrent Markov chain recur?[END_REF] for the discrete case. This has been done in [START_REF] Höpfner | Limit theorems for null recurrent Markov processes[END_REF] for the continuous time case (see also Touati,[START_REF] Touati | Théorèmes limites pour les processus de Markov récurrents[END_REF]) -still based on the splitting method. However, in [START_REF] Höpfner | Limit theorems for null recurrent Markov processes[END_REF] we have approximated the continuous time process by a sequence of processes converging to X which contain "discrete" parts, i.e. time intervals where the process is constant, and we have applied the splitting only to the approximating processes. This approach does not apply here since it does not work with the process itself.

Note that the asymptotic behaviour of additive functionals has been intensively studied for Markov chains (see Chen,[START_REF] Chen | How often does a Harris recurrent Markov chain recur?[END_REF], [START_REF] Chen | The law of the iterated logarithm for functionals of Harris recurrent Markov chains: Self Normalization[END_REF]) as well as for diffusions in dimension one, making use of techniques from analysis or of local time, see for instance Khasminskii, [START_REF] Khasminskii | Asymptotic behaviour of parabolic equations arising from onedimensional null recurrent diffusions[END_REF], [START_REF] Khasminskii | Limit distributions for some integral functionals for null recurrent diffusions[END_REF], and also Csáki and Salminen, [START_REF] Csáki | On the additive functionals of diffusion processes[END_REF]. The existence of a deterministic equivalent (1.1) for integrable additive functionals of Markov chains was established by Chen in [START_REF] Chen | The law of the iterated logarithm for functionals of Harris recurrent Markov chains: Self Normalization[END_REF], and then extended to the case of one-dimensional diffusions by Loukianova and Loukianov in [START_REF] Loukianova | Deterministic equivalent of additive functionals of recurrent diffusions and drift estimation[END_REF]. However, the general case has not yet been studied before.

It was observed in [START_REF] Loukianova | Deterministic equivalent of additive functionals of recurrent diffusions and drift estimation[END_REF] that the existence of a deterministic equivalent (1.1) is very useful in statistical inference for recurrent diffusion processes. In particular, concerning the rate of convergence, it permits to treat null recurrent processes like ergodic ones, replacing t by v t . Using this method, the rate of convergence of parametric MLE of the drift was obtained in [START_REF] Loukianova | Deterministic equivalent of additive functionals of recurrent diffusions and drift estimation[END_REF] for one-dimensional recurrent diffusions. We would like to stress that thanks to (1.1), the result of [START_REF] Loukianova | Deterministic equivalent of additive functionals of recurrent diffusions and drift estimation[END_REF] can be extended to the multi-dimensional setting without further efforts.

To illustrate some non-parametric application of our method, we treat in the second part of this paper the problem of kernel estimation of an unknown drift function b(.) in the case of d-dimensional recurrent diffusions. Note that for this non-parametric problem up to now, only the one-dimensional case has been intensively studied, using techniques that are strictly one-dimensional (local time), see for instance Kutoyants, [START_REF] Kutoyants | Efficient density estimation for ergodic diffusion processes[END_REF] and [START_REF] Kutoyants | it Statistical inference for ergodic diffusion processes[END_REF], Delattre, Hoffmann, Kessler, [START_REF] Delattre | Dynamics adaptive estimation of a scalar diffusion[END_REF]. On the other hand, also the ergodic case has been studied, see for instance Dalalyan and Reiss, [START_REF] Dalalyan | Asymptotic equivalence for ergodic diffusions: the multidimensional case[END_REF], but nothing seems to be known in the general multidimensional possible null recurrent case.

Besides the fact of existence of a deterministic equivalent, the problem in the multidimensional case is to get some kind of uniform version of the ratio limit theorem without using local-time techniques. This is done here using the life cycle decomposition (S n , R n ) of the continuous time process, playing particularly attention to the initial segment by the use of special functions. The somewhat uniform version of the strong Chacon-Ornstein theorem is in some sense the main technical result of this second part of this articleinteresting in its own right -, given in theorem 3.9.

As usual, in order to estimate, we assume a smoothness property at x 0 , i.e. a Hölder condition of the following kind:

sup x∈[x 0 -δ,x 0 +δ] |b(x) -b(x 0 )| • |x -x 0 | -α ≤ γ, (1.2)
for some δ, γ > 0 and some fixed α ∈ (0, 1). Then the Nadaraya-Watson estimator with bandwidth

h = h t = v -1/(2α+d) t attains the rate v -α/(2α+d) t
. This is theorem 3.6. Note that v t depends on the asymptotic behaviour of the process and is not observable. It is possible, using our techniques, to replace v t by V t where V t is some integrable additive functional of X (and hence observable) in order to get a random rate of convergence V -α/(2α+d) t . However, we are not yet able to replace v t by V t in the construction of the estimator itself. So our statistical result is more of theoretical interest. Note however that no results have been known before in the general multi-dimensional case.

2 Nummelin splitting for Markov processes in continuous time, Chen's inequality and deterministic equivalents for additive functionals

Consider a probability space (Ω, A, (P x ) x ), and on (Ω, A, (P x ) x ) a process X = (X t ) t≥0 which is strong Markov, taking values in a locally compact Polish space (E, E), with càdlàg paths, and with X 0 = x P x -almost surely, x ∈ E. We write (P t ) t for the semi group of X and we suppose that X is recurrent in the sense of Harris, with invariant measure µ, unique up to multiplication with a constant. Moreover, let (A t ) t be the filtration generated by X.

We impose the following regularity condition on the transition semi-group P t of X :

Assumption 2.1 1. The transition semi-group P t of the process X is Feller.

2. There exists a sigma-finite positive measure Λ on (E, E) such that for every t > 0, P t (x, dy) = p t (x, y)Λ(dy), where (t, x, y) → p t (x, y) is jointly measurable.

Preliminaries on additive functionals

We are interested in the asymptotic behaviour of integrable additive functionals of the process. We will show -using Nummelin splitting -that it is possible to find a deterministic function v t associated to the process such that all integrable additive functionals are are equivalent to v t in probability.

We recall the definition of an additive functional:

Definition 2.2 An additive functional of the process X is a Ī R + -valued, (A t ) t -adapted process A = (A t ) t≥0 such that 1. Almost surely, the process is non-decreasing, right-continuous, having A 0 = 0.

2. For any s, t ≥ 0, A s+t = A t +A s •θ t almost surely. Here, θ denotes the shift operator.

Examples for additive functionals are A t = t 0 f (X s )ds where f is a positive measurable function. Such an additive functional is said to be integrable, if µ(f ) < ∞.

It is well known that Harris recurrent Markov processes satisfy the ratio limit theorem (or Chacon-Ornstein limit theorem): For any positive, µ-integrable functions f and g such that µ(g) > 0,

lim t→∞ t 0 f (X s )ds t 0 g(X s )ds = µ(f ) µ(g) P x -almost surely ∀ x ∈ E.
We recall the notion of a special function (see also [START_REF] Revuz | Markov chains[END_REF], [START_REF] Brancovan | Fonctionnelles additives spéciales des processus récurrents au sens de Harris[END_REF]):

Definition 2.3 A measurable function f : E → IR + is called special if for all bounded
and positive measurable functions h such that µ(h) > 0, the function

x → E x ∞ 0 exp - t 0 h(X s )ds f (X t )dt
is bounded.

Then the ratio limit theorem can be strengthened in the following way: Let f and g be two µ-integrable, special functions having µ(g) > 0. Then for any initial measures π 1 and π 2 ,

lim t→∞ E π 1 t 0 f (X s )ds E π 2 t 0 g(X s )ds = µ(f ) µ(g) .
This is the strong Chacon-Ornstein limit theorem, see also [START_REF] Brancovan | Fonctionnelles additives spéciales des processus récurrents au sens de Harris[END_REF], [START_REF] Orey | Limit theorems for Markov chain transition probabilities[END_REF].

On Nummelin splitting in continuous time

The aim of this section is to construct -on an extended probability space -a process Z taking values in Z := E × [0, 1] × E which admits a recurrent atom in a certain sense such that the first co-ordinate (Z 1 t ) t is a version of the original process (X t ) t . We start with some preliminary considerations : Introduce a sequence (σ n ) n≥1 of i.i.d. exp(1)-waiting times, independent of the process X itself. Let T 0 := 0, T n := σ 1 + . . . + σ n and Xn := X Tn . Then it is well-known that the chain X = ( Xn ) n is recurrent in the sense of Harris and that its one-step transition kernel U 1 (x, dy) := ∞ 0 e -t P t (x, dy)dt satisfies a minorization condition:

U 1 (x, dy) ≥ α1 C (x)ν(dy), (2.3)
where 0 < α < 1, µ(C) > 0 and ν a probability measure equivalent to µ(• ∩ C) (cf [START_REF] Revuz | Markov chains[END_REF], [START_REF] Höpfner | Limit theorems for null recurrent Markov processes[END_REF], proposition 6.7, [START_REF] Meyn | Proceedings of the Doeblin conference '50 years after Doeblin: development in the theory of Markov chains, Markov processes, and sums of random variables[END_REF]). Note that by assumption 2.1, U 1 (x, dy) ≪ Λ(dy), with density u 1 (x, y) := ∞ 0 e -t p t (x, y)dt. We follow the approach of Nummelin ([21]) in discrete time and define the following transition kernel Q((x, u), dy) from E × [0, 1] to E :

Q((x, u), dy) =      ν(dy) if (x, u) ∈ C × [0, α] 1 1-α U 1 (x, dy) -αν(dy) if (x, u) ∈ C×]α, 1] U 1 (x, dy) if x / ∈ C . (2.4)
Note that by construction,

1 0 Q((x, u), dy)du = U 1 (x, dy). (2.5)
We now give the construction of

Z t = (Z 1 t , Z 2 t , Z 3 t ) taking values in E × [0, 1] × E.
The idea is the following : At any time T n , knowing the position of the process X at that time, i.e. knowing the random variable X Tn , we choose a uniform variable on [0, 1], independently of the past. We use this uniform variable in order to realise a choice of the position X T n+1 of the process at the next time T n+1 according to the splitting technique. But we choose this position X T n+1 already at time T n . Hence at time T n , we dispose both of the positions X Tn and X T n+1 . Finally, letting time evolve, on [T n , T n+1 [, the first co-ordinate of Z represents a choice of the bridge of X from X Tn to the already fixed position X T n+1 . The first coordinate of Z will represent the evolution of the bridge, the second co-ordinate is the uniform variable used in order to realise the splitting, and the third co-ordinate represents the future value X T n+1 . Here is the precise construction :

Let Z 1 0 = X 0 = x. Choose Z 2 0 according to the uniform distribution U on [0, 1]. On {Z 2 0 = u}, choose Z 3 0 ∼ Q((x, u), dx ′ ). Then inductively in n ≥ 0, on Z Tn = (x, u, x ′ ) :
1. Choose a new jump time σ n+1 according to

e -t p t (x, x ′ ) u 1 (x, x ′ ) dt on IR + ,
where we define 0/0 := a/∞ := 1, for any a ≥ 0, and put T n+1 := T n + σ n+1 .

2. On {σ n+1 = t}, put Z 2 Tn+s := u, Z 3 Tn+s := x ′ for all 0 ≤ s < t.

3. For every s < t, choose

Z 1 Tn+s ∼ p s (x, y)p t-s (y, x ′ ) p t (x, x ′ ) Λ(dy).
Choose Z 1 Tn+s := x 0 for some fixed point

x 0 ∈ E on {p t (x, x ′ ) = 0}. Moreover, given Z 1 Tn+s = y, on s + u < t, choose Z 1 Tn+s+u ∼ p u (y, y ′ )p t-s-u (y ′ , x ′ ) p t-s (y, x ′ ) Λ(dy ′ ).
Again, on {p t-s (y, x ′ ) = 0}, choose Z 1 Tn+s+u = x 0 .

At the jump time

T n+1 , choose Z 1 T n+1 := Z 3 Tn = x ′ . Choose Z 2 T n+1 independently of Z s , s < T n+1 , according to the uniform law U. Finally, on {Z 2 T n+1 = u ′ }, choose Z 3 T n+1 ∼ Q((x ′ , u ′ ), dx ′′ ).
Remark 2.4 Let S be any random or deterministic time. Put T 1 (S) := inf{T m : T m > S}. Then, on Z S = (x, u, x ′ ), the construction of (Z (S+t)∧T 1 (S) ) t is according to the same steps 1.-4. above. This will become clear in the proof of theorem 2.7.

Write IF for the filtration generated by Z. Moreover, let C G be the filtration generated by the first two co-ordinates (Z 1 , Z 2 ) of Z. By abuse of notation, for any initial measure π on E, we shall write P π for the unique probability measure under which Z starts from π(dx)U (du)Q((x, u), dx ′ ). E π is then the corresponding expectation. In the same way, we shall write P x in the case where π = δ {x} .

By construction, we have the following :

Remark 2.5 For any n ≥ 0, the strong Markov property holds with respect to T n , i.e. for any f, g : Z → IR measurable and bounded, for any s > 0 fixed,

E π (g(Z Tn )f (Z Tn+s ) = E π (g(Z Tn )E Z Tn (f (Z s ))).
The following first property is shown by a simple calculus.

Proposition 2.6 Under P x we have : The sequence of jump times (T n ) n is independent of the first co-ordinate-process (Z 1 t ) t , and

(T n -T n-1 ) n≥1 are i.i.d. exp(1)-variables. Moreover, T n+1 -T n is independent of F Tn-. Theorem 2.7 Z is a Markov process with respect to IF. Proof Let s, u > 0, let f, g : E × [0, 1] × E → IR + be
positive, bounded and measurable. We fix an initial measure π on E.

1) The existence of the process up to a possibly finite life-time ζ := lim n T n is clear from general considerations (we refer the reader to the paper of Ikeda, Nagasawa, Watanabe, [START_REF] Ikeda | A construction of Markov processes by piecing out[END_REF], on the construction of Markov processes by piecing out). Due to proposition 2.6, under P x , the T n are the jump times of a rate-1-Poisson process, hence ζ = ∞ almost surely.

2) For any n ≥ 0, conditioning on F Tn , and applying steps 1-3 of the construction, we arrive at

E π g(Z s )f (Z s+u )1 {Tn<s<s+u<T n+1 } = E π 1 {Tn<s} ∞ s+u-Tn e -t dt p s-Tn (Z 1 Tn , y)p t-(s-Tn) (y, Z 3 Tn ) u 1 (Z 1 Tn , Z 3 Tn ) g(y, Z 2 Tn , Z 3
Tn )Λ(dy)

p u (y, y ′ )p t-(s+u-Tn) (y ′ , Z 3 Tn ) p t-(s-Tn) (y, Z 3 Tn ) f (y ′ , Z 2 Tn , Z 3 Tn )Λ(dy ′ ) = E π 1 {Tn<s} e -(s-Tn) p s-Tn (Z 1 Tn , y)u 1 (y, Z 3 Tn ) u 1 (Z 1 Tn , Z 3 Tn ) g(y, Z 2 Tn , Z 3 Tn )Λ(dy) ∞ u e -t dt p u (y, y ′ )p t-u (y ′ , Z 3 Tn ) u 1 (y, Z 3 Tn ) f (y ′ , Z 2 Tn , Z 3 Tn )Λ(dy ′ ) = E π g(Z s )1 {Tn<s<T n+1 } E Zs f (Z u )1 {u<T 1 } , since on {s > T n }, L(Z s ; s < T n+1 |Z Tn )1 {s>Tn} = e -(s-Tn) p s-Tn (Z 1 Tn , y)u 1 (y, Z 3 Tn ) u 1 (Z 1 Tn , Z 3 Tn ) Λ(dy)δ (Z 2 Tn ,Z 3
Tn ) (du, dx ′ ).

3) Moreover we have

E π g(Z s )f (Z T n+1 )1 {Tn<s<T n+1 } = E π 1 {Tn<s} ∞ s-Tn e -t dt p s-Tn (Z 1 Tn , y)p t-(s-Tn) (y, Z 3 Tn ) u 1 (Z 1 Tn , Z 3 Tn ) g(y, Z 2 Tn , Z 3
Tn )Λ(dy)

1 0 du Q((Z 3 Tn , u), dx ′ )f (Z 3 Tn , u, x ′ ) = E π 1 {Tn<s} e -(s-Tn) p s-Tn (Z 1 Tn , y)u 1 (y, Z 3 Tn ) u 1 (Z 1 Tn , Z 3 Tn ) g(y, Z 2 Tn , Z 3
Tn )Λ(dy)

E (y,Z 2
Tn ,Z 3
Tn ) (f (Z T 1 )) = E π g(Z s )1 {Tn<s<T n+1 } E Zs (f (Z T 1 )) .
4) Using 2) and 3), one shows easily that

E π g(Z s )f (Z s+u )1 {Tn<s<T n+1 <s+u} = E π g(Z s )1 {Tn<s<T n+1 } E Zs (f (Z u ); u > T 1 .
Hence we have the simple Markov property for the process Z. This finishes the proof. • Note that the sequence (T n ) n is no longer independent of the process Z. The T n are the jump times of (Z 2 , Z 3 ) by construction, and(Z 2 t , Z 3 t ) t is constant on every interval [T n , T n+1 [. Note also that we have to keep the second and the third co-ordinates in order to get a real Markov process.

By construction, we have the following properties for the process Z :

Proposition 2.8 a) A := C × [0, α] × E is a recurrent atom for Z in the following sense : Let R := inf{n : Z Tn ∈ A}. Then L(Z T R+1 |Z 1 T R , Z 2 T R
) is given by the measure ν(dx) U (du) Q((x, u), dx ′ ). b) We have equality in law :

L((X Tn ) n≥0 |X 0 = x) = L((Z 1 Tn ) n≥0 |Z 1 0 = x).
c) We have equality in law :

L((X t ) t≥0 |X 0 = x) = L((Z 1 t ) t≥0 |Z 1 0 = x). Proof a) is evident by construction of Z. b) is evident since 1 0 Q((x, u), dx ′ ) = U 1 (x, dx ′ ). c) Fix t > 0.
Let ϕ : E → IR + be measurable and bounded. Then by construction of the process Z, and since Z 1

Tn is F Tn--measurable,

E x [ϕ(Z 1 t )] = n E x [ϕ(Z 1 t )1 {Tn≤t<T n+1 } ] = n E x [E[ϕ(Z 1 t )1 {t<T n+1 } |F Tn-]1 {Tn≤t} ] = n E x 1 0 du Q((Z 1 Tn , u), dx ′ ) ∞ 0 e -s 1 {t-Tn≤s} ds p t-Tn (Z 1 Tn , y) p s-(t-Tn) (y, x ′ ) u 1 (Z 1 Tn , x ′ ) ϕ(y)Λ(dy) 1 {Tn≤t} = n E x ∞ 0
e -s 1 {t-Tn≤s} ds p t-Tn (Z 1 Tn , y)ϕ(y)Λ(dy)

1 {Tn≤t} = n E x E Z 1 Tn (ϕ(X t-Tn ); t -T n ≤ T 1 ) 1 {Tn≤t} = E x [ϕ(X t )],
since Z 1 Tn ∼ X Tn by b). Here, the fourth equality has been obtained using first that

1 0 duQ((Z 1 Tn , u), dx ′ ) = u 1 (Z 1
Tn , x ′ )Λ(dx ′ ) and then integrating against Λ(dx ′ ). The equality of the processes can be shown in a similar way.

• Remark 2.9 Due to proposition 2.8 c), we can identify the process X as first co-ordinate of the process Z. Hence we have imbedded X into a richer prowess Z who possesses a recurrent atom.

For our purpose we do not need the strong Markov property of Z. But it might be interesting to know conditions for Z being strong Markov. We impose the following additional conditions for that sake :

Assumption 2.10 1. The measure Λ is non-atomic.

2. For any t > 0, for any y ∈ E, x → p t (x, y) is continuous.

3. For any T > 0, y ∈ E, for any compact subset K ⊂ E such that y / ∈ K, there exists a constant C, such that sup x∈K sup t≤T p t (x, y) ≤ C.

4.

x → u 1 (x, y) is continuous in x = y and bounded on any compact set K such that y / ∈ K.

We are mainly interested in applications of our method to diffusion models, and in this situation, assumption 2.10 is quite natural :

Example 2.11 Suppose that the process X is a d-dimensional diffusion given as strong solution of the stochastic differential equation

dX t = b(X t )dt + σ(X t )dW t ,
where W is a m-dimensional standard Brownian motion, where b and σ are bounded, having bounded derivatives of any order. Suppose moreover that the diffusion satisfies the uniform Hörmander condition (we refer the reader to [START_REF] Kusuoka | Applications of the Malliavin calculus[END_REF] for details). Then by [START_REF] Kusuoka | Applications of the Malliavin calculus[END_REF], theorem 3.17 and theorem 6.8, condition 2.10 is satisfied.

Theorem 2.12 Under assumptions 2.1 and 2.10, the strong Markov property holds for any stopping time S such that Z 1 S = Z 3 S almost surely. Moreover, Z can be chosen to have càdlàg paths.

Proof Note that due to assumptions 2.1 and 2.10, for any x = x ′ , for any t > 0, the bridge of the process X from X 0 = x to X t = x ′ is Feller. Hence, for any n ≥ 0, (Z 1 Tn+s ) s<T n+1 -Tn can be chosen to have càdlàg paths, and then the trajectories of Z are càdlàg by constuction. Now, let S be any IF -stopping-time such that Z 1 S = Z 3 S almost surely. Let S n be a sequence of stopping times taking values in a countable set such that S n decreases to S as n → ∞. Let f, g ∈ C b (Z) be positive continuous functions, such that x → f (x, u, x ′ ) vanishes at infinity for all fixed u, x ′ , and let s > 0 be a fixed deterministic time. Let f k be a sequence of positive functions such that

f k (x, u, x ′ ) → f (x, u, x ′ )1 {x =x ′ } for any (x, u, x ′ ), as k → ∞, such that f k (x, u, x ′ ) ≤ f (x, u, x ′ )1 {d(x,x ′ )>1/k}
, where d(., .) is the distance on E. Then, due to the simple Markov property,

E π (g(Z Sn )f k (Z Sn+s )) = E π (g(Z Sn )E Z Sn (f k (Z s ))).
(2.6)

Clearly, Z Sn = (Z 1 Sn , Z 2 Sn , Z 3
Sn ) → Z S , by the path properties of Z. Moreover, since (Z 2 , Z 3 ) is piece-wise constant, we have almost surely : There exists some n 0 such that for all n ≥ n 0 , (Z 2 Sn , Z

Sn ) = (Z 2 S , Z 3 S ). Recall that Z 3 S = Z 1 S . 3
Hence we have to show that for any sequence

z n = (x n , u, x ′ ) → z = (x, u, x ′ ) ∈ Z, with x = x ′ , the corresponding expectations E zn (f k (Z s )) converge to E z (f k (Z s ))
. This is seen as follows. By construction of the process,

E zn (f k (Z s )) = E zn (f k (Z s )1 {s<T 1 } ) + E zn (f k (Z s )1 {s>T 1 } ) = ∞ s e -t p t (x n , x ′ ) u 1 (x n , x ′ ) E p s (x n , y)p t-s (y, x ′ ) p t (x n , x ′ ) f k (y, u, x ′ ))Λ(dy)dt + s 0 e -t p t (x n , x ′ ) u 1 (x n , x ′ ) E x ′ (f k (Z s-t ))dt.
The second expression converges, using assumption 2.10 and dominated convergence. Now have a look at the first expression which equals

e -s u 1 (x n , x ′ ) E p s (x n , y)u 1 (y, x ′ )f k (y, u, x ′ )Λ(dy). Now, y → u 1 (y, x ′ )f k (y, u, x ′ ) ∈ C 0 (E)
, the space of all continuous functions vanishing at infinity, due to assumption 2.10 and by construction of f k . Then, due to the Feller property of X,

E p s (x n , y)u 1 (y, x ′ )f k (y, u, x ′ )Λ(dy) = E xn (u 1 (X s , x ′ )f k (X s , u, x ′ )) → E x (u 1 (X s , x ′ )f k (X s , u, x ′ )) = E p s (x, y)u 1 (y, x ′ )f k (y, u, x ′ )Λ(dy).
Then the assertion follows, using againg the continuity of u 1 (x, x ′ ) in x. Passing to the limit n → ∞ in (2.6) then yields

E π (g(Z S )f k (Z S+s )) = E π (g(Z S )E Z S (f k (Z s ))).
Note that almost surely, Z 1 S+s = Z 3 S+s , and

Z 1 s = Z 3 s , hence letting k → ∞, dominated convergence yields E π (g(Z S )f (Z S+s )) = E π (g(Z S )E Z S (f (Z s ))).
•

Life-cycle decomposition in continuous time and applications

From now on, we will interpret X t as first co-ordinate of the process Z. Put

S 0 := 0, R 0 := 0, S n+1 := inf{T m > R n : Z Tm ∈ A}, R n+1 := inf{T m > S n+1 }, n ≥ 0.
We shall write IF X for the filtration generated by X interpreted as first co-ordinate of Z.

We have the following properties : Proposition 2.13 a) For any n ≥ 1, Z Rn+• is independent of G Sn and of F Sn-, and L(Z 1

Rn |G Sn ) = ν. In this sense, the sequence of IF -stopping times R n is a life-cycle decomposition for the process

Z. b) E(R n -S n |F Sn-) ≤ 1 α , for all n ≥ 1.
Proof a) is clear by construction. We show b): Note that necessarily by (2.3), ν ≪ Λ and write ν(dx ′ ) = ν(x ′ )Λ(dx ′ ). Then by assumption, for all

x ∈ C, u 1 (x, x ′ ) ≥ αν(x ′ ), hence ν(x ′ )/u 1 (x, x ′ ) ≤ 1/α. Since Z 1 Sn is F Sn--mesurable, on {Z 1 Sn = x}, E(R n -S n |F Sn-) = E ν(x ′ )Λ(dx ′ ) ∞ 0 te -t p t (x, x ′ ) u 1 (x, x ′ ) dt = ∞ 0 E ν(x ′ ) u 1 (x, x ′ ) p t (x, x ′ )Λ(dx ′ )te -t dt ≤ 1 α ∞ 0 te -t dt = 1 α ,
and this concludes the proof. • Remark 2.14 Note that R n is not a real life cycle-decomposition for X, i.e. X Rn+• is not independent of σ{X s : s < R n }. This is simply the fact by construction : For all t < R n , X t = Z 1 t depends on Z 3 t and X Rn = Z 3 t for S n < t < R n .

The following equality will be useful in what follows :

Proposition 2.15 Let f : E → IR + be a bounded measurable function. Then

E S n+1 Rn f (X s )ds|F Sn = E Z 1 Rn S 1 0 f (X s )ds . (2.7)
Proof We use Markov's property two times, first with respect to F Rn and then in a second step with respect to

F Sn . Since L(Z Rn |Z Sn ) = δ Z 3 Sn (dx)U (du)Q((x, u), dx ′ ), this yields E S n+1 Rn f (X s )ds|F Sn = E E×[0,1]×E L(Z Rn |Z Sn )(dx, du, dx ′ )E (x,u,x ′ ) S 1 0 f (X s )ds = E E Z 3 Sn S 1 0 f (X s )ds = E E Z 1 Rn S 1 0 f (X s )ds , since Z 3 Sn = Z 1 Rn . •
Recall the definition of a special function 2.3. Take f a fixed bounded positive special function of the process X. Such functions exist always, see also remark 2.21. Then we have :

Proposition 2. [START_REF] Kutoyants | Efficient density estimation for ergodic diffusion processes[END_REF] The functions

E ∋ x → E x S 1 0 f (X s )ds and E ∋ x → E x R 1 0 f (X s )ds
are bounded. Moreover, if the following additional assumption holds

sup x,x ′ ∈E ∞ 0 te -t p t (x, x ′ ) u 1 (x, x ′ ) dt < ∞, (2.8)
then also the functions

Z ∋ (x, u, x ′ ) → E (x,u,x ′ ) S 1 0 f (X s )ds and (x, u, x ′ ) → E (x,u,x ′ ) R 1 0 f (X s )ds are bounded.
Example 2.17 The main application we are interested in are diffusion models like described in example 2.11. In such models, condition (2.8) is satisfied. Note that the main problem is the explosion of p t (x, x ′ ) near the diagonal x = x ′ as time t is small, and multiplication with the factor t acts in the "good sense" for our purpose.

Proof First of all put S := inf{T n : n ≥ 1, Z 1 Tn ∈ C}.

(2.9)

Since f is special, we have that

x → E x ∞ 0 e -t 0 h(Xs)ds f (X t )dt = E x ∞ 0 e -t 0 h(Z 1 s )ds f (Z 1 t )dt
is bounded for any positive function h having µ(h) > 0. Now take h = 1 C . Note that by proposition 2.6, S is the first jump time of a Poisson process having jump rate 1 C (Z 1 s ), hence

E x S 0 f (Z 1 s )ds = E x ∞ 0 e -t 0 1 C (Z 1 s )ds f (Z 1 t )dt ,
and this is bounded in x. Now let S1 , S2 , . . . , Sn , . . . be the successive visits of Z 1 Tn to C, i.e. S1 = S, Sn+1 := inf{T m : T m > Sn , Z 1 Tm ∈ C}, S0 := 0. Moreover, write Rn := inf{T m : T m > Sn }, n ≥ 0. Let K be a constant such that

sup x E x S 0 f (Z 1 s )ds ≤ K, sup x f (x) ≤ K, then E x S 1 0 f (Z 1 s )ds = E x ( S1 0 f (Z 1 s )ds) + n≥1 E x Sn+1 Sn f (Z 1 s )ds1 { Sn<S1} ≤ K + n≥1 E x 1 { Sn<S1} KE Z Sn ( R0 ) + E Z Sn S1 R0 f (Z 1 s )ds ≤ K + n≥1 E x 1 { Sn<S1} K 1 -α + E Z 1 Rn S1 0 f (Z 1 s )ds ≤ K + 2K 1 -α n≥1 P x ( Sn < S 1 ),
where we used that

E x (1 { Sn<S1} E Z Sn ( R0 )) ≤ 1 1 -α , since on (x, u) ∈ C×]α, 1], Q((x, u), dx ′ ) = 1 1-α (U 1 (x, dx ′ ) -αν(dx ′ )) ≤ 1 1-α U 1 (x, dx ′ ).
We used an equality in the spirit of (2.7) (with R n and S n replaced by Rn and Sn ) in order to obtain the second inequality. Note that we have to cut the integral over [ Sn , Sn+1 ] into two pieces [ Sn , Rn ] and [ Rn , Sn+1 ], in order to be able to apply (2.7).

Now,

P x ( Sn < S 1 ) = P x ( Sn-1 < S 1 , Z 2 Sn > α),
and then, conditioning with respect to F Sn-1 and using that Z 2 Sn is independent of F Sn-1 , we get inductively in n that

P x ( Sn < S 1 ) = P x ( Sn-1 < S 1 ) • (1 -α) = (1 -α) n . Hence, x → E x S 1 0 f (Z 1 s )ds is bounded. Finally, E x R 1 0 f (Z 1 s )ds ≤ E x S 1 0 f (Z 1 s )ds + KE x (R 1 -S 1 ),
which is still bounded since E x (R 1 -S 1 ) ≤ 1/α. This yields the first assertion.

Moreover, write z := (x, u, x ′ ). Then

E z S 1 0 f (Z 1 s )ds ≤ K • E z (T 1 ) + E z S 1 T 1 f (Z 1 s )ds ≤ K sup z E z (T 1 ) + E x ′ S 1 0 f (Z 1 s )ds ,
where we used once more the formula (2.7). Note that

E z (T 1 ) = ∞ 0 te -t p t (x, x ′ ) u 1 (x, x ′ ) dt,
and this is bounded using assumption (2.8). Finally, E x ′ S 1 0 f (Z 1 s )ds is bounded, using the first part of the proof.

•

We are now able to formulate Chen's inequality (compare to [START_REF] Chen | The law of the iterated logarithm for functionals of Harris recurrent Markov chains: Self Normalization[END_REF], lemma 1, (2.4)) for the process Z. This is the main result of this section.

Theorem 2.18 Suppose that assumption 2.1 is satisfied. Take a fixed positive, bounded µ-integrable special function f of X. Let π be an arbitrary initial measure. Then we have for any fixed s > 0,

E π t 0 f (X u )du1 { t 0 f (Xu)du≥s}
(2.10)

≤ P π ( t 0 f (X u )du ≥ s)[C + s + E ν ( t 0 f (X u )du)].
Here, C is a constant that depends on the special function f such that

sup x E x R 1 0 f (X u )du + sup x f (x) ≤ C.
Proof Write A t := t 0 f (X s )ds and put σ s := inf{t : A t ≥ s}. Then

E π t 0 f (X u )du1 { t 0 f (Xu)du≥s} = E π (A t ; σ s ≤ t) ≤ sP π (σ s ≤ t) + E π ( t σs f (X u )du; σ s ≤ t).
But, using the Markov property of X with respect to F σs (recall that the original process X is strong Markov!), we get

E π ( t σs f (X u )du; σ s ≤ t) ≤ E π E Xσ s t 0 f (X u )du ; σ s ≤ t . (2.11)
In order to evaluate E Xσ s t 0 f (X u )du, we now use the splitting technique inside the expectation E Xσ s and interpret X u as first co-ordinate of Z. Hence,

E Xσ s t 0 f (X u )du = E Xσ s t 0 f (Z 1 u )du ≤ E Xσ s R 1 0 f (Z 1 u )du + t R 1 f (Z 1 u )du1 {R 1 <t} .
The two integrals in the last expression will be treated separately: First of all, using the property of the special function (see proposition 2.16), we get immediately that

E Xσ s R 1 0 f (Z 1 u )du ≤ C.
Moreover,

E Xσ s t R 1 f (Z 1 u )du1 {R 1 <t} ≤ E Xσ s E Z R 1 t 0 f (Z 1 u )du = E ν t 0 f (Z 1 u )du, since Z 1 R 1 ∼ ν.
Replacing this in (2.11) yields the result.

•

As a corollary of Chen's inequality, we get the existence of deterministic equivalents for additive functionals of the process:

Corollary 2.19 Grant assumption 2.1. Let g be a fixed special function of X with µ(g) > 0, fix some probability m and put

v t := E m t 0 g(X s )ds.
Then for any other µ-integrable function h with µ(h) > 0 and any probability measure π,

lim M →∞ lim inf t→∞ P π v t /M ≤ t 0 h(X s )ds ≤ v t • M = 1.
Proof Let f be the fixed special function of theorem 2.18 and suppose w.l.o.g. that µ(f ) > 0. Then due to (2.10),

P π t 0 f (X s )ds ≥ v t /M ≥ E π t 0 f (X u )du/v t -1/M C/v t + 1/M + E ν t 0 f (X s )ds/v t .
Then, by the strong Chacon-Ornstein theorem, and since

v t → ∞ as t → ∞, lim M →∞ lim inf t→∞ P π t 0 f (X s )ds ≥ v t /M = 1.
Moreover, by Markov's inequality and the strong Chacon-Ornstein theorem,

P π t 0 f (X s )ds > v t • M ≤ E π t 0 f (X s )ds v t M → µ(f ) M µ(g) as t → ∞,
and then the assertion follows letting tend M → ∞.

The general assertion follows then by the ratio limit theorem, since

t 0 h(X s )ds t 0 f (X s )ds → µ(h) µ(f )
almost surely as t → ∞. • Sometimes, the following equality will be useful :

Proposition 2.20 Let f : E → IR + be a measurable function such that µ(|f |) < ∞.
Then, up to multiplication by a constant,

E ν R 1 0 f (X s )ds = Cµ(f ),
where the constant C depends only on the process, not on f.

Proof For n ≥ 1, let ξ n := R n+1 Rn f (X s )ds. As usual, we interpret X as first co-ordinate of Z. Then ξ 0 , ξ 2 , ξ 4 , . . . , ξ 2n are i.i.d., and the same is true for ξ 1 , ξ 3 , ξ 5 , . . . . Hence by the strong law of large numbers,

lim n Rn 0 f (X s )ds n = lim n ξ 0 + ξ 2 + . . . n + ξ 1 + ξ 3 + . . . n = E ν R 1 0 f (X s )ds (2.12)
almost surely. Now, let g be another µ-integrable function such that µ(g) > 0, then the ratio limit theorem gives

lim n Rn 0 f (X s )ds Rn 0 g(X s )ds = µ(f ) µ(g) ,
on the other hand, by (2.12),

lim n Rn 0 f (X s )ds Rn 0 g(X s )ds = E ν R 1 0 f (X s )ds E ν R 1 0 g(X s )ds , thus the assertion, putting C := (E ν R 1 0 g(X s )ds)/µ(g).
•

Note that we use heavily the existence of special functions all over this section. So we close this section with some remarks on special functions.

Remark 2.21 Any positive measurable function f is called special for the discrete chain X (defined at the beginning of section 2.2), if

x → E x ∞ n=1 (1 -h( X1 ) • • • (1 -h( Xn-1 )f ( Xn )
is bounded in x for any bounded, positive measurable function h such that µ(h) > 0 (see [START_REF] Revuz | Markov chains[END_REF]). Now, by [START_REF] Höpfner | Limit theorems for null recurrent Markov processes[END_REF], (5.29), page 59, we know that

E x ∞ n=1 (1 -h( X1 ) • • • (1 -h( Xn-1 )f ( Xn ) = E x ∞ 0 e -t 0 h(Xs)ds f (X t )dt . (2.

13)

As a consequence, any special function of the chain X is also a special function of the process X and vice versa.

The following is a direct consequence of (2.13) and of a known result of [START_REF] Revuz | Markov chains[END_REF], exercice 4.11, chapter 6, page 215:

Corollary 2.22 Suppose that the transition operator P t of X is strongly Feller. Then any positive bounded function f having compact support is special.

Proof By dominated convergence, since P t is strongly Feller, also the transition kernel U 1 = ∞ 0 e -t P t dt of X is strongly Feller. Then by [START_REF] Revuz | Markov chains[END_REF], all positive bounded functions having compact support are special for X, hence for X.

•

3 Application to kernel estimation in multi-dimensional diffusion models

Let X be a diffusion process in dimension d given as solution of the following stochastic differential equation

dX t = b(X t )dt + σ(X t )dW t , (3.14)
where b : IR d → IR d and σ : IR d → IR d×m are supposed to be bounded, such that a strong solution to (3.14) exists, and where W is a m-dimensional standard Brownian motion.

We assume the following:

Assumption 3.1
1. X is recurrent in the sense of Harris with invariant measure µ.

2. The invariant measure admits a continuous Lebesgue density p which is strictly positive everywhere: µ(dx) = p(x)λ(dx), where λ denotes Lebesgue's measure on IR d .

3. The transition semi group of the diffusion satisfies assumption 2.1 and condition (2.8) with Λ(dx) = λ(dx).

Example 3.2 Note that assumption 3.1, 3. is satisfied if the diffusion is elliptic, and if b and σ are bounded, having bounded derivatives of any order, see for instance [START_REF] Williams | To begin at the beginning[END_REF], page 5, and [START_REF] Kusuoka | Applications of the Malliavin calculus[END_REF].

Remark 3.3 a) A one-dimensional diffusion dX t = b(X t )dt + σ(X t )dW t
is Harris recurrent with invariant measure equivalent to Lebesgue's measure if the function

S(x) := x 0 s(y)dy, s(y) = exp(- y 0 2b σ 2 (v)dv) satisfies lim x→-∞ S(x) = -∞, S(0) = 0, lim x→∞ S(x) = ∞,
see for example the monograph of Has'minskii, [START_REF] Has'minskii | Stochastic stability of differential equations[END_REF]. See also Khasminskii, [START_REF] Khasminskii | Asymptotic behaviour of parabolic equations arising from onedimensional null recurrent diffusions[END_REF] and [START_REF] Khasminskii | Limit distributions for some integral functionals for null recurrent diffusions[END_REF], for more concrete examples of null recurrent one-dimensional diffusions, and Höpfner and Kutoyants, [START_REF] Höpfner | On a problem of statistical inference in null recurrent diffusions[END_REF], for a statistical study of parametric and semiparametric models of onedimensional null recurrent diffusions. b) Conditions of recurrence for multi-dimensional diffusions are much less studied (and much more difficult). We refer the reader to Bhattacharya, see [START_REF] Bhattacharya | Criteria for Recurrence and Existence of Invariant Measures for Multidimensional Diffusions[END_REF], who gives some generalisations of the above criterion to the multi-dimensional case.

We observe trajectories of the diffusion continuously in time. Our aim is to estimate the unknown drift function b at some fixed point x 0 ∈ IR d . As usual, we assume a smoothness property at x 0 , i.e. a Hölder condition of the following kind:

sup x∈[x 0 -δ,x 0 +δ] |b(x) -b(x 0 )| • |x -x 0 | -α ≤ γ, (3.15)
for some δ, γ > 0 and some fixed α ∈ (0, 1).

We will use a Nadaraya-Watson type kernel estimator: Let ϕ be a kernel, i.e., ϕ is a continuous positive function having compact support such that IR d ϕ(x)dx = 1. For any bandwidth h > 0, put ϕ h (y) := ϕ(

P π (r t | bt -b(x 0 )| > K) = 0.
(3.17)

Corollary 3.7 Let g be a fixed special function of the diffusion, i.e. a bounded function having compact support. Put

V t := t 0 g(X s )ds, R t := V α 2α+d t .
Then (3.6) remains true when replacing r t by R t , which is an observable quantity.

Proof This follows immediately from the fact that V t /v t is bounded in probability, see corollary 2.19.

•

In the sequel, we are going to give a proof of this theorem.

Preliminaries

We start with some results that will be needed later. First of all, we have a kind of uniform version of the Chacon Ornstein theorem. Proof The proof is given in several steps. This is shown as follows: Using proposition 2.20, we have

E π Rt 0 ϕ ht (X s )f (X s )ds = E π ( R 1 0 ϕ ht (X s )f (X s )ds) + n≥1 E π (1 {Sn≤t} R n+1 Rn (ϕ ht f )(X s )ds) = E π ( R 1 0 ϕ ht (X s )f (X s )ds) + E π (N t )E ν ( R n+1 Rn (ϕ ht f )(X s )ds) = E π ( R 1 0
ϕ ht (X s )f (X s )ds) + E π (N t )µ(ϕ ht f ),

where we used that X Rn+• is independent of {S n ≤ t}.

Now note that due to our assumptions, ϕ is of compact support. Write C := ||ϕ|| ∞ and write I := 1 x 0 +h 0 supp(ϕ) . Then we can write that ϕ ht (X s )f (X s ) ≤ C h d t ||f || 0 I(X s ), where ||f || 0 is the supremum of the continuous function f on x 0 + h 0 supp(ϕ). As a consequence, using that I is a special function,

E π ( R 1 0 ϕ ht (X s )f (X s )ds) ≤ C h d t ||f || 0 sup x E x R 1 0 I(X s )ds,
and this tends to zero after having divided bw v t since h d t v t → ∞. Moreover, E π (N t )/v t converges to a constant depending only on the process and on g, the function used in order to build v t . Hence This gives (3.18).

2.

We have

E π Rt 0 ϕ ht (X s )f (X s )ds -E π t 0 ϕ ht (X s )f (X s )ds = E π Rt t ϕ ht (X s )f (X s )ds = E π E Zt R 1 0 ϕ ht (X s )f (X s )ds ≤ C||f || 0 1 h d t E π (E Zt R 1 0 I(X s )ds) ≤ C||f || 0 sup z E z R 1 0 I(X s )ds 1 h d t ,
where z = (x, u, x ′ ), and this tends to zero after having divided by v t since h d t v t → ∞. This finishes our proof.

•

The following theorem is the main theorem of this section and gives some kind of uniform existence of a deterministic equivalent.

Proposition 3 . 8 1 v t E π t 0 ϕ

 3810 Let f be a positive, bounded, continuous function. Thenlim t→∞ ht (X s )f (X s )ds = c p(x 0 )f (x 0 ),for some constant depending only on the choice of C and α and of the function g of corollary 2.19.

1 .ϕ

 1 We start by showing the following result:Let N t := n≥1 1 {Sn≤t} . Put R t := t+R 1 •∂ t = inf{R n : R n > S Nt+1 }. Then we have lim ht (X s )f (X s )ds = c p(x 0 )f (x 0 ). (3.18)

  ht (X s )f (X s )ds v t = lim t→∞ E π (N t ) v t • lim t→∞ µ(ϕ ht f ) = c p(x 0 )f (x 0 ).

  y-x 0 h )/h d . Let v t be the deterministic equivalent of X of 2.19 and let h t := v Note that the definition of our estimator makes use of the knowledge of v t . However, v t is not observable, so the definition of this estimator is only of theoretical interest for the moment. If one restricts attention to sub-models, for example to the sub-model of ergodic diffusions (where v t could be replaced by t) or the sub-model of null recurrent diffusions where one has regular variation at 0 of resolvents of the diffusion (and in this case v t can be replaced by t α /l(t)), then the definition of the estimator makes perfectly sense.Note that due to remark 2.21, all positive bounded functions having compact support are special functions of the diffusion. As a consequence, any of the functions ϕ ht is special. Moreover, we have the following: Remark 3.5 The set C of condition (2.3) can be chosen to be compact. As a consequence, 1 C is a special function.

	Remark 3.4 E x	0	∞	e -1 t s g(X s )ds ∼ t α 1 l(t)	µ(g),
	as t → ∞ α
				2α+d t	and let π be an arbitrary initial
	measure. Then r t is an upper rate of convergence, i.e.
	lim K→∞	lim sup t→∞
	-1 2α+d
				, where we define	a 0	:= 0.	(3.16)

t ∧ δ → 0 as t → ∞. Note that h d t v t → ∞. We define bt := t 0 ϕ ht (X s )dX s t 0 ϕ ht (X s )ds Proof Since µ(C) > 0 and since µ ∼ λ, by the properties of Lebesgue's measure, C must contain a compact set of positive measure. Then it suffices to replace C in (2.3) by this compact set. Again, thanks to remark 2.21, all positive bounded functions having compact support are special functions. Hence 1 C is special. • Then the following is our main theorem: Theorem 3.6 Suppose that p(x 0 ) > 0. Let r t := v

  and then the assertion follows thanks to proposition 3.8. Moreover, as in the proof of 3.8, there exists a constant independent of t, such that ht (X s )ds/v t .Now write at := E π t 0 ϕ ht (X s )ds/v t and b t := E ν t 0 ϕ ht (X s )ds/v t .Then we know by proposition 3.8, since p(x 0 ) > 0, that lim t→∞ a t = lim t→∞ b t > 0, hence

	Theorem 3.9 We have
	lim M →∞ ϕ ht (X Proof First of all, lim inf t→∞ P π 1 M ≤ t 1 v t 0
	P π	0	t	ϕ ht (X s )ds > M v t ≤ ϕ sup 1 M t 1 v t E π 0 z E z R 1 0 ϕ( X s -x 0 h t )ds < C.
	Then we have, applying Chen's inequality (2.10),
	P π	vt M ≤ t 0 ϕ ht (X s )ds = P π	v t h d t M	≤	0	t	ϕ(	X s -x 0 h t	)ds
			≥ 0 ϕ lim inf E π t 0 ϕ C vth d t + 1/M + E ν t t→∞ P π v t M ≤ t 0 ϕ ht (X s )ds ≥ lim a t -1 M 1 M + lim b t	,
	and the assertion follows, letting tend M → ∞.

s )ds ≤ M = 1. ht (X s )ds , ht (X s )ds/v t -1/M •

We have the following corollary of theorem 3.9:

Corollary 3.10 We have lim K→∞ lim inf t→∞ P π (-K ≤ t 0 ϕ( Xs-x 0 ht )σ(X s )dW s h d t v t ≤ K) = 1.

and then the assertion follows from proposition 3.8. •

Proof of theorem 3.6

We are now able to give the proof of theorem 3.6:

Let t be sufficiently large such that x 0 +h t suppϕ ⊂ [x 0 -δ, x 0 +δ] and such that

By construction, h α t r t = 1. Hence the assertion follows from theorem 3.9 and from corollary 3.10.