Introduction

A web service-based application in SOA vision can be built by discovering and composing sets of interoperable services, according to some specified functionality. A developer has to specify the pieces of functionality needed inside an aimed application, and each piece of functionality is defined as a set of parallel and sequential consecutive tasks. In other words, a piece of functionality inside an application is defined as a workflow of operations, offered by one or more services. This means that for each specified task the developer must discover a web service that offers an operation satisfying this task. This poses a number of challenges because a developer might not have enough knowledge about all of the existing service providers where he can find the required services. On the other hand, if many providers offering a needed service were found, a time-consuming comparison will be required in order to choose the provider offering the most suitable service. Many aspects must be taken into consideration while selecting a service to fulfill a task in the composition. This includes the functional aspect, the non-functional (QoS) and the needed adaptations to compose this service with other ones in the composition. Composing two consecutive services in a workflow implies the composition of two operations, an operation of each service. This necessitates the assignment of certain output parameters of the first operation with certain input parameters of the second one. This outputinput assignment may not always be accomplished directly, because there may be some differences between the parameters and their data types that requires performing some adaptations. Thus, constructing a web service-based composite application can have variable levels of complexity, regarding the needed time and effort to build each part of functionality, consisting of finding and composing the required services, with performing the necessary adaptations. The situation may become more complicated if one or more of the composed services becomes no more usable. This will necessitate the replacement of these services with functionally similar services that can fulfill the left functional gap. Hence, finding services' substitutes, modifying services' proxies and performing new adaptations.

So briefly, the process of constructing a web service-based application consists of:

• Specifying the needed pieces of functionality inside the application, ex.

billing, payment and shipping;

• Each piece of functionality is a workflow of tasks;

• Each task is an operation offered by a web service;

• To satisfy each needed piece of functionality, a search for services must be carried out for each specified task

• Service providers must be found and in case of multiple similar services, a compromise between functional and non-functional aspects of a service must be done, in order to choose the most suitable service, in addition to minimizing the required adaptations when composing the services;

• Services offering the needed tasks must be composed together, taking into consideration the needed adaptations;

• After the long process of discovering and composing the needed services, if a service becomes no more usable after a while, it must be replaced by another one that can fulfill the functional gap, after performing the needed modifications and adaptations.

Web Service Challenges

Web services face several challenging issues coming from several factors. Since, they are offered by various providers, remotely accessed, and sometimes provided for free, there is no guarantee of a continuous execution. An available functioning web service may crash and become unavailable at any time, which necessitates finding an equivalent one to replace it. Unfortunately, this can be hard to achieve since there is a lack of WSDL organizing facilities, especially after the deficiency of the UDDI1 registries: "UDDI did not achieve its goal of becoming the registry for all Web Services metadata and did not become useful in a majority of Web Services interactions over the Web"2 .

A Web Service Registry Proposition

We propose a web service registry, a broker that mediates between service providers and service consumers, considering that a service consumer is a developer of web service-based composite applications. This registry enables providers of publishing their well-described documented services, and providing their estimated QoS information related to these services. It adapts two classifying techniques: Formal Concept Analysis (FCA) and Relational Concept Analysis (RCA). The published services are organized into domains of functionality and in each domain similar services are classified in order to reveal replaceable services. We build our classification using FCA, which is a method of data analysis that takes as input a set of objects and a set of attributes with the relation between them indicating which objects have which attributes. After analyzing the input data, it clusters the objects into concepts depending on their attributes, and reveals the relationships between these concepts, thus, the relationships between the objects. The concepts can then be ordered in a lattice structure for a better browsing and navigation of objects and relationships among them. We adapt this method for classifying web services by considering that the set of objects is a set of web services, and the set of attributes is the set of the offered operations. The resulting classification is represented as a concept lattice for web services, from which we can easily select a needed service by browsing its offered operations, and we can also find the possible substitutes of a selected service. Using this method, services are also classified according to their QoS attributes specified by the providers. This enables services consumer of finding an aimed service depending on its functional and non-functional aspects, as well as finding its possible substitutes. A service consumer may either query the registry for services offering a specific operation, or he can design an abstract business process that describes his aimed composite application, in which he specify the set of needed tasks ordered in a workflow. The registry will analyze the specified abstract process and finds the set of web services that can fulfill each task, by querying the corresponding service lattice. After discovering the sets of services that can fulfill the tasks in order to satisfy the functionality required by the abstract process, another classification is built that reveals the composable services according to each pair of consecutive tasks. This second classification is based on an extension of FCA called RCA.

Inside the registry there are techniques to:

• Infer the domain of functionality for each published service, with the help of the WordNet ontology;

• Building FCA-based classifications for the similar services taking into consideration their QoS values, in order to have a better browsing of functionality and the substitutability relations;

• Designing and analyzing abstract business processes, then finding the candidate services that can fulfill the needed tasks, depending on the functional, non-functional aspects, and the preferences provided by the consumer;

• Building RCA-based classifications for the discovered services, in order to classify them by their composability levels according to each pair of consecutive tasks;

• Selecting the optimal set of composable services, by doing a compromise of QoS and adaptations levels, according to the consumer preferences;

• Keeping track of consumers and their service compositions, and notify them in case of a service failure with possible backups;

• By keeping track of service compositions, the registry acquires knowledge about the new resultant composite functionality;

• Consumers can combine several operations while designing their composition, under a new operation name, like this the registry learns the possible operation composition to realize a requested operation.

Organization of this report

The organization of this report represents the sequence of ideas of our work. Our first step is to extract the tags (keywords) in each WSDL file, which is explained in section 2. These keywords are used afterwards to classify the services into lattices using FCA, as we will see in section 3. We then explain in section 4 how to order a set of services according to their various QoS aspects. After classifying the services by their similar functionality, and their QoS aspects, we need to find a set of composable services, according to their QoS values and composability levels, illustrated in section 5. We present our future work in section 6.

Automatic Web Service Tagging

We propose an approach that automatically extracts a set of relevant tags from a WSDL [START_REF] Falleri | Automatic Tag Identification in Web Service Descriptions[END_REF]. We used a corpus of user-tagged services to learn how to extract relevant tags from untagged service descriptions. This approach adapts techniques from text mining in order to extract candidate tags out of a description, and techniques from machine learning to select relevant tags among these candidates.

We model the tag extraction problem as the following classification problem: classifying a word into one of the two tag and no tag classes. Our overall process is divided into two phases: a training phase and a tag extraction phase.

WSDL + Tags Corpus word 1 + features + class word 2 + features + class word n + features + class

Already classified words

Trained classifier Figure 1 summarizes the behavior of the training phase. In this phase we have a corpus of WSDL files and associated tags, extracted from Seekda. From this training corpus, we first extract a list of candidate words by using textmining techniques. Then several features (metrics) are computed on every candidate. A feature is a common term in the machine learning field. As an example, it may be the frequency of the words in their WSDL file. Finally, since manual tags are assigned to those WSDL files, we use them to classify the candidate words coming from our WSDL files. Using this set of candidate words, computed features and assigned classes, we train a classifier. We have used a corpus of 146 user-tagged web services extracted from Seekda for experiment. The obtained results demonstrated the efficiency of the described approach.

New WSDL file word 1 + features word 2 + features word n + features

Unclassified candidate words

Trained

The extracted keywords are used to classify web services, using Formal Concept Analysis, as explained in the next section.

FCA-Based Web Service Classification

We propose an approach based on Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF] for classifying web services into a lattice structure, which facilitates their browsing and selection [START_REF] Azmeh | Using Concept Lattices to Support Web Service Compositions with Backup Services[END_REF]. A service lattice reveals the relations between the services, easing the discovery of a needed service as well as the identification of its possible alternatives. This helps in the construction of service compositions and ensuring a continuous functionality by supporting them with backup services. In figure 3, we can see a general overview of the main steps of our approach, in which, two service lattices are built:

• a lattice for indexing the services by keywords extracted from their WS-DLs, using the automatic tag extraction approach, described in Section 2,

• a lattice for similar service classification, which is build from a manyvalued context that contains the similarity values that are calculated between operations offered by each pair of services.

Figure 3: The main steps of our approach.

We explain our approach along with a case study described in the next section.

Case study

Let us consider the following travel scenario: a traveller needs to reserve a plane ticket to a desired city. Supposing that this traveller lives in a small city that has no airport, then, he should also travel to the city where the airport is located, in order to take the plane he reserved. Thus, he must also reserve a train ticket, from his home city to the airport city, taking into consideration the flight exact time with the time needed to travel between the two cities. This scenario can be achieved by a travel composite service (TCS), in which 3 functionalities must be satisfied:

• reserve a flight from home city, or airport city, towards a desired city,

• if a train reservation is needed (in case that the home city is not the airport city), then calculate the needed time (duration) to travel between the two cities by train,

• reserve a train ticket, regarding the exact flight time and the calculated duration.

The TCS can be realized by discovering services offering the described functionalities and composing them. It may look like the composition in Figure 4. In this orchestration, if the service T rainW S crashes, for example, an equivalent service offering at least the two used operations calcDuration() and resT rain() must be searched and discovered, in order to recover the missing functionality, and ensure the continuity of the composition. In the following we explain the construction of the keywords lattice, and the similarity lattice. We conclude by showing how to construct this composite travel service, and support it with backup services.

The keywords lattice

The extracted keywords in section 2 are used to generate the first lattice, which represents an indexation of services by keywords. Supposing a set of random web services for travel facilities, the corresponding lattice may resemble the lattice in Figure 5. From this lattice, we can retrieve services in a certain domain by enquiring the lattice using keywords. Such a query returns a sub-lattice of services sharing the specified set of keywords, which are highly probable to provide similar functionalities. We perform a query on a lattice by expressing the set of keywords as a new line, added to the context service × keyword. This results in a new concept in the lattice, labelled query. The services that answer the specified query are represented by the sub-concepts of the query concept. In our scenario, we perform two keyword queries: query1 = {reserve, plane} and query2 = {reserve, train, duration}. This results in the lattice shown in Figure 6, in which, we extract the services answering the two queries and they are:

• for query1: ws 1 , ws 2 , ws 3 , ws 4 , ws 9 and ws 10 ,

• for query2: ws 5 , ws 6 , ws 8 , ws 9 , ws 10 .

We further analyse the two sets of services corresponding to the two queries. We apply a similarity measure on the operations according to each set and we identify the groups of similar operations. For example, an operation labelled reserveF in the lattice, represents a group of similar operations for performing a flight reservation. This way, we can build a new context of service×operation for each set of services. We explain next how to build a many-valued context of similarity values, which are calculated between pairs of operations provided by different services.

The similarity lattice

For clarity sake, we illustrate our approach using an imaginary set of Web services for performing calculations. Each service from this set is parsed by a WSDL parser to extract its signatures. The set of services with their signatures are given unique identifiers, as listed in Table 1. Table 1: A set of calculation services with their operations.

