Thomas Hecht
email: thomashecht95@gmail.com

Patrice Buche
email: patrice.buche@supagro.inra.fr

Juliette Dibie
email: juliette.dibie@agroparistech.fr

Liliana Ibanescu
email: liliana.ibanescu@agroparistech.fr

Cassia Trojahn
email: cassia.trojahn@irit.fr

Dos Santos

Ontology Alignment Using Web Linked Ontologies as Background Knowledge

This paper proposes an ontology matching method for aligning a source ontology with target ontologies already published and linked on the Linked Open Data (LOD) cloud. This method relies on the refinement of a set of input alignments generated by existing ontology matching methods. Since the ontologies to be aligned can be expressed in several representation languages with different levels of expressiveness and the existing ontology matching methods can only be applied to some representation languages, the first step of our method consists in applying existing matching methods to as many ontology variants as possible. We then propose to apply two main strategies to refine the initial alignment set: the removal of different kinds of ambiguities between correspondences and the use of the links published on the LOD. We illustrate our proposal in the field of life sciences and environment.

Introduction

Ontologies are nowadays used as a common and standardized vocabulary for representing concepts and relations from a particular domain (e.g. life-science, geography). The Linked Open Data (LOD) cloud1 contains more and more data sources published and linked together on the Web. Publishing and linking scientific data on the Web using ontologies for describing them should facilitate scientific data sharing, such as giving access to data from specific disciplines or data produced within specific geographic regions [Bizer, 2013].

When a new ontology, the source ontology, is published on the LOD, first, the 'target' ontologies, i.e. ontologies from similar domains with similar concepts, has to be identified among the already published ontologies in order to access new entities (concepts, properties or instances) and data sources. The source ontology can then be linked with each target ontology by finding an alignment (i.e. a set of correspondences) between entities. Different approaches have been proposed for the Ontology Matching task [START_REF] Shvaiko | Ontology matching: state of the art and future challenges[END_REF], Bernstein et al., 2011, Rahm, 2011, Euzenat and Shvaiko, 2007] and a systematic evaluation on data sets from different domains has been carried out over the last ten years by the Ontology Alignment Evaluation Initiative (OAEI) 2 .

In this paper, we propose an ontology matching method for aligning a source ontology with different target ontologies already linked and published on the LOD. An ontology can be either a thesaurus, an ontology or an ontological and terminological resource, expressed in different representation languages. Our method is based on the principle of alignment refinement: starting from a set of input alignments generated by several existing ontology matching methods, we propose to apply different strategies in order to refine this initial alignment set. One of our strategies is to exploit the links between the target ontologies, already published on the LOD.

We illustrate our method in the field of life sciences and environment. In this field, several thesauri have been created and published on the LOD. The two largest ones are AGROVOC3 and NALT 4 . AGROVOC was created in the 1980s by FAO (Food and Agriculture Organization of the United Nations) as a structured multilingual thesaurus for agriculture, forestry, fishery, food and related fields (such as environment). It is available in 19 languages, with about 40 000 terms in each language [START_REF] Caracciolo | Thesaurus maintenance, alignment and publication as linked data: the AGROVOC use case[END_REF]. NALT is a bilingual thesaurus comparable with AGROVOC in terms of covered domain and maintained by USDA (United States Department of Agriculture). It is currently composed of approximately 91 000 terms in English and Spanish. For instance, the vocabulary of AGROVOC is currently linked to 15 international resources like GeoNames 5 , DB-pedia6 and GEMET7 . In addition, 13 390 terms of AGROVOC are currently aligned with NALT [START_REF] Caracciolo | Thesaurus maintenance, alignment and publication as linked data: the AGROVOC use case[END_REF]. In this paper, we focus on the alignment of an ontological and terminological resource NARYQ (n-ary Relations between Quantitative experimental data) [START_REF] Buche | Intégration de données hétérogènes et imprecise guide par une resource termino-ontologique. application au domaine des sciences du vivant[END_REF] with AGROVOC and NALT, in order to publish it on the LOD. NARYQ contains about 1 100 concepts structured into several sub-domains, such as food products, microorganisms and packaging.

This paper is organised as follows. Section 2 describes our method for aligning an ontology with linked ontologies on the LOD. Section 3 discusses the results of our experiments in the field of life sciences and environment. Section 4 presents related work and, finally, Section 5 concludes the paper and presents our perspectives.

Ontology matching method with linked ontologies

In this section, we present our matching method for aligning a source ontology with two target and linked ontologies. Our method is designed to align ontologies, thesauri or ontological and terminological resources, possibly described in different representation languages with different levels of expressiveness (e.g. OWL DL8 , SKOS 9 ). An Ontological and Terminological Resource (OTR) [START_REF] Reymonet | Modelling ontological and terminological resources in OWL DL[END_REF], Roche et al., 2009, McCrae et al., 2011] is a hybrid model that combines a conceptual component and a terminological component: a concept is associated with a set of terms, each term denoting the concept with different lexical functions (e.g. synonyms, abbreviations, etc.). In the following, for the sake of simplicity and the paper's readibility, we abusively use ontology for either ontology, thesaurus or OTR.

The proposed method relies on the refinement of a set of input alignments generated by existing ontology matching methods. Our aim is therefore to be able to apply as much existing matching methods as possible in order to generate as much candidate correspondences as possible. Since the existing ontology matching methods can only be applied to some particular representation languages and the ontologies to be aligned can be expressed in several representation languages with different levels of expressiveness, we propose to apply matching methods on different variants of the ontologies to be aligned. A variant of an ontology corresponds to its expression in a given representation language. The first step of our matching method consists in aligning variants of the source ontology O s with variants of the two target ontologies O 1 t and O 2 t using existing ontology matching methods. It allows the production of an initial set of alignments. In the second step, different refinement strategies are applied to this initial set of alignments, including the exploitation of the links defined on the LOD between the target ontologies. Figure 1 gives the overview of our matching method, which is detailed in the next two subsections.

First step : ontology matching

The first step of our method consists in aligning the source ontology O s with each one of the two target ontologies O 1 t and O 2 t .

Ontology variants

The source and target ontologies to be aligned can be thesauri, ontologies or OTR and may be expressed in different representation languages. Since the existing matching methods are usually designed for one particular representation language, we propose to associate to each ontology a set of variants, defined in the following:

Definition 1 (Set of variants of an ontology). The set V O of variants of an ontology O is composed of its transformations in different representation languages

L 1 , L 2 , . . .. It contains the original version O orig of the ontology. V O = {O orig , O L 1 , O L 2 1 , O L 2 2 , . . .},
where O L i j is the j th transformation of the ontology O using the representation language L i .

The aim of using variants is twofold. First, matching tools are designed to deal with specific input models (OWL ontologies in most cases). Diversifying the kinds of input, we are able to produce more candidate correspondences by using more tools. Second, representing resources using different constructors (OWL and SKOS) allows the encoded knowledge to be exploited in different ways. On the one hand, tools can take advantage of OWL models for better exploiting automated reasoning. On the other hand, the lexicalisation of concepts is better expressed in SKOS models than in OWL models. For instance, in classical SKOS to OWL transformations, both skos:prefLabel and skos:altLabel are mapped to rdfs:label, where skos:altLabel are often used to represent synonyms, but also to refer to related terms. As a consequence, without introducing variants to catch this semantic richness, we could lose this information, which can instead be useful for tools able to deal with the specificities of SKOS.

Matching the ontology variants

The ontology matching process takes as input two ontologies and produces as output a set of correspondences between the entities of these two ontologies. According to [START_REF] Euzenat | Ontology matching[END_REF], this process can be defined as follows:

Definition 2 (Matching process [START_REF] Euzenat | Ontology matching[END_REF]). The matching process is a function f that, applied to two ontologies O s and O t and an (optional) initial alignment A orig , produces a directed alignment A f O s ,O t between the two ontologies (O s → O t ). This process can use matching parameters p (e.g. weights, thresholds) and external resources r (e.g. common knowledge and domain specific thesauri):

A f O s ,O t = f (O s , O t , A orig , p, r)
Definition 3 (Correspondence [START_REF] Euzenat | Ontology matching[END_REF]). Let us consider two ontologies O s and O t , a correspondence c f resulting from a matching process f is a relation r between the two entities e s and e t , denoted c f = id, e s , e t , r, n , such that : c f ∈ A f O s ,O t ; e s ∈ O s and e t ∈ O t ; r ∈ {≡, , } ; n is the confidence level (in general, n ∈ [0, 1]) indicating the degree of confidence that the relation r holds between e s and e t .

Since the structural and the lexical information of the ontologies are exploited in different ways by the matching processes, the use of the most expressive variant of an ontology does not guarantee the best results. Therefore, the first step of our matching method consists in launching several matching processes on several variants of the ontologies to be aligned. Let us consider the source ontology O s , one of the target ontologies O t and the set of matching processes

F = { f 1 , f 2 , . . .}
A f i O j s ,O k t = f i (O j s , O k t , / 0, p, r) (1)
The result of our matching method between the source ontology O s and one of the two target ontologies is a set of sets of correspondences, denoted agr C O s →O t for aggregated set, generated by each matching process of F on each pair of ontology variants. This set, which comes from the concatenation of results from several matching processes on several ontology variants, is denoted:

agr C O s →O t = i, j,k A f i O j s ,O k t (2)
The total number of matching processes launched in order to obtain an alignment between the source ontology O s and each one of the two target ontologies O 1 t and O 2 t is: . These two sets of sets contain many correspondences (suggesting a good coverage) but also a lot of noise (i.e. incorrect correspondences) that has to be reduced.

|V O s | × |V O 1 t | × |F| + |V O s | × |V O 2 t | × |F| (
In order to improve the quality of the correspondences found in the first step, we propose two refinement methods: the first one allows the identification of the potentially correct correspondences (see Subsection 2.2.1), the second refinement method allows the deletion of the correspondences considered as ambiguous and therefore potentially incorrect (see Subsection 2.2.2). Finally, we present in Subsection 2.2.3 our refinement process.

Identification of potentially correct correspondences

We distinguish two ways to identify potentially correct correspondences. When redundancies occur between correspondences that have been generated from at least two distinct matching methods, we assume that these correspondences can be considered as having more chances to be correct. We will retain them in a separate set, denoted recT C O s →O t for recovering set. These correspondences will be presented to the user as potentially correct correspondences. Definition 4 (Recovering set). Let us consider two matching processes f 1 and f 2 applying two distinct matching methods for aligning two ontologies O s and O t , the

recovering set recT C O s →O t is defined as follows: If c f 1 = id 1 , e 1 s , e 1 t , r 1 , n 1 ∧ c f 2 = id 2 , e 2 s , e 2 t , r 2 , n 2 ∧ e 1 s = e 2 s ∧ e 1 t = e 2 t ∧ r 1 = r 2 then c f k ∈ recT C O s →O t , where c f k = c f 1 if n 1 ≥ n 2 c f 2 otherwise
Example 1. Let us also consider the correspondence c 1 generated by a matching process f 1 on the variants NARYQ OW L-SKOS of the source ontology NARYQ, and the variant AGROVOC SKOS of the target ontology AGROVOC (see Subsection 3.1).

Let us also consider the correspondence c 2 generated by a matching process f 2 which applies another matching method as the one used in the matching process f 1 on the variants NARYQ OW L-SKOS and AGROVOC OW L

2

. We have:

c 1 = id 1 , sheep, c 8854, ≡, 0.95 , c 1 ∈ A f 1 NARYQ OW L-SKOS ,AGROVOC SKOS c 2 = id 2 , sheep, c 8854, ≡, 0.75 , c 2 ∈ A f 2 NARYQ OW L-SKOS ,AGROVOC OW L 2
The correspondences c 1 and c 2 generated by two distinct matching methods can be considered as redundant. The recovering set recT C NARYQ→AGROVOC contains the correspondence c 1 with the highest confidence level.

The second way of identifying potentially correct correspondences relies on the same assumption as above, i.e. 'comparable' correspondences can be considered as having more chances to be correct. Let us consider that there exists an alignment as LOD recovering sets. These sets will be presented to the user as sets of potentially correct correspondences.

Definition 5 (LOD recovering set). Let us consider

A LOD O 1 t →O 2 t
the result of a matching process between two ontologies O 1 t and O 2 t from the LOD, a set of matching processes

F 1 = { f 1 1 , f 1 2 , .
. .} applied to two ontologies O s and O 1 t , and a set of matching processes

F 2 = { f 2 1 , f 2 2 , . . .} applied to O s and O 2 t , the LOD recovering sets LOD C O s →O i t , i ∈ [1, 2], are defined as follows: If ∃c ∈ A LOD O 1 t →O 2 t ∧ c = id, e 1 t , e 2 t , ≡, n ∧ c f 1 i ∈ A f 1 i O s ,O 1 t ∧ c f 2 j ∈ A f 2 j O s ,O 2 t ∧ c f 1 i = id 1 , e 1 s , e 1 t , ≡, n 1 ∧ c f 2 j = id 2 , e 2 s , e 2 t , ≡, n 2 ∧ e 1 s = e 2 s ∧ e 1 t = e 2 t , then c f 1 i ∈ LOD C O s →O 1 t and c f 2 j ∈ LOD C O s →O 2 t .
Hence, a correspondence c f 1 i belongs to the LOD recovering set

LOD C O s →O 1 t , if i) the entity source e s (e s = e 1 s = e 2 s
) is aligned with an entity target e 1 t , ii) there exists a correspondence c f 2 i such that the entity source e s is aligned with an entity target e 2 t , iii) there exists on the LOD a correspondence c linking e 1 t and e 2 t .

