Mariem Mahfoudh

Germain Forestier

Laurent Thiry

Michel Hassenforder

Algebraic graph transformations

Keywords: Ontology Evolution, Typed Graph Grammars, Algebraic Graph Transformations, Consistency, AGG

published or not. The documents may come

Introduction

Formalizing knowledge has always presented an existential obsession and an important challenge for humans. The proposed solutions in the literature are mainly organized around databases, data warehouses and more recently ontologies. Ontologies are often defined as an explicit specification of a conceptualization of a domain [START_REF] Gruber | A translation approach to portable ontology specifications[END_REF]. They make possible for a community to reach a consensus and to bridge the gap of the vocabulary heterogeneity and semantic ambiguities. Thanks to their advantages, ontologies are used in a large range of fields such as: semantic web [START_REF] Zhang | A chinese time ontology for the semantic web[END_REF], business decision support [START_REF] Zhao | Decision support in e-business based on assessing similarities between ontologies[END_REF], image interpretation [START_REF] Forestier | Coastal image interpretation using background knowledge and semantics[END_REF], peer-to-peer networks [START_REF] Jung | Reusing ontology mappings for query routing in semantic peer-to-peer environment[END_REF], etc. A counterpart of this popularity, is the constant augmentation of available ontologies. For example, the number of ontologies on the BioPortal increased of 67% in 2013 1 . Furthermore, as building an ontology is an iterative process [START_REF] Noy | Ontology development 101: A guide to creating your first ontology[END_REF][START_REF] Thomopoulos | An iterative approach to build relevant ontologyaware data-driven models[END_REF], the creation of a new ontology actually creates a set of several ontologies versions which is also consistently growing. For example, 51 versions of the Gene Ontology (one of the most successfully ontologies) are monthly released since January 2010 2 . Thus, more and more new ontologies are 1 bioportal.bioontology.org/ontologies 2 geneontology.org/ontology-archive created and the number of versions of existing ontologies is constantly increasing.

Generate a new ontology version is however not a trivial task. It presents several challenges and requires a comprehensive study of the ontology model in order to manage its evolution. Ontologies Evolution is defined by Stojanovic et al. as the timely adaptation of an ontology to the arisen changes and the consistent propagation of these changes to dependent artefacts [START_REF] Stojanovic | Methods and tools for ontology evolution[END_REF]. This process consists in the modification of one or many ontology components (class, property, axiom, individual, etc.) and it may be at instances level (Ontology Population) and/or structural level (Ontology Enrichment) [START_REF] Khattak | Ontology evolution and challenges[END_REF]. Moreover, to preserve ontology consistency, the application of ontology changes must preserve all the ontology model constraints [START_REF] Stojanovic | Methods and tools for ontology evolution[END_REF]. However, ontologies are often developed in a collaborative manner and are usually large and expressive. This makes difficult for a user and/or ontologist to understand all their affected parts (i.e. dependent entities) when changes are made. Therefore, to keep ontology consistency, it is important to have a mechanism that controls how the ontology changes are made and avoids the possible inconsistencies generated due to these changes.

The ontology languages such as Ontology Web Language (OWL 3 ) are prevalent in knowledge representation, although, they are not sufficient for formalizing changes. They are indeed effective to capture static semantics but not changes that require a consistency checking of the interaction between ontologies entities. That is why, the proposed approaches in the literature do not addressed the inconsistencies issue [START_REF] Hartung | Conto-diff: generation of complex evolution mappings for life science ontologies[END_REF] or used an a posteriori process to identify inconsistencies [START_REF] Klein | Change management for distributed ontologies[END_REF][START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF][START_REF] Khattak | Change management in evolving web ontologies[END_REF], etc. Thus, unlike previous approaches, this paper focuses on the critical issue of presenting a formal approach for consistent ontologies evolution by using Typed Graph Grammars and Algebraic Graph Transformations. Typed Graph Grammars (T GG) are a mathematical formalism that permits to represent and manage graphs. They are used in several fields of computer science such as software systems modelling, pattern recognition and formal language theory [START_REF] Ehrig | Graph Transformations in Computer Science[END_REF]. Recently, they started to be used in the ontology field, in particular for the modular ontologies formalization [START_REF] D'aquin | Towards a parametric ontology modularization framework based on graph transformation[END_REF], Resource Description Framework graphs representation [START_REF] Braatz | Graph transformations for the resource description framework[END_REF], collaborative ontologies evolution [START_REF] Leenheer | Using graph transformation to sup-port collaborative ontology evolution[END_REF] and consistent ontologies evolution [START_REF] Mahfoudh | Consistent ontologies evolution using graph grammars[END_REF].

In our previous work [START_REF] Mahfoudh | Consistent ontologies evolution using graph grammars[END_REF], we have introduced the formalization of the ontology changes with Typed Graph Grammars and have focused on the atomic changes. A deeper study is presented in this paper which presents an exhaustive list of the atomic ontology changes and describes how consistently formalize the composite and complex changes. A comparison between the ontology changes representation in the OWL and our T GG formalism is presented to highlight the advantages of the use of graph grammars in the ontologies evolution process. Indeed, T GG and algebraic graph transformations provide a new way to formalize ontology changes and offer mechanisms to control graph transformations while avoiding the inconsistencies. Furthermore, they can reduce the number of elementary changes required to apply the composite and complex changes. The proposed approach has been implemented using a graph transformation tool Attributed Graph Grammar (AGG). In addition, we also present a mechanism to log the ontologies versions and ontology changes with a formal representation. An application is presented with the EventCCAlps ontology developed in the frame of the CCAlps European project 4 .

The rest of the paper is organized as follow: Section 2 presents related work and introduces Typed Graph Grammars and algebraic graph transformations. Section 3 proposes a graph transformation model for evolving ontologies and describes the formalization of ontology changes with Typed Graph Grammars. Section 4 presents an application using the EventCCAlps ontology. Section 5 evaluates and discusses the proposed approach. Finally, a conclusion summarizes the presented work and gives some perspectives. 4 ccalps.eu, project reference number: 15-3-1-IT

Background and review

Related work

Managing ontologies evolution has been an important and active field of research in the recent years [START_REF] Khattak | Ontology evolution and challenges[END_REF]. The approach of Stojanovic et al. [START_REF] Stojanovic | Evolution in the ontology-based knowledge management system[END_REF] is considered as one of the first works that have addressed this issue. It presents a methodology in six phases: change capturing, change representation, semantics of change, change implementation, change propagation and change validation. The approach focuses on the KAON ontologies and identifies three types of ontology changes: 1) atomic change is an ontology change that affects a single ontology entity; 2) composite change is an ontology change that modifies the neighbourhood of an ontology entity; 3) complex change is an ontology change that can be decomposed into elementary and composite ontology changes. Later, Klein et al. [START_REF] Klein | Change management for distributed ontologies[END_REF] have proposed another classification. They distinguish two types of ontology changes: elementary (atomic) and composite (complex). These changes can be specified via logging of incremental changes or by ontology versions comparison. The authors have also studied the problem of inconsistencies ontologies and proposed strategies resolution for each ontology changes. However, it is important to note that, the work is focused on the "ontology enrichment" and do not specify specific operations for the instances. Then, Luong et al. [START_REF] Luong | A rule-based approach for semantic annotation evolution[END_REF] have addressed both the "ontology enrichment" and the "ontology population". They have studied the evolution management for a corporate semantic web while addressing the RDF5 (Resource Description Framework) ontologies. This choice restricts the expressivity of the methodology as the others ontology languages (such as OWL) require further types of changes (cardinality changes, restrictions on the classes, etc.). Thus, Djedidi et al. [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF] have proposed an approach of OWL ontologies evolution based on pattern conception. They have studied both the atomic and composite changes and have used the Pellet reasoner [START_REF] Sirin | Pellet: A practical owl-dl reasoner[END_REF] to detect the inconsistencies. A deeper study of the composite changes is introduced by Javed et al. [START_REF] Javed | Ontology change management and identification of change patterns[END_REF]. It has presented resolution strategies for several composite changes and has described a layered change log for the explicit operational representation of ontology changes. The change log is formalized using a graph-based approach and implemented by OWLAPI 6 . To identify ontologies inconsistencies, Gueffaz et al. [START_REF] Gueffaz | Inconsistency identification in dynamic ontologies based on model checking[END_REF] have proposed CLOCk (Change Log Ontology Checker) approach which use model checking. A transformation of the OWL ontologies into a specific language NuSMV7 is needed. However, no strategies are proposed to solve the inconsistencies. Recently, some researches are interested to look for new formalisms to represent ontologies and find others alternatives to the standard ontology languages. Then, Liu et al. [START_REF] Liu | Modeling ontology evolution with setpi[END_REF] have introduced SetPi calculus [START_REF] Milner | Communicating and mobile systems: the pi calculus[END_REF] to model ontologies evolution process. They have represented ontologies by using SetPi entities and have defined a new formalism for describing the ontology changes. The work presents many ontology changes (basic and composite). However, it does not study the inconsistencies problem and do not proposes any implementation.

As a summary, various approaches have been proposed to define and implement ontology evolution process. The Table 1 presents a comparison of some approaches according to the languages used, the implementation, the inconsistency management and the specificities. Thus, we can see that different ontology languages have been studied: KAON [START_REF] Stojanovic | Methods and tools for ontology evolution[END_REF], RDF [START_REF] Luong | A rule-based approach for semantic annotation evolution[END_REF], OWL [START_REF] Klein | Change management for distributed ontologies[END_REF][START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF][START_REF] Javed | Ontology change management and identification of change patterns[END_REF], etc. Based on these languages, several ontology changes were defined and different classification of theses changes were proposed [START_REF] Stojanovic | Methods and tools for ontology evolution[END_REF][START_REF] Klein | Change management for distributed ontologies[END_REF]. Despite its importance, the problem of inconsistencies resolution is not sufficiently studied. Indeed, some works do not address this issue [START_REF] Hartung | Conto-diff: generation of complex evolution mappings for life science ontologies[END_REF][START_REF] Liu | Modeling ontology evolution with setpi[END_REF]. Others approaches are only focused on the inconsistencies identification [START_REF] Gueffaz | Inconsistency identification in dynamic ontologies based on model checking[END_REF]. Some researches are interested, in addition, to resolve the inconsistencies [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF][START_REF] Luong | A rule-based approach for semantic annotation evolution[END_REF][START_REF] Javed | Ontology change management and identification of change patterns[END_REF]. However, they use a posteriori process of inconsistencies resolution which require the implementation of changes and then, use external resources to check if the ontology consistency is affected or not. In our work, we propose an a priori approach to avoid inconsistencies by using Typed Graph Grammars formalism.

Typed Graph Grammars