Services Id Operations Id Calculator1 ws1 add(a,b) op11 sub(a,b) op12 Calculator2 ws2 add(a,b,c) op21 Calculator3 ws3 add(a,b,c,d) op31 sub(a,b,c) op32 mult(a,b) op33 add(a,b,c) op34
Next, a similarity measure must be chosen, and the operations signatures extracted from the WSDL files will be used by this similarity measure, according to its input format. Several similarity measures for web services exist in the literature. They evaluate the similarity according to the syntactic and semantic levels.The similarity is assessed in the form of values in the range [0,1]. If two operations are sufficiently similar, the similarity value will approach 1, or else it will approach 0. The similarity measure is applied on pairs of operations provided by different services. We do not consider the similarity between operations provided by the same service (it is equal to 0), because when a service becomes dysfunctional, all of its operations become dysfunctional too.

A similarity measure (Sim) can be defined as follows:

Sim : O × O → [0, 1] ∀ op ij ∈ O =⇒ Sim(op ij , op ij ) = 1 (an operation with itself) ∀ op ij , op ik ∈ O =⇒ Sim(op ij , op ik ) = 0 (operations in the same service) ∀ op ij , op nm ∈ O =⇒ Sim(op ij , op nm ) ∈ [0, 1]
(operations in different services)

The calculated similarity values can be presented by a symmetric square matrix that we will call SimM at, as shown in Table 2. This matrix is of size n = |O|, and its diagonal elements are all equal to 1, since we consider that the similarity of an operation with itself is equal to 1 as declared above. From the similarity matrix SimM at, we can extract several binary contexts, by specifying threshold values θ ∈]0, 1]. Thus, the values of SimM at that are greater or equal to the chosen threshold θ are scaled to 1, while other values are scaled to 0. The binary context that corresponds to θ = 0.75 is shown in Table 3, we call it SimCxt.

Table 3: The binary context (SimCxt) for θ = 0.75.

op11 op12 op21 op31 op32 op33 op34 op11 x x x op12 x x op21 x x x x op31 x x op32 x x op33 x op34 x x x
The SimCxt context is a triple (O, O, RSim θ ), where RSim θ is a binary relation indicating whether an operation is similar to another operation or not.

(op ij , op nm ) ∈ RSim θ ⇐⇒ Sim(op ij , op nm ) ≥ θ
We use the SimCxt context to generate a lattice of operations, B(O, O, RSim θ ). This lattice helps in discovering groups of similar operations, which are used later on to construct the services lattice.

In the resulting operation lattice, groups of mutually similar operations can be identified by the concepts having equal extent and intent sets. We call such concepts as square concepts, because they form square gatherings on the binary context matrix. We define a group G op of mutually similar operations Op Sim as:

G op = {Op Sim | (Op Sim , Op Sim ) ∈ B(O, O, RSim θ )}
The notion of square concepts can be better recognized by performing a mutual column-line interchange in the SimCxt, the resulting interchanged context is shown in Table 4. From the lattice in Figure 7 as from the interchanged context in Table 4, we can identify the groups of similar operations, and they are the following: 3.

The groups of similar operations, denoted as G, are used to define the final binary context. This context is a triple (W, G, R), in which the relation R indicates whether or not a service offers the functionality represented by the corresponding group of similar operations.

We will represent each group of operations by an identifier that corresponds to the indices of the operations. The new context is shown in Table 5: From the notice the following:

• ws 1 , ws 2 , and ws 3 offer the functionality denoted by (11, 34, 21), so they can replace each other for this specific functionality

• ws 3 can replace ws 1 and ws 2 , and it offers an additional functionality (33)

We can also infer immediately which services offer a specific functionality (denoted by a specific label), by regarding the indices in the label. We return to our scenario after having generated two similarity lattices, corresponding to query1 = {reserve, plane} and query2 = {reserve, train, duration}.

The lattice that corresponds to query1 is shown in Figure 9 (top), and the one corresponding to query2 in Figure 9 (bottom).

Using these two lattices, the selection of services offering required operations is straightforward. In our scenario, we need three tasks: flight reservation, train reservation (if needed), and calculating the duration needed to travel by train to the aimed destination. By regarding the lattice in Figure 9 (top), we notice that all of the services offer an operation for plane reservation. In this case, a service selection might be done regarding the extra operations that the services provide, like for example the operation rentCar. When we select a certain service, we can immediately extract the set of backup services that are able to replace it if it fails. In the same way, we can select a service for train reservation with obtaining the duration information. Thus, the composition in Figure 4 can be easily achieved and supported with backups, as in Figure 9. Supposing that we selected the service ws 4 named P laneW S, and used its operation resF light (which is grouped with other similar operations under the name reserveF in the lattice). We can notice that for the operation resF light, any other service in the lattice can be a backup for ws 4 . In case where all of the operations of ws 4 were used, we notice that only ws 10 and ws 1 can be backups for ws 4 . Similarly, we selected the service ws 6 , named T rainW S, and used two of its provided operations: calcDuration and resT rain. We notice that ws 6 can be replaced by the services ws 10 , ws 8 and ws 5 . Thus, we have discovered immediate backups for the service T rainW S as we did for the service P laneW S. We can notice that the service ws 10 exists in the two lattices, as a backup for both T rainW S and P laneW S. In this case, if both of these services crash, we can replace them both by a single service, which is ws 10 . This service provides the same functionalities of the two services, with three extra operations that are priceT , rentCar and durationF as can be seen in the lattices in Figure 9.

Our approach has enabled us of an easy service discovery and selection, in order to build our aimed scenario. It has also facilitated the discovery of backup services to support service composition and ensure its continuous functionality.

In the following section, we will include QoS aspect to our web service classification, in order to select a service with the best available QoS values.

QoS-Based Web Service Ordering

Web services have many QoS aspects such as availability, response time, reliability, etc. Selecting a service from a set of services offering different values of QoS may not be a straightforward task.

Supposing a set of services {a,b,c,d,e,f,..} with different values of availability and performance time as in figure 10. In such case, we need to select the service that makes the best compromise between the aspects of QoS supposing than the value 1 is the best and 10 is the worst. In the literature, we can find a similar problem about finding skylines objects 3 . Using the skyline operator, an object is determined to be interesting if it is not dominated by any other object. In this view, we can observe that the interesting service are a, i, and k. We applied the FCA classification on services with their QoS values, in order to have this kind of service ordering. We considered that a service that has a certain QoS value, has also all the values that are lower. In figure 11 In this lattice, we can notice that the skylines services appear at the bottom. They are also the services a, i, and k as given by the skyline operator. We can also observe that to choose a service that makes the optimal compromise between the QoS values (availability and response time), we have to select a service that dominates a greater number of services. For example, the service i would be the best choice because it dominates more services than any other service in the lattice. On the other hand, the service e, which is located at the top of the lattice can be considered as the worst choice because it does not dominate any service. We can check the correction of these conclusions by returning to the actual values of each service. Service i has the values (a=3, rt=2), which is probably the best compromise among all the other values, while service e has the values (a=10, rt=10), which is definitely the worst compromise ever.

The generated lattice has so many empty concepts which can be eliminated using the Galois Sub-Hierarchy (GSH) algorithms4 .

Web Service Composition

We propose an approach based on a variant of FCA called Relational Concept Analysis (RCA) [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF] for the identification of composable services. It allows the classification of web services according to their QoS and composability levels and proposes a query mechanism that allows users to specify their required QoS and composability levels. In the case of multiple choices that satisfy users' requirements, we enhance our approach with a mechanism based on vectors for identifying the optimized choice.

RCA-Based Web Service Classification

We explain our approach along with an abstract composition of three sequential tasks, as in figure 13. We try to identify the concrete services offering the needed functionalities, in order to instantiate the defined orchestration. Our objective is to select composable services with the highest affordable QoS values, and the least required adaptations.

Figure 13: An abstract composition of three sequential tasks.

We have 3 sets of services: S 1i , S 2j and S 3k corresponding to the three tasks. For each service of the three sets, we assume certain values of QoS (for availability (A) and response time (RT)). We categorize the QoS values into 5 levels: very low, low, medium, high and very high, for each of the A and RT values. A service that offers a specific QoS level, does also offer QoS levels that are lower. For each pair of consecutive services (according to our defined orchestration), we assume three composability values: exact, partial and disjoint. We base our classification on Formal Concept Analysis (FCA), which is a data analysis method that aims at extracting concepts from entities described by attributes. The description of entities is encoded in a formal context. For example, in Fig. 14, the third table S 3k is a formal context where entities are services for the Task 3, and are described by the values of availability and response time (attributes). Concepts are maximal sets of entities (extent) sharing a maximal set of attributes (intent), and they are organized in a classification provided with a lattice structure. The lattice associated with the context S 3k is shown in Fig. 18. Each concept in this lattice inherits the attributes of its ascendants (super-concepts), and has lesser attributes than its descendants (sub-concepts). Reversely, each concept inherits the services of its descendants (sub-concepts). For example, the concept c 0 represents the services s 31 and s 33 , which covers the QoS values of the services in the upper concepts, and offers better ones (like: low A and low RT). The concept c 5 indicates that s 33 has very low RT and high A. The concept c 5 is a sub-concept of the concept c 0 , which shows that s 33 has better QoS values than s 31 .

Since we also want to capture the composition relations, existing between pairs of services in an orchestration, we use a variant of FCA called Relational Concept Analysis (RCA), which includes relations in the attributes used for the concept mining. RCA data are given in the form of a Relational Context Family (RCF). An RCF is a set of binary relationships (tables): some (non-relational) tables describe entities by attributes, while some (relational) tables describe relations between entities. The non-relational part of the RCF contains one table for each task: entities are services that can make the task, and attributes are QoS values. Thus, our RCF is composed of three non-relational contexts: S 1i * QoS, S 2j * QoS and S 3k * QoS, and two sets of three relational contexts: composition of S 1i * S 2j and composition of S 2j * S 3k , according to the three considered levels. As we can see in Fig. 14 the extent of a concept C at the current step, thus in the current version of the composition context we add (S xy , C). This can be interpreted as S xy can be composed with at least one service from the set of services grouped in C with the composition level cl. For example, since we have (s 13 , s 25 ) ∈ Exact 12 and since s 25 is in the extent of Concept c 1 (in lattice S 2j ), the scaled Exact 12 table will contain (s 13 , c 1 ). By regarding the lattices in Fig. 15, we can find for example, that the service s 13 (in the leftmost lattice) has in its intent Exact 12 : c1. This means that it can be composed with services contained in the concept c1 (in the middle lattice). Thus, s 13 can be composed at least with s 25 . At a next step this will allow to group a set of services (implementing a first task) because they can be composed with services of another group of services (implementing another task). The process stops when no new concept emerge during the FCA analysis. At the end of the process, a concept lattice is generated for each set of services. In each lattice, services are classified into concepts, showing their QoS levels as well as their composability levels with other services, according to the orchestration. Concept c 7 in the S 1i lattice groups services s 13 and s 11 , and indicates that they can be partially composed with services of concept c 3 of the S 2j lattice, which groups s 23 and s 25 .

Navigation by Query Integration.