Example 2. Let us consider the correspondence c 3 generated by the matching process f 1 of Example 1 and the correspondence c 4 generated by the matching process f 3 on the variants NARYQ OW L-SKOS and NALT OW L . We have:

c 3 = id 3 , surimi, c 33271, ≡, 0.87 , c 3 ∈ A f 1 NARYQ OW L-SKOS ,AGROVOC SKOS
where c 33271 is a concept of AGROVOC;

c 4 = id 4 , surimi, c 40365, ≡, 0.92 , c 4 ∈ A f 3 NARYQ OW L-SKOS ,NALT OW L
where c 40365 is a concept of NALT.

Let us also consider that: ∃c ∈ A f AGROVOC,NALT , c = id c , c 33271, c 40365, ≡, 0.96 .

Then, we have:

c 3 ∈ LOD C NARYQ→AGROVOC and c 4 ∈ LOD C NARYQ→NALT .

Deletion of ambiguous correspondences

We distinguish three types of ambiguity between correspondences. The first type covers the correspondences obtained from the same matching method launched on different variants of the source and target ontologies. The correspondences of this type have the same source entity, the same target entity and the same relation. We propose to remove ambiguities of type 1 by keeping the correspondence with the highest confidence level.

Definition 6 (Ambiguous correspondences of type 1). Let us consider two matching processes f 1 and f 2 applying the same matching method to align two ontologies O s and O t (with O j s and O k t its respective variants), two correspondences c f 1 and c f 2 , from the sets

A f 1 O j 1 s ,O k 1 t and A f 2 O j 2 s ,O k 2 t
, are ambiguous according to type 1 if:

c f 1 = id 1 , e 1 s , e 1 t , r 1 , n 1 ∧ c f 2 = id 2 , e 2 s , e 2 t , r 2 , n 2 ∧ e 1 s = e 2 s ∧ e 1 t = e 2 t ∧ r 1 = r 2 .
The set of sets of non ambiguous correspondences according to type 1 is:

agr * C O s →O t = i, j,k (A f i O j s ,O k t \{c f k }) where c f k = c f 1 if n 1 ≥ n 2 c f 2 otherwise
Remark 1. Let us remember that when redundancies occur between correspondences generated by two distinct matching methods, these correspondences are considered as potentially correct (see Definition 4).

Example 3. Let us consider the correspondence c 1 generated by the matching process f 1 of Example 1. Let us also consider the correspondence c 5 generated by a matching process f 4 using the same matching method as the one used in the matching process f 1 but on the variant NARYQ SKOS and the variant AGROVOC SKOS . We have:

c 1 = id 1 , sheep, c 8854, ≡, 0.95 , c 1 ∈ A f 1 NARYQ OW L-SKOS ,AGROVOC SKOS
where c 8854 corresponds to the concept 'caprins' in AGROVOC.

c 5 = id 5 , sheep, c 8854, ≡, 0.88 , c 5 ∈ A f 4 NARYQ SKOS ,AGROVOC SKOS
The set of sets agr * C NARYQ→AGROVOC of non ambiguous correspondences according to type 1 only contains the correspondence c 1 with the highest confidence level.

The second type of ambiguity covers the correspondences in which an entity of the source ontology O s is aligned, by an equivalence relation, with two distinct entities of the target ontology O t . We propose, in this case, to keep only the most relevant correspondence, i.e. the one that has a priori the highest confidence level. However, considering the fact that these correspondences were not generated by the same matching method, their confidence degrees are not comparable. Therefore, we propose to compute a similarity measure sim on the two correspondences to be compared, which is independent on the matching methods used to generate them. This similarity measure can rely, for instance, on syntactic similarity measures implemented in the Alignment API [START_REF] David | The alignment api 4.0[END_REF]. Here, we use the following syntactic measures: Hamming distance, Levenshstein distance, n-grams and Jaro and Jaro-Winkler to compute the similarity between all the labels, in a given language, of the two entities. The sim measure is the average of the computed similarities.

Definition 7 (Ambiguous correspondences of type 2). Let us consider a set of matching processes F = { f 1 , f 2 , . . .} applied to two ontologies O s and O t , two correspondences c f i and c f j are ambiguous according to the type 2 if:

c f i = id 1 , e 1 s , e 1 t , ≡, n 1 ∧ c f j = id 2 , e 2 s , e 2 t , ≡, n 2 ∧ e 1 s = e 2 s ∧ e 1 t = e 2 t .
The set of sets of non ambiguous correspondences of type 2 is:

agr2 * C O s →O t = i, j,k (A f i O j s ,O k t \{c f k }) where c f k = c f i if sim(e 1 s , e 1 t ) ≤ sim(e 2
s , e 2 t ) c f j otherwise Remark 2. We only consider the equivalence relation here, because with other relations, the correspondences are not necessarily ambiguous, i.e. both of the correspondences can, in some cases, be considered as correct. Finally, the third type of ambiguity covers the correspondences where two distinct entities from the source ontology O s are aligned, by an equivalence relation, with the same entity of the target ontology O t . We propose, in this case, to keep the most relevant correspondence, i.e. the one with the highest similarity measure sim.

Definition 8 (Ambiguous correspondences of type 3). Let us consider a set of matching processes F = { f 1 , f 2 , . . .} applied to two ontologies O s and O t , two correspondences c f i and c f j are ambiguous according to type 3 if:

c f i = id 1 , e 1 s , e 1 t , r 1 , n 1 ∧ c f j = id 2 , e 2 s , e 2 t , r 2 , n 2 ∧ e 1 s = e 2 s ∧ e 1 t = e 2 t ∧ r 1 = r 2 .
The set of sets of non ambiguous correspondences of type 3 is defined as:

agr3 * C O s →O t = i, j,k (A f i O j s ,O k t \{c f k }) where c f k = c f i if sim(e 1 s , e 1 t ) ≤ sim(e 2
s , e 2 t ) c f j otherwise Example 5. Let us consider the correspondence c 1 generated by the matching process f 1 of Example 1 and the correspondence c 6 generated by the matching process f 1 . We have:

c 1 = id 1 , sheep, c 8854, ≡, 0.95 , c 1 ∈ A f 1 NARYQ OW L-SKOS ,

The refinement process

Figure 2 gives the overview of our refinement process, detailed in Subsections 2.2.1 and 2.2.2. The set obtained by the union of the two recovering sets defined in Subsections 2.2.1 is denoted by:

U O s →O t = recT C O s →O t ∪ LOD C O s →O t (4)
We define the set of potentially correct and non ambiguous correspondences between a source ontology O s and a target ontology O t as follows.

Definition 9. The set of potentially correct and non ambiguous correspondences between a source ontology O s and a target ontology O t , denoted agr * ,2 * ,3 * U O s →O t , is the set obtained after the removing of ambiguities of types 1, 2 and 3 as defined in Definitions 6, 7 and 8 from the set U O s →O t given in Equation 4.

Experiments

We illustrate in this section our matching method described above for aligning a source ontology NARYQ (presented in Section 3.1) with each of the two target ontologies AGROVOC and NALT. In the following, the alignment of NARYQ with AGROVOC will be denoted NARYQ → AGROVOC and the alignment of NARYQ with NALT: NARYQ → NALT.

The source ontology NARYQ

The ontology NARYQ (n-ary Relations between Quantitative experimental data) has been created for representing n-ary relations between quantitative experimental data (see [START_REF] Buche | Intégration de données hétérogènes et imprecise guide par une resource termino-ontologique. application au domaine des sciences du vivant[END_REF]). The characteristics of this ontology are the following: (i) it is an OTR; (ii) the labels are available in French and in English; (iii) it is represented in OWL DL and SKOS; and (iv) the conceptual component contains about 1 100 concepts structured into several sub-domains, the most important one in number being food products (≈ 460 concepts), microorganisms (≈ 180 concepts) and packaging (≈ 150 concepts).

Reference alignments

In order to evaluate the quality of the generated alignments and to compare the results of the matching processes, we consider the measures of precision and recall adapted to the ontology matching task [START_REF] Euzenat | Ontology matching[END_REF]. These measures are based on a comparison between an automatically generated alignment A and a reference alignment R. The automatically generated alignment A is in this paper either the individual alignments provided by the matching tools or the alignment resulting from our approach. The construction of a complete reference alignment R was not possible because it is a time-consuming task and it is difficult to find and to involve experts from the domain. Hence, we have built two partial manually validated reference alignments, denoted R + AGROVOC for the alignment NARYQ → AGROVOC, and R + NALT for the alignment NARYQ → NALT. For each ontology and for every concept, we extracted their annotations (e.g. skos:prefLabel, skos:altLabel, rdfs:label, rdfs:comment) in English and in French as well as their structural elements (e.g. skos:broader, rdfs:subClassOf). A first alignment was created using SMOA [START_REF] Stoilos | A string metric for ontology alignment[END_REF] (String Metric for Ontology Alignment), a syntactic similarity metric for ontology matching. Using this metric and the equivalence relation ≡ , an alignment with 1 453 correspondences was generated, which was then manually validated by two experts in a double-blind process, and finally re-conciliated, i.e. the experts reached an a posteriori consensus. This first expert validation was performed in four hours using a visualisation tool developed for this specific task. It produced 318 validated correspondences in R AGROVOC and 394 validated correspondences in R NALT , among which 233 concepts from NARYQ were aligned with both concepts from AGROVOC and concepts from NALT. In order to enrich these first generated reference alignments, an additional set of potentially correct correspondences was generated using our matching method and was validated by two experts. We therefore obtained two new and enriched reference alignments, denoted R

Experimental protocol

