Ngoc Nguyen
email: ngoc-chan.nguyen@loria.fr

Chan

Nattawat Nonsung
email: nattawat.nonsung@siteminder.com

Walid Gaaloul
email: walid.gaaloul@mines-telecom.fr

Service Querying to Support Process Variant Development

Keywords: service composition, service-based business process, process variant, service querying, composition context matching

Developing process variants enables enterprises to effectively adapt their business models to different markets. Existing approaches focus on business process models to support the variant development. The assignment of services in a business process, which ensures the process variability, has not been widely examined. In this paper, we present an innovative approach that focuses on component services instead of process models. We target to recommend services to a selected position in a business process. We define the service composition context as the relationships between a service and its neighbors. We compute the similarity between services based on the matching of their composition contexts. Then, we propose a query language that considers the composition context matching for service querying. We developed an application to demonstrate our approach and performed different experiments on a public dataset of real process models. Experimental results show that our approach is feasible and efficient.

Introduction

Variability has been considered as a key factor that enables software systems to be extended, changed, customized, or configured for use in a specific context [START_REF] Sinnema | Classifying variability modeling techniques[END_REF][START_REF] Sinnema | Covamof: A framework for modeling variability in software product families[END_REF]. Enterprises or organizations usually need to support variability to adapt their business models to different markets. For example, car rental companies, such as Hertz, Avis or Sixt, need to customize their reservation process to follow laws in a country or culture of a region. Suncorp, one of the largest Australian insurance group, has developed more than 30 different variants of the process of handling an insurance claim [START_REF] Van Der Aalst | Intra-and inter-organizational process mining: Discovering processes within and between organizations[END_REF].