We define a query mechanism that enables us to navigate into a lattice, in order to choose a combination of services that satisfies the aimed orchestration, with our aimed levels of QoS and composability. A query determines the required QoS for each requested task, as well as, the needed composability level (required adaptations) between the services. We define a QoS query as a new line (a new entity), integrated into the corresponding service*QoS binary context, specifying the least expected QoS level. In our example, we perform three QoS queries: query 1 , query 2 and query 3 on S 1i * QoS, S 2j * QoS and S 3k * QoS respectively. They are as follows:

• query 1 looks for a service from S 1i , with a low A and a low RT;

• query 2 tries to retrieve a service from S 2j , with a high A and a low RT; Figure 16: The RCF after integrating the QoS queries and specifying the composability level.

• query 3 demands a service from S 3k , with a high A and a medium RT.

In order to select services that satisfy a specific composability level, we merge the relational contexts that express levels equal or greater than the requested level. In other words, if a partial composability level can be accepted, this means that if we find an exact level, it is even better. In this example, we demand an "exact" composability level between S 1i and S 2j , and a "partial" level between S 2j and S 3k . This gives us a variation of our RCF that includes queries, where the relational context compose1 is the context exact12 and compose2 is the fusion of exact23 and partial23, as shown in Fig. 16. This latter RCF generates three lattices, from which we can extract the services combinations that meet our requested QoS and composability. These lattices are illustrated in Fig. 17, from which we can identify the services that satisfy the QoS queries, which appear in the sub-concepts of the concept where a query n appears, and are as follows:

• services s 13 and s 14 for query 1 ;

• services s 23 , s 24 and s 25 for query 2 ;

• services s 32 and s 33 for query 3 .

Web Service Triangles Approach

We can have several service combinations that satisfy our desired orchestration. If we are searching for an optimized selection, this means that we have to find the set of services that meet the optimal compromise of QoS levels and composability. Thus, services that can be coupled according to our acceptable levels of required adaptations and QoS. In order to meet this issue, we propose to represent the services by vectors. A vector per set of services, on which, services are ordered according to their QoS. We also define a vector for composability levels. Each composition can be regarded as a triangle, having a head corresponding to the composability level, and the two other heads corresponding to the pair of services to be composed, as shown in Fig. 19. The optimized choice would be the triangle that has the minimal area, in case of a two services composition. Otherwise, it will be the minimal sum of the services triangles according to an orchestration. Thus in our example, by regarding the triangles in Fig. 19, we notice that the triangle (E, s 25 , s 33 ) represents an optimized composition between S 2j and S 3k (corresponding to Task2 and Task3, respectively). Accordingly, if we consider the triangle (E, s 13 , s 25 ) that shares an edge with the previous triangle, it represents a composition between S 1i and S 2j (corresponding to Task1 and Task2, respectively). These two triangles together may be an optimized combination for the required orchestration, after comparing them with all the existing triangles5 .

Figure 19: Optimizing the service selection.

Perspectives

We have many ideas to improve and complete our works. In the following, we present some of them.

Enhancing Coma++ with WordNet

Coma++ 6 gives us a primary matching of WSDL which can be improved using WordNet7 together with the service functionality domain, in order to match the fields semantically. After doing so, we can annotate the fields with a WordNet concept to have a semantic service.

By matching the fields using Coma++ with the semantic enrichment, we can find the similar fields and thus, the similar functionalities (operations). This will also help us in the identification of the adaptations, i.e. the extra fields (inputs) in an operation that has a similar functionality of another one that doesn't contain these fields. How can we judge if two operations have a similar functionality or not?

The two services must have the same domain and the two operations must have similar names and common fields (inputs and outputs).

Steps:

1. Extract the domain of functionality for each WSDL interface; 2. Using the Coma++ API to automate the matching process between all the pairs of a WSDL interfaces collection having the same domain;

3. Two operations have a similar functionality, if they have similar names, a similar input, and a similar output; 4. For each domain, there must exist a domain ontology, which can be used to annotate the corresponding services;

5. According to the similarity of inputs-inputs and for inputs-outputs, we can continue our classification based on FCA for finding Web services' substitutes, and RCA for finding composable Web services.

WordNet for a WSDL's domain of functionality

We want to divide the WSDL interfaces into their functionality domains. This categorization can be done with the help of WordNet. In figure 20, we can see the steps that are needed to annotate the WSDL file with the WordNet ontology. Every WSDL will be parsed by a TreeTagger, which is a tool for annotating text with part-of-speech and lemma information. Terms of this annotated text will be mapped onto the WordNet ontology. This gives us a set of WordNet concepts for each WSDL file. In order to find out the domain, we search for the branch in WordNet that contains all the concepts for a certain WSDL file.

Similarity may be calculated afterwards between the set of WordNet concepts retrieved for each WSDL file, in order to find similar operations.

Figure 20: WSDL categorization into functionality domains using WordNet.

Modelling abstract business processes

An abstract business process8 is a partially specified process that is not intended to be executed. It may hide some of the required concrete operational details, and may have a descriptive role of the observable process behavior and template.

• A user defines his orchestrations as abstract business processes;

• for each orchestration he defines a list of user-input-variables;

• for each task inside the orchestration, a domain is specified, in order to identify the set of services offering this needed task;

• the composability level can be determined regarding the user indicated output-input that must be coupled together.

Figure 1 :

 1 Figure 1: The training phase.

Figure 2 :

 2 Figure 2: The tag extraction phase

Figure 4 :

 4 Figure 4: The travel composite service (TCS).

Figure 5 :

 5 Figure 5: The concept lattice for a set of services and their keywords.

Figure 6 :

 6 Figure 6: Queries as concepts in the service × keyword lattice.

•Figure 7 :

 7 Figure 7: The generated lattice for (SimCxt) shown in Table3.

Figure 8 :

 8 Figure 8: The final service lattice with possible backups.

Figure 9 :

 9 Figure 9: The TCS composition with its corresponding backups.

Figure 10 :

 10 Figure 10: Services with availability and performance time values.

  , we can see the binary context corresponding to services and QoS values shown in figure 10. The resulting lattice of the context in figure 11 is illustrated in the figure 12.

Figure 11 :

 11 Figure 11: Binary context of services in figure 10 with their QoS values.

Figure 12 :

 12 Figure 12: The service lattice for the context in figure 11.

Figure 14 :

 14 Figure 14: The relational contexts family (RCF) corresponding to the three sets of services.

  , the three relational contexts for composition of S xi * S yj are called Exact xy , P artial xy and Disjoint xy . We run the RCA algorithm on the RCF, illustrated in Fig. 14. The RCA takes as input all the tables and iterates on two steps: (1) building a concept lattice on each non-relational context of services concatenated with the corresponding relational contexts that express composition, that is on S 1i * QoS concatenated with Exact 12 , P artial 12 and Disjoint 12 , on S 2j * QoS concatenated with Exact 23 , P artial 23 and Disjoint 23 and on S 3k * QoS; (2) transform the six relational contexts to integrate the concepts found at that current step (to use this knowledge in the next iteration). During this transformation, we use the existential scaling operator which is one of the scaling operators provided by RCA. Services that form the columns of a composition context are replaced by concepts that group services. If (S xy , S zt ) initially holds in a composition context (with composition level cl) and S zt is in

Figure 15 :

 15 Figure 15: The services lattices for Task 1 and Task 2.

Figure 17 :

 17 Figure 17: The service lattices with the integrated queries.

Figure 18 :

 18 Figure 18: The lattice associated with the context S 3k of Task 3.

Table 2 :

 2 The similarity matrix (SimM at).

Table 4 :

 4 The interchanged (SimCxt) context.

		op11	op34	op21	op31	op12	op32	op33
	op11	x	x	x
	op34	x	x	x
	op21	x	x	x	x
	op31			x	x
	op12					x	x
	op32					x	x
	op33							x

Table 5 :

 5 The final services × groups context.

http://www.uddi.org/pubs/uddi v3.htm

E. Newcomer and G. Lomow, Understanding SOA with Web Services (Independent Technology Guides). Addison-Wesley Professional, 2004.

S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In Proceedings of the 17th International Conference on Data Engineering (ICDE), pages

421-431, 2001.

Arevalo G., Berry A., Huchard M., Perrot G., Sigayret A.: Performances of Galois Subhierarchy-building algorithms. ICFCA 2007, LNCS/LNAI 4390, pp166-180, Springer Verlag.

We haven't shown all the triangles in Fig.19, for the sake of simplicity.

http://dbs.uni-leipzig.de/Research/coma.html

http://wordnet.princeton.edu/

http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.pdf


Cody Roux

Refinement Types as Higher-Order Dependency Pairs

Refinement types are a well-studied manner of performing in-depth analysis on functional programs. The dependency pair method is a very powerful method used to prove termination of rewrite systems; however its extension to higher-order rewrite systems is still the subject of active research. We observe that a variant of refinement types allows us to express a form of higher-order dependency pair method: from the rewrite system labeled with typing information, we build a type-level approximated dependency graph, and describe a type level embeddingorder. We describe a syntactic termination criterion involving the graph and the order, and prove our main result: if the graph passes the criterion, then every well-typed term is strongly normalizing.

Introduction

Types are used to perform static analysis on programs. Various type systems have been developed to infer information about termination, run-time complexity, or the presence of uncaught exceptions.

We are interested in one such development, namely dependent types [McK06,Bru68]. Dependent types explicitly allow "object level" terms to appear in the types, and can express arbitrarily complex program properties using the so called Curry-Howard isomorphism. We are particularly interested here in refinement types [XS98,FP91]. For a given base type B and a property P on programs, we may form a type R which is a refinement of B and which is intuitively given the semantics: R = {t : B | P(t)}

Programing languages based on dependent type systems have the reputation of being unwieldy, due to the perceived weight of proof obligations in heavily specified types. The field of dependently typed programing can be seen as a quest to find the compromise between expressivity of types and ease of use for the programmer.

Dependency pairs are a highly successful technique for proving termination of first-order rewrite systems [AG00]. However, without modifications, it is difficult to apply the method to higher-order rewrite systems. Indeed, the data-flow of such systems is significantly different than that of first-order ones. Let us examine the rewrite rule:

f (S x) (λy. f y) x
The termination of well-typed terms under this rewrite system combined with β-reduction cannot be inferred by simply looking at the left-hand side f (S x) and the recursive call f y in the right hand side as it could be in first-order rewriting.

Here we need to infer that the variable y can only be instantiated by a subterm of S x. This can be done using dependent types, using a framework called size-based termination or sometimes type-based termination [HPS96,Abe04,BFG + 04,Bla04,BR06].

The dependency pair method rests on the examination of the aptly-named dependency pairs, which correspond to left-hand sides of rules and function calls with their arguments in the right-hand side of the rules. For instance with a rule f (c(x, y), z) g( f (x, y))

We would have two dependency pairs, the pair f (c(x, y), z) f (x, y) and the pair f (c(x, y), z) g( f (x, y)).

We can then define a chain to be a pair (θ, φ) of substitutions, and a couple (t 1 u 1 , t 2 u 2 ) of dependency pairs such that u 1 θ * t 2 φ. We may connect chains in an intuitive manner, and the fundamental theorem of dependency pairs may be stated: a (first-order) rewrite system is terminating if and only if there are no infinite chains. See also the original article [AG00] for details.