Several matching processes were launched on several variants of the ontologies to be aligned in order to generate as much candidate correspondences as possible. We first present the ontology variants and then the selected matching processes.

The ontology variants

The variants of NARYQ are :

V NARYQ = {NARYQ OW L-SKOS , NARYQ OW L , NARYQ SKOS }
where the original version of NARYQ, denoted NARYQ OW L-SKOS , is defined using OWL2 DL and SKOS. We also use two variants of NARYQ. The variant NARYQ OW L was generated from its conceptual component by transforming both skos:prefLabel and skos:altLabel into rdfs:label, while the variant NARYQ SKOS was generated using the labels of its terminological component and transforming the conceptual hierarchy into a SKOS hierarchy. The variants of AGROVOC are:

V AGROVOC = {AGROVOC SKOS , AGROVOC SKOS 1 , AGROVOC OW L
V NALT = {NALT SKOS , NALT OW L }
where the original version NALT SKOS was downloaded in April 2013 from the official Web site 12 and the variant NALT OW L was generated from NALT SKOS using the same SKOSParser.

The matching processes

Two available ontology matching tools, implementing different matching approaches with good results in the 2011 and 2012 OAEI campaigns [START_REF] Aguirre | Results of the ontology alignment evaluation initiative 2012[END_REF], were selected: Aroma 13 [David, 2007] and LogMap 14 [Jiménez-Ruiz and Grau, 2011].

Aroma makes use of the association rule paradigm and a statistical measure assessing the implication intensity of the rules. The matching approach is divided into three steps: (1) pre-processing: each ontology entity, i.e. classes and properties, is represented by a set of terms -bag of words; (2) discovery of association rules between entities, and (3) post-processing: cleaning and enhancing the resulting alignment (i.e. deduction of equivalence relations, suppression of cycles in the alignment graph, suppression of redundant correspondences, and enhancement of the alignment by using equality and string similarity-based methods). Aroma is able to deal with both SKOS and OWL variants. This is not the case for LogMap, which encounters problems to parse SKOS variants.

LogMap adopts an approach based on logical reasoning and inconsistency repair techniques. The matching method follows five main steps: (1) lexical indexation of labels of entities and their lexical variations; (2) structural indexation based on in-terval labeling schema for representing extended class hierarchies; (3) computation of initial anchor correspondences by intersecting the lexical indexes of entities; (4) iterative mapping repair and discovery, by filtering out logical inconsistencies in the mappings computed so far and by computing new mappings using string-based similarity method; and (5) ontology overlapping estimation, where ontology fragments overlap in both input ontologies.

Among 24 matching processes launched for aligning NARYQ and AGROVOC (see equation 3), only 9 produced non-empty alignments. From over 12 matching processes launched for aligning NARYQ and NALT, only 4 produced non-empty alignments. In the following, we assume that a correspondence is 'acceptable' if it has a confidence level greater than or equal to 0.5, a threshold empirically defined. The initial sets of alignments generated using the two matching tools (see equa-

Experimental results

Individual results

Table 1 presents the results obtained from each matching tool, with respect to our two partial reference alignments R + AGROVOC and R + NALT (see Subsection 3.2). We can observe that thanks to variants we are able to overcome the limitations of tools in deadling with specific input models and hence we are able to produce more candidate correspondences. While LogMap is not able to generate alignments for the pairs involving SKOS variants (e.g. NARYQ SKOS , AGROVOC SKOS and NALT SKOS ), Aroma produces a set of correspondences with intermediary scores.

Table 2 presents the best scores obtained by the two matching tools and extracted from Table 1. These results are, in fact, an approximation, as they were computed using the partial reference alignments, which may affect the accuracy of the results. The values of each line of Table 2 represent the best score obtained for each indicator (number of correct correspondences, precision, recall or F-measure) by the matching tools. # * corresponds to the highest number of good correspondences; P * corresponds to the best precision; R * corresponds to the best recall; and F-m * corresponds to the best F-measure.

Results of our approach

Table 3 presents the evaluation of NARYQ→ AGROVOC generated by different refinement methods, with respect to the partial reference alignment R + AGROVOC . On the last row of Table 3, the symbol indicates, for the indicator of the column, a better result than the best result of the matching tools for the same indicator presented in Table 2. Table 4 presents the evaluation of NARYQ→ NALT generated by different refinement methods, with respect to the partial reference alignment R + NALT . On the last row of Table 4, the symbol indicates, for the indicator of the column, a better result than the best result of the matching tools for the same indicator presented in Table 2.

Discussion

As we can notice in Tables 3 and4 and as we might expect, (1) increasing the set of alignments allows the recall to be improved for most of the produced alignment sets 15 , and (2) combining the different methods of refinement gives the best results in terms of precision (set agr * ,2 * ,3 * U ). Comparing these results with the best scores obtained by the two matching tools (Table 2), we obtained very promising results. Our approach obtains similar results in terms of F-measure for NARYQ → AGROVOC, while it increases F-measure for NARYQ → NALT. Our approach outperforms the best result in terms of recall for NARYQ → AGROVOC and in terms of precision for NARYQ → NALT. This performance produces very encouraging results.

Most matching tools apply strategies for combining different basic methods (i.e. lexical, structural, etc.) within a matching process and for filtering their results (threshold, weighted aggregation, etc.) (see [START_REF] Euzenat | Ontology matching[END_REF]). Our encouraging results can be explained by the fact that we propose in this paper to refine the sets of alignments produced by different matching methods in two different ways. First, we have identified three types of ambiguity to be resolved in order to refine the set of correspondences by deleting some of them. Second, we propose two new methods for discriminating and improving the sets of correspondences. In the first method, the redundant correspondences generated by at least two matching processes applying distinct matching methods are considered as potentially correct. The second method exploits the alignments defined on the LOD in order to reinforce the validity of some correspondences (i.e. correspondences allowing a same entity 15 Since ambiguous correspondences according to type 1 produce only noises, the evaluation of the best recall is done considering to be aligned with two distinct but linked entities on the LOD are considered as potentially correct). Another original aspect of our approach consists in exploiting ontology variants, taking advantage of the characteristics of the ontologies, which can be ontologies, thesauri, OTR and can be expressed in different representation languages with different levels of expressiveness. This gives us the ability to cover a wide and diverse range of resources.

Related work

A key aspect of our proposal is the use of published links on the LOD as background knowledge for refining the results of a matching process. Similar works in this direction have been proposed in recent years in the literature, encouraged by the increasing number of available data sets on the LOD cloud. In [START_REF] Nikolov | Overcoming schema heterogeneity between linked semantic repositories to improve coreference resolution[END_REF], a schema matching approach which uses existing instance-level coreference links, defined in third-party repositories, as background knowledge is proposed. It aims at generating schema-level correspondences to assist the instance coreference resolution process. Rather than producing strict equivalence or subsumption relations, the algorithm produces fuzzy correspondences representing degrees of overlap between different ontologies. In [START_REF] Pernelle | LDM: Link Discovery Method for new Resource Integration[END_REF], an approach that addresses both link discovery and ontology alignment is proposed, where the results of the link discovery step are exploited to improve the results of the ontology alignment step and vice versa. In [START_REF] Parundekar | Discovering concept coverings in ontologies of linked data sources[END_REF], the proposal consists of (a) generating more expressive concepts from those already present in the ontologies (i.e. exploiting the space of concepts defined by value restrictions), and (b) aligning these extended concepts by exploiting the links between instances on the LOD. Contrary to our approach, these proposals consider a single representation of ontologies (i.e. OWL) and focus on links between instances.

For dealing with the specifities of community-created LOD data sets, a system for finding schema-level links is proposed in [START_REF] Jain | Ontology alignment for linked open data[END_REF]. It computes alignments (not limited to equivalence relations) with the help of noisy communitygenerated data available on the Web, i.e. Wikipedia and Wikipedia category hierarchy. The idea of using Wikipedia category hierarchy, together with a rule-based verification approach, has also been exploited in [START_REF] Grütze | Holistic and scalable ontology alignment for linked open data[END_REF], where a holistic matching approach aims at aligning simultaneously multiple schemes on the LOD. In [START_REF] Cruz | Towards "on the go" matching of linked open data ontologies[END_REF], an extended version of the AgreementMaker system is proposed, aiming at handling subsumption relations and improving its performance when dealing with LOD ontologies. For each source and target concepts, the algorithm searches across several LOD ontologies for all concepts that are defined as subclasses, before applying matching strategies. Contrary to our approach, these works exploit other relations than equivalence and focus on the schema-level of LOD ontologies instead of exploiting the links between them. Contrary to the proposals described above, these latter works do not exploit the instance level within the schema-matching process.

[ Mochol andJentzsch, 2008, Steyskal andPolleres, 2013] propose, like us, to reuse existing tools and to combine their results to align two ontologies. In [START_REF] Mochol | Towards a rule-based matcher selection[END_REF] a set of rules to select appropriate methods for a given pair of ontologies to be aligned is proposed. This selecting process is based on the background information describing the available approaches and the input properties of the ontologies. In [START_REF] Steyskal | Mix'n'match: An alternative approach for combining ontology matchers[END_REF], an iterative method based on voting is proposed, where at every round, the correspondences accepted by the majority of tools are considered as valid. However, these works do not exploit the alignments on the LOD.

With regards to combining multiple alignments, different approaches have been proposed. In [START_REF] Ghoula | Opérateurs de gestion des alignements de ressources de connaissances hétérogènes[END_REF], an approach for normalising, combining and integrating alignments from multiple sources is proposed, where a correspondence can be associated to a set of relations and confidence levels. The algebra defined in [Euzenat, 2008] was applied in order to implement operators like union, composition and intersection. The approach can be applied regardless of the formalism used to represent the ontologies to be aligned. As we do, the normalisation step allows the removing of 'concurrent' (i.e. ambiguous) correspondences. However, we do not apply any combining operator, while they do not exploit LOD alignments. In [START_REF] Lee | etuner: Tuning schema matching software using synthetic scenarios[END_REF], a library of matching components is made available and the user can select which components are to be used within a matching process, how they have to be combined together (average, minimum, maximum, weighed sum, decision trees, etc.), and how the correspondences are finally extracted (from a selection based on thresholding to formulate the selection as an optimisation problem over a weighted bipartite graph). The approach involves well automatic tuning of matching systems in order to find a tuning that optimises the performance of them. Here, we propose a different way for combining multiple alignments. In [START_REF] Eckert | Improving ontology matching using meta-level learning[END_REF], alignments generated from different matching systems are used as training data for a classifier that learns which combination of results provides the best indication of a correct correspondence. The multiple matchers are treated as a black-box. The assumption on which the approach relies is similar to ours : by using multiple matchers one can benefit from the high degree of precision of some matchers and at the same time the broader coverage of other matchers. In [START_REF] Spiliopoulos | Synthesizing ontology alignment methods using the max-sum algorithm[END_REF], combining multiple matchers is seen as a problem of maximising the social welfare within a group of interacting agents. Different agents computing alignments using specific methods and considering a specific kind of ontology entity, interact with each other and share constraints on the validity of the correspondences in order to reach an agreement. Although we do not aim at reaching a consensus between matchers, a correspondence is more likely to be correct if it is accepted by more than one matcher, which are not dedicated to find correspondences between specific ontology entities.

Finally, with respect to matching of terminologies in several languages, [START_REF] Mougin | Using a cross-language approach to acquire new mappings between two biomedical terminologies[END_REF] adopts a notion of refining that is close to ours. The authors present a cross-language approach for matching two biomedical terminologies (MedDRA and SNMI). From a set of correspondences computed using lexical methods, the incorrect correspondences are filtered out using the notion of seman-tic groups, which correspond to the partition of UMLS concepts. If the semantic groups which belong to UMLS concepts of MedDRA and SNMI terms are not the same, the correspondence is considered as incorrect. Then, they compute the number of correspondences which are common to different languages (correspondences which are more likely to be correct) and suppress the ambiguities by eliminating correspondences found in only one language.

Conclusion and perspectives

In this paper, we have proposed a new ontology matching method which can raise one of the challenges of ontology matching stated in [START_REF] Shvaiko | Ontology matching: state of the art and future challenges[END_REF]: matching with background knowledge. In a first step, our matching method allows to generate many correspondences using and combining existing methods for aligning ontologies, thesauri and OTR expressed in different representation languages. Then, it allows a discrimination of the correspondences by removing some ambiguities and by exploiting the redundancy and existing alignments on the LOD, in order to identify a subset of potentially correct correspondences which will be submitted to the user for validation.

This proposal is a preliminary work for publishing ontologies on the LOD. Ontology matching allows a source ontology not only to be enriched with new concepts and/or terms, but also to be linked with existing and in use ontologies on the LOD in order to contribute to the data sharing in the target domain.

In order to improve our process of refinement, we plan in the short term, (i) to evaluate our approach using another data set, such as the OAEI Library task, which offers variants of their thesauri and for which we can find LOD alignments between them, (ii) to take into account the expressiveness of ontology variants to suppress the ambiguities of type 1; (iii) to exploit other relations than the equivalence in the treatment of ambiguities of type 2 -instead of removing ambiguous correspondence of type 2, we plan to propose a methodology based on reasoning for choosing the best correspondence between the ambiguous ones: by removing, for instance, correspondences which introduce a logical inconsistency; (iv) to remove the ambiguities between correspondences by defining new relations -we can, for instance, use an algebra to define a new correspondence with a new relation which combines the relations involved in the ambiguous correspondences; (v) to study how to use the subsumption relation in order to facilitate the identification of potentially correct correspondences; (vi) to study how to use relations between concepts (e.g. their domains and ranges) and their matching results in order to suppress the ambiguities and/or to identify the potentially correct correspondences. In the long term, we plan to exploit indirect alignments between different sources on the LOD to improve the discrimination on the set of correspondences. We also plan to extend our approach to take into account more complex entities such as units of measurement and n-ary relations.

Fig. 1

 1 Fig. 1 Overview of our matching method.

Example 4 .

 4 Let us consider the correspondence c 1 generated by the matching process f 1 of Example 1 and the correspondence c 6 generated by the matching process f 2 of Example 1. We have:c 1 = id 1 , sheep, c 8854, ≡, 0.95 , c 1 ∈ A f 1 NARYQ OW L-SKOS ,AGROVOC SKOSsim(sheep, c 8854) = 0.815, where c 8854 corresponds to the concept 'caprins' in AGROVOC; c 6 = id 6 , sheep, c 9214, ≡, 0.65 , c 6 ∈ A f 2 NARYQ OW L-SKOS ,AGROVOC OW L 2 sim(sheep, c 9214) = 0.621, where c 9214 corresponds to the concept 'goat' in AGROVOC. The set of sets agr2 * C NARYQ→AGROVOC of non ambiguous correspondences according to type 2 only contains the correspondence c 1 with the highest similarity measure.

  AGROVOC SKOS sim(sheep, c 8854) = 0.815, where c 8854 corresponds to the concept 'caprins' in AGROVOC; c 7 = id 7 , ewe, c 8854, ≡, 0.55 , c 7 ∈ A f 1 NARYQ OW L-SKOS ,AGROVOC SKOS sim(ewe, c 8854) = 0.722. The set of sets agr3 * C NARYQ→AGROVOC of non ambiguous correspondences according to type 3 only contains the correspondence c 1 with the highest similarity measure.

Fig. 2

 2 Fig.2Overview of our refinement process.

  validated correspondences, with 361 concepts of NARYQ aligned with concepts of AGROVOC. • R + NALT has 428 validated correspondences, with 424 concepts of NARYQ aligned with concepts of NALT. • 303 concepts of NARYQ are aligned with both concepts of AGROVOC and concepts of NALT. partial, are used in the following as reference alignments.

2, AGROVOC OW L 3 }

 3 AGROVOC SKOS includes AGROVOC in all languages and we used its version downloaded in April 2013 from the official Web site 10 . AGROVOC SKOS 1 is a much smaller version, in English Only, available on the same Web site. The variant AGROVOC OW L 2 was used into the 2007 OAEI campaign. The variant AGROVOC OW L 3 was generated from AGROVOC SKOS using a SKOSParser 11 . The variants of NALT are:

  dences are said 'comparable' if an entity of the source ontology O s is aligned, by an equivalence relation, with two distinct but linked on the LOD entities of the target ontologies O 1

	A LOD O 1 t →O 2

t defined on the LOD between the target ontologies O 1 t and O 2 t , correspont and O 2 t . These correspondences will be kept in two separate sets, denoted LOD C O s →O 1 t and LOD C O s →O 2 t

Table 2

 2 Best scores of alignments obtained by the two matching tools.

	Alignment	# *	P *	R *	F-m *
	NARYQ→ AGROVOC	300	0.90	0.82	0.85
	NARYQ→ NALT	359	0.80	0.83	0.81

Table 3

 3 Evaluation of NARYQ→ AGROVOC with respect to R

	+ AGROVOC .

Table 4

 4 Evaluation of NARYQ→ NALT with respect to R

	+ NALT .

http://linkeddata.org

http://oaei.ontologymatching.org

http://aims.fao.org/standards/agrovoc/about

http://agclass.nal.usda.gov/agt.shtml

http://www.geonames.org

http://dbpedia.org

http://www.eionet.europa.eu/gemet

http://www.w3.org/TR/owl-guide

http://www.w3.org/TR/2009/REC-skos-reference-20090818


Benjamin Moreau
email: benjamin.moreau@opendatasoft.com

Patricia Serrano-Alvarado
email: patricia.serrano-alvarado@ls2n.fr

Emmanuel Desmontils
email: emmanuel.desmontils@ls2n.fr

A Lattice-Based Model for License Classifications

Keywords: Licenses, usage control, privacy, linked data, RDF, ODRL

come

INTRODUCTION

Web applications facilitate combining resources (linked data, web services, source code, documents, etc.) to create new ones. Resource producers should systematically associate licenses with resources before sharing or publishing them. Licenses specify precisely the conditions of reuse of resources, i.e., what actions are permitted, obliged and prohibited when using the resource.

For a resource producer, choosing the appropriate license for a combined resource and choosing the appropriate licensed resources for a combination is a difficult process. It involves choosing a license compliant with all the licenses of combined resources as well as controlling the reusability of the resulting resource through the compatibility of its license. The risk is either, to choose a license too restrictive making the resource difficult to reuse, or to choose a not enough restrictive license that will not sufficiently protect the resource.

We consider a simplified definition of compliance inspired by works like [START_REF] Gr Gangadharan | Service License Composition and Compatibility Analysis[END_REF][START_REF] Governatori | One License to Compose Them All. A Deontic Logic Approach to Data Licensing on the Web of Data[END_REF][START_REF] Kapitsaki | Automating the License Compatibility Process in Open Source Software With SPDX[END_REF][START_REF] Villata | Licenses Compatibility and Composition in the Web of Data[END_REF]: a license 𝑙𝑗 is compliant with a license 𝑙𝑖 if a resource licensed under 𝑙𝑖 can be licensed under 𝑙𝑗 without violating 𝑙𝑖. If a license 𝑙𝑗 is compliant with 𝑙𝑖 then we consider that 𝑙𝑖 is compatible with 𝑙𝑗 and that resources licensed under 𝑙𝑖 are reusable with resources licensed under 𝑙𝑗.

Compatibility of licenses can be verified through the actions permitted, obliged and prohibited. In general, when 𝑙𝑖 is compatible with 𝑙𝑗, the obligations and prohibitions of 𝑙𝑖 exist in 𝑙𝑗, and 𝑙𝑗 has at most the permissions of 𝑙𝑖. Figure 1 shows an excerpt of three Creative Commons (CC) 1 licenses described in RDF using the ODRL vocabulary 2 . We can notice that:

• CC BY is compatible with CC BY, CC BY-NC and CC BY-NC-ND; • CC BY-NC is compatible with CC BY-NC, CC BY-NC-ND; and • CC BY-NC-ND is compatible with CC BY-NC-ND.

Imagine a search engine that can find linked data based on their licenses. Consider this search "find all datasets concerning bikes that can be reused under the CC BY-NC license". The answer must contain datasets with licenses compatible with CC BY-NC that (in our example) are less or as restrictive as it. Consider this other search that will find out the reusability of the combined resource "find all datasets that can reuse a dataset protected by CC BY-NC ". The answer must contain datasets with licenses compliant with CC BY-NC that (in our example) are at least as restrictive as it is (CC BY-NC and CC BY-NC-ND). Answers are order form the least to the most restrictive (or vice versa).

We can imagine a similar search engine for services such as GitHub 3 or APISearch 4 that could find source code repositories or APIs protected by licenses that are compatible or compliant with a specific license.

We argue that a model for license classifications would make possible the existence of such a license-based search engines. Our research question is: given a license 𝑙𝑖, how to automatically position 𝑙𝑖 over a set of licenses in terms of compatibility and compliance? That is, given a set of licenses, what are the licenses that precede and follow 𝑙𝑖 in terms of compatibility and compliance?

Our contribution is twofold: (1) inspired by access control models [START_REF] Denning | A Lattice Model of Secure Information Flow[END_REF][START_REF] Sandhu | Lattice-Based Access Control Models[END_REF], we propose CaLi (ClAssification of LIcenses), a lattice-based model for license classifications and (2) a prototype of a search engine based on a CaLi classification that allows to find datasets of the Web of Data whose licenses are compatible or compliant with a target license.

Our work is a step forward in creating tools that facilitate the creation and reuse of license compliant resources. This kind of effort will encourage the publication and reuse of data in the Web of Data.

The remainder of the paper is as follows. Section 2 discuses related works, Section 3 introduces the CaLi model, Section 4 illustrates the usability of our model, Section 5 shows the implementation of a license-based search engine for linked data, and Section 6 concludes.

RELATED WORK

This section analyses several approaches and tools related to our research question.

Machine-readable licenses

Automatic license classification requires machine-readable licenses. License expression languages such as CC REL 5 , ODRL, or L4LOD6 enable fine-grained RDF description of licenses. Works like [START_REF] Sadeh | Towards Usable Privacy Policies: Semi-Automatically Extracting Data Practices from Websites? Privacy Policies[END_REF] and [START_REF] Cabrio | These Are Your Rights[END_REF] use natural language processing to automatically generate RDF licenses from licenses described in natural language. Other works such as [START_REF] Víctor | A Dataset of RDF Licenses[END_REF] or [2] propose a set of well-known licenses in RDF described in CC REL and ODRL. In this work we do not address these issues, we consider that there exist consistent licenses described in RDF.

Tools for license compliant resources

There exist some tools to facilitate the creation of license compliant resources. TLDRLegal7 , CC Choose8 and ChooseALicense 9 help users to choose actions to form a license for their resources.

CC search10 allows users to find images licensed under Creative Commons licenses that can be commercialized, modified, adapted, or built upon.

Web2rights proposes a tool to check compatibility among Creative Commons licenses 11 .

Finally, Licentia 12 , based on defeasible deontic logic to reason over the licenses, proposes a web service to find licenses compatible with a set of permissions, obligations and prohibitions chosen by the user.

From these tools, only Licentia uses machine-readable licenses 13 described in RDF using ODRL. Unfortunately, Licentia is not able to order licenses in terms of compatibility or compliance.

License compatibility and license combination

The easiest way to choose a license for a combined resource is to create a new one by combining all resource licenses to combine. Several works address the problem of license compatibility and license combination.

In Web services, [START_REF] Gr Gangadharan | Service License Composition and Compatibility Analysis[END_REF] proposes a framework that analyzes compatibility of licenses to verify if two services are compatible and then generate the composite service license. [START_REF] Mesiti | On the Composition of Digital Licenses in Collaborative Environments[END_REF] addresses the problem of license preservation during the combination of digital resources (e.g., music, data, picture, etc.) in a collaborative environment. Licenses of combined resources are combined into a new one.

In the Web of Data, [START_REF] Villata | Licenses Compatibility and Composition in the Web of Data[END_REF] proposes a framework to check compatibility among CC REL licenses. If licenses are compatible, a new license compliant with combined ones is generated. [START_REF] Governatori | One License to Compose Them All. A Deontic Logic Approach to Data Licensing on the Web of Data[END_REF] formally defines the combination of licenses using deontic logic. [START_REF] Soto-Mendoza | Policies Composition Based on Data Usage Context[END_REF] proposes PrODUCE, an approach to combine usage policies taking into account the usage context. These works focus on combining operators for automatic license combination but do not propose to position a license over a set of licenses.

Such operators will be very valuable in the design of an automatic classification.

License classification

Concerning the problem of license classification to facilitate the selection of a license, [START_REF] Daga | A Bottom-up Approach for Licences Classification and Selection[END_REF] uses Formal Concept Analysis (FCA) to generate a lattice of actions. Once pruned and annotated, this lattice can be used to classify licenses in terms of features. This classification reduces the selection of a license to an average of three to five questions. However, this work does not address the problem of license combination and license compatibility. Moreover, FCA is not suitable to generate complex compatibility relations among licenses. FCA defines a derivation operator on objects that returns a set of attributes shared by the objects. We consider that the set of actions in common of two licenses is not enough to infer compatibility. If applied to our introductory license compatibility example, FCA can only work with permissions but not with obligations and prohibitions. That is because 𝑙𝑖 is compatible with 𝑙𝑗 if 𝑙𝑖 permissions are a superset of 𝑙𝑗 permissions, but regarding obligations and prohibitions, 𝑙𝑖 is compatible with 𝑙𝑗 if they are a subset of those of 𝑙𝑗.

In the context of Free Open Source Software (FOSS), [START_REF] Kapitsaki | Automating the License Compatibility Process in Open Source Software With SPDX[END_REF] proposes an approach, based on a directed acyclic graph, to detect license violations in existing software packages. It considers that license 𝑙𝑖 is compatible with 𝑙𝑗 if the graph contains a path from 𝑙𝑖 to 𝑙𝑗. However, as such a graph is build from a manual interpretation of each license, its generalization and automation is not possible.

Lattice-based access control

In the domain of access control, [START_REF] Denning | A Lattice Model of Secure Information Flow[END_REF] proposes a lattice model of secure information flow. This model classifies security classes with associated resources. Like in the compatibility graph of [START_REF] Kapitsaki | Automating the License Compatibility Process in Open Source Software With SPDX[END_REF], security class 𝑠𝑐𝑖 is compatible with 𝑠𝑐𝑗 if the lattice contains a path from 𝑠𝑐𝑖 to 𝑠𝑐𝑗. Thus, this path represents the authorized flow of resources (e.g., resource 𝑟𝑖 protected with 𝑠𝑐𝑖 can flow to a resource protected by 𝑠𝑐𝑗 without violating 𝑠𝑐𝑖.). The lattice can be generated automatically through a pairwise combination of all security classes if 𝑠𝑐𝑖 combined with 𝑠𝑐 𝑘 gives 𝑠𝑐𝑗 where 𝑠𝑐𝑖 and 𝑠𝑐 𝑘 are both compatible with 𝑠𝑐𝑗. [START_REF] Sandhu | Lattice-Based Access Control Models[END_REF] describes several models based on this approach but none focuses on classifying licenses.

None of these works answers our research question. They do not allow to automatically position a license over a set of licenses in terms of both compatibility and compliance.

In our work we propose a lattice-based model inspired by [START_REF] Denning | A Lattice Model of Secure Information Flow[END_REF]. Existing combining operators like [START_REF] Gr Gangadharan | Service License Composition and Compatibility Analysis[END_REF][START_REF] Governatori | One License to Compose Them All. A Deontic Logic Approach to Data Licensing on the Web of Data[END_REF][START_REF] Soto-Mendoza | Policies Composition Based on Data Usage Context[END_REF][START_REF] Villata | Licenses Compatibility and Composition in the Web of Data[END_REF]] make feasible the automatic generation of a lattice. Our model allows users to easily find and compare licenses as well as licensed resources. This model is independent on any license combination approach, license description language and licensed resources so that it can be used in a wide variety of domains.