This section reviews the fundamental notions involved in typed graph grammars and algebraic graph transformations.

Definition 1 (Graph). A graph G(V, E) is a structure composed by a set of vertices V , a set of edges E and an application s : E → V × V that attaches a source/target vertex to each edge.

An attributed graph is a graph extended by a set of attributes name att, a set of possible values val and a mapping valuation v : att → val.

Definition 2 (Graph Morphism). A graph morphism m(f, g) is an application from a graph G(V, E) to a graph G(V , E ) that is defined by two applications f : V → V and g : E → E . A morphism must preserve the structure what means that if e = (s, t) and g(e) = e = (s , t ) then s = f (s) and t = f (t).

Definition 3 (Typing). A typing is a morphism from a graph G(V, E) to a type graph T G(V T , E T ) where V T corresponds to the types of the vertices and E T to the types of edges.

The Figure 1 gives an example of a graph (lower part) and a morphism/typing to a type graph (upper part). Definition 4 (Typed Graph Grammars). A typed graph grammar is a formalism defined by T GG = (G, T G, P ) where:

G is a start graph also called host graph. T G is a type graph and represents the elements type of the graph G.

P is a set of production rules also called graph rewriting rules (or graph transformations) which are defined by a pair of graphs patterns (LHS, RHS) where:

-LHS (Left Hand Side) represents the preconditions of the rewriting rule and describes the structure that has to be found in G.

-RHS (Right Hand Side) represents the postconditions of the rule and must replaces LHS in G.

A rewriting rule can be extended with a set of negative application conditions (N ACs). A N AC is another graph pattern such as: "if there exist a morphism from N AC to the host graph G, then, the rule cannot be applied". In this way, a graph transformation defines how a graph G can be transformed to a new graph G . More precisely, there must exist a morphism that replaces LHS by RHS to obtain G . To apply this replacement, different graph transformations approaches are proposed [START_REF] Rozenberg | Handbook of graph grammars and computing by graph transformation[END_REF]. In this work, we use the algebraic approach [START_REF] Ehrig | Graph-grammars: An algebraic approach[END_REF] based on the pushout concept [START_REF] Barr | Category theory for computing science[END_REF].

Definition 5 (Pushout). The pushout is an operator from the Category Theory [START_REF] Barr | Category theory for computing science[END_REF]. Given three objects (in our case graphs) G 1 , G 2 and G 3 and two morphisms f :

G 1 → G 2 and g : G 1 → G 3 , the pushout of G 2 and G 3 consists of: 1) an object G 4 and two morphisms f : G 2 → G 4 and g : G 3 → G 4 where f • f = g • g; 2) for any morphisms f : G 2 → X and g : G 3 → X such that f • f = g • g , there is a unique morphism k : G 4 → X such that f • k = f and g • k = g .
Algebraic approaches are divided into two categories: the Single PushOut, SPO [START_REF] Löwe | Algebraic approach to single-pushout graph transfor-mation[END_REF] and the Double PushOut, DPO [START_REF] Ehrig | Introduction to the algebraic theory of graph grammars (a survey)[END_REF]. The DP O approach consists of two pushouts and requires an additional condition called the "dangling -Strategies proposed to the ontologist to resolve inconsistencies.

-Global evolution process for KAON ontologies.

-Saving the evolved version and traceability of the evolution process.

-The set of consistency constraints heavily depend on the KAON language. Klein, 2004 [11] OWL OntoView, PROMPTdiff -Identification and resolve of the inconsistencies.

-Change management approach for distributed ontologies.

-Identification of the difference between ontology versions.

-Saving the traceability of the ontology changes. -A deeper study of the complex ontology changes.

-Formalization of the change log using a graphbased approach.

Liu et al., 2014 [24]

OWL ---Proposition of a new formalism to model ontology evolution, the SetPi Calculus.

Table 1: Summary of ontology evolution approaches.

condition". This condition states that the transformation is applicable only if it does not lead to "dangling edges", i.e. an edge without a source or a target node. Indeed, in the SP O approach, one pushout is required and the dangling edges are removed which permits to write a wide variety of transformations not allowed by the DP O approach. Thus, in this work, we only consider the SP O approach. Applying a rewriting rule to an initial graph (G) with the SP O method consists in:

1. Finding a matching of LHS in G, i.e. find a morphism m : LHS → G.

2. Deleting the sub-graph m(LHS) -m(LHS ∩ RHS) from G.

Adding the sub-graph m(RHS) -m(LHS ∩ RHS)

to G to get the final result G .

An example of rewriting rule is presented in Figure 2: all the persons working in the company "Ensisa" are friends.

A graph transformation model for evolving ontologies

In the following, we present our approach for evolving ontologies. We describe the ontology model and the change operations (basic, composite and complex) that may be applied during ontology evolution.

Ontologies as Typed Attributed Graphs

Due to their mathematical foundation and their application conditions, Typed Graph Grammars are suitable to represent changes and control their effects. and appropriate. In this work we focus on the evolution of OWL ontologies and follow the ontology model axioms, heavily influenced by Description Logics [START_REF] Horrocks | Practical reasoning for very expressive description logics[END_REF]. The OWL was chosen because it is the standard proposed by the W3C and the language usually adopted to represent ontologies. Thus, with the typed graph grammar formalism, an ontology is then, a graph G with a typing relation to type graph (T G) where T G represents the OWL ontology meta-model (Figure 3). Therefore, the considered types of vertices are:

V T = {Class(C), P roperty(P ), ObjectP roperty(OP ),-DataP roperty(DP ), Individual(I), DataT ype(D)}.

The edge types correspond to properties used to relate different entities:

E T = {subClassOf, equivalentT o, range, domain, ...}.
For example, subClassOf is a type of edge that is used to link nodes of the type Class. Note that, the restrictions (R) are a special case represented by both nodes (Some-V aluesF rom, RestrictionCardinality, etc.) and edges (hasRestriction, onClass, etc.).

Both the nodes and the edges can contain attributes. For example, among the attributes of the nodes of types C, I and P , we find the attribute name which specifies their locals names and the iri which identifies them. In the figures of this article, the iri has not represented for readability reasons. Proposition 2: With proposition 1, ontology changes can be formalized by an indexed family of rewriting rules:

r i = (N AC i , LHS i , RHS i , DCH i ) where i ∈ {AddClass, RemoveDataP roperty, RenameIndividual, ..}.
In this extended definition, DCH represents the set of Derived CHanges to be applied to correct the inconsistencies may be generated due to the application of the ontology changes. For example, the deletion of a class can provoke the modification of its individuals types (i.e. linking these individuals to other classes such as the superClass or the equivalentClasses) or the deletion of its individuals as well.

Formalization of ontology changes

The application of ontology changes can affect ontology consistency. This section describes thus, our proposition for consistent ontologies evolution using the algebraic graph transformations.

Proposition 3: To preserve consistency, each transformation is refined by a set of negative application conditions (N AC) and derived changes (DCH). Theses conditions and additional changes ensure an a priori approach of inconsistencies resolution, i.e. the obtained ontology does not need an explicit checking as an incorrect ontology version cannot actually be generated.

Inspired by the works of literature [START_REF] Noy | Ontology evolution: Not the same as schema evolution[END_REF][START_REF] Haase | Consistent evolution of owl ontologies[END_REF][START_REF] Qin | Evaluating the validity of data instances against ontology evolution over the semantic web[END_REF], inconsistencies addressed in this work are: Data redundancy that can be generated following an add or rename operation. This type of inconsistency is corrected by the N ACs. Axioms contradiction, the addition of a new axiom should not be accept if it contradicts an axiom already defined in the ontology. Many cases are considered: 1) two classes cannot be disjoint and equivalent at the same time, 2) two classes that share a subsumption relation cannot be disjoints, etc.

Isolated nodes, a node (vertex) V x called isolated if ∀V i ∈ V , ∃E i ∈ E|E i = (V x , V i ).

Atomic changes

The atomic changes include the rename changes, the addition and deletion of some changes. They only affect a single ontology entity although they depend on other ontologies elements. Thus, the Table 2 presents the atomic changes addressed in this work and the ontology concepts which are related. Actually, it is important to note that the N ACs of ontology changes are deduced from these interdependencies. For example, from this table we can see that the AddDataP ropertyAssertion(I, DP, value) change, which adds a DataP ropertyAssertion between an individual I and a dataProperty DP , depends on the Individual, DataP roperty and F unctionalP roperty entities. Indeed, before applying this change, it is necessary to check if the dataProperty DP is a functional property. In this case, if the individual I has already an AssertionDataP roperty with the dataProperty DP , then, the change is not allowed because it will affect the ontology consistency.

In the following, one example for each type of change (rename, addition and deletion) is presented. Others changes are described in the Appendix A. Thus, we define for each change, its N ACs, LHS (pre-condition) and its RHS (post-condition). Of course, this type of change does not have DCH as they affect only a single ontology entity.

Note that some changes do not require any N AC such as RemoveDisjointClasses, RemoveEquivalentObject-P roperties, etc.

Thus, the RenameIndividual(I i , I N ew ) is an ontology change that renames a node of type Individual. The rewriting rule corresponding to this change is defined as follow (Figure 4a):

N AC = {I N ew }. To avoid redundancy, the N AC of this rule should be the graph composed by a node of type Individual with the attribute name is equal to I N ew . This means that such sub-graph should not exist in the ontology graph to apply the change. LHS = {I i }. The LHS represents the pre-condition of a rewriting rule. Thus, in this case, it should be the graph composed by a node of type Individual with the attribute name is equal to I i . This is necessary to specify that the individual to rename should exist in the ontology. RHS = {I N ew }. The RHS specifies the new graph that will replace the LHS graph and will be added to the ontology.

The AddSubClass (C 1 , C 2 ) rewriting rule adds a subClassOf axiom between two classes (Figure 4c) and it is defined by: N ACs : RHS = {C 1 C 2 }, the axiom will be added to the ontology.

1. C 1 C 2 ,
i ∈ C(O)•(C 1 C i )∧(C i C 2 ), if there is a class C i which is the subClassOf the class C 2 and the superClass of C 1 , then, C 1 is already a subClass of C 2 ; 5. ∃(C i , C j ) ∈ C(O)•(C i C 1 )∧(C j C 2 )∧C i ¬C j ,
The RemoveEquivalentObjectP roperties(OP 1 , OP 2 ) rewriting rule removes the equivalentT o axiom between two objectProperties (Figure 4b) and it is defined by: N AC = ∅ LHS = {OP 1 ≡ OP 2 }, the objectProperties and their equivalent relations should exist in the ontology. RHS = {OP 1 , OP 2 }, the axiom will be removed from the ontology.

Composite changes