To prove that no infinite chains exist, one wants to work with the dependency graph: the graph built using the dependency pairs as nodes and with a vertex between N 1 = t 1 u 1 and N 2 = t 2 u 2 if there exist θ and φ such that (θ, φ), (N 1 , N 2 ) form a chain. It is then shown that if the system is finite, then it is sufficient to consider only the cycles in this graph and prove that they may not lead to infinite chains [GAO02]. It is known that in general computing the dependency graph is undecidable (this is the unification modulo rewriting problem, see e.g. Jouannaud et al . [JKK83]), so in practice we compute an approximation (or estimation) of the graph that is conservative: all edges in the dependency graph are sure to appear in the approximated graph. One common (see for instance Giesl [GTSKF06]) and reasonable approximation is to perform ordinary unification on non-defined symbols (that is, symbols that are not at the head of a left-hand side), while replacing each subterm headed by a defined symbol by a fresh variable, ensuring that it may unify with any other term.

In this article, we show that the dependency pair technique with the approximated dependency graph can be modeled using a form of refinement types containing patterns which denote sets of possible values to which a term reduces. These type-patterns must be explicitly abstracted and applied, a choice that allows us to have very simple type inference. This allows us to build a notion of type-based dependency pair for higher-order rewrite rules, as well as an approximated dependency graph which corresponds to the estimation described above. We describe an order on the type annotations, that essentially capture the subterm ordering, and use this order to express a decrease condition along cycles in the approximated dependency graph. We then state the correctness of the criterion: if in every strongly connected component of the graph and every cycle in the component, the decrease condition holds, then every well-typed term is strongly normalizing under the rewrite rules and β-reduction. The actual operational semantics are defined not on the terms themselves, but on erased terms in which we remove the explicit type information. We then conclude with a comparison with other approaches to higher-order dependency pairs and possible extensions of our criterion.

Syntax and Typing Rules

The language we consider is simply a variant of the λ-calculus with constants. For simplicity we only consider the datatype of binary (unlabeled) trees. The development may be generalized without difficulty to other first-order datatypes, i.e. types whose constructors do not have higher-order recursive arguments. We define the syntax of patterns

p, q ∈ P ≔ α | leaf | node(p, q) | | ⊥
With α ∈ V a set of pattern variables, and is called wildcard. Patterns appear in types to describe possible reducts of terms. We define the set of types:

T, U ∈ T ≔ B(p) | T → U | ∀α.T
An atomic type is a type of the form B(p). The set of terms of our language is defined by:

t, u ∈ Trm ≔ x | f | t u | t p | λx : T.t | λα.t | Node | Leaf
With x ∈ X a set of term variables, f ∈ Σ is a set of function symbols and α ∈ V. Defined symbols are in lower case. Notice that application and abstraction of patterns is explicit. A constructor is either Node or Leaf. A context is a list of judgements x : T with x ∈ X and T ∈ T , with each variable appearing only once.

Intuitively, B(p) denotes the set of terms that reduce to some term that matches the pattern p. For instance, any binary tree t is in the semantics of B( ), only binary trees that reduce to Node t 1 t 2 for some binary trees t 1 and t 2 are in B(node( , )), and only terms that never reduce to a constructor are in B(⊥). Our operational semantics are defined by rewriting, which has the following consequences, which may be surprising to a programming language theorist:

-It may be the case that a term t has several distinct normal forms. Indeed we do not require our system to be orthogonal, or even confluent (we do require it to be finitely branching though). Therefore a term is in the semantics of B(node( , )) if all its reducts reduce to a term of the form Node t u. -It is possible for a term to be stuck in the empty context, that is in normal form and not headed by a constructor or an abstraction. Therefore B(⊥) is not necessarily empty even in the empty context.

We write F V(t) (resp. F V(T ), F V(Γ)) for the set of free variables in a term t (resp. a type T , a context Γ). If a term (resp. pattern) does not contain any free variables, we say that it is closed. We write ∀α.T for ∀α 1 .∀α 2 . . . ∀α n .T , and arrows and application are associative to the left and right respectively, as usual. A pattern variable α appears in B(p) if it appears in p. It appears positively in a type T if:

-T = B(p) and α appears in p -T = T 1 → T 2 and α appears positively in T 2 or negatively in T 1 (or both).

With α appearing negatively in T if T = T 1 → T 2 and α appears negatively in T 2 or positively in T 1 (or both).

We consider a type assignment τ : Σ → T , such that for each f ∈ Σ, there is a number k such that

τ f = ∀α 1 , . . . , α n .A 1 → . . . → A k → T f with -n ≥ k -A i = B(α i ) -∀1 ≤ i ≤ k, α i appears positively in T f .
In this case k is called the number of recursive arguments.

To these rules we add the subtyping rule:

G ⊢ t : T T ≤ U sub Γ ⊢ t : U
Where the subtyping relation is defined by an order on patterns:

-p ≪ -α ≪ α -node ≪ node -p 1 ≪ q 1 ∧ p 2 ≪ q 2 ⇒ node(p 1 , p 2 ) ≪ node(q 1 , q 2 ) -⊥ ≪ p
For all patterns p, p 1 , p 2 , q 1 , q 2 . This order is carried to types by:

-p ≪ q ⇒ B(p) ≤ B(q) -T 2 ≤ T 1 ∧ U 1 ≤ U 2 ⇒ T 1 → U 1 ≤ T 2 → U 2 -T ≤ U ⇒ ∀α.T ≤ ∀α.U
This type system is quite similar to the refinement types described for mini-ML by Freeman et al . [FP91], and is not very distant from generalized algebraic datatypes as are implemented in certain Haskell compilers [JVWW06], though subtyping is not present in that framework.

It may seem surprising that we choose to explicitly represent pattern abstraction and application in our system. This choice is justified by the simplicity of type inference with explicit parameters. In the author's opinion, implicit arguments should be handled by the following schema: at the user level a language without implicit parameters; these parameters are inferred by the compiler, which type-checks a language with all parameters present. Then at run-time they are once again erased. This is exactly analogous to a Hindley-Milner type language in which System F is used as an intermediate language [Mil78,JM97]. It is also our belief that explicit parameters will allow this criterion to be more easily integrated into languages with pre-existing dependent types, e.g. Adga [Nor07], Epigram [McK06] or Coq [Coq08].

A constructor term l ∈ L is a term built following the rules:

l 1 , l 2 ∈ L ≔ x | Leaf | Node l 1 l 2 with x ∈ X.
A rewrite rule is a pair of terms (l, r) which we write l r, such that l is of the form f p 1 . . . p n l 1 . . . l k with f ∈ Σ, p i ∈ P and l i ∈ L, such that k is the number of recursive arguments of f . We suppose that the free variables of r appear in l.

We suppose in addition that every function symbol g ∈ r is fully applied to its pattern arguments, that is if τ g = ∀α 1 . . . α l .T then for each occurrence of g in r there are patterns p 1 , . . . , p l ∈ P such that g p 1 . . . p l appears at that position.

In the following we consider a finite set R of rewrite rules. The set R is well-typed if for each rule l r ∈ R, there is a context Γ and a type T such that Γ ⊢ min l : T and Γ ⊢ r : T with ⊢ min defined in figure 2.

α Γ, Γ ′ Γ, x : B(α), Γ ′ ⊢ min x : B(α) Γ ⊢ min Leaf : B(leaf) Γ ⊢ min l 1 : B(p 1 ) Γ ⊢ min l 2 : B(p 2 ) Γ ⊢ min Node p 1 p 2 l 1 l 2 : B(node(p 1 , p 2 )) Γ ⊢ min l 1 : B(p 1 ) . . . Γ ⊢ min l k : B(p k ) α Γ Γ ⊢ min f p 1 . . . p k β k+1 . . . β l l 1 . . . l k : T f φ With τ f = ∀α 1 . . . α l .A 1 → . . . → A k → T f and φ(α i ) = p i if 1 ≤ i ≤ k and φ(α j ) = β j for k < i ≤ l.

Fig. 2. Minimal Typing Rules

Notice that if Γ ⊢ min l i : T then T is unique. Minimal typing is present in other work on size-based termination [BR09], in which it is called the pattern condition. The purpose of minimal typing is to constrain the possible types of constructor terms in left hand sides.

We can then define the higher-order analogue of dependency pairs, which use type information instead of term information.

Definition 1 Let ρ = f p l r be a rule in R, with Γ such that Γ ⊢ min f p l : T , and Γ ⊢ r : T . The set of type dependency pairs DP T (ρ) is the set { f ♯ (p 1 , . . . , p k ) g ♯ (q 1 , . . . , q l ) | ∀i, Γ ⊢ min l i : B(p i ) ∧ g q 1 . . . q l appears in r}

The set DP T (R) is defined as the union of all DP T (ρ), for ρ ∈ R, where we suppose that all variables are disjoint between dependency pairs. The set of higher-order dependency pairs defined above should already be seen as an abstraction of the traditional dependency pair notion (for example those defined in [AG00]). Indeed, due to subtyping, there may be some information lost in the types, if for instance the wildcard pattern is used. As an example, if f, g and h all have type ∀α.B(α) → B( ), consider the rule

f α x g (h α x)
The dependency pair we obtain is

f ♯ (x) g ♯ ( )
The information that g is called on the argument h x is lost.

This approach can therefore be seen as a type based manner to study an approximation of the dependency graph. Note that in the case where h is given a more precise type, like B(α) → B(leaf), which is the case if every normal form of h t is either neutral or Leaf, we have a more precise approximation.

Note that, in addition, a dependency pair is not formally a (higher-order) rewrite rule, though it may be seen as a first-order one.

Definition 2 Let p and q be patterns. We say that p and q are pattern-unifyable, and write p ⊲⊳ q, if p ′ and q ′ are unifyable, where p ′ and q ′ are the patterns p and q in which each occurrence of and each occurrence of a variable is replaced by some fresh variable.

The standard typed dependency graph G R is defined as the graph with -As set of nodes the set DP T (R).

-An edge between the dependency pairs t g ♯ (p 1 , . . . , p k ) and h ♯ (q 1 , . . . , q l ) u if g = h, k = l and for every

1 ≤ i ≤ k, p i ⊲⊳ q i .
This definition gives us an adequate higher-order notion of standard approximated dependency graph. We will now show that it is possible to give an order on the terms in the dependency pairs, which is similar to a simplification order and which will allow us to show termination of well-typed terms under the rules, if the graph satisfies an intuitive decrease criterion.

Definition 3

We define the embeddeding preorder on P written p ⊲ q by the following rules

-p i q ⇒ node(p 1 , p 2 ) ⊲ q for i = 1, 2 -p 1 ⊲ q 1 ∧ p 2 q 2 ⇒ node(p 1 , p 2 ) ⊲ node(q 1 , q 2 ) -p 1 q 1 ∧ p 2 ⊲ q 2 ⇒ node(p 1 , p 2 ) ⊲ node(q 1 , q 2 )
With as the reflexive closure of ⊲ and with the further condition that if p ⊲ q, then p and q may not contain any occurrence of .

Non termination can intuitively be traced to cycles in the dependency graph. We wish to consider termination on terms with erased pattern arguments and type annotations.