In service-based process modeling and execution, variability plays an important role as it enables a dynamic environment in which services can be replaced or reconfigured to adapt to different circumstances [START_REF] Sun | Modeling and managing the variability of web service-based systems[END_REF]. It not only supports the development of business process variants, but also brings out several advantages in process configuration. Concretely, it enhances system availability (by replacing an unavailable service by another), supports runtime configuration (by rebinding services at runtime), optimizes performance (by service replacement if necessary) or optimizes the quality attributes (by changing the configuration of the system) [START_REF] Sun | Modeling and managing the variability of web service-based systems[END_REF][START_REF] Koning | Vxbpel: Supporting variability for web services in bpel[END_REF]. Two contexts that require service variability include: finding alternatives of a service in a business process (see Figure 1a) and retrieving adequate services that can be plugged into some selected positions (see Figure 1b). These requirements have raised research challenges in service matching and querying. These challenges are amplified by the continuous increasing of the number of services and process models along with the maturity of business process management [START_REF] Dumas | Fast detection of exact clones in business process model repositories[END_REF][START_REF] Dijkman | managing Large Collections of Business Process Models Managing Large Collections of Business Process Models[END_REF]. Early approaches focus on service characteristics to support service discovery. Some of them analyze service descriptions [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Platzer | A vector space search engine for web services[END_REF][START_REF] Blake | A web service recommender system using enhanced syntactical matching[END_REF][START_REF] Ma | Web services discovery based on latent semantic approach[END_REF], study the QoS of services [START_REF] Zheng | Wsrec: A collaborative filtering based web service recommender system[END_REF][START_REF] Jiang | An effective web service recommendation method based on personalized collaborative filtering[END_REF][START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF], while others are based on semantic concepts [START_REF] Manikrao | Dynamic selection of web services with recommendation system[END_REF][START_REF] Paolucci | Semantic matching of web services capabilities[END_REF][START_REF] Wu | Latent semantic analysis -the dynamics of semantics web services discovery[END_REF][START_REF] Paliwal | Web service discovery: Adding semantics through service request expansion and latent semantic indexing[END_REF]. Different methods in information retrieval, data mining and artificial intelligence domains have been experimented, such as collaborative filtering [START_REF] Platzer | A vector space search engine for web services[END_REF][START_REF] Zheng | Wsrec: A collaborative filtering based web service recommender system[END_REF][START_REF] Jiang | An effective web service recommendation method based on personalized collaborative filtering[END_REF][START_REF] Wu | Latent semantic analysis -the dynamics of semantics web services discovery[END_REF], associated rules [START_REF] Kokash | Web service discovery based on past user experience[END_REF][START_REF] Birukou | Improving web service discovery with usage data[END_REF][START_REF] Birukou | Ic-service: A service-oriented approach to the development of recommendation systems[END_REF], clustering [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Ma | Web services discovery based on latent semantic approach[END_REF][START_REF] Elgazzar | Clustering wsdl documents to bootstrap the discovery of web services[END_REF], divide and conquer [START_REF] Ma | Web services discovery based on latent semantic approach[END_REF]. In contrast, recent approaches pay much attention on business process models. Instead of retrieving services, they attempt to evaluate the behavior equivalence of services in business processes [START_REF] Weidlich | The icop framework: identification of correspondences between process models[END_REF][START_REF] Weidlich | Behaviour equivalence and compatibility of business process models with complex correspondences[END_REF], compare process models [START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF][START_REF] Yan | Fast business process similarity search with feature-based similarity estimation[END_REF][START_REF] Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF][START_REF] Dijkman | A classification of differences between similar business processes[END_REF][START_REF] Li | On measuring process model similarity based on high-level change operations[END_REF][START_REF] Dongen | Measuring similarity between business process models[END_REF][START_REF] Ehrig | Measuring similarity between semantic business process models[END_REF], develop configurable process models [START_REF] Rosemann | A configurable reference modelling language[END_REF][START_REF] Rosa | Configurable multi-perspective business process models[END_REF][START_REF] Van Der Aalst | Configurable services in the cloud: supporting variability while enabling cross-organizational process mining[END_REF], or build a query language that supports searching for execution paths in business processes [START_REF] Awad | Bpmn-q: A language to query business processes[END_REF][START_REF] Awad | Semantic querying of business process models[END_REF][START_REF] Awad | Efficient compliance checking using bpmn-q and temporal logic[END_REF][START_REF] Sakr | A framework for querying graph-based business process models[END_REF][START_REF] Sakr | Partial process models to manage business process variants[END_REF].

In this paper, we address the research problem of finding suitable services for selected positions in a business process. We propose an approach that takes into account service composition context, which is defined as relations between a given service and its neighbors. These relations are exposed by sequences of flows and connection elements between them, i.e., AND, OR, XOR, etc. They are labeled by the names of services and connection elements. We take existing process models as input in order to learn from the past design. We exploit the knowledge acquired for previous designed process to infer service similarity. Concretely, we present the service composition context as a graph in which the considered service is positioned at the center. We compute the similarity between services based on the matching of their context graphs. We also propose a query language as a tool to search for similar services.

It is worthy to notice that the service composition context can be represented by any of existing process modeling languages, such as Petri net, UML diagram, EPC, BPMN and YAWL [START_REF] Sakr | Partial process models to manage business process variants[END_REF]. Business process ontology [START_REF] Hepp | An ontology framework for semantic business process management[END_REF] and semantic annotation [START_REF] Di Francescomarino | Reasoning on semantically annotated processes[END_REF][START_REF] Dimitrov | A bpmo based semantic business process modelling environment[END_REF] can also be applied. The most importance issue is that the relation between services, which is defined as sequences of connection elements, is represented. In our approach, we use BPMN and graph theory to model the service composition context as they are one of the most popular tools for process modeling [START_REF] Ko | Business process management (bpm) standards: a survey[END_REF] and suitable for service relation formalization.

The objective of our approach is twofold: (i) to propose a new approach for the computation of similarity between component services in servicesbased processes and (ii) to provide a useful query tool for process variant development. By identifying adequate services for selected positions, our approach not only supports the process creation during the design time, but also enables the service configuration during the runtime.

The work presented in this paper is an extension of our previous work [START_REF] Chan | Querying services based on composition context[END_REF], in which the composition context is improved to take into account parallel relations between services and similarity between connection elements. Richer experiments and deeper discussion are also provided.

Our paper is organized as follows. The next section presents a motivating example. Section 3 introduces definitions and notations. Detail of the service similarity computation is presented in section 4. A query language is proposed in section 5. An implementation and different experimental results are shown in section 6. Section 7 presents related work. Finally, section 8 concludes our work and provides an outline on the future work.

Motivating Example

Consider a travel agency. Suppose that they have had in their information system two business process models named 'flight-reservation' and 'hotel-reservation', which correspond to flight and hotel booking functions (see Figure 2). The travel agency decides to design a new process to offer a new train booking function. The process designer can rapidly sketch out the trainreservation process with some basic services as shown in Figure 3. Suppose that he is looking for a service, which is annotated by a round-corner rectangle with a '?' symbol. This requested service has to fulfill some composition constraints, such as: it has to be executed before 'Process payment' and/or executed after 'Present alternatives' and/or has similar connection flows with the missing position, etc.

Existing approaches, such as text-matching mechanism and process equivalence, are not applicable for this inquiry as they do not provide a way to express composition constraints. Text-matching approaches do not consider the interactions between services in business processes.Whereas, processquerying approaches return similar process models instead of services. In this case, our approach can be applied as it focuses on the composition context around services. Concretely, it detects that the 'unknown' service has similar context with the 'Request customer detailed Info.', 'Request customer basic Info.' and 'Request credit card Info.' in the existing flight & hotel reservation processes (Figure 2) because they have similar connections from/to the same services, which are 'Present alternatives' and 'Process payment'. So, we recommend these services for the missing position and the process designer may select the 'Request credit card Info.' service for this position as it is the most suitable (Figure 4). We provide also a query language which allows the process designer to express his requests with flexible constraints (see details in section 5). By querying services based on composition context, our approach not only assists the process designer during the design time (completing a model or developing new process variants) but also helps to guarantee the completion of business process instances during the execution time by finding alternatives of a service in case of failure.

Preliminaries

In this section, we present some notations and definitions that are used to formally define a business process (section 3.1) and the composition context of a service (section 3.2). We also explain how we handle loop cases (section 3.3). We use the 'train-reservation' process (Figure 3) and the 'flight-reservation' process (Figure 2) to illustrate our approach.

Business Process Graph

As the structure of a business process can be mapped to a graph, we choose graph theory to present a business process. Indeed, there are a number of graph-based business process modeling languages, e.g., BPMN, EPC, YAWL, and UML activity diagram. Despite their variances in expressiveness and modeling notations, they all share the common concepts of tasks, events, gateways, artifacts and resources, as well as relations between them, such as transition flows [START_REF] Sakr | Partial process models to manage business process variants[END_REF]. In our approach, we use BPMN in our approach to present business processes as it is one of the most popular business process modeling language.

We consider termination events (such as start or end events) as termination services. We define a connection element as either a connecting object (e.g., sequence flow and message flow), or a gateway (e.g., AND-split, OR-split), or an intermediate event (e.g., error message, message-catching) (Figure 5). For example, in Figure 3, s 1 , a 1 , a 2 , e 1 are services; and 'flowtransition', 'event-based-gateway' and 'message-catching' are connection elements. Although services and connection elements in our approach are defined using BPMN notations, they are easily mapped to equivalent notations in other business process modeling and workflow languages, e.g., tasks and workflow control patterns [START_REF] Van Der Aalst | Business process management: A survey[END_REF]. Relations between services in a business process are presented by the execution orders between them. In our previous work [START_REF] Chan | Querying services based on composition context[END_REF], we considered only the causal relation between services, i.e., a service is situated next to another service (such as connection between a 5 and a 2 or a 2 and a 7 in Figure 2). In this work, we improve our definitions to take into account both causal and parallel relations, i.e., the relations between services that belong to parallel flows, e.g. relation between a 7 and a 6 in Figure 2.

: connection elements

Let A P be the set of services and C P be the set of connection elements in a business process P . Definition 3.1 (next relation). Let e i , e j ∈ A P ∪C P . A next relation e i to e j , denoted by e i → P e j , indicates that e j follows e i in P . Definition 3.2 (connected relation). Let e i , e j ∈ A P ∪C P . e i is connected to e j in P , denoted by e i ↔ P e j , iff e i → P e j or e j → P e i .

Definition 3.3 (connection flow).

A connection flow from a i to a j , a i , a j ∈ A P , denoted by

a j a i f P , is a sequence of connection elements c 1 , c 2 , . . . , c n ∈ C P satisfying: a i ↔ P c 1 , c 1 ↔ P c 2 , . . . , c n-1 ↔ P c n , c n ↔ P a j . a j a i f P ∈ C * P , C * P is set of sequences of connection elements in P 1 .
Definition 3.4 (connected relation label). The label of a connected relation e i ↔ P e j , e i , e j ∈ A P ∪C P , denoted by l(e i ↔ P e j ), is defined as following:

l(e i ↔ P e j ) =    e i e j ,
if e i → P e j e j e i , if e j → P e i Definition 3.5 (connection flow label). The label of a connection flow a j a i f P , denoted by l( a j a i f P ), is defined as following:

l( a j a i f P ) = l(a i ↔ P c 1 ).l(c 1 ↔ P c 2 ) . . . l(c n-1 ↔ P c n ).l(c n ↔ P a j )
where c 1 , c 2 , . . . , c n ∈ C P :

a j a i f P = c 1 c 2 . . .c n .
For example, the label of the connection flow from 'Search flights' to 'Present alternatives' in Figure 2 is: a 5 'sequence'.'sequence'a 2 ; from 'Present alternatives' to "Request customer detailed Info." is: a 2 'event-based-gateway'. 'event-based-gateway''message-catching'.'message-catching''parallel-split'. 'parallel-split'a 7 .

We notice that:

• An edge connecting two services a i , a j ∈ A P can be labeled by either l( a j a i f P ) or l( a i a j f P ). For example, the edge connecting a 5 to a 2 in Figure 2 can be labeled by l( a 2 a 5 f P )=a 5 'sequence'.'sequence'a 2 or l( a 5 a 2 f P )= 'sequence'a 2 .a 5 'sequence'.

• There can be more than one connection flow between two services. For instance, in the case that two services are connected by an AND-split and an AND-join (parallel relation). In this case, we number these connection flows to distinguish them. For example, there are two connection flows from a 7 to a 6 in Figure 2 and we number them as follows: l( a 6 a 7 f 1 P )='parallel-split'a 7 .'parallel-split'a 6 and l( a 6 a 7 f 2 P )=a 7 'synchronization'.a 6 'synchronization'.

We consider each service as a node, each connection flow as an edge. We define business process as a multigraph, in which, set of edges is a multiset (Definition 3.6). Definition 3.6 (Business Process graph). A business process graph of P is an undirected labeled multigraph G P = (V P , E P , L P , l) in which V P is a set of nodes, E P is a multiset of edges, L P is a set of edge labels, and l is a mapping function that maps edges to labels, where:

• V P = A P ,
• E P ⊆ A P × A P , g , g : A P × A P -→ N g((a i , a j )) is the multiplicity of (a i , a j ). If g((a i , a j )) > 1, the edges connecting a i to a j are numbered by (a i , a j ) t , t = 1..k, k > 1.

• L P = l(E P ), where:

l : E P -→ L P (a i , a j ) → l( a j a i f P ) , if g((a i , a j )) = 1 (a i , a j ) t → l( a j a i f t P ) , if g((a i , a j )) = k > 1, t = 1..k
For example, the business process graphs of the 'train-reservation' process (Figure 3) and the 'flight-reservation' process (Figure 2) are presented in Figure 6. Edges:

Nodes:

Figure 6: Business process graphs of the 'train-reservation' process (Figure 3) and the 'flight-reservation' process (Figure 2)

Service Composition Context

We define the composition context of a service as a business process fragment that includes the associated service and the closest relations to its neighbors. A composition context is presented as a graph in which the associated service is located at the center. Its neighbors are located in layers according to their shortest path lengths to the associated service. The composition context of a service can be considered as a business fragment that presents the behavior of the associated service.

We present in the following some definitions that are used to formally define the composition context. Definition 3.7 (connection path). A connection path from a i to a j in a business process graph G P , denoted by a j a i P P , is a sequence of services a 1 , a 2 , . . . , a k where a 1 = a i , a k = a j and ∃( a t+1 at f P ∈ C

* P ∨ at a t+1 f P ∈ C * P ) ∀1 ≤ t ≤ k -1.
According to Definition 3.7, a connection path in a business process graph is undirected. It means that the edges in a connection path can be oriented in different directions. For example, in Figure 2, a connection path from 'Search flights' (a 5 ) to 'Request customer detailed Info.' (a 7 ) can be either 'a 5 , a 2 , a 7 ' or 'a 5 , a 2 , a 6 , a 7 ' or 'a 5 , a 2 , a 6 , a 3 , a 7 ', etc. Definition 3.8 (connection path length). The length of a connection path a j a i P P , denoted by L( a j a i P P ) is the number of connection flows in the path. Definition 3.9 (shortest connection path). The shortest connection path between a i and a j , denoted by a j a i S P , is the connection path between them that has the minimum connection path length.

For example, in Figure 2, the shortest path from a 5 to a 7 is 'a 5 , a 2 , a 7 ' and its length is 2. Definition 3.10 (k th -layer neighbor). a j is a k th -layer neighbor of a i in a business process P iff ∃ a j a i P P : L( a j a i P P ) = k. The set of k th -layer neighbors of a service a i is denoted by N k P (a i ). N 0 P (a i ) = {a i }. For example in Figure 2, s 2 and a 2 are the 1 st -layer neighbors of a 5 ; a 5 , e 3 , a 7 and a 6 are the 1 st -layer neighbors of a 2 ; a 6 is one of the 2 nd -layer neighbors of a 5 and so on.

As the distance from a service a i to its k th -layer neighbors is k, we can imagine that the k th -layer neighbors of a service a i are located on a circle whose center is a i and k is the radius. The circle is latent since it exists but it is not explicitly represented in the business process graph. We call this latent circle connection layer and the area limited by two adjacent latent circles connection zone. Connection layers and connection zones of a service are numbered. A connection flow connecting two (k -1) th -layer neighbors, or a (k -1) th -layer neighbor to a k th -layer neighbor is called a k th -zone flow (Definition 3.11).

Definition 3.11 (k th -zone flow). av au f P is a k th -zone flow of a i iff ∃ av au f P : (a u , a v ∈ N k-1 P (a i )) ∨ (a u ∈ N k-1 P (a i ) ∧ a v ∈ N k P (a i )) ∨ (a v ∈ N k-1 P (a i ) ∧ a u ∈ N k P (a i )).
The set of all k th -zone flows of a service a i ∈ P is denoted by

Z k P (a i ). Z 0 P (a i ) = ∅ and |Z k P (a i )| is the number of connection flows in the k th connection zone of a i .
For example in Figure 2, the connection from a 2 to a 7 is the 2 nd -zone flow of a 5 while the connection from a 7 to a 3 is its 3 rd -zone flow. |Z 2 P 2 (a 5 )| = 3 as in the 2 nd -zone of a 5 , there are three connection flows, which are from a 2 to a 6 , a 7 and e 3 .

Intuitively, the connection paths between two services present their relation in term of closeness. The longer the connection path is, the weaker their relation is and the shortest connection path between two services presents their best relation. To illustrate the best relations of a service to others services in a business process, we define the service composition context graph (formally defined in Definition 3.12) which presents all the shortest paths from a service to others. Each service in a business process has a composition context graph. Each vertex in the composition context graph is associated to a number which indicates the shortest path length of the connection path to the associated service. The vertexes that have the same shortest path length value are considered to have the same distance to the associated service and are located on the same layer around the associated service. We name the number associated to each service in a composition context graph the layer number. The area limited between two adjacent layers is called zone. The edge connecting two vertexes in a composition context graph belongs to a zone. We assign to each edge in the composition context graph a number, so-called zone number, which determines the zone that the edge belongs to.

The edge connecting two services a i , a j in the composition context graph of a service a x is associated to a zone number such that: if a i and a j are located on two adjacent layers, the edge (a i , a j ) will belongs to the zone limited by the two adjacent layers; and if a i and a j are located on the same layer, the edge connecting them belongs to the outer zone of the layer they are located on.

Concretely, assume that e ij is the edge connecting two vertexes a i and a j in the composition context graph of a service a x . The lengths of the shortest connection paths connecting a i and a j to a x are l 1 = L( ax a i S P ) and l 2 = L( ax a j S P ) respectively. Let d = |l 1 -l 2 |, d has only two possible values, which are 0 and 1 (see our proofs [46], section A). In the case that d = 0 (l 1 = l 2 ), i.e., a i and a j are both l th 1 -layer neighbors of a x , we assign to e ij l 1 + 1 as zone value. In the case that d = 1, i.e., a i and a j belong to two adjacent layers, e ij is the k th -zone flow connecting a i and a j and we assign to e ij the zone value k, i.e., min(l 1 , l 2 ) + 1. Consequently, we assign to the connection flow connecting a i and a j in the composition context graph of a x the value M in( L( ax a i S P ), L( ax a j S P )) + 1. The maximum zone value of all connection flows in the context graph of a x will be M ax(L( ax at S P )) + 1 ∀a t ∈ P . In any linked business process graph, we can always calculate the shortest path length between two services. Therefore, in the composition context graph of a service, we can always identify the layers on which services are located. Consequently, we can always assign layer number to a service and thus, zone number, to a connection flow in a composition context graph. Definition 3.12 (Composition context graph). The composition context graph of a service a x ∈ P , denoted by G ax P = (V ax P , E ax P , L P , l), is an undirected labeled multigraph created from G P = (V P , E P , L P , l). V ax P is a set of vertexes associated to their layer numbers and E ax P is a set of edges associated to their zone numbers. V ax P and E ax P are defined as following: -

V ax P = {(a i , L( ax a i S P )) : a i ∈ V P } -E ax P = {(< (a i , a j ), g((a i , a j )) >, a j a i z ax P ) :< (a i , a j ), g((a i , a j )) >∈ E P , a j a i z ax P = M in(L( ax a i S P ), L( ax a j S P )) + 1}
For example, the composition context graphs of the 'unknown' service (a x in Figure 3) and the 'Request credit card Info.' (a 6 in Figure 2) are presented in Figure 7. In these graphs, all causal and parallel flow relations are presented.

Loop Cases

There are three typical loop cases in a business process: self-loop, loop via another service and loop via other services. By applying Definition 3.12, the possible layers to which the loop services can belong are depicted in Figure 8. In the self-loop case (Figure 8a), if a service a i is located on the k th -layer, then its self-loop edge belong to the zone (k + 1) th because according to Definition 3.12, the zone number of this edge is a i a i z ax P = M in(L( a i ax S P ), L(

a i ax S P ))+ 1 = M in(k, k) + 1 = k + 1.
In the loop-via-another-service case (Figure 8b), there are two possibilities: (i) the two services are located on adjacent layers (e.g., a j and a i ) and (ii) the two services are located on the same layer (e.g., a i and a h ). In the first possibility, assume that a i and a j are respectively located on the (k -1) thlayer and k th -layer, the edges connecting them are assigned the zone number

a j a i z ax P = a i a j z ax P = M in(L( a i ax S P ), L( a j ax S P )) + 1 = M in(k -1, k) + 1 = k, i.
e., they are on the zone limited by these adjacent layers. In the second possibility, assume that a i and a h are located on the same k th -layer, the edges connecting them are assigned the zone number a h a i z ax P = a i a h z ax P = M in(L( a i ax S P ), L( a h ax S P )) + 1 = M in(k, k) + 1 = k + 1, i.e., they are presented on the outer zone of the layer where the services are located.

In the loop-via-other-services case (for example, Figure 8c shows the loop created by 3 services), the edges between services are assigned their zone numbers following Definition 3.12. For the two services located on adjacent layers (e.g., a j and a i , or a j and a h in Figure 8c), the edge connecting them belongs to the zone limited by these layers. For the two services located on the same layer (e.g., a i and a h in Figure 8c), the edge connecting them belongs to the outer zone of their layer.

So, in any business process graph, including graphs that contain loops, we can always calculate the shortest path length between two services. Therefore, in the composition context graph of a service, we can always identify the layers on which rest services are located. Consequently, we can always assign a layer number to a service and thus, a zone number to a connection flow, in a composition context graph.

Composition Context Similarity

The k th -zone neighbors of a service and their connection flows create a process fragment around the associated service. This fragment contains the business context that reflects the behavior of the associated service. In this section, we present our methodology to compute the matching between two composition contexts. We firstly present how we match two connection flows (section 4.1). Then, we elaborate the matching between two composition contexts (section 4.2). Finally, we show how we integrate the similarity between connection elements into our composition context similarity computation (section 4.4).

To illustrate the computation process, we will consider the composition context of the 'unknown' service in the 'train-reservation' process (a x in Figure 3) and the 'Request credit card Info.' service in the 'flight-reservation' process (a 6 in Figure 2). The composition context graphs of these services are shown in Figure 7.

Connection Flow Matching

To compute the matching between two connection flows, we propose to use the Levenshtein distance (LD for short) [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. In information theory, the LD is a metric for measuring the difference between two sequences of characters. The LD is defined as the minimum number of edits needed to transform one sequence of characters into the other, with the allowable edit operations being insertion, deletion, or substitution of a single element. For example, the LD between "gumbo" and "gambol" is 2, between "kitten" and "sitting" is 3, etc. Inspired by this, we consider each connection element in a connection flow as a character and we label connection flows as a sequence of characters. Then, the similarity between two connection flows can be computed based on the similarity of their labels using LD.

Let st 1 = l( av au f P 1 ), st 2 = l( an am f P 2 ). Let Dif f be a function that computes the difference between two connection flows. We have:

M ( av au f P 1 , an am f P 2 ) = 1 - Dif f (st 1 , st 2 ) M ax(length(st 1 ), length(st 2 )) (1)
where:

• Dif f (st 1 , st 2 ) = LD(l( av au f P 1 ), l( an am f P 2 )), if (a u = a m ) ∧ (a v = a n ) • Dif f (st 1 , st 2 ) = LD(l( av au f P 1 ), l( am an f P 2 )), if (a u = a n ) ∧ (a v = a m ) • Dif f (st 1 , st 2 ) = M ax(length(st 1 ), length(st 2 )), i.e., M ( av au f P 1 , an am f P 2 ) = 0, in other cases.
For example in Figure 7, we have M p ( a 4 a 3 f P 1 , a 4 a 3 f P 2 ) = M ("a 3 S.Sa 4 ", "a 3 S.Sa 4 ") = 1 -0 4 = 1; M p ( a 2 a 1 f P 1 , a 2 a 5 f P 2 ) = 0 and so on. We prove that LD of two strings is equal to LD of their inverse strings (see our proofs [46], section B). So, whatever the edges (a u , a v ) and (a m , a n ) are labeled by l( av au f P 1 ) or l( au av f P 1 ) and l( an am f P 2 ) or l( am an f P 2 ), Equation 1gives the same value.

In the case that there is more than one connection flow between two services, we compute all possible matching between them and we select the best matching value.

Composition Context Matching

To compute the composition context matching between two services, we propose to sum up the matching of the connection flows in the two contexts. There are two cases to consider: the first zone and other zones. In the first zone, we match the connection flows that connect the two associated services and same services in the first layer. In other zones, we match the connection flows that connect the same services. We sum all matching values then divide them by the number of connection flows in the considered zones of the first service.

We apply Equation 1 to compute the composition context matching in either the first and other zones. However, Equation 1 considers only connection flows that connecting the same services in two business processes. So, to adapt it in the first zone, we assume that the two associated services have the same name, so-called a 0 . Then, we match connection flows connecting a 0 to the same services in the first layer.

Formally, let a i , a j are two associated services. We change a i , a j to a 0 . Then, ∀a c ∈ N 1 P 1 (a i ) ∩ N 1 P 2 (a j ), we compute the similarity between ac a i f P 1 and ac a j f P 2 based on the similarity between ac a 0 f P 1 and ac a 0 f P 2 . Basically, the composition context matching between a i ∈ P 1 and a j ∈ P 2 within k zones, denoted by MC k (G a i P 1 , G

a j P 2 )
, is computed by Equation 2.

MC k (G a i P 1 , G a j P 2 ) = k t=1 av au f P 1 ∈Z t P 1 , an am f P 2 ∈Z t P 2 MF t ( av au f P 1 , an am f P 2 ) k t=1 |Z t P 1 (a i )| (2)
where k is the number of considered zones, |Z t P 1 (a i )| is the number of connection flows in the t th zone of G a i P 1 , and MF t ( av au f P 1 , an am f P 2 ) is the matching value of av au f P 1 and an am f P 2 in zone t:

MF t ( av au f P 1 , an am f P 2 ) =                M ( av au f P 1 , an am f P 2 ) if          t = 1, (a u = a m ) ∨ (a v = a n ) ∨(a u = a v ∧ a m = a n ) t = 1, (a u = a m ∧ a v = a n ) 0 other cases
For example, the composition context matching between a x and a 6 (Figure 7) computed by Equation 2 is:

MC 3 (G ax P 1 , G a 6 P 2 ) = M ( ax a 2 f P 1 , a 6 a 2 f P 2 ) + M ( ax e 1 f P 1 , a 6 e 3 f P 2 ) + M ( a 3 ax f P 1 , a 3 a 6 f P 2 ) +M ( e 1 a 2 f P 1 , e 3 a 2 f P 2 ) + M ( a 4 a 3 f P 1 , a 4 a 3 f P 2 ) + M ( e 2 a 4 f P 1 , e 4 a 4 f P 2 ) 3 + 3 + 2 = 3 4 + 4 5 + 1 2 + 1 + 1 + 1 8 = 0.63

Zone Weight

The behavior of a service is strongly reflected by the connection flows to its closet neighbors while the interactions with other neighbors in the further layers do not heavily reflect its behavior. Therefore, we propose to assign a weight (w t ) for each t th connection zone, so called zone-weight and integrate this weight into the similarity computation. Since the zone-weight has to have greater values in smaller t th connection zone, we propose a zone-weight value computed by a polynomial function which is

w t = k + 1 -t k
, where t is the zone number (1 ≤ t ≤ k) and k is the number of considered zones around the service. All connection flows connecting the associated service have the greatest weight (w 1 = 1) and the connection flows connecting services in the furthest zone have the smallest weight (w k = 1 k ). Then, the composition context matching between G a i P 1 and G a j P 2 within k zones and with zone weight, denoted by MW k (G a i P 1 , G

a j P 2 )
, is given by Equation 3.

MW k (G a i P 1 , G a j P 2 ) = 2 k + 1 × k t=1 k + 1 -t k × av au f P 1 ∈Z t P 1 an am f P 2 ∈Z t P 2 MF t ( av au f P 1 , an am f P 2 ) |Z t P 1 (a i )| (3)
where:

MF t ( av au f P 1 , an am f P 2 ) =                M ( av au f P 1 , an am f P 2 ) if          t = 1, (a u = a m ) ∨ (a v = a n ) ∨(a u = a v ∧ a m = a n ) t = 1, (a u = a m ∧ a v = a n ) 0 other cases
For example, the composition context matching between a x and a 6 (Figure 7) computed by Equation 3 is:

MW 3 (G ax P 1 , G a 6 P 2 ) = 2 3 + 1 × ( 3 3 × M ( ax a 2 f P 1 , a 6 a 2 f P 2 ) + M ( ax e 1 f P 1 , a 6 e 3 f P 2 ) + M ( a 3 ax f P 1 , a 3 a 6 f P 2 ) 3 + 2 3 × M ( e 1 a 2 f P 1 , e 3 a 2 f P 2 ) + M ( a 4 a 3 f P 1 , a 4 a 3 f P 2 ) 3 + 1 3 × M ( e 2 a 4 f P 1 , e 4 a 4 f P 2 ) 2 ) = 2 4 × ( 3 3 × 3 4 + 4 5 + 1 2 3 + 2 3 × 1 + 1 3 + 1 3 × 1 2 ) = 0.65

Similarity Between Connection Elements

Connection elements serve as fundamental factors to specify execution constraints and dependencies between services. For example, a sequence specifies a causal relation, an AND-split specifies a parallel execution, an OR-split specifies a choice, etc. The connection elements can show common execution behavior such as sequential, concurrent, choice, etc. So, their behaviors are not totally different. For example, consider two services a i and a j that can be connected by: (1) a 'sequence' or (2) an 'AND-split'. The two connection elements are different, however, they have common execution behavior, which is: a j is executed right after a i .

In the previous sections (4.2 and 4.3), we consider that the matching between two connection elements has only two values: 0 (in the case that they do not have the same type) and 1 (in the case that they have the same type). In this section, we propose a metric to compute the similarity between connection elements in terms of execution properties. This metric allows evaluating their similarity by a real value between 0 and 1.

We firstly identify matching rules that the similarity has to satisfy (section 4.4.1). Then, we present our proposition to compute the similarity between typical connection elements (section 4.4.2). Finally, we describe how to integrate the computed similarity into the composition context matching (section 4.4.3).

Matching Rules

In our work, we deal with basic connection elements, which are sequence, AND, OR and XOR as they are commonly used in business processes. Other elements and complex gateways are not considered. However, the same principles and methodology can be applied.

We present our analysis on the '-split' elements, including AND-split, OR-split and XOR-split. A '-split' connection element consists of one input and multiple output flows. The similarities between '-join' elements can be inferred with the same reasoning.

To compute the similarity between connection elements, we firstly specify three matching rules that our approach satisfies, which are:

x If two connection elements are identical, their similarity is 1.

For example, similarity of two 'sequence' is 1; similarity of two 'ANDsplit' elements is 1 and so on.

y Similarity between two connection elements that have the same types but different number of output flows is 1. Similarity between two different connection elements is less than 1. For example, similarity between two 'AND-split' elements that have different number of output flows is 1 whereas similarity between an 'AND-split' and an 'OR-split' is less than 1. z In the case that two connection elements are different, the less different the numbers of output flows are, the greater similarity value is. For example, consider the matching between an 'AND-split' that has 2 output flows and two 'OR-split' that have respectively (1) 2 output flows and (2) 3 output flows. The similarity value of the 'AND-split' and the first 'OR-split' must be higher than the similarity value of the 'AND-split' and the second 'OR-split'.

Similarity Computation

Connection elements indicate the number of possible execution cases. The number of possible execution cases is impacted by the type of the connection element and the number of output flows derived by the connection element.

In our approach, we analyze the number of possible execution cases and compute the similarity between connection elements based on the probability that an output flow is executed.

Consider the case where two services a i and a j are connected by a connection element c. The connection flow from a i to a j is notated by a j a i f = c. c can be a sequence, an 'AND-split', an 'OR-split' or an 'XOR-split'.

We call a case that satisfies the constraints of a connection element a 'possible execution case' or a 'possible case' in short. For example, if c is a 'sequence', it has only one possible execution case, in which the service following c is executed; if c is an 'AND-split', it also has one possible execution case in which all services pointed by the output flows of c are executed; but if c is an 'OR-split', it has multiple execution cases: 'at least one of the services pointed by output flows needs to be executed'.

Let x, y and z be the number of output flows that an 'AND-split', an 'OR-split' and an 'XOR-split' respectively have. The numbers of possible cases of these connection elements are given in the 4 th column of Table 1. The last column of Table 1 presents the probabilities that an output flow is executed. We explain in the following how we compute these values.

For the 'sequence' and 'AND-split' cases, there is only one possible execution case, in which all services are executed. Hence, the probability that Element Presentation No. paths No. possible cases

Probability that an output flow is executed Sequence

a i a j 1 1 1
AND-split

a i a j 1 x x 1 1
OR-split

a i a j y 1 y 2 y -1 2 y-1 2 y -1 XOR-split a i a j z 1 z z 1 z
Table 1: Probability that a j appears in the possible cases an output flow is executed is 1.

For the 'OR-split' case, the execution is completed if at least one of y services in the y output flows is executed. The number of cases where at least one of y services is executed is 2 y -1. On the other hand, the number of possible cases where an output flow is 'executed' is 2 y 2 = 2 y-1 . So, the probability that an output flow is executed is 2 y-1 2 y -1 . For the 'XOR-split' case, for z output flows, there are z possible execution cases. Therefore, the probability that an output flow is executed is 1 z . To compute the similarity between these connection elements, we propose to combine the weight of an output flow and the probability that it is executed. The weight of an output flow is specified by the inverse number of output flows. For example, consider an 'AND-split' that derives 3 output flows. The weight of each output flow is 1 3 . Consequently, the similarity between two connection elements c u and c v , denoted by S(c u , c v ), is given as following:

S(c u , c v ) = w * cu × w * cv × P + cu × P + cv ( 4
)
where w * (c u ), w * (c v ) are respectively weights of an output flow of c u and c v ; P + cu and P + cv are probabilities that an output flow of c u and c v is executed. The similarities between aforementioned connection elements are given in Table 2. In the section C of our proofs [46], we prove that the similarities computed by our approach satisfy the aforementioned matching rules.

Similarity

Sequence AND-split(x) OR-split(y) XOR-split(z)

Sequence 1 1 × 1 x × 1 × 1 1 × 1 y × 1 × 2 y-1 2 y -1 1 × 1 z × 1 × 1 z AND-split(x) 1 1 x × 1 y × 1 × 2 y-1 2 y -1 1 x × 1 z × 1 × 1 z OR-split(y) 1 1 y × 1 z × 2 y-1 2 y -1 × 1 z XOR-split(z) 1
Table 2: Similarities between typical connection elements For example, with x = 2, y = 3, z = 4, S(AND-split,sequence)=0.5, S(OR-split,sequence)=0.19, S(XOR-split,sequence)=0.06, S(AND-split,ORsplit)=0.10, S(AND-split,XOR-split)=0.03 and S(OR-split,XOR-split)=0.01.

Integration into the Composition Context Matching

The composition context matching is computed from the matching of connection flows (section 4). A connection flow is a sequence of connection elements that connect two services (Definition 3.3). It can contain one or more connection elements. We propose to integrate the similarity between connection elements in the case where connection flows contain only one connection element. For example, consider two connection flows ay ax f P 1 and av au f P 2 of two composition context graph G a i P 1 and G a j P 2 . Assume that they are located on the same connection zone and connect the same ending services. Each of them contains only one connection element, which is c and c respectively. Similarity between them is inferred by the similarity between the connection elements, which is computed by Equation 4.

In the case that connection flows contain more than one connection element, we transform them to strings of characters and reuse Levenshtein distance to compute their similarity (section 4.1).

As the similarity between connection elements is applied to compute the similarity of connection flows, it impacts on the final result of the composition context matching. In our experiments, we analyze matching cases with and without the similarity between connection elements to assess its impact.

Service Querying

Each service in a business process has a composition context which presents the relations between the service and its neighbors. By matching composition contexts, we can find services that have similar relations to common neighbors. In this section, we present a query language used to retrieve relevant services to a selected position in a business process (section 5.1) and its execution (section 5.2).

Query Grammar

The query in our approach not only helps to search for relevant services based on a given composition context but also allows adding constraints to filter the searching results. It consists of three parameters, which are: an associated service, connection constraints, and a radius. The associated service is the service whose composition context is considered to be matched with other contexts. Connection constrains are services or connection flows to be included/excluded to filter the query's results. The radius is the number of connection layers taken into account for the composition context matching. It specifies the largeness of the considered composition contexts.

We present in the following our proposed query grammar using the Extended Backus-Naur Form (EBNF)2 [START_REF] Wirth | What can we do about the unnecessary diversity of notation for syntactic definitions?[END_REF]. We use ';' to separate the input parameters; '(' and ')' to separate query's constrains; '<' and '>' to group services or connection flows; '[' and ']' to separate a connection flow and its ending services. We use '+' and '-' signs to include/exclude constraints; and '|' sign for multiple choice operator. Details of the grammar are presented in Table 3.

1.

Query ::= ServiceID,':',[Constraint],':',Radius;

= 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'; 11. DigitNotZero ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
12.

Digit ::= '0' | DigitNotZero; The query grammar is explained as follows:

• The query is defined in line 1 with three parameters separated by ':'. The constraint is optional. It can be defined to filter the query result. It can also be absent if we want to execute only the composition context matching without filtering.

• In line 2, the service identifier is defined as a string of characters or digits. It has to start by a character.

• In line 3, we define constraints. A constraint can be an included/excluded service or a connection flow. It can also include different items and operators. Operators in a constraint can be OR, INCLUDE, EXCLUDE. We use '|', '+' and '-' to specify these operators. Consequently, we define a constraint as a 'Term' or another constraint with '|' operator.

• In line 4 we define a 'Term' as an 'Item' or another constraint with the '+' and '-' operators.

• The 'Item' is defined in line 5. It can be a service or a connection flow that is included/excluded in the query. It can also be another constraint which is grouped by '(' and ')'. Definitions in line 3, 4 and 5 allow specifying a constraint with multiple services, connection flows, operations and grouped conditions.

• In line 6, we define a connection flow which is presented within '<' and '>' signs. It includes a string of connection elements connecting two services.

• The string of connection elements is defined in line 7. It includes at least a connection element which is defined in line 8.

• In line 9, we define the radius as a natural number greater than 0.

• Finally, lines 10, 11, 12 define literal characters and digits.

Examples of our query are given in Table 4. These queries are used to find services that have composition contexts similar to the composition context of s x . These composition contexts are limited to 3 layers. In Table 4, we also explain the concerned constraints used to filter the query result. In our motivating example (Figure 3), as the designer wants to find services whose composition contexts are similar to a x , he selects a x as the associated services. Then, he can specify two constraints as follows: [START_REF] Sinnema | Classifying variability modeling techniques[END_REF] the queried service should be executed right after 'Present alternatives' (a 2 ) and before 'Process payment' (a 3 ) and (2) it is connected from a 2 by a connection flow 'event-based-gateway''message-catching' and to a 3 by a 'sequence'. Finally, he specifies the radius, which is 1 in this case, because he wants to find the contexts in which a 2 and a 3 are connected directly to a x . Consequently, his query is:

Query Explanation

a x :+<a 2 ['event-based-gateway''message- catching']>+<[sequence]a 3 >:1.
More examples about our query can be given as follows. If the process designer wants to find services that have similar context to 'Search trains' (a 1 ) within the first zone, he can make a query as following: a 1 ::1. If he wants to find services that are similar to 'Search trains' but not followed by 'Present alternatives', he will exclude the connection flow connecting 'Search trains' to 'Present alternatives' in its first layer. The query will be: a 1 :-(<a 1 [sequence]a 2 >):1. In the case that he wants to know possible payment methods, he may select 'Process payment' service (a 3 ) and add a constraint which does not include a 'sequence' that connects to 'Send confirmation' service (a 4 ). He can also widen the considered composition context in two layers to get more results. So, his query is: a 3 :-(<['sequence']a 4 >):2. Or, if he wants to find services that are similar to 'Search trains' (a 1 ), and include the services 'Request payment Info.' (a 8 ) and 'Process payment' (a 3 ) but exclude the AND-join connection between them, his query is as follows: a 1 :+a 8 +a 3 -(<a 8 ['AND-join']a 3 >):5, etc.

Query Execution

In general, queries are processed as follows:

1. We capture the composition context of the associated service. The largeness of the composition context is specified by the radius parameter. 2. We match the composition context of the associated service to composition contexts of other services in other processes. 3. We refine the matching result by selecting only services whose composition contexts satisfy the query's constraints. 4. We sort the selected services based on the matching values and pick up top-N services3 for the response.

Implementation & Experiments

In this section, we present our implementation (section 6.1) and experiments (section 6.2) to validate our approach.

Implementation

To demonstrate our approach, we implemented an application that allows the process designer to create business processes and get recommendations during the design phase. Our application was developed based on Signavio4 , which is a platform for business process design. This platform provides a web-based graphical interface to design business processes. By developing our approach based on Signavio, we achieve two targets: (1) we propose a user-friendly tool through the graphical suite and (2) we widen the user community and make our approach visible as Signavio is widely known in the community. Our tool is published at http://www-inf. it-sudparis.eu/SIMBAD/tools/WebRec/. In this application, the process designer can design and store business processes. During the design, he can select a service and process a query. He needs to specify the number of layers/zones needed to be taken into account and choose an algorithm to be executed. The composition context matching is executed beforehand. Then, query constraints are applied on the matching result to filter unrelated services. Queries and their results can be saved and reloaded for a future use.

A screen-shot of the application is shown in Figure 9. The areas 1, 2 and 3 show the BPMN elements for design, canvas and property of the selected element. They are provided by the Signavio platform. We developed the areas 4, 5, and 6. Area 4 contains the buttons for launching the context matching and query, area 5 shows the list of previous queries and area 6 displays either the query design or its results.

A basic scenario6 is as follows:

1. A process designer opens the application to design a new process. He can also load an existing process for editing. 2. During the design, he can select a service, create a query, and specify the number of layers (or zones) needed to be taken into account for the composition context matching. 3. He can select to run one of 4 prepared algorithms 7 . 4. The application executes the query and returns results. When the designer selects a service from the result, it shows the corresponding process in which the selected service is highlighted. 5. The designer can copy services from the returned process and paste them on the active canvas to continue his design. 6. He can save the executed query for future usage. He can also load, modify and executed a saved query.

Experiments

We performed experiments on a large public collection of business processes. Our goal is three fold: (i) to evaluate the feasibility of our approach;

(ii) to measure its accuracy and to (iii) evaluate the performance of our algorithm. Details of the dataset and experiments are given as following.

Dataset & Experimental Cases

The dataset used in our approach is shared by the Business Integration Technologies (BIT) research group8 of the IBM Zurich [START_REF] Fahland | Instantaneous soundness checking of industrial business process models[END_REF]. It contains business process models designed for financial services, telecommunications, and other domains. It is presented in XML format following BPMN 2.0 standard. Each XML file stores the data of a business process, including elements' IDs, service names, and the sequence flows between elements. The dataset consists of 560 business processes with 6363 services. There are 3781 different services in which 1196 services appear in more than one process. In average, there are 11.36 services, 18.96 gateways (including parallel, exclusive and inclusive gateways) and 46.81 sequence flows in a process.

We performed experiments to measure the feasibility, the accuracy and the performance of our approach. We evaluate the feasibility based on the number of services whose matching values with others are greater than a given threshold. We also observe the impact of the number of selected zones (k th -zone number) and zone weight on the number of returned services. We evaluate the accuracy based on the Precision and Recall and we evaluate the performance based on the computation time.

Our algorithm was experimented with 5 different cases which are presented in Table 5. In Case 1, we considered only the zone-weight. The parallel flow relations and connection element similarity were not taken into account in the composition context matching. In Case 2, we considered only the parallel relations, regardless the zone-weight and connection element similarity. Case 3 took into account both parallel flow relations and zone-weight, whereas Case 4 considered parallel relations and connection element similarity. In Case 5, the algorithm was performed with all parameters above.

In our previous work [START_REF] Chan | Querying services based on composition context[END_REF], we presented some preliminary results of the first case, which considers only zone weight and consecutive relations between services. In this work, apart from the additional results of the first case, we present and discuss about the experimental results of the other cases which take into account parallel relations between services and similarity between connection elements. In the first experiment, we aim at evaluating the feasibility of the approach and the impact of parameters. The feasibility is evaluated based on the number of services that can have recommendations. Figure 10 shows the percentages of services whose matching values with other services are greater than or equal to 0.5. It shows that cases 2, 3, 4, 5, which take into account the parallel flow relations, retrieve greater number of services than case 1. The zone-weight parameter has no impact in the first zone. Hence, with k = 1, case 2 and case 3 has the same number of services (similar to case 4 and 5). However, with k = 2, the number of services and similarity values decreased. Case 3 and case 5, which take into account zone weight in their computation, retrieve more services than case 2 and case 4 respectively. It means that zone weight impacts on the number of retrieved services. When we take into account zone weight, we retrieve more services. Similarly, the similarity between connection elements impacts on the number of retrieved services. When we take into account similarity between connection elements (case 4 and case 5 compared to case 2 and case 3 respectively), we retrieve more services. Case 5, which takes into account both zone-weight and connection element similarity, retrieves the highest number of services.

In this experiment, we obtained 77.7% services whose matching values are greater than 0 and 21.48% services whose matching values are greater than 0.5. In the worst cases, we obtained 61.3% services whose matching values are greater than 0 and 8.57% services whose matching values are greater than 0.5. These results show that our approach can provide recommendations for a majority services as we can retrieve similar services for more than 2/3 number of services in average. It means that our approach is feasible and can be applied in real use-cases. To examine the impact of k th -zone values, we run our algorithms with k from 5 to 1. The experimental results (Figure 11) show that when k decreases, the number of recommended services increases. It is because when k decreases that the number of unmatched services in further layers decreases, the matching values between composition contexts increase, the number of services increases.

This experimental results also show that zone-weight and similarity between services impact on the number of retrieved services. Cases 3 and case 5, which take into account zone-weight, has more services than case 2 and 4 respectively. Similarly, cases 4 and 5, which take into account similarity between services, has more services than case 2 and 3 respectively. When we take into account the parallel flow relations between services, many services located on the further layers of a composition context graph are relocated on the nearer layers. Therefore, the matching values in the first zone are high and these values decrease quickly when we consider further zones. Figure 11 shows that in Cases 2, 3, 4 and 5, which take into account parallel flow relations, the number of services is very low with great k and very high with small k. Meanwhile, in Case 1, the number of services slightly change when k decreases.

-Algorithms accuracy :

Our approach is based on service composition context regardless the identifier of the considered service. The identifier of a service is used just for determining the associated composition context. In this experiment, we aim at using it as the ground-truth data for the Precision and Recall computation. Our objective in to assess how accurate is our approach when it is used to recommend services for an empty position in a process. To do so, for a selected service in a process, we consider this service as an unknown service. We compute recommendations for this selected position. A relevant recommendation should contain the selected service.

Concretely, consider a selected service s in a process P . Assume that s appears in n processes. The recommendations for this selected position consist of l services, in which t(t ≤ l) services are s. Precision and Recall of these recommendations are given by Equation 5.

P recision = t l ; Recall = t n (5)
In our experiment, we tune the number of recommended services for each position from 5 to 1. We consider the matching in the first zone. To ignore the noise of the irrelevant processes, we compute Precision and Recall for only the services that appear in at least 10 business processes. Consequently, 29 services and 267 processes are used in our experiment.

The average Precision and Recall values are shown in Figure 12. The Precision and Recall values of the examined cases are not so different, as the different parameters that distinguish these cases has a slight impact if we consider just the the first zone (as explained in the previous section). The Precision values increase when the number of recommended services decreases. This means that the relevant services mostly appear at the top of the recommendation list. In other words, when we shorten the recommendation list, the recommendations generated by our approach are more focused and precise.

Currently, there are few approaches [START_REF] Lincoln | Machine-assisted design of business process models using descriptor space analysis[END_REF][START_REF] Lincoln | Searching business process repositories using operational similarity[END_REF] that consider the matching between services in processes. They however they use the matching results to search for relevant processes. In addition, they do not provide experiments with Precision and Recall values. So, we can not compare the accuracy of our approach to their experiment. Instead, we consider the random case, where a system recommends randomly services for a selected position. We compare the simplest case of our approach, which make recommendations without considering the concurrent relation and similarity between connection elements, with the random case. Figure 13 shows the result of our experiment. In this experiment, we make recommendations randomly for each service which appears in at least 10 business processes and compute the average Precision and Recall values. Figure 13 shows that the worst result of our approach is still much better than the best result of the random case (with 5 recommended services, our approach achieves 10.01 times higher Precision value and 20.62 times higher Recall value).

-Algorithms performance :

We performed all experiments on a computer running Ubuntu 11.10 with configuration: Pentium 4 CPU 2.8GHz, cache 512KB, RAM 512MB, HDD 80GB. We evaluated the performance of our algorithms by the computation time.

We measure the time that each algorithm consumes to perform the matching between a service and all other services in the dataset. Figure 14 shows the average computation time of all algorithms in the case that the k th -zone value is 3. In average, our algorithms spend less than 2 seconds to compute the matching between a service and the other 6362 services. This means that these algorithms have acceptable computation time as they can make recommendations in a very short time by considering a large number of services. The result also shows that Case 1, which does not take into account parallel flow relations, is the least time-consuming. Other cases, which consider more parameters, are more time-consuming. To shorten the response time for recommendations, the matching computation in our approach can be done offline. On synthesis, the statistics on the number of recommended services showed that our approach is feasible. The Precision and Recall values showed that our approach is accurate. Finally, experiments on the computation time showed that our approached is of good performance.

Related Work

Approaches supporting service querying have focused on the text matching between the query string and service descriptions [START_REF] Platzer | A vector space search engine for web services[END_REF][START_REF] Blake | A web service recommender system using enhanced syntactical matching[END_REF][START_REF] Wu | Latent semantic analysis -the dynamics of semantics web services discovery[END_REF]. Some of them clustered services [START_REF] Dong | Similarity search for web services[END_REF][START_REF] Ma | Web services discovery based on latent semantic approach[END_REF], or examined the quality of services [START_REF] Yu | Efficient algorithms for web services selection with end-to-end qos constraints[END_REF][START_REF] Zheng | Wsrec: A collaborative filtering based web service recommender system[END_REF][START_REF] Jiang | An effective web service recommendation method based on personalized collaborative filtering[END_REF], whereas others relied on the service semantic descriptions [START_REF] Manikrao | Dynamic selection of web services with recommendation system[END_REF][START_REF] Paolucci | Semantic matching of web services capabilities[END_REF][START_REF] Paliwal | Web service discovery: Adding semantics through service request expansion and latent semantic indexing[END_REF]. These approaches have exploited explicit knowledge exposed by services themselves, e.g., text-based description, and/or communication environment, e.g., throughput or response time. They have not yet considered the business context into which services are integrated. In our approach, we complement this existing work by exploiting the composition context around each service.

Recent research on querying to support process design and execution pays much attention on business process models. To support the design, a query language, named BPMN-Q, has been proposed [START_REF] Awad | Semantic querying of business process models[END_REF][START_REF] Sakr | A framework for querying graph-based business process models[END_REF][START_REF] Sakr | Partial process models to manage business process variants[END_REF]. This language allows retrieving partial process fragments that start from a given activity (corresponding to service in our approach) and end by another given activity. To support the execution, Momotko et. al. [START_REF] Momotko | Process query language: A way to make workflow processes more flexible[END_REF] proposed a query language to retrieve the status of service instance during the process execution time. Meanwhile, Beeri et. al. [START_REF] Beeri | Querying business processes[END_REF][START_REF] Beeri | Monitoring business processes with queries[END_REF][START_REF] Beheshti | A query language for analyzing business processes execution[END_REF] proposed a query language and Balan et al. [START_REF] Balan | Bp-ex: a uniform query engine for business process execution traces[END_REF] proposed a tool for business process monitoring. Different from them, our approach can be applied in both design and execution phases. We compute the similarity between composition contexts instead of the perfect matching of service names and their connections. We allow including/excluding services and connection flows. In addition, we exploit the relations between services in the design instead of the attributes of a service instance.

Deutch et. al. [START_REF] Deutch | Querying structural and behavioral properties of business processes[END_REF] were inspired by [START_REF] Beeri | Querying business processes[END_REF] and proposed a model for querying the structural and behavioral properties of business processes. While [START_REF] Deutch | A structural/temporal query language for business processes[END_REF] proposed a query language for process specifications and Markovic et. al [START_REF] Markovic | Querying in business process modeling[END_REF] proposed an ontoloty-based framework for process querying. In our approach, we focus on the service's 'behavior', i.e., relations between services, instead of the process 'behavior', and we match the service (composition context) graphs instead of the process graphs.

Other approaches that aim at facilitating the process design without building a query language include business process searching [START_REF] Yan | Fast business process similarity search with feature-based similarity estimation[END_REF][START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF] and process similarity measuring [START_REF] Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF][START_REF] Li | On measuring process model similarity based on high-level change operations[END_REF][START_REF] Ehrig | Measuring similarity between semantic business process models[END_REF][START_REF] Guentert | Evaluation measures for similarity search results in process model repositories[END_REF][START_REF] Dijkman | A classification of differences between similar business processes[END_REF][START_REF] Dongen | Measuring similarity between business process models[END_REF][START_REF] Kunze | Behavioral similarity: A proper metric[END_REF][START_REF] Wang | A behavioral similarity measure between labeled petri nets based on principal transition sequences[END_REF]. Their objective is to help the process designer find similar processes to a selected process. Related to them, our work also helps to facilitate process design. However, instead of comparing process models, we focus on comparing services in process models.

The concept of composition context has been introduced in our previous work [START_REF] Chan | Querying services based on composition context[END_REF][START_REF] Chan | Composition context matching for web service recommendation[END_REF], in which we consider only the consecutive relation between services. In this work, we upgrade our model to take into account both consecutive and parallel relations. We also evaluate the similarity between connection elements and examine its impact on the context matching. Finally, we develop a context free grammar language and graphical user interface application for service querying. Richer experimental results of different matching cases have been also provided and analyzed.

Conclusion

In this paper, we present a service recommendation approach that takes into account existing process models for assisting the development of process variants. We introduce the service composition context and propose an algorithm to compute the similarity between services. We also evaluate the similarity between connection elements and measure its impact on the composition context matching. A query language is also proposed as a useful tool for service querying.

Our approach is autonomic and independent. It can be combined with other approaches for better matching or filtering. Indeed, there are rationales and benefits behind the service composition context as it informs us about the service's behavior and thereafter can unveil its business context. By using this context, we not only focus on specific parts of the business process but also avoid the computational complexity problem of the business process structure matching.

Due to the general limitation of public business process datasets, which provide only elements' identifier and services' names without any further information such as the one we used in our experiment, the validation of our approach so far is done with only the perfect match of services' names. However, our approach can be easily improved to deal with other comparison metrics and the validation can be extended for the imperfect matching. For example, we can take into account neighbors if their similarities on another comparison metric are greater than a certain threshold.

In our future work, we intend to investigate other service properties and study the co-existence of connection flows in business processes, as well as the number of times that a service is used in order to refine our matching algorithm. We also aim at extending our approach to extract the hidden knowledge existing in business processes logs as another input.

Figure 1 :

 1 Figure 1: Finding services to be composed in a business process

Figure 2 :

 2 Figure 2: Flight & hotel reservation processes

Figure 3 :

 3 Figure 3: An incomplete train reservation process

Figure 4 :

 4 Figure 4: The complete train reservation process

Figure 5 :

 5 Figure 5: Services and connection elements

  a

Figure 7 :

 7 Figure 7: Composition context graphs of a x (in Figure3) and a 6 (in Figure2)

Figure 8 :

 8 Figure 8: Connection flows in loop cases

  = ('+'|'-')Term | Constraint,'|',Term; 4. Term ::= Item | Term,'+',Item | Term,'-',Item; 5. Item ::= ServiceID| ConFlow | '(',Constraint,')'; 6. ConFlow ::= '<',[ServiceID],'[',FlowString,']',[ServiceID]'>'; 7. FlowString ::= ConElement,{ConElement}; 8. ConElement ::= 'sequence'|'AND-split'|'AND-join'|'OR-split'|'ORjoin'|'XOR-split'|'XOR-join';

  s x ::3 composition context matching without filtering s x :+s 1 -s 2 :3 s x :-s 2 +s 1 :3 services in the results have s 1 but do not have s 2 in their composition contexts s x :+(s 1 |s 2 )-s 3 :3 s x :-s 3 +(s 1 |s 2 ):3 services in the results have s 1 or s 2 but do not have s 3 in their composition contexts s x :+<s 1 ['sequence']s 2 >:3 services in the results have a connection flow s 1 'sequence's 2 in their composition contexts s x :-s 1 +<['ANDsplit''OR-split']>:3 services in the results do not have s 1 but have a connection flow 'AND-split''OR-split' in their composition contexts s x :-(s 1 |<['ORsplit']s 2 >):3 services in the results do not have s 1 or a connection flow 'OR-split's 2 in their composition contexts s x :+<s 1 ['AND-split']s 2 > +<s 2 ['AND-join']s 3 >:3 services in the results have both connection flows s 1 'AND-split's 2 and s 2 'AND-join's 3 in their composition contexts

  It uses BPMN notations. It has two versions: commercial and open source. The open source version with limited features is published 5 for free downloading and testing.

Figure 9 :

 9 Figure 9: Application screen-shot

Figure 10 :

 10 Figure 10: Percentage of services whose matching value >= 0.5

Figure 11 :

 11 Figure 11: Percentage of services with different k th -zone values

Figure 12 :

 12 Figure 12: Precision and Recall values computed by taking into account the first zone

Figure 13 :

 13 Figure 13: Comparing the simplest case of our approach to the random case

Figure 14 :

 14 Figure 14: Average computation time with k = 3

Table 3 :

 3 Query grammar

Table 4 :

 4 Query examples

Table 5 :

 5 Examined cases 6.2.2. Results -Approach feasibility and parameter impact :

The connection flow from a j to a i is the inverse of the connection flow from a i to a j

the EBNF standard is adopted by ISO, no. ISO/IEC 14977

N can be flexibly tuned by the process designer

http://www.signavio.com/

http://code.google.com/p/signavio-core-components/

Tutorial at: http://www-inf.it-sudparis.eu/SIMBAD/tools/WebRec/tutorial. html and video demo at: http://www-inf.it-sudparis.eu/SIMBAD/tools/WebRec/ demo.html

at the current stage, we have developed 4 algorithms for the composition context matching, which are with/without zone weight and with/without connection element similarity

http://www.zurich.ibm.com/csc/bit/


Dmitry A Abanin

Wojciech De Roeck

François Huveneers

Exponentially slow heating in periodically driven many-body systems

Keywords: numbers: 73.43.Cd, 05.30.Jp, 37.10.Jk, 71.10.Fd

We derive general bounds on the linear response energy absorption rates of periodically driven many-body systems of spins or fermions on a lattice. We show that for systems with local interactions, energy absorption rate decays exponentially as a function of driving frequency in any number of spatial dimensions. These results imply that topological many-body states in periodically driven systems, although generally metastable, can have very long lifetimes. We discuss applications to other problems, including decay of highly energetic excitations in cold atomic and solid-state systems.

INTRODUCTION

Time-dependent driving recently emerged as a new versatile tool for engineering various quantum states of matter. In non-interacting systems, periodic driving can be used to modify band structures, and in particular to make them topologically non-trivial [1][2][3][4].

Experimentally, periodic driving has been used to realize strong artificial magnetic fields [5], as well as 2D Bloch bands with non-zero Chern numbers (similar to the Haldane model) in systems of cold atoms in optical lattices [6,7]. Theoretically, natural extensions of these ideas to topologically non-trivial Floquet manybody states have been proposed. In particular, it was suggested that topological Floquet bands can host fractional Chern insulators [8], as well as symmetry-protected topological states [9].

Topological order and more generally quantum order are usually associated with ground states and low temperatures, where they are protected by a finite excitation gap. However, periodic driving breaks energy conservation, making the very concept of the ground state meaningless. It was argued [16][17][18] that under driving, generic many-body systems that obey the eigenstate thermalization hypothesis [10][11][12], eventually heat to up to an infinite-temperature, featureless state. Thus, "Floquet topological insulators" are generally metastable. It is important to understand their lifetimes, and use the theoretical understanding to design experiments in which the Floquet many-body states would be long-lived.

In this paper, we derive general results regarding the heating of periodically driven many-body systems on a lattice. We consider both the cases of local driving (timedependent perturbation acting only on a few degrees of freedom), and a global driving (driving applied everywhere in the system). The latter setup is relevant to cold atoms experiments [5][6][7]. Assuming that interactions are local, we prove a general bound for the linear-response heating rates, which indicates that at high driving frequency (much higher than a natural energy scale of the system, e.g., kinetic or interaction energy of one particle), heating is exponentially slow. Fundamentally, this bound follows from the locality of quantum dynamics in systems with local interactions, and, for the case of global driving, relies on the Lieb-Robinson bounds.

RESULTS

We consider a lattice system of spins or fermions with a local Hamiltonian H = N i=1 h i , subject to a periodic time-dependent perturbation with an operator O = i O i , which is a sum of one or more local terms O i . It is understood that i runs over the sites of the lattice and h i , O i act on a fixed, finite number of sites around i.

For simplicity, we focus on the case of harmonic driving with frequency ω and strength g:

H(t) = H + g cos(ωt)O. (1)
and we fix ||O i || ≤ 1 for concreteness. We assume that the system is initially in a thermal equilibrium, and is described by a density matrix ρ β , β = 1/T . The energy absorption rate dE/dt is related to σ(ω), the dissipative part of the linear-response function, by dE/dt = 2g 2 ωσ(ω), upon averaging over a cycle and up to higher orders in g. The response σ(ω) can be expressed in terms of different-time commutators of operators O i :

σ(ω) = ij σ ij (ω), σ ij (ω) = 1 2 ∞ -∞ dte iωt [O i (t), O j (0)] β , (2)
where ... β denotes thermal averaging and O i (t) refers to the Heisenberg dynamics generated by the timeindependent H. One can show that ωσ(ω) is positive and symmetric in ω, see e.g. [START_REF] Mahan | Many-Particle Physics[END_REF][START_REF] Tong | Lecture notes on 'Kinetic Theory[END_REF]. For concreteness, let us take ω ≥ 0 so that σ(ω) ≥ 0. To be precise, in finite volume, ωσ(ω) is a positive distribution rather than arXiv:1507.01474v2 [cond-mat.stat-mech] 29 Jul 2015 a bonafide function and we will need to integrate this distribution over small intervals to state rigorous results: we write f ([ω 1 , ω 2 ]) ≡ ω2 ω1 f (ω) dω.

Local driving

First, using the locality of the Hamiltonian, we prove the following bound for individual terms σ ij (ω):

There is a κ > 0 and a numerical constant C such that, for any δω > 0, ω > 0,

|σ ij ([ω, ω + δω])| ≤ Ce -κ|ω| , (3)
uniformly in the total volume. Note that it is only the dissipative (asymmetric in time) part of the response function that decays exponentially. The reactive (symmetric in time) part contains a principal value integral rather than a δ-function, cfr. ( 5), in energy, and it generically decays no faster than 1/ω. We first prove (3) for i = j. It is convenient to write σ ii as a sum of contribution of individual eigenstates |n of H:

σ ii (ω) = π n p n (γ n ii (ω) -γ n ii (-ω)), (4)
where

p n = e -βEn Z , Z = Tr(e -βH
) is the probability that the system is in eigenstate |n , and γ n ii is given by

γ n ii (ω) = m | m|O i |n | 2 δ(E n -E m -ω). (5)
To estimate this quantity, let us rewrite it as follows, for any k:

γ n ii (ω) = m | m|[[[O i , H], H], ..., H]|n | 2 ω 2k δ(E n -E m -ω), (6)
where the r.-h.s. contains k commutators with H, and we have used the fact that E n -E m = ω. Next, we use the fact that in local systems, the norm of

[[[O i , H], H], ..., H] can be bounded as ||[[[O i , H], H], ..., H]|| ≤ ε k k!, (7)
where ε is an energy scale that can be expressed via ||h i || (local norm of the Hamiltonian), the range of h j and O i , and the coordination number of the lattice. Integrating Eq.( 6) over an interval [ω, ω + δω], and using inequality (7), we obtain:

γ n ii ([ω, ω + δω]) ≤ ε k k! ω k 2 ≤ εk ω 2k , ∀k ∈ N (8)
Choosing k = ω εe , we arrive at the estimate

γ n ii ([ω, ω + δω]) ≤ e -κω , κ = 2 εe , (9)
and therefore, using (4) and the fact that n p n = 1, we obtain

σ ii ([ω, ω + δω]) ≤ 2πe -κω . (10)
The off-diagonal terms σ ij , i = j, can be bounded by diagonal ones using positive-definiteness of ωσ ij and the Cauchy-Schwartz inequality:

|σ ij (ω)| ≤ 1 √ 2 (σ ii (ω) + σ jj (ω)) . (11)
Thus, just like diagonal terms, off-diagonal terms decay exponentially at large frequency, concluding the proof.

The above result can be immediately applied to the case of local driving, when the operator O acts only on a finite number of n lattice sites (i.e. O i on other sites are taken to be zero), while the system size N is taken to infinity. For such a setup, the energy absorption rate will be smaller than ∼ n 2 e -κ|ω| , where n is the number of lattice sites affected by the periodic driving.

The result (3) has a clear intuitive meaning for two particular cases. The first example is a gapped many-body system at zero temperature, e.g., a gapped spin chain with a maximum energy per spin of order J. The existence of the gap implies exponential decay of correlations with a typical length scale ξ. When the spin chain is subject to a periodic drive, in order to absorb a large energy ω, a local operator O i must flip a large number n ∼ ω/J spins. It is clear that at large n ξ the amplitude of such a process should be exponentially small. Another example is provided by a system with weak interactions, e.g., a weakly interacting Fermi-gas. Then, absorbing a large energy ω requires a creation of n ∼ ω/J particlehole pairs (J in this case denotes a maximum energy of one electron-hole pair) -a process which will be suppressed as V n , where V is the interaction strength. Our analysis shows that the energy absorption rate remains exponentially small much more generally: the bound applies to systems without gaps and also to systems with strong interactions.

Global driving

Next, we consider the case of global driving, when O i = 0 for all lattice sites. This setup is generic and relevant, in particular, to all experiments in which driving is used to create topological states. In this case, we prove a different bound:

There is a κ > 0 and a numerical constant C such that, for any δω > 0, ω > 0,

|σ([ω, ω + δω])| ≤ N Ce -κ|ω| . ( 12
)
with N the total number of spins. It is intuitively clear that the absorption rate in this case should be proportional to N . Therefore one cannot simply use the bound

(3), since it would give a heating rate that scales as N 2 . Thus, we use Lieb-Robinson bounds [38] to estimate σ ij for remote i and j. For two operators A, B with ||A||, ||B|| ≤ 1 and support in regions X, Y , they read:

||[A(t), B]|| ≤ Ce -a(r-v LR t) , r = dist(X, Y ), (13)
with v LR the Lieb-Robinson velocity and C a numerical constant (below we always use C for numerical constants whose value can change from line to line). We choose to measure distances in units of the lattice spacing, and hence a is simply a numerical constant as well. a, C, v LR are determined by the norm and range of h i and the type of lattice. Without loss of generality, we assume κω 1 (for small values of κω, the bound can always be satisfied by tuning C). We will prove the bound (12) for δω = (δω) 0 with some arbitrary but fixed (δω) 0 > 0 (we will use in the proof that (δω) 0 is smaller than quantities that diverge with ω → ∞). The bound for arbitrary δω is then recovered as follows: For δω < (δω) 0 , we have σ([ω, ω + δω]) ≤ σ([ω, ω + (δω) 0 ]), hence the bound. For δω > (δω) 0 , we dominate σ([ω, ω + δω]) ≤ k≥0 σ([ω + k(δω) 0 , ω+(k+1)(δω) 0 ]) and we apply the result for each term in the sum, so that the result follows by readjusting C.

First, we dominate, for ω ≥ 2(δω) 0 ,

σ([ω, ω + (δω) 0 ]) ≤ e 1 -e -8 ∞ -∞ dω e -ω -ω (δω) 0 2 σ(ω ) (14)
This relies on positivity of σ(ω ≥ 0) and the symmetry σ(-ω) = -σ(ω). Then we split σ(ω) = ij σ ij (ω) in ( 14) and we recast the resulting integrals in the time domain:

∞ -∞ dω e -ω -ω (δω) 0 2 σ ij (ω ) = √ π(δω) 0 ∞ -∞ dt e -(t/δt) 2 e -iωt [O i (t), O j ] β , δt = 2 (δω) 0 . ( 15
)
Our strategy is to estimate terms with dist(i, j) ≥ r * , with r * large, using Lieb-Robinson bounds, and to bound terms with dist(i, j) < r * using (3). We will choose r * = 2κω/a with κ being the κ featuring in (3). Fist, we study a general (i, j)-term in (15) with dist(i, j) = r ≥ r * . We break the time-integral in the r.h.s. of ( 15) into an integral over the interval [-t c , t c ] with t c = t c (r) = r/(2v LR ), and an integral over the rest of the real axis. The former is bounded by LR-bounds (13):

tc -tc dt e -(t/δt) 2 e -iωt [O i (t), O j ] β ≤ 2Ct c e -ar/2 .
(16) and the latter is bounded using

||[O i (t), O j ]|| ≤ 2 (since ||O i || ≤ 1): 2 ∞ tc dt e -(t/δt) 2 e -iωt [O i (t), O j ] β ≤ 2 √ πe -(tc/δt) 2 δt.
(17) Using (16,17) and setting δt < t c (since (δω) 0 is fixed and κω 1), we bound the sum over (i, j) with r ≥ r * by

CN r d-1 * r * v LR e -ar * /2 + v 2 LR (δt) 3 r * e - r * 2v LR δt 2 , (18)
By increasing r * , the exponent in the second term becomes at least as small as that in the first term and we can bound (18) by

CN r d * 1 v LR e -κω
This provides a bound for the contribution of remote pairs |i -j| ≥ r * to the r.-h.s. of Eq.( 15). Multiplying by √ π(δω) 0 and using (δω) 0 /v LR ≤ C, we bound their contribution to the response function ( 14) by CN r d * e -κω . There are ∼ r d * remaining terms with dist(i, j) < r * . Their contribution to ( 14) can be bounded using (3), which gives CN r d * e -κω , as well. Recalling r * = 2κω/a, we get an overall bound (i.e. summed over all r) of the form

CN (κω) d e -κω
for the response function. By slightly reducing κ (the new value is called κ again) and increasing C, we get the bound (12).

The necessity of averaging over a frequency window δω is likely an artefact of our proof. We expect that in the thermodynamic limit, the bounds (3,12) hold for σ(ω) itself, i.e. that the distribution is a bonafide function, but we cannot prove this, see also [36,37] for mathematical details and [35] for a polynomial bound at large ω.

EXTENSIONS

Let us briefly comment on extensions of our results. First, we note that in d = 1 we can in fact choose the decay rate κ to be arbitrarily large at the cost of increasing the numerical prefactors C in (3,12). This is achieved by improving the bound in the r.h.s. of (7) to C(γ)e -γk k!, for any γ > 0, as described in [28,39]. The extension for local driving is immediate and for global driving, we then simply choose r * with a larger κ. Hence in d = 1, the decay is in fact superexponential, but one should not expect such an improvement to hold in d ≥ 2 [29], nor for the case of quasilocal, exponentially decaying O i , h i (instead of strictly local).

It is also possible to obtain similar results as ours for some models of lattice bosons, e.g. the Bose-Hubbard model at high temperature, but then the exponential decay is weakened to a stretched exponential. The key observations are that a) the bound (7) fails trivially for unbounded h i and one has to use a weighted norm instead and b) one needs to assume (spatial) decay of correlations for the thermal ensemble • β (provable by cluster expansions at high temperature) as Lieb-Robinson bounds are no longer available, see [27].

The most important extension [27], however, is to go beyond linear response and to allow for general initial states, showing that the phenomenon described here is quite similar to localization in energy, except that, presumably, it in general breaks down after a sufficiently long time, [16][17][18].

Finally, for completeness, we mention that there are two remarkable cases where the energy localization does not break down for long times: 1) driven MBL systems at not too small frequencies, see [21][22][23] and 2) noninteracting fermions, i.e. with h i , O i containing only linear and quadratic terms in c, c † . In that case, by performing a canonical transformation, we fall back on a one-particle problem where exact dynamical localization is possible [START_REF] Bukov | [END_REF]. In the case where H describes noninteracting fermions but O is of order q > 2 in the fields c, c † , we do not expect genuine localization but still the linear response vanishes exactly: σ(ω) = 0 whenever ω exceeds the bandwidth times q, as one sees from (5).

DISCUSSION

The main implication of the above results is that, although many-body states (e.g. topological states) in isolated, periodically driven systems are generally metastable, they have a very long life time, if driving frequency is much higher than the natural energy scale of the system. We note that this limit is indeed realized in recent experiments.

Further, we note that there has been recent interest in dynamical localization in periodically driven many-body systems [17,[19][20][21][22][23][24]. In such studies, numerical simulations are a useful tool. Our results imply that, in order to observe delocalization at high driving frequency, one may have to study the system dynamics at (exponentially) long times.

Our results also can be directly applied to a different class of problems: the decay of a highly energetic excitation into many low-energy excitations. One physical model where such a problem naturally arises and has been studied is the large-U Fermi-Hubbard model,

H = J ij ,s=↑,↓ c † is c js + U i n i↑ n i↓ , U J (19)
where ij denotes neighbouring sites, and s is a spin label. Doublons (doubly occupied sites) have a typical energy ∼ U which is much greater than the kinetic energy J. At temperatures T U , when there are very few doublons in the system, one can ask how quickly doublons decay into particle-hole pairs. This problem has been addressed experimentally [25] and theoretically [26] using perturbation theory, and the decay rates were found to be exponentially small in U/J. Therefore, in this case our bound appears to be saturated.

We note that the bound is non-perturbative in the interaction strength of the systems, and we expect it to be useful for other strongly interacting systems where excitations with very different energy scales are present, e.g., equilibration of Fermi-Fermi cold gases with very different mass parameters, as well as random spin models with a broad distribution of exchange couplings. For random spin models, an exponential decay of a local spin correlation function at high frequency has been previously obtained using mean-field-type approximations [30,31]. Our results are consistent with this earlier study in d > 1, but show that in one-dimensional systems the decay at high frequency is even faster than exponential.

CONCLUSION

We have proven that the dissipative part of the linear response for local lattice systems decays exponentially at high frequencies. In particular, this means that heating by periodic driving will be exponentially slow. This result provides a foundation for so-called Floquet many-body phases by showing that, though metastable, they will be very long-lived.

Acknowledgements. D.A. acknowledges support by Alfred Sloan Foundation. W.D.R. also thanks the DFG (German Research Fund) and the Belgian Interuniversity Attraction Pole (P07/18 Dygest) for financial support and both F.H. and W.D.R. acknowledge the support of the CNRS Inphynity grant.