The composite changes affect an ontology entity and its neighbourhood and require then, additional changes (DCHs) to preserve the ontology consistency. Thus, the Table 3 shows the interdependencies between theses changes organized as a matrix dependencies. The value of a matrix element (i, j) indicates that the application of a change related to row i involved the application of the changes in column j. In the following, some composite changes are presented.

The RemoveCardinalityRestriction(C, OP ) rewriting rule removes a CardinalityRestriction defined on a class C and an objectProperty OP . It is composed of two rules. The first one presents the derived change RemoveAs-sertionObjectP roperty that deletes all the assertions which are defined on OP . The second rule defines the principal rewriting rule that allows the deletion of the restriction.

The RemoveObjectP roperty(OP ) rewriting rule removes an ObjectP roperty(OP ) and all its dependencies from the ontology. The Figure 5 presents the six rules which define the change. Then, the first five rules describe the derived changes (DCH) must be applied to preserve the consistency of the ontology and the last one presents the principal rewriting rule. Thus, the restrictions defined on the property OP should be all deleted. This is achieved by the application of the following rules:

RemoveAllV aluesRestriction(OP ), RemoveSomeV aluesRestriction(OP ), RemoveHasV alueRestriction(OP ) and RemoveCardinalityRestriction(OP ).

Then, it is necessary to delete all the ObjectP ropertyAssertion which reference the objectProperty OP . For the other relations, such as domain, range, etc., they are directly deleted without needing to add specific controls. The deletion is achieved during the application of the transformation as the SP O approach removes all the dangling edges.

Complex changes

The complex ontology changes are sophisticated operations. They are identified by grouping basic and composite changes and affect several ontology entities which are not necessarily adjacent. They are mostly used to aggregate many and different changes into one in order to perform generic tasks. They help the user to adapt his ontology without being lost in the details of each elementary changes. Table 4 presents the set of complex changes addressed in this work and the changes they are compound of.

The P ullU pClass(C, C p ) change moves a class C up in its class hierarchy and attaches it to the parents of its pre-vious parent class C p . Consequently, the class C is not any more a subClass of C p and thus, does not infer its properties. The figure 6 It requires the application of the AddClass(C N ew ), RemoveClass(C 1 ) and RemoveClass(C 2 ) rewriting rules. However, to preserve the consistency ontology, before deleting C 1 and C 2 , all their properties and axioms should be attached to C N ew . Formally: 1) Then, it requires the application of AddClass(C N ew1 ), AddClass(C N ew2 ) and RemoveClass(C) rewriting rules. As the M ergeClasses change, the SplitClass rewriting rule requires, before deleting C, the attachment of all its properties and axioms to the C N ew1 and C N ew2 .

∀C i ∈ C(O) • C i C 1 do the rewriting rule AddSubClass(C i , C N ew ) and ∀C j ∈ C(O) • C 1 C j do AddSubClass(C N ew , C j ), 2) repeat the process with C 2 , 3) ∀C i ∈ C(O) • C i ≡ C 1 do AddEquivalentClasses(C i , C N ew ),

Implementation

EventCCAlps ontology

In this section, we present the EventCCAlps OWL ontology used as a use-case study to describe and validate our research work. The ontology is developed in the frame of the European project CCAlps which aims at helping the collaboration between Creative Companies in Alpine space. It links companies and partners for the organization of events. The Figure 7 presents an extract from the EventCCAlps ontology represented with typed graph attributed formalism. Note that the ontology was converted into AGG graphs using our software OWLToGGX 8 . The 8 http://mariem-mahfoudh.info/ksem2013/ Figure shows then, some entities which describe the organized events. An event can be a "Conference", a "Meeting" or a "BestComp". It starts at one day/time and finishes at another day/time, may be described by "Tag" and can receive "Particular" and "Company" participants.

In the EventCCAlps ontology, the changes are frequent both at the instances level (e.g. add events and partners) and schema structure (e.g. create new entities joining the project, delete entities leaving the project).

Application

Several tools have been proposed to support graph rewriting: AGG [START_REF] Ermel | Handbook of graph grammars and computing by graph transformation[END_REF], Fujaba [START_REF] Nickel | The fujaba environment[END_REF] or Viatra [START_REF] Varró | Generic and meta-transformations for model transformation engineering, 2004-The Unified Modeling Language[END_REF]. To implement our approach, we chose the AGG (Attributed Graph Grammar) tool that is considered as one of the most important tools. and DP O) and provides graphical editors for graphs and rewriting rules. The Figure 8 shows the AGG graphical user interface and presents how to implement ontology changes 9 . Different editors are shown: A) an editor for node and edge types that allows user to specify the elements of the type graph; B) a graphical editor for graphs that creates and shows the host graph and type graph; C) a graphical editor for rewriting rules that permits to define the N ACs, LHS and RHS of each rule. An ex-ample of grammar graph is also presented. It is namely GraphTransformationSystem and it is consisting of: 1) the type graph that presents the ontology meta-model; 2) the host graph that contains the ontology to be evolved; 3) two rewriting rules (AddDataP ropertyAssertion and AddDisjointClasses).

Note that the rewriting rules corresponding to the composite and complex changes are classified by layers to define the sequence of their application. Now, we present real cases study with the CCAlps project. Thus, as mentioned above, the EventCCAlps ontology defines events whose the participants may be "Particular" or "Company". However, due to the part- ners requirements, it was necessary to distinguish between the companies types and thus replace the "Company" entity by the "CCI" and "NotCCI" concepts where CCI (Creative and Cultural Industries) are the companies whose the activities take origin from individual creativity such as performing arts, graphic design, etc. Thus, the rewriting rules corresponding to this change is SplitClass(Company, CCI, N otCCI). The Figure 9 presents the different rules required to apply the change as described in the Section 3.2.3 and shows the ontology result. Therefore, the class "Company" are deleted and all its properties and axioms are attached to the "CCI" and "NotCCI" classes. These new classes have now, a subclass "Partner", a super-class "Participant" and they are connected by the "worksFor" property.

The Figure 10 presents the AddDisjointClasses(M eeting, Event) change that adds a disjunction axiom between the two classes "Meet-ing" and "Event". The rewriting rule is composed by five NACs: 1) NAC 1 avoids redundancy; 2) NAC 2 forbids the application of the rule if the classes "Meeting" and "Event" are equivalent, because classes cannot be disjoint and equivalent at the same time; 3) NAC 3 prohibits the transformation if the class "Event" is a subclass of the class "Meeting". Classes that share subsumption relation cannot be disjoint; 4) NAC 4 forbids the transformation if the class "Meeting" is a subclass of the class "Event"; 5) NAC 5 forbids the application of the rule if the classes have common individuals.

As the classes "Meeting" and "Event" share a subsumption relation (a "Meeting" is a subClassOf "Event") then, the rewriting rule cannot be applied (violation of the NAC 4) and an alert box appears to inform user that the transformation cannot be achieved.

Results and discussion

Formalisms comparison

The two main advantages of our method are: (1) to provide a new way to formalize ontology changes while controlling the graph transformations and avoiding the inconsistencies with an a priori manner; (2) to facilitate the description of composite and complex changes while reducing the number of the rewriting rules required to apply them. In order to highlight these two main features, we present in this section a comparison between the ontology changes representation in the T GG formalism proposed in this paper and the closest related approach: Djedidi et al. [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF] (see Section 2.1).

The Table 5 presents two examples of ontology changes: AddObjectP roperty and P ullDownClass. In [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF], the changes are considered as composite/complex. The first one is composed of three basic changes and the second one of two basic changes. The execution of the ontology changes requires the use of Pellet reasoner which is used as an external resource to identify the inconsistencies that can appear. Therefore, the inconsistencies resolution is achieved by an a posteriori manner. If the ontology consistency is affected, the changes must be canceled to go back to the previous ontology version. In our work, these changes are considered as elementary changes as they are composed by only one rewriting rule. Moreover, to preserve the ontology consistency, the checking of the inconsistencies is achieved by the negative application conditions (N AC) which ensure an a priori approach of inconsistencies resolution. Thus, there is no need of an external resource to check the consistency of the ontology as the entire the evolution process is supported by the TGG formalism.

Complexity

The most expensive step in time and resource of the proposed approach is the recognition of the LHS from the host graph G. This search is an NP-complete problem. More precisely, a search of a sub-graph composed of k elements in a graph compound of n elements has a complexity of O(n k ). However, the cost of calculation remains quite acceptable if the size of the LHS graph is limited [START_REF] Karsai | On the use of graph transformations in the formal specification of computer-based systems[END_REF]. This condition is generally satisfied in ontology changes application. The number of nodes of the LHS graph can be used as a measure of the complexity of the ontology change. As presented in Table 6, the LHS size is quite limited for simple change (0 to 3 nodes). For more complex changes, the DHC size has also to be considered.

The execution time is also dependent of the size of the LHS and the ontology's change type (simple or complex). In the example presented in this paper (see section 4.1), the ontology's graph is composed of 21 nodes. The execution of the AddDisjointClasses(Event, M eeting) change took 10 milliseconds (with a LHS composed of 2 nodes). The execution of the complex ontology change Split-Classes(Company, CCI, N otCCI) took only 700 milliseconds (with a LHS composed of 37 nodes). These execution times are quite acceptable as they offer a real-time feedback when executing changes on small-sized ontologies.

Discussion