Operational Semantics and the Main Theorem

Rewriting needs to be performed over terms with erased pattern annotations. The problem with the naïve definition of rewriting arises when trying to match on patterns. Take the rule

f node(α, β) (Node x y) Leaf
In the presence of this rule, we wish to have, for instance, the reduction

f (Node (g x) (h x)) Leaf
However, there is no substitution θ such that node(α, β)θ = . There are two ways to deal with this. Either we take subtyping into account when performing matching, or we do away with the pattern arguments when performing reduction. We adopt the second solution, as it is used in practice when dealing with languages with dependent type annotations (see for example McKinna [McK06]). Symmetrically, we erase pattern abstractions as well.

Definition 4 We define the set of erased terms Trm | | as:

t, u ∈ Trm | | ≔ x | f | λx.t | t u | Leaf | Node Where x ∈ X and f ∈ F .
Given a term t ∈ Trm, we define the erasure |t| ∈ Trm | | of t as:

|x| = x | f | = f |λx : T.t| = λx.|t| |λα.t| = |t| |t u| = |t| |u| |t p| = |t| | Leaf | = Leaf | Node | = Node
An erased term can intuitively be thought of as the compiled form of a well typed term.

Definition 5 An erased term t head rewrites to a term u if there is some rule l r ∈ R and some substitution σ from X to terms in

Trm | | such that |l|σ = t ∧ |r|σ = u We define β-reduction β as λx.t u β t{x → u}
And we define the reduction as the closure of head-rewriting and β-reduction by term contexts. We then define * and + as the symmetric transitive and transitive closure of , respectively.

We can now express our termination criterion. We need to consider the strongly connected components, or SCCs of the typed dependency graph. A strongly connected component of a graph G is a full subgraph such that each node is reachable from all the others.

Theorem 6 Let G be the typed dependency graph for R and let G 1 , . . . , G n be the SCCs of G. Suppose that for each G i , there is a recursive index ι i : Σ → N which to f ∈ Σ associates an integer 1 ≤ ι i f ≤ k (with k the number of recursive arguments of f ).

Suppose that for each 1 ≤ i ≤ n and each rule f ♯ (p 1 , . . . , p n ) g ♯ (q 1 , . . . , q m ) in G i , we have p ι i f q ι i g . Finally suppose that for each cycle in G i , there is some rule f ♯ (p 1 , . . . , p n ) g ♯ (q 1 , . . . , q m ) such that

p ι i f ⊲ q ι i g then for every Γ, t, T such that Γ ⊢ t : T , |t| ∈ SN R
The proof of this theorem can be found in the appendix. Let us give two examples of the application of this technique.

Example 1 Take the rewrite system given by the signature:

{app : ∀αβ.(B(α) → B(β)) → B(α) → B(β), f : B(leaf), g : ∀α.B(α) → B(leaf)}, . We give the rewrite rules: app → λαβ.λx : B(α) → B(β).λy : B(α).x y f → app node(lea f, lea f ) leaf (g node(leaf, leaf)) (Node leaf leaf Leaf Leaf) g node(α, β) (Node α β x y) → Leaf g leaf Leaf → f
or, in more readable form with pattern arguments and type annotations omitted:

app → λx.λy.x y f → app g (Node Leaf Leaf) g (Node x y) → Leaf g Leaf → f
It is possible to verify that the criterion can be applied and that in consequence, according to theorem 6, all well typed terms are strongly normalizing under R∪β.

Indeed, we may easily check that each of these rules is minimally typed in some context. Furthermore, we can check that the dependency graph in figure 3 has no cycles.

One may object that if we inline the definition of app and perform β-reduction on the right-hand sides of rules we obtain a rewrite system that can be treated with more conventional methods, such as those performed by the AProVe tool [GTSK05] (on terms without abstraction, and without β-reduction). However this operation can be very costly if performed automatically and is, in its most naïve form, ineffective for even slightly more complex higher-order programs such as map, which performs pattern matching and for which we need to instantiate. By resorting to typing, we allow termination to be proven using only "local" considerations, as the information encoding the semantics of app is contained in its type.

g ♯ (leaf) f ♯ f ♯ app ♯ f ♯ g ♯ (node(leaf, leaf))
However it becomes necessary, if one desires a fully automated termination check on an unannotated system, to somehow infer the type of defined constants, and possibly perform an analysis quite similar in effect to the one proposed above. We believe that to this end one may apply known type inference technology, such as the one described in [CK01], to compute these annotated types. In conclusion, what used to be a termination problem becomes a type inference problem, and may benefit from the knowledge and techniques of this new community, as well as facilitate integration of these techniques into type-theoretic based proof assistants like Coq [Coq08].

Let us examine a second, slightly more complex example, in which there is "real" recursion.

Example 2 Let R be the rewrite system defined by

f (Node x y) → g (i (Node x y) g (Node x y) → f (i x) g Leaf → f (h Leaf) i (Node x y) → Node (i x) (i y) i Leaf → Leaf h (Node x y) → h x
Again with the type arguments omited, and with types f, g : ∀α.B(α) → B( ), h : ∀α.B(α) → B(⊥) and i : ∀α.B(α) → B(α). Every equation can by typed in the context Γ = x : B(α), y : B(β), The system with full type annotations is given in the appendix.

The dependency graph is given in figure 3, and has as SCCs the full subgraphs of G R with nodes {i ♯ (node(α, β))

i ♯ (α), i ♯ (node(α, β)) i ♯ (β)}, { f ♯ (node(α, β)) g ♯ (node(α, β), g ♯ (node(α, β) f ♯ (α)} and {h ♯ (node(α, β)) h ♯ (α)} respectively.
Taking ι s = 1 for every SCC and every symbol s ∈ Σ, it is easy to show that every SCC respects the decrease criterion on cycles. For example, in the cycle

f ♯ (node(α, β)) g ♯ (node(α, β)) ⇆ g ♯ (node(α, β)) f ♯ (α)
we have node(α, β) node(α, β) and node(α, β)⊲α, so the cycle is weakly decreasing with at least one strict decrease.

We may then again apply the correctness theorem to conclude that the erasure of all well-typed terms are strongly normalizing with respect to R ∪ β. This rule can be typed in the context x : B(node(leaf, leaf)), y : B(leaf), but not minimally typed, and passes the termination criterion: the dependency graph is without cycles, as node(leaf, leaf) does not unify with leaf. However, this system leads to the non terminating reduction f Leaf Leaf f Leaf Leaf.

i ♯ (node(α, β)) i ♯ (α) i ♯ (node(α, β)) i ♯ (β) f ♯ (node(α, β)) g ♯ (node(α, β)) f ♯ (node(α, β)) i ♯ (node(α, β)) g ♯ (node(α, β)) f ♯ (α) g ♯ (node(α, β)) i ♯ (node(α, β)) g ♯ (leaf) f ♯ (⊥) g ♯ (lea f ) h ♯ (leaf) h ♯ (node(α, β)) h ♯ (α)

Comparison, future work

Several extensions of dependency pairs to different forms of higher-order rewriting have been proposed [KISB09,Bla06,GTSK05,SK05,AY05]. However, these frameworks do not handle the presence of bound variables, for which the usual approach is to defunctionalize (also called lambda-lifting) [DN01,Joh85].

In particular, all the techniques cited above, when applied to example 1, where we replace the rule app → λx.λy.x y with the rule app x y → x y (which does not involve bound variables), generate a dependency graph with cycles. For example, in Sakai & Kusakari [SK05], using the SN framework the dependency graph is:

f [] g[] f [] app[g, Node[Leaf, Leaf]] g[Leaf] f [] app[x, y] x[y]
It is of course possible to prove that there are no infinite chains for this problem (the criterion is complete), but we have not much progressed from the initial formulation! Using the SC-framework from the same paper, which is based on computability (as is our framework), we obtain the following graph:

f [] g[z] f [] app[g, Node[Leaf, Leaf]] g[Leaf] f []
However it is not possible to prove that there are no infinite chains for this problem, as there is one! Therefore the criterion presented in this paper allows a finer analysis of the possible calls.

The termination checking software AProVE [GTSK05] succeeds in proving termination of example 1, by using an analysis involving instance computation and symbolic reduction. As noted previously, it seems that such an analysis may be used to infer the type annotations required in our framework. At the moment it is unclear how the typing approach compares to these techniques. More investigation is clearly needed in this direction.

AProVE can also easily prove termination of the second rewrite system (example 2). However semantic information needs to be inferred (for example a polynomial interpretation needs to be given) when trying to well-order the cycle

f (Node x y) g (i (Node x y) ⇆ g (Node x y) f (i x)
This information is already supplied by our type system (through the fact that i is of type ∀α.B(α) → B(α)), and therefore it suffices to consider only syntactic information on the approximated dependency graph. The subterm criterion by Aoto and Yamada [AY05] is insufficient to treat this example.

The framework described here is only the first step towards a satisfactory higher-order dependency pair framework using refinement types. We intuitively consider a "type level" first-order rewrite system, use standard techniques to show that that system is terminating, and show that this implies termination of the object level system. More work is required to obtain a satisfactory "dependency pairs by typing" framework.

Our work seems quite orthogonal to the size-change principle [LJBa01], which suggests we could apply this principle to treat cycles in the typed dependency graph, as a more powerful criterion than simple decrease on one indexed argument.

It is clear that the definitions and proofs in the current work extend to other first-order inductive types like lists, Peano natural numbers, etc. We conjecture that this framework can be extended to more general positive inductive types, like the type of Brower ordinals [BJO02]. These kinds of inductive types seem to be difficult to treat with other (non type-based) methods.

For now types have to be explicitly given by the user, and it would be interesting to investigate inference of annotations. Notice that trivial annotations (return type always B( )) can very easily be infered automatically. Some work on automatic inference of type-level annotations has been carried out by Chin et al . [CK01] which may provide inspiration. On the other hand, we believe that the inference of the explicit type information in the terms is quite feasible with current state-of-the-art methods, for example those used for inferring the type of functional programs using GADTs [JVWW06].

We believe that refinement types are simply an alternative way of presenting the dependency pair method for higher-order rewrite systems. It is the occasion to draw a parallel between the types community and the rewriting community, by emphasizing that techniques used for the inference of dependent type annotations (for example work on liquid types [RKJ08]), may in fact be used to infer information necessary for proving termination and (we believe) vice-versa. It may also be interesting in the case of a programming language for the user to supply the types as documentation, in what some call "type directed programing".

We only consider matching on non-defined symbols, though an extension to a framework with matching on defined symbols seems feasible if we add some conversion rule to our type system.

A The full system of example 2

Every rule is typed in the context x : B(α), y : B(β), and we remind that the types of defined functions are:

f, g : ∀α.B(α) → B( ) h : ∀α.B(α) → B(⊥) i : ∀α.B(α) → B(α)
The rewrite system with all type annotations is then

f node(α, β) (Node α β x y) → g node(α, β) (i node(α, β) (Node α β x y) g node(α, β) (Node α β x y) → f α (i α x) g leaf Leaf → f ⊥ (h leaf Leaf) i node(α, β) (Node α β x y) → Node node(α, β) (i α x) (i β y) i leaf Leaf → Leaf h node(α, β) (Node α β x y) → h α x B Proof of theorem 6
The proof uses computability predicates (or candidates). As mentioned before, the absence of control, and particularly the lack of orthogonality makes giving accurate semantics somewhat difficult. We draw inspiration from the termination semantics of Berger [Ber05], which uses sets of values to denote terms. As is standard in computability proofs, each type will be interpreted as a set of strongly normalizing (erased) terms. Suppose a term t reduces to the normal forms Leaf and Node Leaf Leaf. In that case t is in the candidate that contains all terms that reduce to Leaf or Node Leaf Leaf, or are hereditarily neutral. If t the erasure of a term of type B(α) for some pattern variable α, the interpretation [[B(α)]] must depend on some valuation of the free variable α. If we valuate α by some closed pattern p and interpret [[B(α)]] by the set of terms whose normal forms are neutral or match p, then the only possible choice for p is . Clearly this does not give us the most precise possible semantics for t, as it also includes terms such as u = Node (Node x y) Leaf. However we need precise semantics if we are to capture the information needed for the dependency analysis: if we take the constructor term l = Node Lea f x, then a reduct of t does match l, but this can never happen for u. To give sufficiently precise semantics to terms, we therefore need to interpret pattern variables with sets of closed patterns. In this case we will interpret α by the set {leaf, node(leaf, leaf)} to capture the most precise semantics possible for t.

We define the interpretation of types, and prove that they satisfy the Girard conditions. We then show that correctness of the defined function symbols implies correctness of the semantics.

Definition 7 A value is a term v ∈ Trm | | of the form: -λx.t -Node t u -Leaf For any t ∈ Trm | | we say v is a value of t if t * R∪β v and v is a value. A term is neutral if it is not a value,
-v ≪ -v ≪ p if v is neutral. -v ≪ node(p, q) if v = Node v 1 v 2 with v 1 ≪ p ∧ v 2 ≪ q. -v ≪ leaf if v = Leaf.
A pattern valuation, or valuation if the context is clear, is a partial function with finite support from pattern variables V to non-empty sets of closed patterns. If p is a pattern, θ is a pattern valuation and F V(p) ⊆ dom(θ) then pθ is the set defined inductively by:

-αθ = θ(α) -leaf θ = leaf -θ = -⊥θ = ⊥ -node(p 1 , p 2 )θ = {node(q 1 , q 2 ) | q 1 ∈ p 1 θ ∧ q 2 ∈ p 2 θ}
We may write pθ = {p | α 1 ← θ(α 1 ), . . . , α n ← θ(α n )}, using inspiration from list comprehension notation (as in Berger [Ber05]). If α dom(θ) and P is a nonempty set of closed patterns, we write θ al P for the valuation that sends β ∈ dom(θ) to θ(β) and α to P. Notice that pθ is a set of closed patterns.

Finally if θ is a valuation and t is a term in SN, we write t ≪ pθ if for every normal form v of t: ∃q ∈ pθ, v ≪ q

The type interpretation [[ ]] is a function that to each T ∈ T and each valuation θ such that F V(T ) ⊆ dom(θ) associates a set [[T ]] θ ⊆ SN R∪β . We define it by induction on the structure of T :

-

[[B(p)]] θ = {t ∈ B | t ≪ pθ} -[[T → U]] θ = {t ∈ SN | ∀u ∈ [[T ]] θ , t u ∈ [[U]] θ } -[[∀α.T ]] θ = {t ∈ SN | ∀P, t ∈ [[T ]] θ α
P } Where B is the smallest set that verifies: sub: By application of the correctness of subtyping (lemma 18), and the induction hypothesis.

B = {t ∈ SN | ∀v a value of t, v = Leaf ∨v = Node t 1 t 2 ∧ t 1 , t 2 ∈ B} -node-intro: let t, u be terms in [[B(α)]] θ and [[B(β)]] θ ,
Now it remains to show that each function symbol is computable. By analogy with the first-order dependency pair framework, we need to build an order on terms that is in relation to the approximated dependency graph. Then sequences of decreasing terms will be the analogue of chains, and we will show that there can be no infinite decreasing sequences. Instead of actual terms, it is more convenient, when dealing with higher-order rewriting, to order tuples of terms labeled by a head function symbol, i.e. instead of having f t > gu we have ( f, t) > (g, u). The reason for this is that recursive calls in the right-hand side of rewrite rules needn't be applied to all their arguments. We will therefore need a way of using typing to "predict" which arguments may be applied, using the order on tuples as above.

However it is quite subtle to build this order in practice: indeed, a natural candidate for such an order is (the transitive closure of) the order defined by ( f, t) > (g, u) if and only if

∃θ, φ, f ♯ (p 1 , . . . , p n ) g ♯ (q 1 , . . . , q m ) ∈ G, ∀i, j, t i ∈ [[B(p i )]] θ ∧ u j ∈ [[B(q j )]] φ
This would allow us to easily build the relation between the graph and the order, and show that each call induces a decrease in this order. Sadly, this order may not be well founded even in the event that the termination criterion is satisfied. Consider for example the rule f node(α, β) (Node x y) f α x, typeable in the context Γ = x : B(α), y : B(β). Given the above definition, we have ( f, t) > ( f, u) provided that there are closed p and q such that t ≪ p and u ≪ q. But then we may take p = q = and if t = z and u = z with z a variable, then ( f, z) > ( f, z). The rewrite system does satisfy the criterion, as node(α, β) ⊲ α, but the order is not well founded.

One possible solution is to restrict the reduction to call-by value on closed terms, where a reduction in R can occur only if the arguments to the defined function are in normal form, and values (although β-reduction can occur at any moment). However we strive for more generality.

Another solution, in the previous example, is to impose the condition that t must be equal to Node t 1 t 2 , which makes the counter-example invalid. However, we still do not have any necessary relationship between t and u, and we may take in particular t = Node x y and u = Node x y, which again results in a non well founded sequence. The solution is to take, instead of just a particular instance of the pattern variables, the most general possible instance. Definition 20 Take the set P min of minimal patterns to be the subset of P defined by: p, q

∈ P min ≔ α | leaf | node(p, q)
Let t be a term in normal form. We inductively define the pattern form pat(t) of t inductively:

-pat(t) = ⊥ if t is neutral. -pat(Leaf) = leaf -pat(Node t u) = node(pat(t), pat(u)) -pat(t) = otherwise.
We define the partial type matching function match P that takes terms t 1 , . . . , t n in Trm | | , and minimal patterns p 1 , . . . , p n in P min and returns a pattern valuation:

-if p 1 = α 1 , . . . , p n = α n and t i = t j whenever α i = α j , then match P (t, p)(α i ) = t i -if p i = node(q 1 ,
q 2 ) and t i = Node u 1 u 2 then match P (t; p) = match P (t 1 , . . . , t i-1 , u 1 , u 2 , t i+1 , . . . , t n ; p 1 , . . . , p i-1 , q 1 , q 2 , p i+1 , . . . , p n ) -if p i = leaf and t i = Leaf then match P ( p, t) = match P (t 1 , . . . , t i-1 , t i+1 , . . . , t n ; p 1 , . . . , p i-1 , p i+1 , . . . , p n ) match P is undefined in other cases.

The type matching can be seen as a way of giving the most precise possible valuation for terms that match some left-hand side of a rule. Notice that for each f ♯ ( p) g ♯ (q) ∈ G, each p i is in P min . Indeed, an examination of the minimal typing rules show that only minimal patterns may appear in types.

Note also that if match(t, p) = θ, then for each i, t i ≪ p i θ, by a simple induction.

Definition 21 A link is a tuple (n, t, u) such that -t, u ∈ SN -n = f ♯ ( p) g ♯ (q) ∈ G -match P (t, p) is defined, and if it is equal to θ, then ∀ j, u j ≪ q j θ ′ For some extension θ ′ of θ such that F V(q) ⊆ dom(θ ′ ).
A chain is an eventually infinite sequence c 1 , c 2 , . . . of links such that if c i = (n i , t i , u i ), then for each i,

u i * t i+1 and if n i = f ♯ i ( p) g ♯ i (q) then g i = f i+1 . Notice that if F V(q) ⊆ F V( p) then we may take θ ′ = θ in the definition of chains.
We first need to show a correspondence between the chains and the graph, that is:

Lemma 22 For each chain c 1 , c 2 , . . . such that c i = (n i , t i , u i ), there is a path n 1 → n 2 → . . . in G R . Proof. It suffices to show that if c 1 = (n 1 , t, u), c 2 = (n 2 , u ′ , v) is a chain, then there is an edge between n 1 = f ♯ ( p)
g ♯ (q) and n 2 = g ♯ (r) h ♯ (s). First note that the variables of q and r are distinct by hypothesis. Notice that for each i, u i ≪ q i θ for some t and match P (r i , u ′ i ) is defined. We need to prove for each i that q i ⊲⊳ r i . As u i * u ′ i , all normal forms of u ′ i are also normal forms of u i . We proceed by induction on match P (r i , u ′ i ).

r i is a variable. We can conclude immediately by the definition of ⊲⊳, as a fresh variable can unify with any pattern. u ′ i = Leaf and r i = leaf. In this case Leaf is a normal form of u i , so there is some q ′ ∈ q i θ such that Leaf ≪ q ′ . From this it follows that q i is either leaf, or some variable. This allows us to conclude that q i ⊲⊳ leaf. u ′ i = Node u ′1 i u ′2 i and r i = node(r 1 i , r 2 i ). Now let us examine q i . We may exclude the cases q i = leaf and q i = ⊥, as every normal form of u ′ i is a normal form of u i and is of the form Node v v ′ . In the case q i = α or q i = we may easily conclude. The only remaining case is q i = node(q 1 i , q 2 i ). From the induction hypothesis we get q 1 i ⊲⊳ r 1 i and q 2 i ⊲⊳ r 2 i , which imply q i ⊲⊳ r i

If the conditions of the termination theorem are satisfied, the there are no infinite chains, in the same way as for the first-order dependency pair approach.

Theorem 23 Suppose that the conditions of theorem 6 are satisfied. Then there are no infinite chains.

We need to define and establish the well foundedness of the embedding order on terms.

Definition 24 We mutually define the strict and large embedding preorder on erased terms in normal form ⊲ and by:

-t 1 u ⇒ Node t 1 t 2 ⊲ u -t 2 u ⇒ Node t 1 t 2 ⊲ u -t 1 ⊲ u 1 ∧ t 2 u 2 ⇒ Node t 1 t 2 ⊲ Node u 1 u 2 -t 1 u 1 ∧ t 2 ⊲ u 2 ⇒ Node t 1 t 2 ⊲ Node u 1 u 2 -Leaf Leaf -t u if t and u are neutral. -t ⊲ u ⇒ t u
Note that the preorder is not an order: for instance, x y and y x.

Lemma 25 The preorder ⊲ is well-founded.

Proof. Given a term in normal form t, define size(t) inductively:

size(Node t 1 t 2 ) = size(t 1 ) + size(t 2 ) + 1 size(t) = 0 otherwise.

It is then easy to verify by mutual induction that if t ⊲ u, size(t) > size(u) and if t u then size(t) ≥ size(u). Well foundedness of the order on naturals yields the desired conclusion.

To show that there are no infinite chains, we will exploit the fact that if c = (n, t, u) is a link, that is decreasing in the embedding order on patterns, then there is a decrease in the normal forms from t to u.

To show this, we must prove that pattern-matching does indeed completely capture the "pattern semantics" of a term in B.

Lemma 26 Suppose t are terms in B and p are minimal patterns. If match P (t, p) is defined and equal to θ, then for each q ∈ p i θ, is a normal form v of t i such that pat(v) = q.

Proof. We proceed by induction on the definition of match P :

p i = α i . In this case (as match P (t, p) is defined) By definition αθ is equal to {pat(v) | v is a normal form of t i }. p i = leaf. In this case t i = Leaf and therefore we can take v = Leaf.

p i = node(p 1 i , p 2 i ). In this case, t i = Node t 1 i t 2 i . By the induction hypothesis, for any q 1 ∈ p 1 i θ and q 2 ∈ p 2 i θ there are normal forms v 1 and v 2 of t 1 i and t 2 i such that q j = pat(v j ) for j = 1, 2. It is easy to observe that Node v 1 v 2 is a normal form of t i , and that q = node(q 1 , q 2 ) is an element of p i θ, and pat(Node v 1 v 2 ) = q allows us to conclude.

To prove that there are no infinite chains, we need to relate the decrease of the patterns to the decrease of the normal forms of the terms that appear in chains.

Lemma 27 Suppose that p and q are closed patterns such that p ⊲ q (respectively p q), and v 1 , v 2 normal forms such that pat(v 1 ) = p and v 2 ≪ q. Then v 1 ⊲ v 2 (respectively v 1 v 2 ).

Proof. We prove both properties simultaneously by induction on the derivation of p ⊲ q:

p = node(p 1 , p 2 ) and p 1 q. We have v 1 = Node u 1 u 2 with pat(u 1 ) = p 1 . By induction hypothesis u 1 v 2 , and therefore Node u 1 u 2 ⊲ v 2 . p = node(p 1 , p 2 ), q = node(q 1 , q 2 ) with p 1 ⊲ q 1 and p 2 q 2 . In that case v

1 = Node v 1 1 v 2 1 and v 2 = Node v 1 2 v 2 2 . The induction hypothesis gives v 1 1 ⊲ v 1 2 v 2 1 v 2
2 , from which we may conclude. -The symmetrical cases are treated in the same manner.

p = leaf and q = leaf. In this case, v 1 = v 2 = Leaf, and v 1 v 2 .

Lemma 28 Let c = (n, t, u) be some link such that n = f ♯ ( p) g ♯ (q). Suppose that there is i such that p i ⊲ q i , (respectively p i q i ). Then if v is a normal form of u, there exists some normal form v ′ of t such that v ′ ⊲ v, (respectively v ′ v).

Proof. Let θ = match P (t, p), which is guaranteed to exist by hypothesis. First notice that for every α ∈ F V( p), θ(α) does not contain . Indeed, given t ∈ B, the normal form of t is also in B. It can only be neutral, equal to Leaf, or in the form Node t 1 t 2 with t i in the above form.

We treat the ⊲ case first. Suppose that v is a normal form of u i . By definition, we have u i ≪ q i θ, which means by definition that there is some r ∈ q i θ such that v ≪ r. Since p i ⊲ q i , this implies that there is some r ′ ∈ p i such that r ′ ⊲ r. We have by lemma 26 that there exists some v ′ a normal form of t i such that pat(v ′ ) = r ′ , which allows us to conclude using lemma 27.

We finally have all the tools to give the proof of well foundedness of chains. Proof. of theorem 23. By contradiction, let c 1 , c 2 , . . . be an infinite chain, such that for each i, c i = (n i , t i , u i ). By lemma 22, n 1 , n 2 , . . . is an infinite path in G. By finiteness of G, there is some SCC G ′ and some natural number k such that n k , n k+1 , . . . is contained in G ′ . By hypothesis, if

n i = f ♯ i ( p i ) g ♯ i (q i ),
there is an index j such that for each i, p i j q i j or p i j ⊲ p j i . Furthermore, again by hypothesis, there are an infinite number of indexes i such that p i j ⊲ q i j . Let V i = {v | v is a normal form of t i j } and U i = {v | v is a normal form of u i j }. We apply lemma 28 to show that for each v ′ i ∈ U i there exists v i ∈ V i such that v i ⊲ v ′ i for these indexes and v i v ′ i for the others.

We wish to show that there is an infinite chain v 1 , v 2 , . . . such that v i v i+1 for each i and v i ⊲ v i+1 for an infinite number of indexes i, contradicting wellfoundedness of ⊲ (lemma 25).

To do this we first notice that V i+1 ⊆ U i , as u i * t i+1 . Then we build the following tree:

-We have a node at the top, connected to every element of V k .

-We have a node between a ∈

V i and b in U i if a b or a ⊲ b. -We have a node between a ∈ U i and b ∈ V i+1 if a = b.
Notice first that every V i , U i is finite, as the rewrite system is finite (each strongly normalizing term therefore has a finite number of normal forms). We wish to apply König's lemma which states: every finitely branching infinite tree has an infinite path. It is easy to see that the tree is finitely branching: every V i and U i is finite, and it is equally easy to verify that the tree is infinite, as no V i or U i is empty (the t i and u i are strongly normalizing and therefore have at least one normal form). This give us the existence of an infinite path in the tree, which concludes the proof.

To prove that the function symbols are in the interpretation of their type, we shall (obviously) need to consider the rewrite rules. In particular, we need to relate the minimal typing used to derive the types of left hand sides and pattern matching, in order to prove that our notion of chain is the correct one.

Lemma 29 Suppose that Γ is a context, that l 1 , . . . , l k are constructor terms and that Γ ⊢ min l 1 : B(p 1 ), . . . , Γ ⊢ min l k : B(p k ). Suppose that t 1 , . . . , t k match l 1 , . . . , l k . Then match P (t, p) is defined.

Proof. We proceed by induction on the structures of l i (matching the cases of the match P judgement) l 1 = x 1 , . . . , l n = x n . In this case, the only applicable case for ⊢ min is the variable case. If x i = x j , then t i = t j . Furthermore p i = α i for some variable α i and again, α i = α j if and only if x i = x j , by linearity of α i and α j in Γ. Therefore if α i = α j , then t i = t j , and match P (t, p) is defined. l i = Leaf. In this case the only applicable rule is the leaf rule, and p i = leaf and t i = Leaf. By induction match P (t, p) is defined. l i = Node l 1 i l 2 i . In this case we apply the node rule, and we have p i = node(p 1 i , p 2 i ). Again, we have t i = Node t 1 i t 2 i , and we may conclude by the induction hypothesis.

Our reason for defining pattern matching is to provide the "closest" possible pattern semantics for a term. In fact we have the following result, which states that any valuation θ such that t is in [[B(α)]] θ can be "factored through" match(t, p):

Lemma 30 Suppose that t is a tuple of strongly normalizing terms, that α is a tuple of pattern variables, and θ ′ is a valuation that verifies:

∀i, t i ∈ [[B(α i )]] θ ′
Suppose in addition that p are minimal patterns such that match P (t, p) is defined and equal to θ. Let φ be the substitution that sends α i to p i . Then ∀i, θ • φ(α i ) ≪ θ ′ (α i ) Proof. We proceed by induction on the judgment match P (t, p).

p i = β i for each p i , and therefore φ(α i ) = β i . In that case, θ • φ(α i ) = {pat(v) | v normal form of t i }. Furthermore, t i ≪ θ ′ (α i ). Take some v a normal form of t i . We have some q ∈ θ ′ (α i ) such that v ≪ q. We then verify that pat(v) ≪ q, which implies θ • φ(α i ) ≪ θ ′ (α i ) p i = leaf. In this case, θ ′ • φ(α i ) = leaf. By t i ≪ θ ′ (α i ) and t i = Leaf, we have that θ ′ (α i ) contains leaf or , and in each case we can conclude. p i = node(p 1 i , p 2 i ). In this case, t i = Node t 1 1 t 2 i , and

θ • φ(α i ) = {node(r 1 , r 2 ) | r 1 ∈ p 1 i θ ∧ r 1 ∈ p 2 i θ}
By t i ≪ θ ′ (α i ) we have for each normal form v of t i some q in θ ′ (α i ) such that v ≪ q. In addition v is of the form Node v 1 v 2 , where v 1 is a normal form of t 1 i and v 2 is a normal form of t 2 i . From this we get that either q = , in which case we are done, or q = node(q 1 , q 2 ) with v 1 ≪ q 1 and v 2 ≪ q 2 . In this case we apply the induction hypothesis to deduce that there is some r 1 ∈ p 1 i θ and r 2 ∈ p 2 i θ such that r 1 ≪ q 1 and r 2 ≪ q 2 , and thus node(r 1 , r 2 ) ≪ node(q 1 , q 2 ).

Definition 31 We define the following order > d p on pairs ( f, t) with f ∈ Σ and t a tuple of terms:

( f, t) > d p (g, u) ⇔ ∃t ′ , n = f ♯ ( p) g ♯ (q), t * t ′ ∧ (n, t ′ , u) is a link That is, if t reduces to t ′ such that there is a link between t ′ and u, and where the associated node corresponds to a call from f to g.

Lemma 32 If the conditions of theorem 6 are satisfied then the order > d p is well-founded.

Proof. Any infinite decreasing sequence ( f 1 , t 1 ) > ( f 1 , t 2 ) > . . . gives rise to an infinite chain, which is not possible by theorem 23.

We have enough to prove the main theorem, that is correctness of defined symbols.

Theorem 33 Suppose that the conditions of theorem 6 are satisfied. Then for each f ∈ Σ and each valuation θ, f ∈ [[τ f ]].

Proof. Suppose that τ f = ∀α.B(α 1 ) → . . . → B(α k ) → T f . Take θ a valuation and t 1 , . . . , t n in [[B(α 1 )]] θ , . . . , [[B(α k )]] θ . We need to show that

f t 1 . . . t n ∈ [[T f ]] θ
Note that each t i is strongly normalizing. We proceed first by induction on t ordered by strict reduction. As t = f t is neutral, it suffices to consider all the one step reducts t ′ of t. These reducts are of two forms:

Fig. 3 .

 3 Fig. 3. Dependency graph of example 1

Fig. 4 .

 4 Fig. 4. The dependency graph for example 2

  and is hereditarily neutral if it has no values. Definition 8 Let P c be the set of closed patterns, and NF is the set of Rβnormal forms in Trm | | . The term matching relation ≪ ⊆ NF × P c is defined in the following way:

  respectively. The normal forms of Node t u are of the form Node t ′ u ′ , with t ′ and u ′ normal forms of t and u, respectively. Therefore, to check if Node t u ≪ node(θ(α), θ(β)), it suffices to check t ≪ θ(α) and u ≪ θ(β), both of which are true by hypothesis.t-app: straightforward by the induction hypothesis. -p-app: by hypothesis, |t|σ ∈ [[∀x.T ]] θ , this gives by definition |t|σ ∈ [[T ]] θ x pθ , and by the substitution lemma (lemma 13), |t|σ ∈ [[T {x → p}]] θ , therefore |t p|σ ∈ [[T {x → p}]] θ symb: By hypothesis.

The positivity condition is quite similar to the one used in the usual formulation of type-based termination, see for instance Abel[Abe06] for an in depth analysis. The typing rules are also similar to the ones for type-based termination. The typing rules of our system are given by the typing rules in figure1.ax Γ, x : T, ∆ ⊢ x : T Γ, x : T ⊢ t : U t-lam Γ ⊢ λx : T.t : T → U Γ ⊢ t : T α F V(Γ) p-lam Γ ⊢ λα.t : ∀α.T leaf-intro Γ ⊢ Leaf : B(leaf) node-intro Γ ⊢ Node : ∀αβ.B(α) → B(β) → B(node(α, β)) Γ ⊢ t : T → U Γ ⊢ u : T t-app Γ ⊢ t u : U Γ ⊢ t : ∀α.T p-app Γ ⊢ t p : T {α → p} symb Γ ⊢ f : τ fFig. 1. Typing Rules

Acknowledgements

We thank Frederic Blanqui for the discussions that led to the birth of this work and for very insightful comments concerning a draft of this paper, as well as anonymous referees for numerous corrections on a previous version of this paper.

The next step in the reducibility proof is to verify that the interpretation of terms verify the Girard conditions: A subset X ⊆ Trm | | satisfies the Girard conditions if 1. strong normalization: X ⊆ SN 2. stability by reduction: for every term t ∈ X, if u is such that t * u, then u ∈ X. 3. "sheaf condition": if t is neutral, and for every term u such that t u, u ∈ X, then t ∈ X.

These embody the exact combinatorial properties required to carry through the inductive proof of correctness, namely that every well-typed term is in the interpretation of its type.

Lemma 9 If T ∈ T is a type, then for every valuation θ,

[[T ]] θ satisfies the girard conditions

Proof. We proceed by induction on the structure of T .

-T = B(p)

• Strong normalization: by definition of B.

• Stability by reduction. Suppose that t ∈ [[B(p)]] θ . If t * u, then the set of normal forms of u is contained in the set of normal forms of t. • Sheaf condition. Suppose that t is neutral and that each one step reduct of t is in [[B(p)]] θ . Now either t is in normal form, and then t ≪ pθ (as it is non empty), or for every one step reduct u of t, u ≪ pθ. But in this case every normal form of t is the normal form of some t u, and thus t ≪ pθ.

• Strong normalization: by definition. Now we give the conditional correctness theorem, which states that if the function symbols belong to the interpretation of their types, then so does every well-typed term.

Definition 10 Let θ be a pattern valuation, σ a substitution from term variables to erased terms, and Γ a context. We say that (θ, σ) validates Γ, and we write σ | = θ Γ, if the set of free pattern variables in Γ is contained in dom(θ), and if for every x ∈ dom(Γ)

Theorem 11 Suppose that for each f ∈ Σ and each valuation θ,

We need the classic substitution lemma for types:

Lemma 12 For every patterns q, p and valuation θ, if α is not in the domain of θ, then p{α → q}θ = pθ α qθ Proof. We proceed by induction on the structure of p:

p = α: trivial.

p = β α: We have p{α → q} = β and therefore p{α

which by induction is equal to

which allows us to conclude.

Lemma 13 (substitution lemma) Let T be a type and θ a pattern valuation. If α does not appear in the domain of θ then:

Proof. We proceed by induction on the type.

-Atomic case:

But by lemma 12, q{α → p}θ = pθ α pθ , from which we can conclude. -Arrow case: straightforward from induction hypothesis.

case ∀β.T . We may suppose by Barendregts convention that β is distinct from α, not in the domain of θ and distinct from all variables in p. We then have:

We may apply the induction hypothesis, which gives:

And as β does not appear in p:

Which concludes the argument.

We may easily generalize this result to:

Corollary 14 Let T be a type. If φ is a substitution, and θ is a valuation such that the variables of T do not appear in the domain of θ, then:

Where θ • φ is the valuation defined by θ • φ(α) = φ(α)θ.

Another useful lemma states that type interpretations only depend on the value of the pattern substitutions in the free variables of the type.

Lemma 15 Let T be some type and θ, θ ′ be two closed pattern substitutions.

Proof. Straightforward induction on T .

The next lemmas show correctness of the interpretation with respect to subtyping.

Definition 16 Let P and Q be sets of closed patterns. We write P ≪ Q if for each p ∈ P, there is a q ∈ Q such that p ≪ q.

Lemma 17 Let θ be a pattern valuation. If p ≪ q, then pθ ≪ qθ Proof. Induction on the derivation of p ≪ q. The only interesting case is node(p 1 , p 2 ) ≪ node(q 1 , q 2 ) with p i ≪ q i for i = 1, 2. In that case, if r ∈ node(p 1 , p 2 )θ, we have r = node(r 1 , r 2 ) with r i ∈ p i θ for i = 1, 2. By induction hypothesis, there is r ′ 1 , r ′ 2 in node(q 1 , q 2 )θ such that r i ≪ r ′ i for each i. Then we take node(r ′ 1 , r ′ 2 ) ∈ node(q 1 , q 2 )θ to conclude.

Lemma 18 Suppose T ≤ U. Then for all θ,

Proof. We proceed by induction on all the possible cases for the judgement T ≤ U.

p ≪ q: We first show that for all terms t, and every non-empty set of closed patterns P and Q, if P ≪ Q, then t ≪ P ⇒ t ≪ Q. This follows from the following fact: if v is in normal form and r ≪ s, then

To show this we proceed by induction on the ≪ judgement. The first three cases are easy. In the fourth case, v ≪ node(r 1 , r 2 ) which by definition implies that v = Node v 1 v 2 , with v 1 ≪ r 1 and v 2 ≪ r 2 . We can then conclude by the induction hypothesis. Now using lemma 17, we have, if p ≪ q, t ≪ pθ ⇒ t ≪ qθ.

Now let t ∈ [[B(p)]

] θ , we have by definition t ≪ pθ, and by the previous remark, t ≪ qθ

for all valuations θ ′ . Take θ ′ to be θ α P . We have:

From this we can deduce t ∈ [[U]] θ α P and conclude.

We shall also need the fact that given T and a valuation θ, then

a weakening of θ on the variables in positive position in T .

Lemma 19 Let T be a type and θ, θ ′ two pattern valuations. If θ(α) ≪ θ ′ (α) for every free variable α ∈ T in a positive position, and θ(β) = θ ′ (β) for every other variable, then

for every free variable α in a negative position, then

Proof. First notice that if p is a pattern, then pθ ≪ pθ ′ , by a simple induction on p. We prove both propositions simultaneously by induction on T :

-T = B(p). All variables of p appear positively in T . Then by the above remark, pθ ≪ pθ ′ , and therefore

We treat the positive case. We have by induction hypothesis

, as all variable of T 1 that appear positively in T appear negatively in T 1 , and

The negative case is treated in the same fashion. -T = ∀α.U: straightforward induction.

We can now prove the correctness of the interpretation relative to that of the function symbols (theorem 11).

Proof. We proceed by induction on the typing derivation.

ax: by definition of σ | = θ Γ.

t-lam: By induction hypothesis, for all σ ′ , θ ′ such that

We proceed by well founded induction on the reducts of t and u. Thus if (λx : T.t)σu (λx : T.t ′ )σu ′ with t t ′ or u u ′ , then we may conclude by well-founded induction hypothesis. The remaining case is (λx :

] θ , we apply the main induction hypothesis with σ ′ = σ x u and θ ′ = θ. It can be argued that this argument is the fundamental combinatory explanation for normalization of β-reduction.

p-lam: by induction hypothesis, for all σ ′ , θ ′ such that σ

Let σ, θ be some such valuations and P be a set of closed patterns. As |λα.t|σ = |t|σ, we need to show that |t|σ ∈

, by virtue of lemma 15. We may therefore conclude that |t|σ is in

We conclude by the induction hypothesis. -There is some rule l r ∈ R, and some substitution σ such that |l|σ = t, and |r|σ = t ′ . We then proceed by induction on ( f, t) ordered by > d p . We have by hypothesis that there is some context Γ and some derivation Γ ⊢ min l i : B(p i ) for each i, and a derivation Γ ⊢ r : T f φ, with φ the substitution that sends α i to p i . By lemma 29, match P = ψ is defined. We therefore have

] ψ•φ by the substitution lemma. By lemma 30, ψ • φ ≪ θ. We may then apply the positivity condition of τ f using lemma 19 to deduce that

] ψ by the substitution lemma. By hypothesis, Γ ⊢ r : T f φ, so we would like to apply the correctness theorem 11 to show that

The correctness theorem itself can not be applied, as it takes as hypothesis the correctness of function symbols, which we are trying to prove. But we will proceed in the same manner, making essential use of the well-founded induction hypothesis.

Let us first show by induction on the derivation of Γ ⊢ min l i that for each

We have nothing to show here.

• l i = Node l 1 l 2 . Simple application of the induction hypothesis. Now we prove by induction on the derivation of Γ ⊢ r :

We can exactly mimic the proof of theorem 11, except for the symb case. In this case, there is a g such that r = gq, and if τ g = ∀β.B(β 1 ) → . . . → B(β m ) → T g , we need to show that, for some extension ψ ′ of psi, g ∈ [[B(q 1 ) → . . . → B(q m ) → T g ]] ψ ′ . Recall the induction hypothesis on ( f, t), which states that for every θ, if ( f, t) > d p (g, u), then gu ∈ [[T g ]] θ . Now take θ to be ψ ′ • ζ where ζ is the substitution that sends β i to q i . It suffices to show that if for (g, u). For this we need to show that there exists n ∈ G such that:

We just take n to be the node that corresponds to the call site of gq. In this case, r = p and s = q. By definition, match P (t, p) is defined and equal to ψ. Then ψ ′ is an extension of ψ and as

Corollary 34 Every well-typed term is in the interpretation of its type, that is

∀Γ, t, T Γ ⊢ t : T ⇒ |t| ∈ [[T ]]

Where [[T ]] is [[T ]] θ where θ is the valuation that sends every variable to the set { }.

Proof. In fact it does not matter which θ we choose: let θ be any valuation. Given a variable x and a type T , by lemma 9, x ∈ [[T ]] θ , as x is neutral and in normal form. Given Γ ⊢ t : T , we can therefore take the substitution σ that sends every variable x ∈ dom(Γ) to itself. In that case σ(x) ∈ [[Γ(x)]] θ by the above remark, and by the combination of theorem 11 and theorem 33, |t|σ ∈ [[T ]] θ . But in this case |t|σ = |t|.

We obtain the statement of theorem 6 as a corollary: every well typed term is in the interpretation of its type, but this interpretation only contains strongly normalizing terms by lemma 9.