CALI: A LATTICE-BASED LICENSE MODEL

CaLi is a model that allows to express license classifications with a lattice structure. The model considers a finite set of licenses, a combining operator, a compatibility relation over licenses, resources and their association with licenses, and a constraint set. The combining operator applied to the set of licenses produces a lattice that expresses the compliance and compatibility among licenses.

Next section introduces the CaLi model, then we describe its lattice structure and we finish with a simple example of a CaLi-based classification.

Model description

The license classification model is introduced by Definition 3.1.

Definition 3.1. CaLi = ⟨𝐿, ⨁ , →, 𝑅, ↦ →, 𝐶⟩. 𝐿 = {𝑙1, ..., 𝑙𝑛} is a set of licenses.
⨁ is a license combining operator. → is the compatible with relation defined on pairs of licenses. 𝑅 = {𝑟1, ..., 𝑟𝑚} is a set of resources. ↦ → is the protected by relation between 𝑅 and 𝐿. 𝐶 = ⟨𝐶𝐿, 𝐶→⟩ is a finite set of constraints to express viability.

𝐶𝐿 is a set of constraints over 𝐿 and 𝐶→ is a set of constraints over → in 𝐿 × 𝐿.

A license is considered as a set of actions. Actions used in 𝐿 can be taken from 𝐴 = {𝑎1, ..., 𝑎𝑛}, a set of actions that can be applied on resources.