Ontology Changes Classification. In our previous work [START_REF] Mahfoudh | Consistent ontologies evolution using graph grammars[END_REF], we distinguished the ontology changes considering the classification proposed by Klein et al. [START_REF] Klein | Change management for distributed ontologies[END_REF]. Indeed, this classification of basic/elementary and composite/complex changes is based on the user's vision and does not take into consideration the system's vision. That is why some changes, such as RemoveClass, are considered as basic changes (user's vision) although at the system level they are rather composite since they call for corrective operations. For example, the RemoveClass change involved others basic changes as RemoveRestriction, RemoveIndividual, etc. Therefore, in this work we have reclassified the ontology changes and make the distinction between basic, composite and complex changes by considering the system's vision.

Logging. Saving and storing the changes for later use is an important task in ontology evolution as this type of information may be useful in the management of the distributed and dependent ontologies. Indeed, by using the AGG tool, we can preserve after each application of ontology change, a log file that stores the type graph, the host graph (i.e. the ontology) and the rewriting rules in a formal and semantic representation (Figure 11). Currently, in our work, all the applied changes as well as the different ontology versions can be recovered. The Figure 12 shows how storing the versions of the same ontology with AGG tool. Thus, at t 0 , we have the first ontology version (O V 0 ). Then, when the ontology changes are requested, another file is generated to store both the ontology and the rewriting rules (O V 0 + R V oT oV 1 ). After applying ontology changes, a new ontology version will be generated including the rewriting rules (O V 1 + R V oT oV 1 ). This makes possible the identification of the difference between two ontologies versions, providing that the changes are defined by our methodology. However, a further study should be carried out to optimize the storing of the various versions and to answer to the following questions: us should we save all the ontology versions? How to identify and choose the most relevant versions?

Conclusion

In this paper, we have proposed Typed Graph Grammar and Algebraic Graph Transformations to formalize and manage ontologies evolution. Several ontology changes (basic, composite and complex) were presented and an a priori approach of inconsistencies resolution was introduced. Thanks to the negative application conditions (N AC) and derived changes (DCH), our method avoids the inconsistencies and preserve the evolved ontology quality. The use of algebraic graph transformations offers several advantages. In particular, it allows to simply and formally define the rewriting rules corresponding to the ontology changes. Moreover, it reduces the number of elementary changes required to apply the composite and complex changes providing thus, a gain in time and resources. The execution time of most of the ontology changes are quite limited (< 1 second). To further evaluate the performance of our approach, we are currently working on evaluating the influence of the size of LHS on larger ontologies.

In the near future, we are planning to develop a plugin for the Protege 10 editor which will present the different ontology changes. Indeed, the internal graph transformation engine of the AGG tool can be used by a Java API and thus, be integrated into other custom applications. Then, we intend to benefit from the formal operations of graph theory and category theory to study, without using Ontology Changes Djedidi et al. [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF] Proposed formalism

AddObjectP roperty(OP, C1, C2)

The change is composed of three basic changes: 1. AddObjectP roperty-(OP ), 2. AddDomain(OP, C1) 3. AddRange(OP, C2).

-The change is formalized by one rewriting rule.

-The rule forbids the data redundancy. 5: Ontology changes formalization according to Djedidi et al. [START_REF] Djedidi | ONTO-EVO a l an ontology evolution approach guided by pattern modeling and quality evaluation[END_REF] and the proposed approach. Table 6: The LHS's size of some ontology changes.

RHS

the logging file, the difference between ontology versions and the automatic detection of the ontology changes. This study may be inspired by both the existent works in the meta-modelling [START_REF] Fondement | Big metamodels are evil[END_REF] and ontologies [START_REF] Hartung | Conto-diff: generation of complex evolution mappings for life science ontologies[END_REF].

Figure 1 :

 1 Figure 1: Example of typing graph.

Proposition 1 :Figure 2 :

 12 Figure 2: An example of rewriting rule with SPO approach.

  This incoherence requires to link the isolated node to the rest of the graph. Depending of the type of node, derived changes are proposed. Orphaned individual is an inconsistency which is generated as a result of removal of classes containing individuals.

Figure 3 :

 3 Figure 3: Type Graph used for the rewriting rules formalization.

  classes which share a subsumption relation cannot have subClasses that are disjoint; LHS = {C 1 , C 2 }, the classes should exist in the ontology.

  Rewriting rule for the AddSubClass change.

Figure 4 :

 4 Figure 4: Rewriting rules of some atomic ontology changes.

  presents the rewriting rules that defined the change. Thus, the RemoveObjectP ropertyAssertion derived change check if the class C has individuals which share an objectP ropertyAssertion on the class C p properties. In this case, all these assertions must be deleted. The RemoveDataP ropertyAssertion remove all the dataP ropertyAssertion defined on the class C individuals and the class C p dataProperties. The M ergeClasses(C 1 , C 2 , C N ew ) change merges two exiting classes C 1 and C 2 into a new class (C N ew ).

  4) repeat the process with C 2 , etc. The SplitClass(C, C N ew1 , C N ew2 ) change splits an exiting class (C) into two new created classes C N ew1 and C N ew2 .

Figure 5 :

 5 Figure 5: Rewriting rule for the RemoveObjectP roperty change.

Figure 6 :

 6 Figure 6: Rewriting rule for the P ullU pClass change.

Figure 7 :

 7 Figure 7: An extract from EventCCAlps ontology represented with the typed attributed graph formalism.

Figure 8 :

 8 Figure 8: AGG graphical user interface.

Figure 9 :

 9 Figure 9: SplitClass(Company, CCI, N otCCI) rewriting rule.

Figure 10 :

 10 Figure 10: AddDisjointClasses(M eeting, Event) rewriting rule.

  C2): move down a class (C1) in its class hierarchy and attach it as a child to its previous sibling class (C2).The change is composed of two basic changes: 1. AddSubClass(C1, C2) 2.RemoveSubClass-(C1, Cp) where Cp is the parent class of C1 and C2.-The change is formalized by one rewriting rule.-The rule forbids the application of the change if the classes C1 and C2 are disjoint as classes that share a subsumption relation cannot be disjoint.

  At least 3 nodes for the principal change. At least 4 nodes for the first DCH. At least 6 nodes for the second DCH.

2 .

 2 ∃Ii ∈ I(O) • (Ii = I2) ∧ ((I1, Ii) ∈ OPi) ∧ ( 1OPi); 3. ∃ nOPi • (∃Ii ∈ I(O)) ∧ {(I1, Ii) ∈ OPi} = n. {I1, I2, OPi} {(I1, I2) ∈ OPi)} -, I2) ∈ OPi)} {I1, I2, OPi} -AddIndividual-(I N ew , Ci) {I N ew } {Ci} {I N ew ∈ Ci} -RemoveRestrictionsTable A.7: Formalization of ontology changes with T GG.

Figure 11 :Figure 12 :

 1112 Figure 11: An extract from the log file of ontology changes.

  Rollback and Rollforward algorithms to revert ontology to the previous or next state respectively based on the logged ontology changes.

	Luong	et	RDF(S)	CoSWEM	-Strategies to detect	-Evolution management for a corporate semantic
	al.,	2007		(Corporate	and resolve the inconsis-	web.
	[20]			Seman-		tency of the semantic an-	-Logging management.
				tic	Web	notations.
				Evolution	-Strategies to resolve
				Manage-	the ontology changes in-
				ment)		consistencies.
	Djedidi	et	OWL DL	Onto-		-Identification inconsis-	-Approach based on the pattern conception.
	al.,	2010		EVO A L	tencies using Pellet rea-	-Evaluation of the evolved ontology quality and
	[12]			prototype	soner.	guiding change resolution.
							-Approach required heavy activities.
	Gueffaz et	OWL DL	Prototype	-Identification incon-	-Approach for evolving ontologies based on
	al.,	2012				sistency using NuSMV	model checking.
	[23]					checker.
	Hartung et	OBO (Open	Conto-diff	-	-Identification of the difference between ontology
	al.,	2013	Biomedical	tool,			versions.
	[10]		Ontologies)	OnEX web-		-Approach based on the result of a semi-
			and RDF	application		automatic match operation computed by COG
							(change operation generating) rules.
	Khattak et	RDFS and	Protégé		-Management incon-	-Approach of change history management for
	al.,	2013	OWL	plug-in		sistencies using KAON	evolving ontologies.
	[13] -Proposition of a Javed et al., API. OWL OnE (On--Strategies to detect
	2013 [22]		tology		and resolve the incon-
				Editing)	sistency	of	ontology
				tool		changes.

Table 2 :

 2 Matrix dependency between basic ontology changes and ontology entities.

		condition to avoid redundancy;
	2. C 2	C 1 , the subsumption relation cannot be
	symmetric;

Table 3 :

 3 Matrix dependency between composite ontology changes.

Table 4 :

 4 It supports the algebraic approaches (SP O Matrix dependency of complex ontology changes.

	PullUpClass	AddClass	RemoveClass	AddSubClass	AddDisjointClasses	AddEquivalentClasses	AddIndividual	AddObjectProperty	RemoveObjectProperty	RemoveObjectPropertyAssertion	RemoveDataPropertyAssertion	AddSubProperty	AddEquivalentProperties	AddDisjointProperties
	MergeClasses
	SplitClass
	SplitObjectProperty
	MergeObjectProperties

w3.org/TR/owl-ref

w3.org/RDF

owlapi.sourceforge.net

nusmv.fbk.eu

All the materials used in this section (ontology in graph (AGG format) along with the code of the presented ontology changes) are available for download here: http://mariemmahfoudh.info/kbs2014/

protege.stanford.edu

Acknowledgment

The authors would like to thank the European project CCAlps which funded this work (project number is 15-3-1-IT).


H Ghazzai
email: hend.ghazzai@msb.tn

R Lahmandi-Ayed
email: rim.lahmandi.ayed@gmail.com

Ecolabels: Is More Information Better?

Keywords: Is More Information Better? Ecolabel, Complete Information, Partial Information, Environmental Quality, Vertical Differentiation. JEL Classification L11, Q58

published or not. The documents may come

Introduction

The ecological quality of a product is a credence attribute difficult or impossible to be identified by a simple consumer. Ecolabels are precisely intended to minimize this information asymmetry between consumers and firms by providing information on the ecological quality of the product. One may think that the more accurate the information provided the better off are consumers, the environment and perhaps even the social welfare. In other terms, we would expect that more information should be desirable, at least from the viewpoint of consumers and the environment. Ecolabels have proliferated over the last forty years and different types have been created. We are interested in two types of ecolabels. Type I ecolabels, such as the "Blue Angel" label, the "EU Ecolabel" and "Nordic Swan" among others, are awarded by a third party authority to products fulfilling some minimal criteria in terms of respect of the environment. As such they deliver partial information on the environmental attributes of a product as they only allow consumers to know whether a product satisfies the label criteria and not to know its exact environmental quality. Type III ecolabels also called Environmental Product Declarations consist of a set of quantified data describing different environmental aspects of a product and are awarded by a third party organization. They give consumers complete information about a product environmental quality (Examples are "Eco-Leaf" and "IBU Environmental Product Declaration").

The objective of this paper is to compare the impact of type I (partial information) and type III (complete information) ecolabels on social welfare, consumers, firms and the environment.

To answer our research question, we consider a vertical differentiation model with two firms each offering a good characterized by its environmental quality. We compare two scenarii. In the first scenario, a labeling authority maximizing the social welfare offers a partial information label (type I) then firms decide whether to adopt the label i.e. firms choose whether to offer an environmental quality that satisfies the labeling criteria and finally compete in prices. In a second scenario, firms choose their environmental qualities among all the possible values and then apply for a complete information label (type III) awarded by an independent labeling authority (assumed to be able to know the exact quality of the product and to inform consumers about it), prior to price competition. We prove that the social welfare is always higher with a partial information label and that the profit of the green firm is always higher with a complete information label. When comparing the equilibrium qualities chosen by firms in both cases, we prove that a partial information label is more stringent than the high quality certified by the complete information label authority for low marginal costs and high environmental sensitivity to quality. Finally, depending on the environmental sensitivity to quality and the marginal cost of quality, the low quality firm profit, the industry profit, the environmental damage and consumers' surplus may be higher or lower with a partial information label. Interestingly, consumers' preferences and industry preferences may change twice as the marginal cost of quality increases. Some interesting agents' behavior also appear. We show that the industry and the consumers may have divergent preferences for the label's type. For high enough marginal costs, even though firms, contrary to consumers, do not have any intrinsic preferences for the environmental quality, they can cooperate (through appropriate transfers between them) and campaign for the label's type the more friendly to the environment going against consumers' interests.

The Literature Review: The theoretical literature on ecolabels has mainly focused on type I ecolabels by studying different issues: (1) Firms' incentives to adopt environmentally friendly products [START_REF] Amacher | Environmental quality competition and eco-labeling[END_REF]Ben Youssef & Lahmandi-Ayed, 2008;[START_REF] Andre | Strategic quality competition and the Porter Hypothesis[END_REF] (2) Effects of ecolabels on international trade [START_REF] Nimon | Ecolabels and International Trade in the Textile and Apparel Market[END_REF][START_REF] Greaker | Eco-labels, Trade and Protectionism[END_REF] (3) Implication of imperfect monitoring of ecolabels [START_REF] Ibanez | Can eco-labeling schemes preserve the environment? Environmental and resource economics[END_REF][START_REF] Ibanez | Can eco-labeling schemes preserve the environment? Environmental and resource economics[END_REF][START_REF] Hamilton | Green markets, eco-certification, and equilibrium fraud[END_REF][START_REF] Hamilton | Green markets, eco-certification, and equilibrium fraud[END_REF] (4) Perverse and undesirable effects of ecolabels [START_REF] Mattoo | Eco-labeling: Policy consoderations[END_REF][START_REF] Mattoo | Eco-labeling: Policy consoderations[END_REF][START_REF] Dosi | Is ecolabeling a reliable environmental policy measure?[END_REF][START_REF] Dosi | Is ecolabeling a reliable environmental policy measure?[END_REF](5) Competition between ecolabels [START_REF] Harbaugh | Label confusion: The Groucho effect of uncertain standards[END_REF]Ben Youssef & Abderrazak, 2009;[START_REF] Fischer | Competing environmental labels[END_REF]. The first scenario of this paper corresponds to the game studied in Ben Youssef & [START_REF] Benyoussef | Eco-labeling, competition and environment: Endogenization of labeling criteria[END_REF]. They use a vertical differentiation model with a central authority and two identical firms. A central authority chooses first the level of labeling criteria so as to maximize the social surplus, then firms compete in environmental qualities and prices. We compare the results of their paper to the case where the central authority certifies the exact quality of a firm i.e. the central authority issues a type III ecolabel. Little attention has been given to the market implications of type III labels and to the comparison of different labels' types. To our knowledge, only two papers compare labels' types: Fisher & Lyon (2016) and [START_REF] Li | Green, greener, greenest: Eco-label degradation and competition[END_REF]. They both compare multi-level labels which establish graded levels of certification and type I labels. More precisely, they compare a twolevel ecolabel and a type I ecolabel (which may be considered as a multi-level ecolabel with only one level). In this paper, we compare a type I label and a type III one which consists in giving firms the possibility to choose from a continuous segment and not from a discrete set as in a multi-level ecolabel. Besides, they both consider price-taking firms while we consider strategic firms choosing their prices and having market power. Fisher & Lyon (2016) and [START_REF] Li | Green, greener, greenest: Eco-label degradation and competition[END_REF] use different models. The former consider a finite number of firms divided into two types based on their unit-costs of reducing the environmental damage of their product and a continuum of consumers characterized by their intensity of preference for the label's stringency (defined as the minimum effort of a firm to reduce its environmental damage). The latter consider a finite number of firms differing by their unit-costs and a finite number of consumers differing by their preference for the environmental quality of a good. Both papers consider labeling authorities managed by different sponsors (NGO, Industry, Government...). For each type of schemes, the labeling authority choice between a single level (Type I) and a multi-level label depends on the model's parameters. [START_REF] Leire | Product-Related Environmental Information to Guide Consumer Purchases-A Review and Analysis of Research and Perceptions, Understanding and Use among Nordic Consumers[END_REF] and Van Amstel et Al ( 2008) study the type of information provided by ecolabels and examine the role of ecolabels in reducing the information gap between consumers and producers. They mainly focus on consumers' perception and use of ecolabels and not on the market implication of different types of labels as we do in our paper.

The remainder of the paper is organized as follows. Section 2 describes the model and presents some preliminary results. Section 3 provides the results. We conclude in Section 4. All proofs are provided in Appendix.

The Model and Preliminary Results

We consider a model of vertical differentiation with two firms (i = 1, 2) each producing a good of environmental quality q i . We assume that consumers are aware of the need to preserve the environment for current and future generations. This consciousness is tackled through their preference for the most environment friendly product if they have the choice between several environmental qualities offered at the same price. Consumers are characterized by their intensity of preference for the environmental quality, denoted by θ, and are uniformly distributed over the interval [θ, θ], with 0 < θ < θ. We assume that each consumer buys exactly one unit of the product from the firm which ensures to him/her the highest utility. As in [START_REF] Mussa | Monopoly and product quality[END_REF], the indirect utility of a consumer θ buying quality q i at price p i , is given by:

u i (θ) = θq i -p i .
The highest price consumers are willing to pay for the product (denoted by y) is supposed to be sufficiently high so as it is never constraining.

Production of some quality q is characterized by a constant marginal cost c(q) = αq with α ≥ 0. The marginal cost c(q) is then assumed to be an increasing function with respect to q as environment friendly processes are supposed to be more costly.

Before the set-up of an ecolabel, firms produce quality q. In fact, they have no incentive to produce a quality better than q as it is more costly and not recognized by consumers. As the environmental quality is not observable by consumers, the set-up of an ecolabel aims at providing consumers with information about the environmental quality of a product. We consider two types of ecolabels:

1. Partial information ecolabels (type I) indicate that the environmental quality of the good exceeds some given threshold q, called in the following "labeling criteria". Hence, as far as consumers are concerned, a labeled firm has a priori a quality q i ≥ q and a non-labeled one has a quality q i < q. The preceding assumptions about consumers' beliefs imply that Firm i will choose its quality q i from the pair {q, q}. Indeed as consumers are not able to make the difference between q and a quality q satisfying q ≤ q < q and between q and a better quality, producers set the product in "some category" (labeled or not labeled) at the least cost.

2. Complete information ecolabels (type III) indicate the exact environmental quality of the good and therefore give complete information to consumers about the environmental quality of a firm's product. In this framework, Firm i chooses its quality q i from all the quality segment [q, q], then the labeling authority certifies the exact environmental quality of the product giving consumers complete information about the exact quality of the product.

Moving to a quality q greater than q means that a firm is becoming greener. This involves a fixed cost I increasing with respect to the difference between the initial and the new quality assumed to be given by:

I(∆q) = β(∆q) 2 ,
with β > 0 and ∆q = qq.

We assume that each unit consumed involves a damage d. The unit damage is supposed to be decreasing with environmental quality at a constant rate µ > 0. Formally, we assume that:

d = γ -µq, with γ > 0.
Parameter µ reflects the environmental sensitivity to quality. The higher µ, the higher the impact of the environmental quality on the environment. Parameter γ refers to the maximal environmental damage occurring in the case of a null quality.

We consider two games corresponding respectively to the two types of labels: the partial information label and the complete information one.

1. The labeling authority chooses the level of labeling criteria q so as to maximize the social welfare.

2. Firms simultaneously choose their qualities in the pair {q, q}.

3. The labeling authority attributes the ecolabel to the deserving firms (i.e. when q ≥ q). 4. Firms simultaneously choose their prices in [0, y].

The social welfare to be maximized in the first step is equal to the sum of consumers' and producers' surpluses minus the environmental damage caused by the consumption of goods.

Complete Information Label

The game is organized as follows:

1. Firms simultaneously choose their qualities q i in the segment [q, q].

2. The labeling authority indicates the exact environmental quality of each firm.

Firms simultaneously choose their prices in [0, y].

Multiple equilibria may exist at the quality stage of the partial information label game. When needed we adopt the following selection assumption:

(SA): If multiple equilibria exist at the quality stage of the game, we choose the equilibrium where firms produce the highest qualities.

The selection assumption (SA) ensures that the resulting environmental damage is the lowest possible. Indeed, for some values of the labeling criteria, a firm has the same profit with the labeled product and the non-labeled one. With assumption (SA), it chooses to produce the labeled one. This is the way firms are supposed to have an ecological consciousness. In other words, firms are environment friendly when producing a higher quality does not decrease their profits.

We now enounce a first result about the price equilibrium under a partial or complete information label.

Result 1. Denote by q 1 and q 2 the qualities sold respectively by Firms 1 and 2 and suppose without loss of generality that q 1 ≤ q 2 , at price equilibrium:

• If q 1 = q 2 = q. Firms share equitably the market and set prices p 1 = p 2 = αq.

• If q 1 < q 2 then, 1. High Maginal Costs: if α ≥ 2θ -θ, only Firm 1 is active and prices and demands are given by:

       p 1 = αq 2 -θ(q 2 -q 1 ), p 2 = αq 2 . and        D 1 = θ -θ, D 2 = 0.
2. Low Maginal Costs: if α ≤ 2θ -θ, only Firm 2 is active and prices and demands are given by:

       p 1 = αq 1 , p 2 = αq 1 + θ(q 2 -q 1 )
. and

       D 1 = 0, D 2 = θ -θ.
3. Intermediate Maginal Costs: if 2θ -θ < α < 2θ -θ, both firms are active and prices and demands are given by:

       p 1 = 1 3 [(θ -2θ)(q 2 -q 1 ) + αq 2 + 2αq 1 ], p 2 = 1 3 [(2θ -θ)(q 2 -q 1 ) + 2αq 2 + αq 1 ]. and        D 1 = θ-2θ+α 3 , D 2 = 2θ-θ-α 3
.

The consumer indifferent between q 1 and q 2 is characterized by θ = θ+θ+α 3 . The proof of Result 1 can be found in Ben Youssef and [START_REF] Benyoussef | Eco-labeling, competition and environment: Endogenization of labeling criteria[END_REF]. Result 1 leads to some properties on the demands and firms' margins when the marginal cost is intermediate given by Lemma 1.

Lemma 1 (Demands and firms' margins in the intermediate marginal costs case). In the intermediate marginal costs case, at equilibrium, 1. The demands of both firms do not depend on qualities.

2. The high quality firm demand is decreasing with α and the low quality firm demand is increasing with α.

3. The margin of the high quality firm is decreasing with α and the margin of the low quality firm is increasing with α.

4. The margin of both firms is increasing with respect to the difference between firms' qualities.

Lemma 1 follows immediately from Result 1. The variation of the demands with α may be explained as follows: the marginal cost, being given by c(q) = αq, increases more quickly for the high quality firm than for the low quality one, which makes both prices increase but more the high quality product's one and thus makes the high quality firm loose some of its market share to the benefit of the low quality one. As for the variation of the firms' margins with α, as α increases, the cost differentiation between firms increases as well. The increase in the high quality firm's costs can be only partially compensated by a price increase, which reduces the margin of the high quality firm. Indeed, the temptation of the high quality firm to increase its price is restricted by the competition with it competitor. The low quality firm, however, can afford increasing its market share as the increase in its costs is less important than its rival. Finally, the variation of firms' margins with respect to the difference between firms' qualities is due to the relaxed competition between firms when products are more differentiated.

We finally enounce a second result about the firms' qualities under both types of labels when the marginal cost of quality is high. The proof of Result 2 is given in Appendix.

Result 2 (High Marginal Costs). If α ≥ 2θ -θ then both firms keep producing q whatever the label's type.

When the marginal cost α is too high, whether under a partial information label or a complete information one, firms completely ignore it and keep producing q, as moving to any higher quality is too costly. The case of high marginal costs is thus obvious as no change occurs under both types of ecolabels. We assume in the rest of the paper that α < 2θ -θ.

3 Is More Information Better?

We aim in this section to compare the two types of ecolabels; partial information and complete information labels, from the viewpoint of each type of agent, the environment and the planner. We first present the results of the partial information label game then those of the complete information label one. Then, we compare the effects of both labels on global welfare, qualities, environmental damage, firms' profits, industry profit and consumers' surplus.

The partial information label game was completely solved by [START_REF] Benyoussef | Eco-labeling, competition and environment: Endogenization of labeling criteria[END_REF]. The equilibrium labeling criteria with a partial information label as well as the qualities produced by firms are recalled (but formatted differently) in Lemma 2. The equilibrium qualities chosen by firms with a complete information label are provided in Lemma 3. Propositions 1 to 5 give the results of the comparison. Denote by:

δ L = (θ-θ)(θ-α) β , δ * L = (θ-θ)(θ+θ-2α+2µ) 4β
,

δ I = (2θ-θ-α) 2 9β
,

δ * I = (2θ-θ-α)(4θ+θ-5α+6µ) 36β
. The subscript "L" refers to the case where the marginal cost is low (α ≤ 2θ -θ), while "I" refers to the case where the marginal cost is intermediate (2θ -θ < α < 2θ -θ). δ L and δ I are defined to be the maximal ∆q allowing the adoption of the partial information label by one firm, i.e. allowing a nonnegative profit for the labeled firm, respectively in the low and intermediate marginal costs cases. δ * L and δ * I correspond to the differential of quality ∆q that maximizes the social welfare with a positive green demand without constraint i.e. when δ L and δ I are not binding, respectively in the low and intermediate marginal costs cases.

Lemma 2 (Partial Information Label). In the partial information label case, assuming without loss of generality that q 1 ≤ q 2 , depending on the marginal cost α, two cases are distinguished:

1. Low marginal costs (α ≤ 2θ -θ): at equilibrium one firm is labeled and the other firm is non-labeled but only the labeled firm is active. Depending on the environmental sensitivity rate µ, the optimal labeling criteria and the equilibrium qualities are given as follows:

• if µ ≤ 3θ-θ
2 -α then q * = δ * L + q; q 1 = q and q 2 = δ * L + q.

• if µ > 3θ-θ 2 -α then q * = δ L + q; q 1 = q and q 2 = δ L + q.

2. Intermediate marginal costs (2θ -θ < α < 2θ -θ): at equilibrium both firms are active.

Depending on the environmental sensitivity rate µ, the optimal labeling criteria and the equilibrium qualities are given as follows:

• if µ ≤ 5α-4θ-θ 6

then q * = q, which amounts to no label and q 1 = q 2 = q.

• if

5α-4θ-θ 6 < µ ≤ 4θ-5θ+α 6
then q * = δ * I + q; q 1 = q and q 2 = δ * I + q.

• if µ > 4θ-5θ+α 6

then q * = δ I + q; q 1 = q and q 2 = δ I + q.

When the marginal cost is intermediate and the environmental sensitivity to quality is too low (2θ -θ < α < 2θ -θ and µ ≤ 5α-4θ-θ 6

), the labeling authority chooses the labeling criteria q = q which amounts to the same as the absence of the label. Both firms produce q and no environmental improvement is observed. This is because the impact of the environmental quality is too small, while it costs too much. It is worth noting that the inequality µ ≤ 5α-4θ-θ 6 is never satisfied when α < 4θ+θ 5 , as we easily check that 2θ -θ < 4θ+θ 5 < 2θ -θ. Thus, when 2θ -θ < α < 4θ+θ 5 , this sub-case is not relevant. In all other cases, one firm which will be referred to as the brown firm keeps producing q, and the label is adopted by the other firm which will be referred to as the green firm. The choice of the stringency of the label depends on the marginal cost of quality and the environmental sensitivity to quality. Result 4 in the appendix gives the expressions of the social welfare, firms' profits, environmental damage, consumers' surplus and industry profits at equilibrium with a partial information label. We now move to the results of the complete information label case.

Lemma 3 (Complete Information Label). In the complete information label case, assuming without loss of generality that q 1 ≤ q 2 , depending on the marginal cost α, the equilibirum qualities are given as follows:

1. Low marginal costs (α ≤ 2θ -θ): q * 1 = q and q * 2 = δ L 2 + q. Only firm 2 is active.

2. Intermediate marginal costs (2θ -θ < α < 2θ -θ): q * 1 = q and q * 2 = δ I 2 + q. Both firms are active.

With a complete information label firms choose their qualities which are then certified by the labeling authority giving consumers the exact information on the firms' quality. One firm keeps producing q and remains brown. The other firm offers a higher quality than q and becomes greener. The choice of the green quality depends on the marginal cost of quality. The existence of a complete information label has thus an impact on the economic agents and on the environment. Result 5 in Appendix gives the expressions of the social welfare, firms' profits, environmental damage, consumers' surplus and industry profits at equilibrium with a complete information label.

Denote by α

= -4θ + 5θ -3 √ 3(θ -θ) and by α = 5θ -4θ + 3 √ 2(θ -θ). We easily check that 2θ -θ < α < θ < α < 2θ -θ.
Table 1 provides the different zones of interest for in Propositions 1 to 5. These zones are depicted in Figure 1 in the (α, µ)-space.

Zones

α µ 1 α ≤ 2θ -θ Any µ > 0 2 2θ -θ < α ≤ α Any µ > 0 3 α < α ≤ α µ > 2 3 (α+θ-2θ) 2 2θ-θ-α + α-θ 2 4 α < α ≤ α α-θ 2 < µ < 2 3 (α+θ-2θ) 2 2θ-θ-α + α-θ 2 α < α < 2θ -θ µ > α-θ 2 5 θ < α < 2θ -θ µ < α-θ 2 Table 1 -Zones 1 2 3 4 5 Figure 1
-Zones in the (α, µ)-space of interest for Propositions 1 to 5.

We now give the results of the labels' comparison through Propositions 1 to 5.

Proposition 1 (The social welfare and the green firm profit). For all values of (α, µ), such that α < 2θ -θ and µ ≥ 0, the social welfare is higher and the profit of the green firm lower with a partial information label than with a complete information one.

A partial information label always leads to a higher social welfare compared to a complete information label. With a partial information label, the labeling authority chooses the labeling criteria q so as to maximize the social welfare anticipating the fact that one firm is green and one firm remains brown. With a complete information label, only one firm is green as well but the determination of the green quality corresponds to a decentralized choice by firms at the subgame perfect equilibrium. It does not result from a maximization of social welfare, the role of the labeling authority being limited to observe the qualities and inform consumers on their exact values.

A complete information label gives more power to firms and more precisely to the green firm which always prefers this type of label. Indeed, with a complete information label, firms choose their qualities from all the segment [q, q]. To ensure maximal differentiation the brown firm chooses the lowest quality q. Hence, the green quality corresponds to the best response of the green firm to q i.e. the one that maximizes its profit given its rival's quality. Whereas with a partial information label, the choice of the green firm reduces to only one possibility: the label quality chosen by the authority so as to maximize the social welfare taking into account the interests of all parties and not only the green firm's one.

Proposition 2 (The green qualities). The green quality is more stringent under a partial information label than under a complete information label in zones 1 to 4 of Figure 1 (i.e. when µ > α-θ 2 ) and less stringent in zone 5 (i.e. when µ < α-θ 2 ). The labeling criteria chosen by the authority issuing a partial information label may be more or less stringent than the green quality certified by the authority issuing a complete information label. Higher labeled quality is beneficial to the environment and to the brown firm which is better off with more differentiation allowing it higher prices and higher profits. But higher labeled quality hurts the consumers of the brown quality because of higher prices induced by more differentiation; and is not always beneficial to the green firm which has to bear higher investment costs. The partial information labeling authority has to take into consideration all these diverging interests. When µ is sufficiently high relative to the marginal cost parameter, the environmental damage has an important weight in the social welfare and the production cost is not too high for the green firm, which urges the labeling authority to choose more stringent labeling criteria relative to a decentralized choice by firms (complete information). When µ is sufficiently low relative to the marginal cost parameter, the opposite occurs: the green quality in the complete information label case is greener than in the partial information label one. This is so even if with type III ecolabels (complete information) there is no authority to set labeling criteria. It occurs when the weight of the environmental damage in the social welfare maximized by a type I labeling authority is too low compared to the weight of other agents that are better off with less stringent labeling criteria, namely the green firm and the consumers of the brown quality.

Proposition 3 (The environmental damage and the brown firm profit). Using the zones defined in Table 1 and depicted in Figure 1, we have the following:

• In zone 1, the profit of the brown firm is null whether with a partial or a complete information label and the environmental damage is lower with a partial information label.

• In zones 2, 3 and 4, the profit of the brown firm is higher; and the environmental damage is lower with a partial information label than with complete information label.

• In zone 5, the profit of the brown firm is lower and the environmental damage is higher with a partial information label than with complete information label.

In Zone 1, when the marginal cost is low, there is no room for a brown firm. The green firm, under both types of labels, takes all the market. The brown firm is thus indifferent between the two types of labels. In the rest of the zones, as we explained above, the brown firm benefits from a higher green quality. The comparison for the brown firm's profit follows from the comparison of the green qualities.

The same reasoning applies for the environmental damage as the higher the green quality the lower the environmental damage (demands for both qualities being constant with respect to qualities as explained in Lemma 1). As the green quality is higher under a partial information label in zones 1 to 4 than under a complete information label, then the environmental damage is lower in these zones. The opposite occurs in zone 5.

Proposition 4 (Comparison of Consumers' surplus). Using the zones defined in Table 1 and depicted in Figure 1, we have the following:

• In zones 1, 2 and 5, consumers' surplus is higher with a partial information label than with a complete information one.

• In zones 3 and 4, consumers' surplus is lower with a partial information label than with a complete information one.

Consumers' population is composed of consumers of the brown product and consumers of the green one. Buying a green quality procures consumers a higher gross utility but at a higher price. The positive quality effect outweighs the negative price effect for small enough α as the price of the green quality remains sufficiently low. This is confirmed by the expression of the surplus of green consumers when both firms are active (i.e. for intermediate α) given by:

CS (q) = θ θ (θq - 1 3 (αq + 2αq + (2θ -θ)∆q))dθ = (2θ -θ -α) 2 9 q + (2θ -θ -α)(θ -α) 6 q,
with θ = θ+θ+α 3 . The surplus of green consumers is thus linearly related to the green quality q and is positively related to q if α < θ. Green consumers are thus positively affected by the green quality for small α and negatively affected by the green quality for high α. Brown consumers are always better off with a lower green quality. Indeed, a high green quality corresponds to higher differentiation allowing higher prices. Thus, brown consumers are always negatively affected by the green quality. Hence, brown consumers' preferences and green consumers' preferences diverge for small α and converge for high α. When α is low (α ≤ 2θ -θ), the brown product has no market share. Beyond this threshold, as α increases the brown demand increases and the green demand decreases as explained in Lemma 1. Consumers' preferences are determined by the green consumers for low values of α (zones 1 and 2) and by brown consumers for high values of α (zones 3, 4 and 5), following the relative weight of each type of consumers in the whole population. In zones 1 and 2, partial information labeling which leads to a higher green quality (Proposition 2) is preferred by green consumers, thus by the whole population. Both brown and green consumers prefer the lowest green quality in zones 3, 4 and 5, thus complete information in zones 3 and 4 and partial information in zone 5. Interestingly, the preference of consumers may change twice as α varies. The set of parameters in which partial information is preferred is not a connected set. Mathematically, this occurs because the function corresponding to the difference between consumers' surplus under the two types of labels is a piece-wise defined 4 th degree polynomial function (see Appendix).

Proposition 5. Using the zones defined in Table 1 and depicted in Figure 1, we have the following:

• In zones 1,2, 3 and 5, the industry profit is lower with a partial information label than with a complete information one.

• In zone 4, the industry profit is higher with a partial information label than with a complete information one.

The industry profit is the sum of the brown firm and the green firm profits. The comparison for the industry between both types of labels is determined by the relative weight of demands of both types of product, the profit margin of each firm and the difference between the green qualities with a partial information label and a complete information one. When the marginal cost is low the profit of the green firm has more weight as this firm has a higher demand and a more important margin. As previously proved, the green firm is better off with a complete information label (Proposition 1). Hence, the industry profit is higher with a complete information label in zones 1, 2, and 3. When the marginal cost keeps increasing, the market share of the brown firm becomes more important as well as its margin and the industry profit is more affected by the brown firm profit and therefore the brown firm preferences. The brown firm prefers more differentiation between firms' products allowing it to set higher prices. Thus, it prefers a higher green quality. Consequently, the industry profit is higher with a partial information label in zone 4 as the the partial information label is more stringent than the green quality of a complete information label and the industry profit is lower with a partial information label in zone 5. As observed with consumers' preferences, mathematically, the function corresponding to the difference of industry profits under the two types of labels is a piece-wise defined 4 th degree polynomial function (see Appendix). Interestingly, the industry, as a whole, may prefer a centralized choice of ecolabels (partial information label) to a decentralized one (complete information label). If we observe the interests of the industry as a whole, the consumers and the environment, there is never convergence between the three. They never agree on a type of ecolabels. Now, more precisely, in zone 4, the two firms together make more profit under a partial information label and it is possible for the brown firm to convince the green firm through an appropriate compensation to "campaign" for the set-up of a partial information label, which is also more friendly for the environment (Proposition 3) but goes against the interest of consumers (Proposition 4). In zone 5, the two firms together make more profit under complete information label. In this case, it is possible for the green firm to convince the brown firm, through an appropriate transfer, to campaign for the set-up of a complete information label more friendly to the environment but going against the consumers' interests.

To sum up, in zones 4 and 5, if firms agree on appropriate transfers, the industry may seem more friendly to the environment than consumers, while firms do not have an intrinsic preference for green products, contrary to consumers.

Conclusion

We compared in this paper the effects of a partial information label and a complete information one on the social welfare, the economic agents and the environment. While a partial information label always improves the social welfare and deteriorates the green firm profit compared to a complete information label, there is no clear advantage of one type of label over the other for the environment, the brown firm, the industry and consumers. We showed that the preferences of environmentalists and the brown firm depend on how stringent are the labeling criteria of a type I authority compared to the green quality of a complete information label. We also proved that consumers and industry preferences are complex as they may change twice as the marginal cost of quality increases. One of the main limitations of this paper is the assumption that the market is fully covered. Relaxing this assumption will lead to demands that depend on firms' qualities. However, the maximization of the social welfare is not obvious in this case and the equilibria of the partial information case can only be found numerically. This may be done in a future work. Another way to extend our work is to consider a different composition of the participants in the type I labeling process. Indeed, in our paper, we consider a labeling authority that gives equal weights to firms, consumers and the environment. We may study the situation where the participants in the standardization process of the labeling authority do not have equal powers. The objective function of the labeling authority will thus depend on the weight of each category of participants.

Proof of Result 3

We distinguish three cases:

1. When α ≤ 2θ -θ, as proven in Result 1, only the green firm is active. The expressions of firms' profits, industry profit, environmental damage, consumers' surplus and the social welfare, for a given q produced by the green firm, are as follows:

Π 2 = (θ -α)(θ -θ)∆q -β∆q 2 = β(δ L -∆q)∆q, Π 1 = 0, Π = Π 1 + Π 2 = β(δ L -∆q)∆q, D = (γ -µq)(θ -θ) = D -µ∆q(θ -θ), CS = θ θ (θq -αq -θ∆q)dθ = (θ -θ) 2 2 q -(α -θ)(θ -θ)q = CS + (θ -θ) 2 2 ∆q, S W = CS + Π 1 + Π 2 -(γ -µq)(θ -θ) = (θ -θ)[( θ + θ 2 -α -µ)q -γ] -β∆q 2 , = S W + β∆q(2δ * L -∆q).
2. When 2θ-θ < α < 2θ-θ and one firm is green i.e. q > q, the expressions of firms' profits, industry profit, environmental damage, consumers' surplus and the social welfare for a given q are as follows: Result 4. In the partial information label case, depending on the marginal cost α and the environmental sensitivity to quality µ, at the SPNE, the firms' profits, the industry profit, the environmental damage, consumers' surplus and the social welfare are given in Table 3 for low α and Table 4 for intermediate α.

Π 2 = 1 9 (2θ -θ -α) 2 ∆q -β∆q 2 = β(δ I -∆q)∆q, Π 1 = 1 9 (α + θ -2θ) 2 ∆q = βδ I ∆q, Π = Π 1 + Π 2 = β(δ I + δ I -∆q)∆q, D = (γ -µ q) 2θ -θ -α 3 + (γ -µq) α + θ -2θ 3 = D -µ∆q 2θ -θ -α 3 , CS = θ θ (θq - 1 3 (2αq + αq + (θ -2θ)∆q))dθ + θ θ (θq - 1 3 (αq + 2αq + (2θ -θ)∆q))dθ, = CS + ∆q( (θ -α)(2θ -θ -α) 6 - (θ -2θ + α) 2 9 ), S W = CS + Π 1 + Π 2 -(γ -µq)( 2θ -θ -α 3 ) -(γ -µq) α + θ -2θ 3 , = S W + β∆q(2δ * I -∆q).
α ≤ 2θ -θ and µ ≤ 3θ-θ 2 -α α ≤ 2θ -θ and µ > 3θ-θ 2 -α Π 1 = 0 Π 1 = 0 Π 2 = βδ * L (δ L -δ * L ) Π 2 = 0 Π = βδ * L (δ L -δ * L ) Π = 0 D = D -µδ * L (θ -θ) D = D -µδ L (θ -θ) CS = CS + (θ-θ) 2 2 δ * L CS = CS + (θ-θ) 2 2 δ L S W = S W + βδ * 2 L S W = S W + βδ L (2δ * L -δ L )
Table 3 -The SPNE outcome for low α with a partial information label. Table 4 -The SPNE outcome for intermediate α with a partial information label.

Proof of Result 4

We substitute ∆q in the general expressions given in Table 2 by the values provided in Lemma 2.

Proof of Lemma 3

Using Result 1, we distinguish two cases:

• If α ≤ 2θ -θ, firms' profits are given by: Π 1 = -β(q 1q) 2 , Π 2 = (θ -α)(θθ)(q 2q 1 ) -β(q 2q) 2 .

We check that ∂Π 1 ∂q 1 = -2β(q 1q) < 0. Thus, Firm 1 chooses q * 1 = q. We check that Π 2 is concave down with respect to q 2 and that it is maximized at q * 2 = δ L 2 + q.

• If 2θ -θ < α < 2θ -θ, firms' profits are given by: Π 1 = 1 9 (2θ -θα) 2 (q 2q 1 ) -β(q 1q) 2 , Π 2 = 1 9 (2θ -θα) 2 (q 2q 1 ) -β(q 2q) 2 .

We check that ∂Π 1 ∂q 1 = -1 9 (2θ -θα) 2 -2β(q 1q) < 0. Thus, Firm 1 chooses q * 1 = q. We check that Π 2 is concave down with respect to q 2 and that it is maximized at q * 2 = δ I 2 + q. Result 5. In the complete information label case, depending on the marginal cost α, at the SPNE, the firms' profits, the industry profit, the environmental damage, consumers' surplus and the social welfare are given in Table 5. Table 5 -The SPNE outcome with a complete information label.

α ≤ 2θ -θ 2θ -θ < α < 2θ -θ Π 1 = 0 Π 1 = βδ I δ I 2 Π 2 = β δ 2 L 4 Π 2 = β

Proof of Result 5

We substitute ∆q in the general expressions given by Table 2 by the values provided in Lemma 3.

Denote by S W p , S W c , the social welfare with a partial and complete information label, respectively. Denote by Π p 2 and Π c 2 , the green firm profit with a partial and complete information label, respectively.

Proof of Proposition 1

We start by comparing the social welfare in both cases:

• If α ≤ 2θ -θ then -if µ < 3θ-θ 2 -α then S W p -S W c = β(δ * L -δ L 2 ) 2 > 0. -if µ >

3.

  When 2θ -θ < α < 2θ -θ and both firms are brown then Π 1 = Π 2 = Π = 0; D = D, CS = CS and S W = S W. The general expression established in the previous case are still valid in this case with ∆q = 0.

  2θ -θ < α < 2θ -θ and 2θ -θ < α < 2θ -θ and 2θ -θ < α < 2θ -θ and µ ≤ S W + βδ * 2 I S W = S W + βδ I (2δ * I -δ I )

  S W + βδ L (δ * L -δ L 4 ) S W = S W + βδ I (δ * I -δ I 4 )

.Figure 2 -

 2 Figure 2 -Difference of consumers' surplus and difference of industry profit curves for θ = 2.5, θ = 1.5, β = 1 and µ = 0.75 .

Partial Information Label

The game is organized as follows:

Appendix Proof of Lemma 1

The proof is based on Result 1. The firms' demands and margins with intermediate marginal costs are given respectively by: 

. and

(q 2q 1 ),

2θ-θ-α 3

(q 2q 1 ).

Proof of Result 2

The proof is based on Result 1. Assuming that q 1 < q 2 , we have that Π 1 = (α -θ)(q 2q 1 )β(q 1q) 2 and Π 2 = -β(q 2q) 2 . We easily check that Π 1 is decreasing with respect to q 1 and Π 2 is decreasing with respect to q 2 . Thus, both firms produce q. When q 1 = q 2 = q then Π 1 = Π 2 = -β(∆q) 2 and both firms produce q.

Denote by

. Denote by D, CS and S W the environmental damage, consumers' surplus and the social welfare, respectively, when both firms produce q. They are given as follows:

Denote by Π 1 , Π 2 , Π, D, CS and S W, respectively the brown firm's profit, the green firm's profit, the industry profit, the environmental damage, consumers' surplus and the social welfare. Result 3 gives their general expressions. Whether in the partial information label case or in the complete information one, Lemmas 2 and 3 show that either both firms produce q or one firm remains brown and the other firm becomes green.

Result 3. The general expression of firms' profits, Industry profit, environmental damage, consumers' surplus and the social welfare at price equilibrium when one firm produces q and the other firm produces q ≥ q are given in Table 2.

)

Table 2 -The firms' profits, the industry profit, the environmental damage, the consumers' surplus and the social welfare when one firm produces q and the other q.

if

We now move to the comparison of the green firm profits

Proof of Proposition 2

The cases that appeared when the label is a partial information label have to be distinguished here:

then a partial information labeling authority does not offer any label i.e. ∆ q = 0. Thus,

then obviously δ I > δ I 2 . Denote by Π p 1 and Π c 1 , the brown firm profit with a partial and complete information label, respectively. Denote by D p and D c , the environmental damage with a partial and complete information label, respectively.

Proof of Proposition 3

The brown firm profit is null when α < 2θ -θ as consumers only buy the green product whatever the label's type. When 2θ -θ < α < 2θ -θ then the profit of the brown firm is positively and linearly related to ∆q. Thus, the brown firm prefers that the green firm offers the highest possible quality. Using the results of Proposition 2, we have:

The same results hold when considering the environmental damage. We first notice from Table 2 that the environmental damage is linearly and negatively related to the green quality. Thus,

• If α ≤ 2θ -θ then the partial information labeling criteria are more stringent than the green quality of the complete information label and consequently D p -D c < 0.

• If 2θ -θ < α < 2θ -θ then the partial information labeling criteria are more stringent than the green quality of the complete information label if and only if µ > α-θ 2 in which case, we have D p -D c > 0.

Denote by CS p and CS c , consumers' surplus with a partial and complete information label, respectively.

Proof of Proposition 4

We now examine consumers' surplus:

• If α ≤ 2θ -θ then consumers' surplus is positively and linearly related to ∆q as shown in Table 2. As the labeling criteria with a partial information label are more stringent than the green quality of the complete information label then CS p -CS c > 0

• If 2θ -θ < α < 2θ -θ then consumers' surplus is linearly related to ∆q as shown in Table 2. However, the relationship can be positive or negative depending on the sign of

. We show that if 2θ -θ < α < α then

< 0. Thus,

2 then α > α. Thus, CS p -CS c > 0 as the partial information label is less stringent than the green quality of the complete information label and as consumers' surplus is negatively related to ∆q.

-If µ > α-θ 2 and α < α then CS p -CS c > 0 as the partial information label is more stringent than the green quality of the complete information label and as consumers' surplus is positively related to ∆q.

-If µ > α-θ 2 and α > α then CS p -CS c < 0 as the partial information label is more stringent than the green quality of the complete information label and as consumers' surplus is negatively related to ∆q.

Denote by Π p and Π c , the industry profit with a partial and complete information label, respectively.

Proof of Proposition 5

We now examine the industry profit.

• If α ≤ 2θ -θ, then the industry profit is equal to the green firm profit and is higher with a complete information label as shown in Proposition 1.

if µ > 4θ-5θ+α 6 then Π p -Π c = β δ I 2 (δ I -δ I 2 ). We have that Π p -Π c > 0 if and only if δ I > δ I 2 which is equivalent to α 2 -2α(5θ -4θ) -2θ 2 + 7θ 2 -4θθ > 0. The quadratic expression is positive if α > α and negative if α < α. Thus, * if α < α then δ I < δ I 2 and Π p -Π c < 0. * if α > α then δ I > δ I 2 and Π p -Π c > 0. Difference of consumers' surplus and difference of industry profits under the two types of labels Denote by ∆CS (α) = CS p (α) -CS c (α) the difference between consumers' surpluses with a partial information label and a complete information label at equilibrium and denote by ∆Π(α) = Π p (α) -Π c (α) the difference between industry profits with a partial information label and a complete information label at equilibrium. Using Results 4 and 5, the expressions of ∆CS (α) and ∆Π(α) for θ-θ 2 < µ < 3θ-θ 2 are respectively given by: ) if α > 6µ+4θ+θ 5

. ) if 6µ -4θ + 5θ < α < ) if α > 6µ+4θ+θ 5

.

Figure 2 gives the curves of ∆CS (α) and ∆Π(α) in the particular case where θ = 2.5, θ = 1.5, β = 1 and µ = 0.75.


Federica Turi

Nathalie T H Gayraud

Maureen Clerc

Zero-Calibration

Zero-calibration cVEP BCI using word prediction: a proof of concept

Zero-calibration cVEP BCI using word prediction: a proof of concept

Federica Turi Nathalie Gayraud Maureen Clerc Inria Sophia Antipolis-Mediterranée, Université Côte d'Azur -France Introduction:

Brain Computer Interfaces (BCIs) based on visual evoked potentials (VEP) [START_REF] Bin | VEP-based brain-computer interfaces: Time, frequency, and code modulations[END_REF] allow for spelling from a keyboard of flashing characters. Among VEP BCIs, code-modulated visual evoked potentials (c-VEPs) are designed for high-speed communication [START_REF] Bin | A high-speed BCI based on code modulation VEP[END_REF]. In c-VEPs, all characters flash simultaneously. In particular, each character flashes according to a predefined 63-bit binary sequence (m-sequence), circular-shifted by a different time lag. For a given character, the m-sequence evokes a VEP in the electroencephalogram (EEG) of the subject [START_REF] Spüler | Online adaptation of a c-VEP brain-computer interface (BCI) based on error-related potentials and unsupervised learning[END_REF], which can be used as a template. This template is obtained during a calibration phase at the beginning of each session. Then, the system outputs the desired character after a predefined number of repetitions by estimating its time lag with respect to the template. Our work avoids the calibration phase, by extracting from the VEP relative lags between successive characters, and predicting the full word using a dictionary.

Material, Methods and Results:

Using the time-windowed EEG generated while the user is gazing at the first character, we compute the average response X a over N repetitions. Since the system has not been calibrated, the first character cannot be displayed. For the second character, we again compute the average response, and shift it by l•s time samples where s is the time lag between two consecutive characters. This produces L shifted averages X l , l = {0 , … , L-1}, where L is the number of characters on the keyboard. Using the lag l = argmax l {corr(X a ,X l )} which produces the maximum correlation to the initial average response, we compute the relative position of this character with respect to the first. Finally, we generate all valid pairs of characters separated by l, and only retain those corresponding to the beginning of valid words within a dictionary. These word beginnings are displayed on the screen as feedback. We repeat this procedure for the following characters, until we are left with a single word (Fig. 1). At that moment, we will have recovered the original letter, and the absolute position of X a can be thereafter used during the computation of the time lag. We conducted offline experiments using the database presented in [START_REF] Spüler | Online adaptation of a c-VEP brain-computer interface (BCI) based on error-related potentials and unsupervised learning[END_REF], composed of 9 subjects, 2 sessions per subject, and 640 trials per session. The signals were preprocessed using a Butterworth filter between 1 and 15 Hz. Each experiment consisted of spelling a 3letter word and was parameterized by the number of repetitions. We repeated the experiment 100 times by simulating the spelling of 3-letter words that we randomly selected among 1014 3-letter English words. We compared our results to a calibrated experiment (Fig. 1b and1c), where we used N repetitions of three characters to compute an average absolute response X a , and performed the same pre-processing as in [START_REF] Spüler | Online adaptation of a c-VEP brain-computer interface (BCI) based on error-related potentials and unsupervised learning[END_REF].

Discussion:

Our zero-calibration method achieves good accuracy, even with only 8 repetitions. In comparison, the experiments preceded by calibration reach a good accuracy after 12 repetitions of the m-code flashes. On Fig. 1b we distinguish two groups of subjects: in green, those that perform well, reaching on average an accuracy that exceeds 75% after 12 repetitions; in red, those whose performance does not produce a accuracy higher than 50%. This trend is also seen in the results of [START_REF] Spüler | Online adaptation of a c-VEP brain-computer interface (BCI) based on error-related potentials and unsupervised learning[END_REF]. We keep the same color coding on Fig. 1c. While some subjects reach accuracy values equal to 100% after the calibration, others perform poorly, even compared to the zero-calibration method.

Significance:

Zero-calibration BCIs are widely research as their use is more natural. We have shown that a word prediction-based zero-calibration method in c-VEP BCIs can be efficient. Since this method relies on the correct detection of relative time lags, online experiments will be conducted to further determine the efficiency of our method.