⨁ is an associative and commutative binary operator that specifies for any pair of licenses, the combined license that is compliant with both licenses. For licenses 𝑙𝑖 and 𝑙 𝑘 , if 𝑙𝑖 ⨁ 𝑙 𝑘 = 𝑙𝑗 then 𝑙𝑗 is compliant with 𝑙𝑖 and 𝑙 𝑘 . For licenses 𝑙𝑖 and 𝑙𝑗, we write 𝑙𝑖 → 𝑙𝑗 iff 𝑙𝑖 is compatible with 𝑙𝑗 (or 𝑙𝑗 is compliant with 𝑙𝑖). 𝑙𝑖 → 𝑙𝑗 implies 𝑙𝑖 ⨁ 𝑙𝑗 = 𝑙𝑗, i.e., 𝑙𝑗 overcomes 𝑙𝑖.

Concerning 𝑅, we write 𝑟𝑖 ↦ → 𝑙𝑖 when the resource 𝑟𝑖 is protected by 𝑙𝑖. For 𝑟𝑖 ↦ → 𝑙𝑖, if 𝑙𝑖 is compatible with 𝑙𝑗 then 𝑟𝑖 can be protected by 𝑙𝑗.

In this work, we introduce the concepts of viability of a license and viability of a → relation.

• A viable license is a license that allows the licensed resource to be used. A license 𝑙𝑖 is viable iff it respects all 𝐶𝐿 constraints. We define a constraint on licenses as an application 𝜔𝐿 : 𝐿 → 𝐵𝑜𝑜𝑙𝑒𝑎𝑛 which associates each license of 𝐿 with either True or False. Our model with the lattice structure allow to answer our research question given a license 𝑙𝑖, how to automatically position 𝑙𝑖 over a set of licenses in terms of compatibility and compliance? For a license 𝑙𝑖, the licenses which precede it in the lattice are compatible with it, and the licenses which follow it in the lattice are compliant with this one. This is equivalent to say that 𝑙𝑖 is compliant with the licenses which precede it in the lattice and it is compatible with the licenses which follow it in the lattice.

When the constraint set 𝐶 is not empty, 𝐶 ̸ = ∅, 𝑙𝑖 is compatible with 𝑙𝑗 if there exists a path from 𝑙𝑖 to 𝑙𝑗 where all compatible with relations and all licenses are viable.

Example 1

Consider a classification where licenses are simplified to a set of prohibitions. The set 𝐴 of actions is {read, modify, distribution}. The license combining operator consists in the union of prohibitions. Resources are datasets in 𝑅. This 𝐶𝑎𝐿𝑖 classification is described as follows. In this example, the constraint that characterizes viable licenses is, if the 𝑚𝑜𝑑𝑖𝑓 𝑦 action is prohibited then the 𝑟𝑒𝑎𝑑 action must be too:

𝐿 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡(𝐴)
𝜔𝐿 1 (𝑙𝑖) = { 𝐹 𝑎𝑙𝑠𝑒 if 𝑟𝑒𝑎𝑑 ∈ 𝑃 𝑟 𝑙 𝑖 and 𝑚𝑜𝑑𝑖𝑓 𝑦 / ∈ 𝑃 𝑟 𝑙 𝑖 ; 𝑇 𝑟𝑢𝑒 otherwise.
Figure 2 shows a visual representation of the lattice of this example. In the lattice, 𝐼 = ∅ and 𝑆 = 𝐴. The combining operator generates the powerset of the first level of the lattice. The first level of the lattice is composed by the minimal set of licenses that allows CaLi to generate all other licenses. Due to the combining operator, the minimal set for this example is composed of licenses having only one action ∈ 𝐴, i.e., |𝑙𝑒𝑣𝑒𝑙1| = |𝐴|. The total number of licenses in L is 2 |𝑙𝑒𝑣𝑒𝑙 1 | = 2 |𝐴| . Non-viable licenses, 𝑙1 and 𝑙5, are part of the lattice but they cannot protect resources.

To the question, "find resources whose licenses are compatible with 𝑙4", this lattice allows to answer 𝑟1, 𝑟2, 𝑟3 and 𝑟5 which are protected by 𝑙0 and 𝑙2 which precede 𝑙4 in the classification as well as by 𝑙4 itself. That means that resources protected by 𝑙0, 𝑙2 and 𝑙4 can be reusable with resources protected by 𝑙4.

Similarly, to the question, "find resources whose licenses are compliant with 𝑙4", this lattice allows to answer 𝑟5 and 𝑟7, which respectively are protected by license 𝑙7 as well as by 𝑙4 itself. That means that resources protected by 𝑙4 are reusable with resources protected by 𝑙4 and 𝑙7.

Thus, analyzing compatibility and compliance allow to evaluate the reusability of resources.

Licenses above 𝑙4 are more restrictive than 𝑙4 and licenses below 𝑙4 are less restrictive than 𝑙4. The least restrictive compliant license for 𝑙4 is the direct following one 𝑙7. The most

LICENSE CLASSIFICATION FOR ACTIONS OF CREATIVE COMMONS

Creative Commons (CC) proposes easy-to-understand licenses that are widely used when publishing resources on the web (creative content, linked data 14 , etc.). Licenses are composed of at most 7 actions distributed in permissions, obligations and prohibitions: cc:Distribution, cc:Reproduction, cc:DerivativeWorks, cc:CommercialUse, cc:Notice, cc:Attribution, cc:ShareAlike. CC REL is the language to express Creative Commons licenses in RDF. CC proposes only 7 licenses but with the CaLi model we search to produce a complete classification of all possible licenses using these 7 actions.

Description of a CC classification based on CaLi

In this CC classification, we consider that each license has a set of permissions, obligations and prohibitions. Licenses are consolidated, that is, each term of the set of actions 𝐴 must appear in each license. The idea is that each action be permitted, obliged or prohibited in each license. The license combining operator makes the intersection of permissions, the union of obligations and the union of prohibitions of concerned licenses. Concerning the set of constraints that characterizes viable licenses and viable → relations:

𝜔𝐿 1 (𝑙𝑖) = { 𝐹 𝑎𝑙𝑠𝑒 if (𝑃 𝑙 𝑖 ∩ 𝑂 𝑙 𝑖 ) ∪ (𝑃 𝑙 𝑖 ∩ 𝑃 𝑟 𝑙 𝑖 ) ∪ (𝑂 𝑙 𝑖 ∩ 𝑃 𝑟 𝑙 𝑖 ) ̸ = ∅; 𝑇 𝑟𝑢𝑒 otherwise.
That is, sets of permissions, obligations and prohibitions are mutually disjoint.

𝜔→ 1 (𝑙𝑖, 𝑙𝑗) = { 𝐹 𝑎𝑙𝑠𝑒 if cc:ShareAlike ∈ 𝑂 𝑙 𝑖 and 𝑙𝑖 ̸ = 𝑙𝑗; 𝑇 𝑟𝑢𝑒 otherwise.
That is, cc:ShareAlike term obligates the distribution of derivative works only under the same license.

𝜔→ 2 (𝑙𝑖, 𝑙𝑗) = { 𝐹 𝑎𝑙𝑠𝑒 if cc:DerivativeWorks ∈ 𝑃 𝑟 𝑙 𝑖 ; 𝑇 𝑟𝑢𝑒 otherwise.
That is, if cc:DerivativeWorks is prohibited in 𝑙𝑖 then resources protected by 𝑙𝑖 should not be protected by 𝑙𝑗.

Other constraints could be defined, but for the purposes of this classification we consider that these three constraints are enough. 𝐼 = ⟨𝑙 𝑙 , 𝐴, ∅, ∅⟩ is the license compatible with all other licenses of the lattice. 𝐼 is obtained by creating a license that permits all actions from 𝐴. 𝑆 = ⟨𝑙𝑠, ∅, 𝐴, 𝐴⟩ is the license compliant with all other licenses of the lattice. 𝑆 is obtained by combining all licenses with ⨁ . The size of the lattice for this classification (i.e., the number of licenses) is 2 2|𝐴| where 2|𝐴| is the size of the first level. The first level of the lattice is composed of the minimal set of licenses that allows ⨁ to generate all possible licenses, that is, all licenses having |𝐴| -1 actions in permissions and at most one action in obligations or prohibitions:

|𝑃 𝑙 𝑖 | = |𝐴| -1 and |𝑂 𝑙 𝑖 |+|𝑃 𝑟 𝑙 𝑖 | = 1.
That gives 2 |𝐴| = 14 licenses in our example. Thus, this classification is composed of 16384 licenses. The set of constraints identifies 2134 viable licenses. 15

Analysis of the CC classification based on CaLi compared to the Creative Commons family

Our CC classification that uses the seven actions of Creative Commons is consistent with the one obtained from the web2rights tool. The number of licenses produced by CaLi is huge compared to the number of Creative Commons licenses but our goal is not classify their seven licenses. Our goal is to have a formal model that automatically classifies all possible licenses from a set of actions. To control the number of viable licenses, depending on the context, the set of constraints can be expanded. For instance, all compatibility rules identified in [START_REF] Villata | Licenses Compatibility and Composition in the Web of Data[END_REF] can be included as 𝐶𝐿 constraints.

Table 1 shows some licenses of the first level of this lattice.

Next levels of the lattice are produced by the combining operator. Table 2 shows some licenses of the Creative Commons family. Notice that CC BY is produced by 𝑙1 ⨁ 𝑙2 and CC BY-NC by 𝑙1 ⨁ 𝑙2 ⨁ 𝑙3. Table 3 shows some licenses that are not part of the Creative Commons family. First license is like CC BY-NC but without the obligation to give credit to the copyright holder and/or author of the work. The second license prohibits to make multiple copies of the resource. The third license obligates the reuse of the resource by making exact copies of the original source. The last license is the third license with the prohibition to make a commercial use of the resource.

The combining operator may produce non-viable licenses or non-viable compatibility relations. Table 4 shows one nonviable license of the lattice that does not respect 𝐶1.

Figure 3 shows a small part of the lattice of this CaLi classification, the one that concerns the compatibility relations of Creative Commons licenses. This graph shows only licenses and → relations that are viable. Thanks to 𝐶2, the compatibility relation between CC BY-SA and CC BY-NC-SA is identified as non-viable and thanks to 𝐶3, the compatibility relation between CC BY-ND and CC BY-NC-ND is identified as non-viable. We recall that the compatibility relations of this graph are conform to the ones obtained from the web2rights tool.

A CaLi-based classification for licenses of the Web of Data

This search engine is based on a CaLi classification that is similar to the CC classification of last section with the following particularities: (i) 𝐴 contains the set of 72 actions considered by ODRL16 , (ii) licenses are not required to be consolidated, and (iii) a 𝜔𝐿 2 constraint is added to 𝐶𝐿. Unlike Creative Commons actions, ODRL actions are organized using inclusion. For example, action use is included by CommercialUse or play is included by display. To preserve this dependency we include the constraint 𝜔𝐿 2 in 𝐶𝐿 such that, if an action 𝑎𝑖 is prohibited all the actions included in 𝑎𝑖 must not be permitted nor obligated. For example, a license that prohibits Use is not viable if it permits or obligates Commercial Use.

𝜔𝐿 2 (𝑙𝑖) = ⎧ ⎨ ⎩ 𝐹 𝑎𝑙𝑠𝑒 if ∃𝑎𝑖 ∈ 𝑃 𝑟 𝑙 𝑖 and ∃𝑎𝑗 included by 𝑎𝑖 and (𝑎𝑗 ∈ 𝑃 𝑙 𝑖 or 𝑎𝑗 ∈ 𝑂 𝑙 𝑖 ); 𝑇 𝑟𝑢𝑒 otherwise.
The generation of a lattice has a complexity of 𝑂(2 𝑛 ). In our case, 𝑛 = 2|𝐴| and the number of nodes in the lattice is 2 144 . The number of nodes grows exponentially with the number of terms resulting in a combinatorial explosion. Generating the complete lattice is not suitable for a real scenario with a large number of terms. In next section, we show how we can generate part of the lattice on the fly to implement a license compliant tool.

Implementation of a license-based search engine

Since the complete lattice cannot be generated, we propose two algorithms to generate on the fly part of the lattice. This approach is in 𝑂(𝑛) where 𝑛 is the number of existing nodes. We chose to generate the most used licenses in datahub17 and in the OpenDataSoft platform18 . We extracted the sets of permissions, obligations and prohibitions from an existing set of RDF licenses 19 . As currently we do not take into account other aspects of a license like its jurisdiction, all licenses having the same sets will be considered in the same node.

The search engine maintains an index of licenses. The condition to add a license to our index is to have at least the URI of one RDF dataset associated to this license. As in this implementation the combining operator cannot combine all licenses to generate the complete classification (because the complete lattice cannot be generated), we make a verification of compatibility and compliance of the new license over (potentially all) existing licenses in the classification. The goal is to be conform to the partial order of the lattice. The challenge is to find the right place to insert new licenses. First, the classification graph 𝐺 is initialized with the infimum 𝐼, the supremum 𝑆 and the compatibility relation 𝐼 → 𝑆. Then, in order to insert a new license in the classification, Algorithm 1 adds a new license 𝑙𝑖 and calls Algorithm 2 to position 𝑙𝑖 in the right place in the classification.

Algorithm 1 adds 𝑙𝑖 to the classification 𝐺 only if it is viable. License 𝑙𝑖 is viable if it respects all constraints in 𝐶𝐿 (in the particular case of the license-based search engine, 𝐶1 and 𝐶4). Then, it calls the recursive Algorithm 2 with 𝐼 and 𝐺, to classify 𝑙𝑖 in licenses compliant with 𝐼, i.e., the recursive link starts from the Infimum. Licenses compliant with 𝐼 are all the licenses of 𝐺.

To be conform to the partial order of the then 𝑙𝑗 is compliant with 𝑙𝑖. This algorithm recursively links 𝑙𝑖 to the least restrictive licenses compliant with 𝑙𝑖 in the classification.

Algorithm 2 tries to add compatible relations → between 𝑙𝑖 and the least restrictive compatible licenses that are compliant with 𝑙𝑗 (𝐿𝑅𝐶 𝑙 𝑗 ). A compatible relation is added only if it is viable. Relation → is viable if it respects all 𝐶→ constraints (in the particular case of the license-based search With these algorithms, when licenses are inserted to 𝐺 the partial order of the lattice is maintained. The produced graph is part of the lattice and is directed and acyclic.

Another strategy can be implemented to reduce the average number of operations needed to classify a new license. Algorithms 1 and 2 could start from the bottom (the least restrictive license 𝐼) or the top (the most restrictive license 𝑆) of 𝐺 depending on the cardinality of permissions, obligations and prohibitions sets of the new license to insert.

Once the graph is enriched with licenses and associated datasets, answering our questions is straightforward. Finding all licensed datasets whose licenses are compliant with a particular license 𝑙𝑖 means to retrieve datasets protected by 𝑙𝑖 and all datasets protected by licenses that are above 𝑙𝑖 in the graph. Similarly, finding all licensed datasets whose licenses are compatible with a specific license 𝑙𝑖 means to retrieve datasets protected by 𝑙𝑖 and all datasets protected by licenses that are below 𝑙𝑖 in the graph.

The prototype of this search engine is available at http: //cali.priloo.univ-nantes.fr20 . The home screen21 enables fulltext and license compliant searches of RDF datasets. The CaLi classification is available through a documented API22 containing functions that can answer our questions. For example, with /api/licenses/{licenseID}23 /compatible, it is possible to retrieve licenses compatible with a particular license (e.g., CC BY-NC24 ). Likewise, with /api/licenses/{licenseID} /compliant it is possible to retrieve licenses compliant with a particular license (e.g., CC BY-NC25 ). A graph visualization of the classification is also available26 .

The source code is available at Github27 under the MIT license. The classification is stored using Neo4j 28 because it facilitates the storage and exploration of graph structures.

CONCLUSIONS AND PERSPECTIVES

In this paper we proposed CaLi, a model to express license classifications. The goal is to encourage the publication and reuse of resources in a license compliant web.

CaLi can be used to classify licenses in different contexts where resources need to be reused. It considers a set of licenses, a combining operator, a compatibility relation over the set of licenses and a set of constraints. We consider licenses as sets of permissions, obligations and prohibitions. The combining operator applied automatically to the set of licenses produces a lattice that expresses both compliance and compatibility among licenses. This lattice garantees a partial order over licenses where the relation is compatible with is reflexive, transitive and antisymmetric.

A limitation of our approach is the complexity in 𝑂(2 𝑛 ) of the lattice implementation. We demonstrate that the implementation of part of the lattice on-the-fly, in 𝑂(𝑛), is useful for a real application like the license-based search engine we present.

A perspective of this work is to take into account other aspects of a license related to usage contexts like jurisdiction, dates of reuse, etc. Another perspective is to analyse how two CaLi classifications can be compared. That is, (1) if two classifications are defined with different sets of actions 𝐴1 and 𝐴2, (2) if there exist an aligment between 𝐴1 and 𝐴2, and (3) if the combining operators of both classifications are compatible then find a function (for instance) to pass from a lattice to another.

Figure 1 :

 1 Figure 1: Three Creative Commons licenses described in RDF.

Figure 2 :

 2 Figure 2: Visual representation of the CaLi classification of Example 1.

  14 https://ns.inria.fr/l4lod/v2/l4lod_v2.html 𝐿 = {⟨𝑃, 𝑂, 𝑃 𝑟⟩}; 𝑃, 𝑂, 𝑃 𝑟 are sets of permissions, obligations and prohibitions containing actions ∈ 𝐴; the union of these sets is 𝐴. 𝐴 ={cc:Distribution, cc:Reproduction, cc:DerivativeWorks, cc:CommercialUse, cc:Notice, cc:Attribution, cc:ShareAlike}. ⨁ is the license combining operator, 𝑙𝑖 ⨁ 𝑙𝑗 ≡ ⟨𝑃 𝑙 𝑖 ∩ 𝑃 𝑙 𝑗 , 𝑂 𝑙 𝑖 ∪ 𝑂 𝑙 𝑗 , 𝑃 𝑟 𝑙 𝑖 ∪ 𝑃 𝑟 𝑙 𝑗 ⟩ where 𝑃 𝑙 𝑖 is the permission set of 𝑙𝑖, 𝑂 𝑙 𝑖 is the obligation set of 𝑙𝑖, and 𝑃 𝑟 𝑙 𝑖 is the prohibition set of 𝑙𝑖. → is the compatible relation stating that 𝑙𝑖 → 𝑙𝑗 iff 𝑃 𝑙 𝑖 ⊇ 𝑃 𝑙 𝑗 and 𝑂 𝑙 𝑖 ⊆ 𝑂 𝑙 𝑗 and 𝑃 𝑟 𝑙 𝑖 ⊆ 𝑃 𝑟 𝑙 𝑗 . 𝐶 = ⟨𝐶𝐿, 𝐶→⟩ where 𝐶𝐿 = {𝜔𝐿 1 } and 𝐶→ = {𝜔→ 1 , 𝜔→ 2 }.

Figure 3 :

 3 Figure 3: Compatibility of Creative Commons licenses taken from the CC classification.

  • A viable compatible with relation, 𝑙𝑖 → 𝑙𝑗, is a relation that allows a resource licensed under 𝑙𝑖 to be licensed under 𝑙𝑗. A → relation between two licenses is viable iff it respects all 𝐶→ constraints. We define a constraint on → relations as an application 𝜔→ : 𝐿 × 𝐿 → 𝐵𝑜𝑜𝑙𝑒𝑎𝑛 which associates each → with either True or False. 𝑙𝑖 → 𝑙 𝑘 and 𝑙𝑗 → 𝑙 𝑘 ⇒ 𝑙𝑖 ⨁ 𝑙𝑗 → 𝑙 𝑘 . For (a) without loss of generality we can consider that every pair of licenses is combined and the combining operator is commutative and associative. In (b), for any two licenses 𝑙𝑖 and 𝑙𝑗 the least upper bound is 𝑙𝑖

	3.2 Lattice structure ⟨𝐿, →,	⨁ ⟩
	The set of licenses 𝐿, the compatible with relation → and
	the combining operator	⨁	form a lattice with the following
	properties:
	(1) ⟨𝐿, →⟩ is a partially ordered set.
	(2) 𝐿 is finite.
	(3) 𝐿 has an infimum (or greatest lower bound) 𝐼 such that
		𝐼 → 𝑙𝑖 ∀𝑙𝑖 ∈ 𝐿.
	(4)	⨁	is a totally defined least upper bound operator on 𝐿.
	Demonstrations.
								e., if
		two licenses are compatible with each other, then they are
		the same license.
	Property (2) is demonstrated by the fact that the set of
	actions 𝐴 is finite. If a license is a set of actions and the license
	combining operator	⨁	is a least upper bound operator, then
	𝐿 is finite.
	Property (3) can be made without loss of generality consid-
	ering as infimum a license 𝐼 with zero, one or more actions.
	Property (4) is demonstrated by showing that every pair
	of licenses is combined and the result is a combined license
	(i.e.,	⨁	is totally defined) and that the license combining
	operator is a least upper bound, that is, ∀𝑙𝑖, 𝑙𝑗, 𝑙 𝑘 ∈ 𝐿:
	(a) 𝑙𝑖 → 𝑙𝑖	⨁	𝑙𝑗 and 𝑙𝑗 → 𝑙𝑖	⨁	𝑙𝑗.
	(b) ⨁	𝑙𝑗. This property implies
	the existence of a supremum 𝑆 (or least upper bound) that
	is a 𝑙1	⨁	𝑙2	⨁	...	⨁	𝑙𝑛 of 𝑛 licenses.

Property

[START_REF] Cabrio | These Are Your Rights[END_REF]

is demonstrated by showing that the relation → is reflexive, transitive and antisymmetric.

∀𝑙𝑖, 𝑙𝑗, 𝑙 𝑘 ∈ 𝐿: (a) 𝑙𝑖 → 𝑙𝑖 (reflexive), i.e., a license is compatible with itself. (b) 𝑙𝑖 → 𝑙𝑗 and 𝑙𝑗 → 𝑙 𝑘 ⇒ 𝑙𝑖 → 𝑙 𝑘 (transitive), i.e., if 𝑙𝑖 is compatible with 𝑙𝑗 and 𝑙𝑗 is compatible with 𝑙 𝑘 then 𝑙𝑖 is compatible with 𝑙 𝑘 . (c) 𝑙𝑖 → 𝑙𝑗 and 𝑙𝑗 → 𝑙𝑖 ⇒ 𝑙𝑖 = 𝑙𝑗 (antisymmetric), i.

  where each 𝑙𝑖 is a set of prohibited actions 𝑃 𝑟 𝑙 𝑖 taken from 𝐴 ={read, modify, distribution}. ⨁ is the license combining operator where 𝑙𝑖 ⨁ 𝑙𝑗 ≡ 𝑃 𝑟 𝑙 𝑖 ∪ 𝑃 𝑟 𝑙 𝑗 . → is the compatible with relation stating that 𝑙𝑖 → 𝑙𝑗 iff 𝑃 𝑟 𝑙 𝑖 ⊆ 𝑃 𝑟 𝑙 𝑗 . 𝑅 = {𝑟1, 𝑟2, 𝑟3, 𝑟4, 𝑟5, 𝑟6, 𝑟7} ↦ → is the protected by relation such that 𝑟1, 𝑟2 ↦ → 𝑙0; 𝑟3 ↦ → 𝑙2; 𝑟4 ↦ → 𝑙3; 𝑟5 ↦ → 𝑙4; 𝑟6 ↦ → 𝑙6; 𝑟7 ↦ → 𝑙7. 𝐶 = ⟨𝐶𝐿, 𝐶→⟩ where 𝐶𝐿 = {𝜔𝐿 1 } and 𝐶→ = ∅ (all → relations are viable).

Table 1 :

 1 Some licenses of the first level of the lattice.

	Label	Permissions	Obligations	Prohibitions
		cc:Distribution,
		cc:Reproduction,
	𝑙 1	cc:ShareAlike, cc:DerivativeWorks,	cc:Attribution	∅
		cc:CommercialUse,
		cc:Notice,
		cc:Distribution,
		cc:Reproduction,
	𝑙 2	cc:ShareAlike, cc:DerivativeWorks,	cc:Notice	∅
		cc:CommercialUse,
		cc:Attribution
		cc:Distribution,
		cc:Reproduction,
	𝑙 3	cc:ShareAlike, cc:DerivativeWorks,	∅	cc:CommercialUse
		cc:Notice,
		cc:Attribution
		cc:Distribution,
		cc:Reproduction,
	𝑙 4	cc:ShareAlike, cc:DerivativeWorks,	cc:CommercialUse	∅
		cc:Notice,
		cc:Attribution
	Label	Permissions	Obligations	Prohibitions
		cc:Distribution,
	𝑙 1 (CC BY) ⨁ 𝑙 2	cc:Reproduction, cc:ShareAlike, cc:DerivativeWorks,	cc:Notice, cc:Attribution	∅
		cc:CommercialUse
		cc:Distribution,
	𝑙 1 (CC BY NC) ⨁ 𝑙 2 ⨁ 𝑙 3	cc:Reproduction, cc:ShareAlike,	cc:Notice, cc:Attribution	cc:CommercialUse
		cc:DerivativeWorks

Table 2 :

 2 Some Creative Commons licenses of the lattice.

  lattice, Algorithm 2 uses the combining operator to check if two licenses are compatible. Using CaLi, license 𝑙𝑖 is compatible with 𝑙𝑗 iff 𝑙𝑖 ⨁ 𝑙𝑗 = 𝑙𝑗. We recall that if 𝑙𝑖 is compatible with 𝑙𝑗

				Label			Permissions	Obligations	Prohibitions
										cc:Distribution,
										cc:Reproduction,
					𝑙 3					cc:ShareAlike, cc:DerivativeWorks,	∅	cc:CommercialUse
										cc:Notice,
										cc:Attribution
										cc:Distribution,
		𝑙 1	⨁	𝑙 2	⨁	𝑙 𝑚		cc:ShareAlike, cc:DerivativeWorks,	cc:Notice, cc:Attribution	cc:Reproduction
										cc:CommercialUse
										cc:Distribution,	cc:Notice,
	𝑙 1	⨁	𝑙 2	⨁	𝑙 𝑛	⨁	𝑙 𝑜	cc:ShareAlike,	cc:Attribution,	cc:DerivativeWorks
										cc:CommercialUse	cc:Reproduction
		𝑙 1 ⨁ ⨁ 𝑙 𝑛 𝑙 2 ⨁ ⨁ 𝑙 𝑜 𝑙 3		cc:Distribution, cc:ShareAlike	cc:Notice, cc:Attribution, cc:Reproduction	cc:DerivativeWorks, cc:CommercialUse

Table 3 :

 3 Some non Creative Commons licenses of the lattice.

	Label	Permissions	Obligations	Prohibitions
				cc:Distribution,
				cc:Reproduction,
	𝑙 3	⨁	𝑙 4	cc:ShareAlike, cc:DerivativeWorks,	cc:CommercialUse	cc:CommercialUse
				cc:Notice,
				cc:Attribution

Table 4 :

 4 One non-viable license of the lattice.

Algorithm 1 :

 1 Adds and classifies a new license in the classification. Function addAndClassify(𝑙𝑖, 𝐺): Data: 𝑙𝑖: License, 𝐺: Classification Graph, 𝐼: 𝐶2 and 𝐶3). Algorithm 2 checks if 𝑙𝑖 is compatible with a least restrictive licenses 𝑙𝑐𝑜𝑚𝑝 compliant with 𝑙𝑗. If 𝑙𝑖 is compatible with 𝑙𝑐𝑜𝑚𝑝 and 𝑙𝑖 is compatible with 𝑙𝑗 then 𝑙𝑖 is inserted between 𝑙𝑗 and 𝑙𝑐𝑜𝑚𝑝. If 𝑙𝑖 is only compatible with 𝑙𝑐𝑜𝑚𝑝, 𝑙𝑖 is linked to 𝑙𝑐𝑜𝑚𝑝. Otherwise, Algorithm 2 is called again to find the least restrictive licenses compliant with 𝑙𝑖 in the graph containing licenses compliant with 𝑙𝑐𝑜𝑚𝑝.

		Infimum,
		𝐶𝐿: Constraints on licenses
		Result: Returns 𝐺 with 𝑙𝑖 classified
	2	if viable(𝑙𝑖, 𝐶𝐿) then
		// 𝑙𝑖 respects all 𝐶 𝐿 constraints
	3	Add 𝑙𝑖 to 𝐺
		// Classifies 𝑙𝑖 in licenses compliant with 𝐼
	4	classify(𝑙𝑖, 𝐼, 𝐺)
	5	end
	6	return 𝐺
	7 end
	engine, Algorithm 2: Recursively classifies the new license to
	compliant licenses
	8	end
	9	else if 𝑙𝑖	⨁	𝑙𝑐𝑜𝑚𝑝 ̸ = 𝑙𝑐𝑜𝑚𝑝 then
		// Classifies 𝑙𝑖 in licenses compliant with 𝑙𝑐𝑜𝑚𝑝
	10	classify(𝑙𝑖, 𝑙𝑐𝑜𝑚𝑝, 𝐺)
	11	end
	12 end

1 1 Function classify(𝑙𝑖, 𝑙𝑗, 𝐺): Data: 𝑙𝑖, 𝑙𝑗, 𝑙𝑐𝑜𝑚𝑝: License, 𝐺: Classification Graph, 𝐶→: Constraints on compatibility relations, 𝐿𝑅𝐶 𝑙 𝑗 : Least restrictive licenses compliant with 𝑙𝑗 in 𝐺 2 for 𝑙𝑐𝑜𝑚𝑝 ∈ 𝐿𝑅𝐶 𝑙 𝑗 do 3 if 𝑙𝑖 ⨁ 𝑙𝑐𝑜𝑚𝑝 = 𝑙𝑐𝑜𝑚𝑝 and viable(𝑙𝑖 → 𝑙𝑐𝑜𝑚𝑝, 𝐶→) then // 𝑙𝑖 is compatible with 𝑙𝑐𝑜𝑚𝑝 // 𝑙𝑖 → 𝑙𝑐𝑜𝑚𝑝 respects all 𝐶→ constraints 4 add 𝑙𝑖 → 𝑙𝑐𝑜𝑚𝑝 to 𝐺 5 if 𝑙𝑗 ⨁ 𝑙𝑖 = 𝑙𝑖 and viable(𝑙𝑗 → 𝑙𝑖, 𝐶→) then // 𝑙𝑖 is between 𝑙𝑗 and 𝑙𝑐𝑜𝑚𝑝 6 add 𝑙𝑗 → 𝑙𝑖 to 𝐺 7 delete 𝑙𝑗 → 𝑙𝑐𝑜𝑚𝑝 from 𝐺

https://creativecommons.org/ns

https://ns.inria.fr/l4lod/

https://tldrlegal.com/

https://creativecommons.org/choose/

https://choosealicense.com/

https://ccsearch.creativecommons.org/

http://www.web2rights.com/creativecommons/

http://licentia.inria.fr/

purl.org/NET/rdflicense

This CaLi classification can be generated from https://github.com/ benjimor/CaLi/tree/combinatory_method5 A LICENSE-BASED LINKED DATA SEARCH ENGINEWe experiment the usefulness of a CaLi classification with the implementation of a license-based search engine for the Web of Data.

https://www.w3.org/TR/odrl-vocab/#actionConcepts

https://old.datahub.io/

https://data.opendatasoft.com/pages/home/

A video demonstration is available at https://youtu.be/ YkSWHSiD-Ps.

http://cali.priloo.univ-nantes.fr

http://cali.priloo.univ-nantes.fr/api

licenseID is the hash of permissions, obligations and prohibitions of a license.

http://cali.priloo.univ-nantes.fr/api/licenses/ 3154600001362308832/compatible

http://cali.priloo.univ-nantes.fr/api/licenses/ 3154600001362308832/compliant

http://cali.priloo.univ-nantes.fr/graph

https://github.com/benjimor/CaLi

ACKNOWLEDGMENTS

Authors thank Matthieu Perrin for his helpful comments on this work.

://creativecommons.org/ 2 https://www.w3.org/TR/odrl-model/ 3 https://github.com/


Alexandre M Amory
email: amamory@inf.ufrgs.br

Marcelo Lubaszewski

Fernando G Moraes

Edson I Moreno
email: emoreno@inf.pucrs.br

Test Time Reduction Reusing Multiple Processors in a Network-on-Chip Based Architecture

The increasing complexity and the short life cycles of embedded systems are pushing the current system-onchip designs towards a rapid increasing on the number of programmable processing units, while decreasing the gate count for custom logic. Considering this trend, this work proposes a test planning method capable of reusing available processors as test sources and sinks, and the on-chip network as the test access mechanism. Experimental results are based on ITC'02 benchmarks and on two open core processors compliant with MIPS and SPARC instruction set. The results show that the cooperative use of both the on-chip network and the embedded processors can increase the test parallelism and reduce the test time without additional cost in area and pins.

Introduction

Recently, networks-on-chip (NoCs) emerged as an alternative communication architecture for complex system-on-chip (SoC) [START_REF] Guerrier | A Generic Architecture for on-Chip Packet-Switched Interconnections[END_REF]. In addition, there is a rapid increasing on the number of programmable processing units in current designs. Considering this trend and the complexity for testing such systems, the reuse of both, the processor and the on-chip network for test, seems a promising approach to reduce test costs [START_REF] Amory | Reducing Test Time with Processor Reuse in Network-on-Chip Based Systems[END_REF]. Softwarebased test of IP cores, i.e., the test based on the reuse of an embedded processor, presents several advantages, such as cheaper external test equipment, less test pins and minimal area overhead [START_REF] Huang | A Self-Test Methodology for IP Cores in Bus-Based Programmable SoCs[END_REF] [START_REF] Hwang | Test Data Compression and Test Time Reduction Using an Embedded Microprocessor[END_REF].

The reuse of embedded processors for test is not new, but no previous approach evaluated systems that support multiple processors on a parallel architecture. Huang et al. [START_REF] Huang | A Self-Test Methodology for IP Cores in Bus-Based Programmable SoCs[END_REF] evaluated the reuse of a MIPS processor on a busbased architecture, while Hwang and Abraham [START_REF] Hwang | Test Data Compression and Test Time Reduction Using an Embedded Microprocessor[END_REF] evaluated the reuse of an ARM processor on a Wishbone bus architecture. Amory et al. [START_REF] Amory | Software-Based Test for Non-Programmable Cores in Bus-Based System-on-Chip Architectures[END_REF] developed a CAD tool, which helps the designer to integrate cores on a bus-based SoC and to generate test programs. The results were validated implementing the system in FPGA.

This paper proposes a new software-based test planning approach for NoC-based systems, which reuses the embedded processors and the NoC for testing.

Test Using NOCs

The process of using the NoC to carry the test pat-terns can be divided in three main steps. The first step corresponds to the characterization of the NoC in terms of time and power consumption. The performance metrics of a NoC router can be divided in two parts: the routing latency and the flow control latency. The routing latency is the intra-router time required to create a connection through the router, while the flow control latency is defined as the interrouter time required to send flits in the channels. In addition to the characterization of performance metrics, the designer also has to characterize the power consumption to send the test packets, which is identical to the power consumption of the NoC in functional mode. In our experiments, the power consumption has been measured as the mean power consumption to send packets of random size and random payload. This value is added to each router the packet passes through. Besides performance and power characterization, the designer also has to feed the tool with the topology, the routing algorithm, the number of routers and the flit width. Currently the tool supports NoCs based on grid topology using XY routing algorithm.

The second set of information the designer has to provide the tool with concerns the system. This set of information consists of the position of each core (including the processors reused for test), and the number and position of the IO ports that can be connected to the external tester. The position of the CUTs, processors and IO ports determine the order and priority of the test. The cores closer to IO ports or processors are tested first.

The second step comprises the characterization of the processors reused for test. A processor can be used during test in different ways. It can run a test program that reads the compressed test data from a memory, decompresses it and sends it to the core under test (CUT), or it can work as a test pattern generator emulating a pseudo-random BIST logic. Each of these test applications has to be modeled differently. Currently, we are modeling the BIST application, but in the near future we will also support decompression. In terms of time, the BIST application consumes time to generate the BIST pattern and to send it to the CUT. In terms of power consumption, the BIST application consumes power to generate patterns and to send it to the CUT. The test application has to be characterized in terms of time, memory requirements and power to each processor in the system reused for test. This step is necessary because the processors may have different instruction-sets, times to run the test application and power consumptions. Once this characterization is done, the results can be inserted into the proposed tool. In this work we modeled the Leon and Plasma processors, http://www.gaisler.com/ and http://www.opencores.org/, which are synthesizable VHDL models of processors compliant, respectively, with SPARC V8 and MIPS-I.

In addition to the characterization presented before, it is very important to take into account the test of the processor itself in the overall reuse strategy. Thus, the designer should provide the tool with the number of test patterns necessary to test each processor. A processor is reused for test just after it has been successfully tested. Complex processors require a large number of patterns to be tested, and may be reused for test few times, not contributing to reduce the global test time.

The last step comprises the CUTs characterization. We assume a core-based design methodology where the cores are acquired from the core providers to be integrated into the system chip. The core provider is responsible for the core test knowledge transfer. We assume this information is available with the core description since the proposed tool uses it for the global test planning.

Experimental Results

Experimental results for the proposed reuse approach are presented for three examples based on the benchmarks d695, p22810, and p93791 of the ITC'02 SoC Test Benchmarks set [START_REF] Marinissen | A Set of Benchmarks for Modular Testing of SoCs[END_REF]. To system, cores representing the Leon and Plasma processors are added. For d695 system, six processor cores are added, whereas for p22810 and p93791 benchmarks, eight cores are added. The total number of cores of the new systems is 16, 36, and 40, respectively. The network dimensions for each system are, respectively, 4x4, 5x6 and 5x5.

Figure 1 presents the test time results for systems d695_Leon, p22810_Leon, and p93791_Leon, when different numbers of Leon processors are reused for test and two external interfaces (input and output) are used. Experiments with and without power constraints are presented for each system. This constraint is defined as a percentage of the sum of all cores power consumption. Thus, for example, a power limit of 50% indicates that the power limit corresponds to half of the sum of all cores power consumption in test mode. Notice that in a real case, the designer can define any power limit.

The results presented in Figure 1 demonstrate that increasing the number of processors reused for test reduces the test time compared to the test without processor reuse. One can observe that even smaller systems like d695_leon can take advantage of the extra test interface, with test time reduction of 28%. For larger systems such as p93791_leon, the gain in test time can be as high as 44%. Despite of this, imposing power constraints the test reduction reaches up to 37%, since there is more parallelism and more processors running the test programs.

For the p22810_leon system, we get some test time reduction, but it is not regular because of the greedy behavior of the scheduling algorithm. The greedy behavior of the presented algorithm forces it to select the first test interface available. This can increase the test time because we assume the processor takes 10 clock cycles to generate a test pattern, while the external tester takes zero clock cycles. Thus, if a processor is available in a given instant and an external tester is available a few instants later, the resource used will be the processor, since it was available before. However, the external tester should be used because it is faster than the processor.

Final Remarks

This work evaluates the impact of reusing processors to test a NoC-based system. The processors available in the system are programmed with an application to test cores of the system. The results presented demonstrate that, increasing the number of test sources/sinks to explore the NoC parallelism, reduce the system test time without additional area and test pins.

Figure 1 -

 1 Test times.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE