Introduction

Case-based reasoning [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]] is a reasoning paradigm based on analogy making. Through the reuse of previous problem-solving experiences, called cases, a new problem, called the target case can be solved. Case-based reasoning is usually performed in four steps: firstly, a case similar to the target case is selected in the case base, then that case, called the source case, is adapted in order to solve the target case. The suggested solution is then revised based on user feedback. Finally the solution is stored in the case base to be reused. Thereby, case-based reasoning differs from most artificial intelligence techniques, for it is memory-based. This paradigm is inspired from cognitive sciences, as it mimics human reasoning that largely relies on previous experiences.

The objective of this internship was to design an adaptation operator to be used in casebased reasoning. That adaptation operator had to combine two distinct adaptation paradigms: revision-based adaptation, introduced by Jean Lieber in [Lieber, 2007], and rule-based adaptation. Revision-based adaptation consists in modifying minimally the source case so that it solves the target case. Revision-based adaptation is dependent of how modifications are measured. Rule-based adaptation accounts for adaptation knowledge in the form of adaptation rules or reformulations [START_REF] Melis | Reformulation in Case-Based Reasoning[END_REF]]. These rules represent possible substitutions within the source case, and are applied to it so that it solves the target case.

An adaptation operator in the propositional logic formalism, that is for cases expressed as propositional formulae, has been designed and the corresponding algorithm has been implemented, within the REVISOR library, a collection of revision engines in different formalisms. The algorithm is based on both the semantics tableaux method, a proof procedure used in many logical formalisms, and on the A * algorithm, a widely used and efficient graph search algorithm. This allows for short computing times, with respect to the complexity of the problem.

Chapter 1 presents the scientific context of this internship. Chapter 2 introduces the logical formalism and notions used throughout this report. The revision process is specified for this formalism, and algorithms implementing revision operators are presented. Chapter 3 explains the role of the adaptation process in case-based reasoning and different specifications of this process. Chapter 4 expresses the adaptation problem as a search problem, then presents the A * algorithm. Chapter 5 details the adaptation algorithm that has been designed, and proves it returns the expected results. A study of its complexity is also provided. Section 6 presents an implementation of this algorithm within REVISOR, a collection of revision and adaptation engines. Finally, Chapter 7 concludes and presents some future work.

Chapter 1

Scientific Context

This Chapter presents the scientific context of this internship. This internship was conducted in the Orpailleur team at LORIA. Orpailleur's research domains are knowledge discovery, data mining, semantic web and case-based reasoning. This internship was focused on case-based reasoning, and more precisely on belief revision and adaptation. This Chapter presents these reasoning paradigms. Section 1.1 introduces the case-based reasoning paradigm. Section 1.2 presents the belief revision process, and Section 1.3 shows how it can be used in the adaptation algorithm presented in this report.

Case-based Reasoning

Case-based reasoning is a reasoning paradigm based on the reuse of chunks of experience called cases. A case represents a problem-solving episode, that is the problem itself and one of its solutions. Intuitively, a case has a problem part and a solution part, though it is not formally necessary. A case-based reasoning system contains a case base, that is a collection of these problem-solving experiences. The input of a case-based reasoning system is a problem called the target case. It is a case whose solution part is ill-defined: the aim of the case-based reasoning system is to precise the solution part of the target case. A simple example of case-based reasoning is adapting cooking recipes: for instance, in order to cook an apple pie, one could use a recipe for a pear pie. Since apples and pears are similar fruits, a pear pie recipe can be adapted as an apple pie recipe by replacing pears with apples.

The R4 Model. In [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF], Aamodt and Plaza describe a case-based reasoning process in four steps, illustrated in figure 1.1, commonly called the R4 model or the "4 R's":

Retrieve. For a given problem, the Retrieve step consists in retrieving from the case base a case similar to that problem. That retrieved case is also called the source case. For example, in order to solve the problem "How to cook an apple pie ?", the system would search in the case base for matching recipes. Assuming the system does not have an apple pie recipe, it could retrieve an other pie recipe instead, for instance, a pear pie.

Reuse. The Reuse step consists in reusing the source case in order to specify the solution part of the target case. Usually the source case cannot be used to solve the target case without some changes: then, the source cased is modified, or adapted so that it can solve it. In the pie example, it consists in replacing the pears in the pie by apples. The difficulty of this step depends on how close to the target the retrieved source case is.

Revise. The Revise consists in collecting the feedback from the user of the case-based reasoning system. For example, after using the adapted pear pie recipe to cook an apple pie, the user could think that the apple pie is too sweet. He could then revise the solution by modifying the recipe so it contains less sugar.

Retain. Finally, the solved target case is added to the case base, to be used for further problem-solving episodes. Indeed, a larger case base make the case-based reasoning process more efficient and more accurate.

Note that several approaches can exist for each of these four steps. In particular, this report presents an adaptation algorithm that specifies the adaptation process of the Reuse step, here called the adaptation step. That step of case-based reasoning has only recently received attention in the case-based reasoning literature 1 . Yet, this step is necessary for the case based-reasoning system to be able to suggest solutions to new problems.

Figure 1.1: R4 case-based reasoning process [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]] . 1 See, e.g, [START_REF] Minor | Towards Case-Based Adaptation of Workflows[END_REF], Manzano et al., 2011, Coman and Muñoz-Avila, 2012, Rubin and Watson, 2012]

Belief Revision

Belief revision is a process consisting in incorporating new beliefs to a belief base. For this process, new beliefs are considered more reliable than older ones: if a new belief is inconsistent with the belief base, old beliefs are minimally modified to become consistent with the new. In other words, revision maximizes the amount of old beliefs that stay in the revised belief base. However, if the old and new beliefs are consistent, then the new ones are added to the belief base without changing the old ones. The main challenge in belief revision is to modify old beliefs as less as possible: thus, ways to measure changes in a belief base must be defined.

Revision is performed on beliefs describing a static world, that is, beliefs that are generally true rather than true at only one given moment. For example, the belief "it is snowing" is typically not about a static world, as it describes a transient state of the world, and thus could be outdated at some point. It would not make sense to revise a belief that is outdated, as it would not be necessary to keep such a belief in the belief base. However the belief "if it snows, then it is cold outside" is true, independently of the moment it is evaluated. Intuitively, belief revision does not reflect a change of the world, but rather a change of one's belief about that world.

Because of the many possible ways to measure change in a belief base, multiple revision operators exists. The AGM postulates defined in [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF] are accepted as a set of properties a belief revision operator should have.

Adaptation

Adaptation is one of the steps of the case-based reasoning process, also called the Reuse step. The adaptation algorithm presented in this report is based on the approach now called revisionbased adaptation2 or -adaptation, introduced in [Lieber, 2007]. This approach is based on a belief revision operator, . Revision-based adaptation takes into account domain knowledge, that is knowledge that does not belong to one case, but can be used to better understand the cases. For example, "Apples and pears are fruits" can be considered as domain knowledge.

The adaptation approach presented in this report is original as it proposes to account for domain and adaptation knowledge. Adaptation knowledge represents ways to adapt a source case to solve the target case. For example, "In a pie recipe, apples can replace pears" provides information on how a pear pie recipe can be adapted to cook an apple pie. The presented approach will account for that adaptation knowledge in the form of adaptation rules, also called reformulations in [START_REF] Melis | Reformulation in Case-Based Reasoning[END_REF].

Chapter 2

Preliminaries

This Chapter provides necessary notions that will be used throughout that report. Section 2.1 first introduces propositional logic, the formalism in which the adaptation operator presented in this report will be defined. Then, Section 2.2 explains the notion of mathematical distances, and how these distances are used in propositional logic. Section 2.3 describes how belief revision is performed in propositional logic. Section 2.4 describes the notion of implicant, and Section 2.5 presents one procedure to compute implicants: the semantic tableaux method. Finally, Section 2.6 presents how implicants are used to perform belief revision.

Propositional Logic

Let V = {a 1 , . . . , a n } be a set of n distinct symbols called propositional variables. A propositional formula built on V is either:

• a variable a i ,
• the conjunction of two propositional formulae:

ϕ 1 ∧ ϕ 2 ,
• the disjunction of two propositional formulae:

ϕ 1 ∨ ϕ 2 ,
• the negation of a propositional formula: ¬ϕ 1 ,

• an implication of two propositional formulae:

ϕ 1 ⇒ ϕ 2 ,
• an equivalence of two propositional formulae:

ϕ 1 ⇔ ϕ 2 ,
where ϕ 1 and ϕ 2 are two propositional formulae. A literal is a propositional formula of the form a i (positive literal) or ¬a i (negative literal), where a i ∈ V. If = ¬a i is a negative literal, then ¬ denotes the positive literal a i (instead of the equivalent formula ¬¬a i ). Let L be the set of the propositional formulae.

Interpretations and Models. Let IB = {T, F} be the set of booleans, where T stands for true, and F for false. An interpretation x is defined as an ordered n-tuple of booleans: (x 1 , . . . , x n ). IB n represents the set of all interpretations. ϕ x is the truth value of ϕ interpreted by x, and evaluates to:

• x i , if ϕ = a i , • (ϕ 1 ∧ ϕ 2 ) x = T iff ϕ x 1 = T and ϕ x 2 = T, • (ϕ 1 ∨ ϕ 2 ) x iff ϕ x 1 = T or ϕ x 2 = T, • (¬ϕ 1 ) x = T iff ϕ x 1 = F, • (ϕ 1 ⇒ ϕ 2 ) x = (¬ϕ 1 ∨ ϕ 2 )
x , and

• (ϕ 1 ⇔ ϕ 2 ) x = ((ϕ 1 ⇒ ϕ 2 ) ∧ (ϕ 2 ⇒ ϕ 1 )) x .
For ϕ ∈ L, let Mod(ϕ) = {x ∈ IB n | ϕ x = T} called the set of models of ϕ. The two relations |= and ≡ between formulae are defined as follows: let ϕ 1 , ϕ 2 be two propositional formulae,

ϕ 1 |= ϕ 2 iff Mod(ϕ 1 ) ⊆ Mod(ϕ 2 ), ϕ 1 ≡ ϕ 2 iff Mod(ϕ 1 ) = Mod(ϕ 2 ).
(L, |=) is called the propositional logic with n variables.

Disjunctive Normal Form. A formula is in disjunctive normal form or DNF if it is a disjunction of clauses, where clauses are literals or conjunctions of literals. That is, a formula ϕ is in DNF, iff it is under one of these forms:

• ϕ = , where is the disjunction of an empty clause.

• ϕ = ⊥, where ⊥ is the disjunction of zero clauses.

• ϕ = 1 ∧ . . . ∧ n , for n ≥ 1 and n literals 1 , . . . , n , where 1 ∧ . . . ∧ n is a single clause.

• ϕ = ϕ 1 ∨ ϕ 2 , for any two formulae ϕ 1 and ϕ 2 in DNF.

A formula in DNF is satisfiable iff at least one of its clauses is satisfiable, and a clause is satisfiable iff it does not contain a literal and its negation ¬ . Note that a formula can have several distinct DNF.

Conjunctive Normal Form. Conjunctive normal form or CNF is the converse form to the DNF. A formula is in conjunctive normal form is a conjunction of clauses, where clauses are literals or disjunctions of literals.

Negative Normal Form. A formula is in negative normal form or NNF if it contains only the connectives ∧, ∨ and ¬, and if ¬ appears only in front of propositional variables. Every formula can be put in NNF by applying, as rewriting rules oriented from left to right, the following equivalences, until none of these equivalences is applicable (for ϕ, ϕ 1 , ϕ 2 ∈ L):

ϕ 1 ⇔ ϕ 2 ≡ (ϕ 1 ⇒ ϕ 2 ) ∧ (ϕ 2 ⇒ ϕ 1 ) ϕ 1 ⇒ ϕ 2 ≡ ¬ϕ 1 ∨ ϕ 2 ¬¬ϕ ≡ ϕ ¬(ϕ 1 ∨ ϕ 2 ) ≡ ¬ϕ 1 ∧ ¬ϕ 2 ¬(ϕ 1 ∧ ϕ 2 ) ≡ ¬ϕ 1 ∨ ¬ϕ 2
A formula in DNF or in CNF is necessarily in NNF (the converse is false). For example, the formula ¬(¬a ∧ b) can be put in NNF in a few steps: first using the equivalence ¬(ϕ 1 ∧ ϕ 2 ) ≡ ¬ϕ 1 ∨ ¬ϕ 2 , it becomes (¬¬a ∨ ¬b). Then, the double negation is removed, using the equivalence ¬¬ϕ ≡ ϕ. Thus, the formula is in the form (a ∨ ¬b), and since the ¬ connective only appears preceding a propositional variable, the formula is therefore in NNF.

Distances

In mathematics, a distance d on a set U is a function d : U × U → R that verifies these four properties, for any elements of U, x, y and z: Distances on Interpretations. Distances can be defined on IB n , the set of propositional logic interpretations. Let d be such a distance, ϕ a propositional formula, and x, y two interpretations in IB n . The following shortcut is used:

d(ϕ, y) = inf x∈Mod(ϕ 1 ) d(x, y)
Indeed, a formula can be represented as the set of interpretations that satisfies it, thus, the distance between an interpretation y and a formula ϕ can be defined as the minimal distance between y and models of ϕ. Similarly, the distance between two formulae ϕ 1 and ϕ 2 can be defined as:

d(ϕ 1 , ϕ 2 ) = inf y∈Mod(ϕ 2 ) d(ϕ 1 , y)
Two properties can be deduced from these definitions: d(ϕ, y) = 0 iff y is a model of ϕ, and

d(ϕ 1 , ϕ 2 ) = 0 iff ϕ 1 ∧ ϕ 2 is consistent.
Hamming Distance. In [Hamming, 1950], Hamming defines a distance function on binary words of same length, and was first used in telecommunication to measure error in transmissions. An error in a transmission, or a flip, is characterized as a bit that differs from the original word and the transmitted word. The Hamming distance, noted d H , is equal to the numbers of flips. Being n-tuples of booleans, propositional logic interpretations can be considered as binary words. Thus, the Hamming distance on the set of propositional logic interpretations, IB n is defined by, for x, y ∈ IB n :

d H (x, y) = |{i | i ∈ {1, 2, . . . , n}, x i = y i }|
In other words, d H (x, y) is equal to the number of variables with a different interpretation in x and y. A flip in an interpretation x is defined as the change of truth value of one propositional variable a i : this operation is also called a flip on a i , noted F a i .

Belief Revision in Propositional Logic

Let ψ be the beliefs of an agent, expressed as a propositional logic formula. The agent is confronted to new beliefs expressed by the formula µ. The new beliefs of the agent is denoted by

ψ µ. If ψ ∧ µ is consistent, then ψ µ = ψ ∧ µ.
Otherwise, according to the minimal change principle [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF], ψ has to be modified minimally into a formula ψ such that ψ ∧ µ is consistent. Then ψ µ = ψ ∧ µ.

Revision Operators. A revision operator is defined by the distance function it uses to measure changes in the belief base, as such, multiple revision operators can be defined. The Dalal revision operator [Dalal, 1988] is based on the previously-defined Hamming distance. There exists a set of postulates defining the properties of a revision operator, called the AGM postulates, described by Alchourron, Gärdenfors and Makinson in [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF]. In [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF], Katsuno and Mendelzon define a new set of postulates equivalent to the AGM postulates for revision operators in propositional logic. For any belief revision operator • in propositional logic:

(R1) ψ • µ implies µ. (R2) If ψ ∧ µ is satisfiable then ψ • µ ≡ ψ ∧ µ. (R3) If µ is satisfiable then ψ • µ is also satisfiable. (R4) If ψ 1 ≡ ψ 2 and µ 1 ≡ µ 2 then ψ 1 • µ 1 ≡ ψ 2 • µ 2 . (R5) (ψ • µ) ∧ ϕ implies ψ • (µ ∧ ϕ). (R6) If (ψ • µ) ∧ ϕ is satisfiable then ψ • (µ ∧ ϕ) implies (ψ • µ) ∧ ϕ.
Let ψ and µ be two formulae, ψ d µ is a formula whose models are the models of µ that are the closest ones to those of ψ, according to the distance function d:

Mod(ψ d µ) = {y ∈ Mod(µ) | d(ψ, y) = d(ψ, µ)} a b ψ = a ∧ b µ = ¬a ∨ ¬b F F F T F T F T T F F T T T T F Figure 2.1: Truth table of the formulae ψ = (a ∧ b) and µ = ¬a ∨ ¬b.
Note that this definition specifies ψ d µ up to logical equivalence, but this is sufficient since a revision operator has to satisfy the irrelevance of syntax principle, according to the (R4) postulate.

The propositional formula ψ d µ can be written as:

x∈Mod(ψ d µ) ϕ x | Mod(ϕ x ) = x ϕ x = a i ∈V a i , if x i = T ¬a i , if x i = F
Example. This example describes the computation of ψ d H µ, for ψ = a ∧ b and µ = ¬a ∨ ¬b. Firstly, it is necessary to compute Mod(ψ) and Mod(µ). Figure 2.1 shows the truth table of ψ and µ. ψ has one model (T, T) and µ has three: (F, F), (F, T), (T, F). Then, d H is computed between every model of ψ and every model of µ, by counting the differences between each model:

d H ((T, T), (F, F)) = 2 d H ((T, T), (F, T)) = 1 d H ((T, T), (T, F)) = 1
The distance is minimal between the models (T, T) of ψ and (F, T) of µ, and (T, T) of ψ and

(T, F) of µ. Thus Mod(ψ d H µ) = {(F, T), (T, F)}, and ψ d H µ = (¬a ∧ b) ∨ (a ∧ ¬b).

Implicant Theory

A set of literals L is often assimilated to the conjunction of its elements, for example {a, ¬b, ¬c} is assimilated to a ∧ ¬b ∧ ¬c and vice-versa. In particular, L is satisfiable iff there is no literal ∈ L such that ¬ ∈ L.

An implicant of ϕ, I is a conjunction or a disjunction of literals, such that I |= ϕ and I is satisfiable. However, as there exists a duality between conjunctive and disjunctive implicants, only conjunctive implicants will be considered. An implicant I of ϕ is prime if for any conjunction of literals C such that C ⊂ I, C |= ϕ. That is, a prime implicant I is minimal. Let PI(ϕ) be the set of prime implicants of ϕ. Then:

ϕ ≡ I∈PI(ϕ)

I

Note that, for a formula ϕ in the form of a conjunction of literals, PI(ϕ) = {ϕ}. An algorithm to find efficiently prime implicants of a formula is detailed in [Socher, 1991].

Semantic Tableaux

In propositional logic, the method of semantic tableaux is used to determine the satisfiability of a formula. Intuitively, it consists in transforming the formula into one of its DNF: it is then sufficient to prove the satisfiability of one of its conjunctive clauses to prove the satisfiability of the formula. The semantic tableau of a formula ϕ is a tree structure representing ϕ, in which a branch represents a clause, and the disjunction of all the clauses is the DNF of ϕ.

Expansion Rules. Initially, the tableau of a formula ϕ is a tree with a single node representing ϕ. Assuming ϕ is in NNF, tableaux calculus defines two expansion rules (∨) and (∧) that can respectively be applied on nodes representing formulae in the form of ϕ 1 ∨ ϕ 2 or ϕ 1 ∧ ϕ 2 :

• The (∨) rule is applied on nodes representing a disjunctive formula.

ϕ 1 ∨ ϕ 2 ϕ 1 | ϕ 2 (∨)
That is, any node representing a disjunction can be expanded by splitting the current branch in two new branches, and adding respectively the first and second operands to the first and second branches:

ϕ 1 ∨ ϕ 2 ϕ 1 ϕ 2
• The (∨) rule is applied on nodes representing a conjunctive formula.

ϕ 1 ∧ ϕ 2 ϕ 1 ϕ 2 (∧)
That is, any node representing a conjunction can be expanded by adding its two operands to the current branch:

ϕ 1 ∧ ϕ 2 ϕ 1 ϕ 2
Note that nodes can be expanded at most once in each branch. The procedure stops when no more nodes can be expanded.

Figure 2.2 presents an example of the tableau of the formula ¬(¬a ∧ b) ∧ (c ∨ d) built using these two rules. The formula must first be put into NNF: using the equivalences defined in Section 2.1, it can be deduced that

¬(¬a ∧ b) ∧ (c ∨ d) ≡ (a ∨ ¬b) ∧ (c ∨ d).
The (∧) rule is first applied to the conjunction of (a ∨ ¬b) ∧ (c ∨ d), so a ∨ ¬b and c ∨ d are added to the branch. Then the (∨) rule is applied on a ∨ ¬b, and the branch is split in two. The formula a is added to one of the new branches, while ¬b is added to the other. The (∨) is similarly applied on c ∨ d. Note that, at this point, c ∨ d appears in two branches. Thus, these two branches are both split in two, and c and d both appear twice in the leaves of the tree.

¬(¬a ∧ b) ∧ (c ∨ d) ≡ (a ∨ ¬b) ∧ (c ∨ d) a ∨ ¬b c ∨ d a c d ¬b c d Figure 2.2: Fully-expanded tableau for the formula ¬(¬a ∧ b) ∧ (c ∨ d).
Clashes and Satisfiability. A branch contains a clash when there are a literal and its opposite literal ¬ in this branch, it is said there is a clash on . As branches represents conjunctions of literals, a branch containing a clash is equivalent to ⊥. Thus, the branch need not to be expanded: adding any literal to the branch would not affect the semantics of the formula it represents, as ⊥ ∧ ≡ ⊥.

If each branch contains at least one clash, then the formula is unsatisfiable: each branch is equivalent to ⊥, and a DNF of the formula is a disjunction between them, thus the formula is equivalent to ⊥. Conversely, if at least one branch does not contain a clash, then the formula is satisfiable, since its DNF contains a satisfiable clause. Branches without clashes are said to be consistent.

Simple Algorithm. Let branches be a function that for any propositional formula ϕ in NNF, returns the set of tableaux branches of ϕ. Each branch is represented by the set of every literal it contains. For any formula ϕ in NNF, branches(ϕ) is defined as:

• If ϕ is a literal, such that ϕ = , then: branches(ϕ) = {{ }}.
• If ϕ is in the form ϕ 1 ∨ ϕ 2 , with ϕ 1 and ϕ 2 two propositional formulae, then: branches(ϕ) = branches(ϕ 1 ) ∪ branches(ϕ 2 ).

• If ϕ is in the form ϕ 1 ∧ ϕ 2 , with ϕ 1 and ϕ 2 two propositional formulae, then: branches

(ϕ) = {B 1 ∪ B 2 | (B 1 , B 2 ) ∈ branches(ϕ 1 ) × branches(ϕ 2 ) and B 1 ∪ B 2 consistent}.
As ϕ is equivalent to the disjunction of its branches, the following equivalence holds for any propositional formula ϕ: ϕ ≡

B∈branches(ϕ) B (2.1)
Tableaux in Implicant Theory. Let ϕ be a propositional formula. Branches of the tableau of ϕ can be seen as implicants of ϕ. Indeed, for any branch B ∈ branches(ϕ), it is easily deduced from (2.1) that B |= ϕ.

Implicant-based Revision

Implicant-based revision is a belief revision operation performed on set of implicants of formulae. Tableaux can also be used to perform implicant-based revision in propositional logic, using tableaux repairs [Schwind, 2011]: when revising a formula ψ by a formula µ, usually ψ ∧ µ is not satisfiable, that is every branch of its tableau contains a clash. Tableaux repairs consists in removing from the branches the literals causing clashes. This modifies the ψ ∧ µ so it becomes satisfiable.

Intuitively, implicant-based revision consists in finding implicants of ψ that are the closest to implicants of µ, according to some distance function. As implicants are formulae, computing the distance between two implicants can be done by computing the minimal distance between two of their respective models, as previously defined in Section 2.2.

ψ d H µ can be computed in a few steps. First, branches(ψ) and branches(µ) are computed. Then every branch of ψ is combined with each branch of µ. If a branch contains a clash between a literal from ψ and a literal ¬ from µ, from ψ is removed from the branch. Indeed, since ψ is being revised by µ, it is not possible to modify µ to repair the clash on . The operation of removing from ψ coincides with the flip operation defined in Section 2.2, as is removed in favor of ¬ . To each branch is associated a cost equal to the number of clashes repaired this way. Finally, ψ d H µ is determined by the disjunction of the branches of minimal cost. The single branch of ψ, {a, b} can be combined with either of the two branches of µ, {¬a}, {¬b}. The union {a, b} ∪ {¬a} results in a clash on a, while {a, b} ∪ {¬b} results in a clash on b. These two clashes can be repaired by removing respectively a and b from them. Thus, the two branches {¬a, b} and {a, ¬b} are obtained. As one clash has been repaired in each of them, the cost associated to them is of 1. Since there is no other branches with a cost less or equal to 1, ψ d H µ = (¬a ∧ b) ∨ (a ∧ ¬b), which of course coincides with the result found in Section 2.3.

Advantages of Implicant-based Revision.

The truth table method used to compute revision with d H has a time complexity of O(2 n ), as there is 2 n possible interpretations, where n is the number of variables. Implicant-based revision is also computed in exponential time, however, computing time does not depend on the number of variables n, but rather the branching factor in the tableaux of the formulae. Thus, computing time largely depends on the form of the formulae: computing the tableau of a formula in DNF can be done in linear time with respect to the size of the formula1 . However computing the tableau of an equivalent formula in conjunctive normal form is done in exponential time, with respect to the number of clauses. The output of implicantbased revision is a set of tableaux branches, that is trivially changed into DNF. Consequent revisions operations on a belief base can take advantage of an output in DNF, as every revision beyond the first would be done on a belief base already in DNF.

Chapter 3

Adaptation in Case-based Reasoning

Let (L, |=) be the logic in which the knowledge containers of the case-based reasoning application are defined. A source case Source ∈ L is a case of the case base. Often, such a case represents a specific experience: Mod(Source) is a singleton. However, this assumption is not formally necessary (though it has an impact on the complexity of the algorithms). A target case Target ∈ L represents a problem to be solved. This means that there is some missing information about Target and solving Target leads to adding information to it. So, adaptation of Source to solve Target consists in building a formula CompletedTarget ∈ L that makes Target precise: CompletedTarget |= Target. To perform adaptation, the domain knowledge DK ∈ L can be used. Therefore, the adaptation process has the following signature:

Adaptation : (DK, Source, Target) → CompletedTarget (Source, Target) is called the adaptation problem (DK is supposed to be fixed).

Of course, this does not completely specify the adaptation process. Several approaches are introduced in the case-based reasoning literature. Two of them are presented below: Section 3.1 presents the revision-based adaptation approach, then Section 3.2 presents rule-based adaptation. Finally, Section 3.3 presents a combination of these two approaches.

Revision-based Adaptation

Let be a revision operator in the logic (L, |=) used for a given case-based reasoning system. The -adaptation is defined as follows:

CompletedTarget = (DK ∧ Source) (DK ∧ Target)
Intuitively, the source case is modified minimally so that it satisfies the target case. Both cases are considered with respect to the domain knowledge.

Let ψ = (DK ∧ Source), µ = (DK ∧ Target) and ψ such that ψ µ = ψ ∧ µ. Revisionbased adaptation consists in revising ψ by µ. Note that since DK appears in both ψ and µ, it will not be affected by the revision process, that is ψ |= DK. The advantage of using revision-based adaptation is that it always provides a result, which is not the case of all adaptation approaches.

In particular, next Section introduces an adaptation approach relying on adaptation knowledge that in some cases may fail to adapt the source case to the target case.

Rule-based Adaptation

Rule-based adaptation is a general approach to adaptation relying on domain-specific adaptation knowledge in the form of a set AK of adaptation rules (see, e.g., [START_REF] Melis | Reformulation in Case-Based Reasoning[END_REF], where adaptation rules are called reformulations). An adaptation rule R ∈ AK, when applicable on the adaptation problem (Source, Target), maps Source into CompletedTarget which makes Target precise. Adaptation rules can be composed (or chained): if R 1 , R 2 , . . . , R q ∈ AK are such that there exist q + 1 cases C 0 , C 1 , . . . , C q verifying:

• C 0 = Source,
• C q makes Target precise (C q |= Target),

• for each i ∈ {1, . . . , q}, R i is applicable on (C i-1 , C i ) and maps C i-1 into C i , then C q = CompletedTarget is the result of the adaptation of Source to solve Target. The sequence R 1 ; R 2 ; . . . ; R q is called an adaptation path.

Given an adaptation problem (Source, Target), there may be several adaptation paths to solve it. In order to make a choice among them, a cost function is introduced: cost : R ∈ AK → cost(R) > 0. The cost of an adaptation path is the sum of the costs of its adaptation rules.

An adaptation rule R is defined by two sets of literals, left and right, and is denoted by R = left right. Let (Source, Target) be an adaptation problem. Several cases have to be considered:

• If Source is a conjunction of literals represented by a set of literals L, then R is applicable on Source if left ⊆ L. In this situation:

R(Source) = R(L) = (L \ left) ∪ right • If Source is in DNF, such that Source = i L i
, where the L i 's are conjunctions of literals, R is applicable on Source if it is applicable on at least one L i . Then:

R(Source) = i R(L i ) if R is applicable to L i , L i otherwise.
• If Source is not in DNF, it is then replaced by an equivalent formula in DNF.

Given an adaptation rule R = left right, repairs(R) = left\right, that is the set of literals whose presence is necessary to apply R, and that are effectively removed by application of R. Every adaptation rule must be such that repairs(R) = ∅.

Combining Rule-based and Revision-based Adaptation

Let us consider the following distance on U = IB n (for x, y ∈ U):

δ AK (x, y) = inf{cost(p) | p: adaptation path from x to y based on rules from AK} (x and y are interpretations that are assimilated to conjunctions of literals). By convention, inf ∅ = +∞ and thus, if there is no adaptation path relating x to y, then δ AK (x, y) = +∞ and vice-versa. Otherwise, it can be shown that the infimum is always reached and so, δ AK (x, y) = 0 iff x = y (corresponding to the empty adaptation path).

It has been shown [START_REF] Cojan | Belief revision-based case-based reasoning[END_REF] that rule-based adaptation can be simulated by revision-based adaptation with no domain knowledge (i.e., DK is a tautology) and with the δAK revision operator. When rule-based adaptation fails (no adaptation path from Source to Target), δAK -adaptation gives CompletedTarget equivalent to Target (no added information).

The failure of rule-based adaptation is due to the fact that no adaptation rules can be composed in order to solve the adaptation problem. In order to have an adaptation that always provide a result, the idea is to add 2n adaptation rules, one for each literal: given a literal , the flip of the literal is the adaptation rule F = , where is the empty conjunction of literals. It can be noticed that a cost is associated to each literal flip and that it may be the case that cost(F ¬ ) = cost(F ). Now, let d AK be the distance on U = IB n defined, for x, y ∈ U, by d AK (x, y) = inf cost(p) p: adaptation path from x to y based on rules from AK and on flips of literals Let AK = dAK . AK -adaptation is a revision-based adaptation using the adaptation rules, thus combining rule-based adaptation and revision-based adaptation, and that can take into account domain knowledge.

It can be noticed that if AK = ∅ and cost(F ) = 1 for every literal then d AK = d H . Moreover the following assumption is made:

For any R ∈ AK, cost(R) ≤ ∈repairs(R) cost(F ) (3.1)
In fact, this assumption does not involve any loss of generality. If an adaptation rule violates (3.1), then it does not appear in any optimal adaptation path: applying the flips of all the literals of its repair part will be less costly then applying the rule itself, and applying a flip never generates new clashes. However, it is always possible that a flip is used despite the existence of lower cost rules: indeed, the application of a rule can generate clashes by introducing new literals in the formula, and the subsequent repair costs could exceed those of using flips.

Chapter 4

Revision and Adaptation as Search Problems

While computing d H between two interpretations is straightforward (and can be done in time proportional to the number of variables n by counting differences between the interpretations), the computation of d AK poses a more complex problem. Indeed, it is necessary to determine which rules will appear in an optimal adaptation path, and in which order. This Chapter presents how graph search algorithms can be used to efficiently implement revision and adaptation operators. Firstly, basics of graph theory and graph searching are introduced in Section 4.1. A naive graph modeling of revision problems, a second graph modeling based on implicant revision and a final modeling of the previously-presented adaptation approach are presented in Section 4.2. Finally, an efficient search algorithm to compute adaptation will be explained in Section 4.3.

Graph Theory and Search Problems

Graphs are structures representing a set of objects in which pairs of elements can be connected by links. Each element is represented by a vertex, and links are represented by edges. Edges are expressed as pairs of vertices. These pairs of vertices can be considered to be ordered (to represent an asymmetric link), in which case the graph is said to be directed. Graphs are commonly used to represent state spaces: each vertex represents a possible state of the world, while edges represents possible transitions between those states. Edges are usually given an arbitrary cost, that is the cost of transitioning from one state to another by following this edge.

Graph search algorithms are used to solve search problems in state spaces. A problem is represented by one or several initial states1 , and a criteria for a state to be considered final. Solutions to a problem are presented as paths, that is sequences of edges, that from the initial state leads to one final state. To each path can be associated a cost that is the sum of the costs of every edge. A solution is said to be optimal when it is one of the least costly solutions.

Revision and Adaptation

The set of propositional logic interpretations, IB n , is the set of possible states of the world. Belief revision for an operator d can be realized as a search problem in state space: states are interpretations, and a transition from a state S x representing an interpretation x and a state S y representing an interpretation y has a cost of d(x, y). ψ d µ is then computed by first enumerating ψ and µ models that will determine, respectively, the initial and final states, then finding the shortest paths between them. Models of µ that are linked to models of ψ by a shortest path are then set as the models ψ d µ.

Implicant-based Revision. The implicant-based revision algorithm described in Section 2.6 implementing d H can too be realized as a search problem. However, states are no more elements of IB n , but ordered pair of implicants or tableaux branches. Initial states are states whose first element is a branch of the tableau of ψ, and the second a branch of the tableau of µ. Possible transitions from one state to another are determined by flips, that is the removal of a literal from a branch of ψ to solve a clash. A state is final iff there is no clash between its branch from ψ and its branch from µ. Note that the use of flips require the graph to be directed: each flip remove a literal with a cost of 1, however there is no converse transition that adds literals. Because transitions can only remove clashes, there is no cycles, and there is no dead ends except for final states. Also, it is easy to estimate the cost of the optimal solution: that cost is equal to minimum number of clashes in an initial state.

Adaptation as a Search Problem. Intuitively, rule-based adaptation can be similarly realized as a search problem using adaptation rules between states. Thus, realizing the adaption operator defined in Section 3.3-AK -as a search problem consists in adding the adaptation rules to the implicant-based revision search problem. The search problem realizing AK is much more complex than the implicant-based revision problem: because rules can generate clashes, finding a solution is not straightforward, and cycles can be generated. For the same reason, estimating the cost of the optimal solution is not trivial.

A * Algorithm

Given that computing AK requires finding optimal adaptation paths, an optimal search algorithm must be used. An algorithm is optimal if it finds solutions with a minimal cost. A * is a heuristicbased best-first search algorithm [Pearl, 1984] that is optimal when using an admissible heuristic function. It is suited for searching state spaces where there are a finite number of transitions from a given state to its successor states and for which the cost of a path is additive (the cost of a path is the sum of the cost of the transitions it contains). Given a state S, let F * (S) be the minimum of the costs of the paths from an initial state to a final state that contain S. F * (S) is defined as:

F * (S) = G * (S) + H * (S)
where G * (S) is the minimal cost of the paths from an initial state to S and H * (S) is the minimal cost of the path from S to a final state.

Usually, as in the AK problem, F * is unknown and is approximated by a function F defined as:

F(S) = G(S) + H(S)
For the A * algorithm to be optimal, it is necessary that for any state S, G and H verifies the following inequalities:

G(S) ≥ G * (S) H(S) ≤ H * (S)
Usually, G(S) is the cost of the path that has already been generated for reaching S and thus, G(S) ≥ G * (S). Then, the main difficulty is to find an admissible H, also called the heuristic function. The constant function 0 is an admissible H (it is then equivalent to run Dijkstra's algorithm [Dijkstra, 1959], that is also optimal) but the closer an admissible H is to H * , the faster the search is.

The A * algorithm consists in searching the state space, starting from the initial states, in ascending order of their F(S). Once A * reaches a final state, it is known that the path used to reach it is an optimal solution. Space Complexity Issues. Given the total number of states that grows exponentially with the number of variables, it would be inefficient to generate every state at the start of the execution of the algorithm. Thus, states will not be generated until the search algorithm visits them. Because A * does not need to visit every state to find an optimal solution, this makes the algorithm effectively less memory expensive.

Introducing the Running Example

Let ψ = a ∧ b and µ = ¬a ∧ ¬c be two propositional formulae. The computation of ψ AK µ will be detailed along with the presentation of the algorithm. For this purpose, the following adaptation knowledge AK will be used:

AK = {R 1 , R 2 } R 1 = a ∧ b b ∧ c R 2 = b ∧ c a ∧ b
The following cost function will be used:

cost(R 1 ) = 0.5 cost(R 2 ) = 0.5 cost(F a ) = 2 cost(F ¬a ) = 1 cost(F b ) = 1 cost(F ¬b ) = 1 cost(F c ) = 1 cost(F ¬c ) = 1

Algorithm

The algorithm uses an A * search, where a state is an ordered pair (L, M) of individually consistent sets of literals. That is L is consistent, M is consistent, but L ∪ M may not be. The function branches, defined in Section 2.5, is used by the algorithm to generate the set of initial states.

In order to abide by Katsuno and Mendelzon postulate of irrelevance to the syntax, the function min-branches introduced, that convert the output of the branches function into the set of prime implicants of the formula, represented as sets of literals. Indeed, equivalent formulae have the same set of prime implicants.

For any set of literals L, let L ¬ = {¬ | ∈ L}. For example, if L = {a, ¬b, ¬c} then L ¬ = {¬a, b, c}. L is said to be consistent if and only if L ∩ L ¬ = ∅.

Given the propositional formulae ψ and µ, the set of the initial states is:

min-branches(ψ) × min-branches(µ)

Figure 5.1 describes the computation of the initial states for the running example. Note that, because ψ and µ are conjunctions of literals, the set of branches of their respective tableaux coincides with the set of their primes implicants.

A final state is a state (L, M) such that L ∩ M ¬ = ∅ (which is equivalent to the fact that L ∪ M is consistent). If (L, M) is a non final state, then there exits ∈ L such that ∈ L ∩ M ¬ : there is a clash on .

The transitions from a state to another state are defined as follows. There is a transition σ from the state x = (L x , M x ) to the state y = (L y , M y ) if M x = M y and: • there exists an adaptation rule R such that R is applicable on L x and L y = R(L x ).

• there exists a literal ∈ L x such that L y = F (L x ) or branches(ψ = a ∧ b) = {B 1 ∪ B 2 | (B 1 , B 2 ) ∈ {{a}} × {{b}} and B 1 ∪ B 2 consistent.} = {{a} ∪ {b}} = {{a, b}} branches(µ = ¬a ∧ ¬c) = {B 1 ∪ B 2 | (B 1 , B 2 ) ∈ {{¬a}} × {{¬c}} and B 1 ∪ B 2 consistent.} = {{¬a} ∪ {¬c}} = {{¬a, ¬c}} min-branches(ψ) × min-branches(µ) = {({a, b}, {¬a, ¬c})}
The cost of a transition σ is the cost of the rule (literal flip or adaptation rule) it uses. Using a slight variant of the A * algorithm, it is possible to determine the set of least costly transition sequences leading to a final state of the problem. That is, the algorithm does not stop after finding the first optimal solution, but after finding every other optimal solutions (i.e., the solutions with the same minimal cost). The detailed algorithm is presented in Algorithm 1 and is explained hereafter.

The algorithm first creates the initial states (line 3). For every initial state S 0 , G(S 0 ) = 0, that is the cost of reaching S 0 is 0. In the case no value of G is set for a state S, G(S) evaluates to +∞, meaning there is no known path from an initial state to S. The algorithm then finds a state S c minimizing F(S c ) = G(S c ) + H(S c ), that is the cost of reaching S c from an initial state plus the heuristic cost of reaching a final state from S c (line 10). For each rule or flip σ that can be applied on S c , it creates the state S d such that S c σ -→ S d . If G(S d ) > G(S c ) + cost(σ), that is there is no known less or equally costly path to S d , then G(S d ) is set to G(S c ) + cost(σ). Each generated S d is added to the set of states to explore, while S c is removed from it (lines 15 to 20). The algorithm repeats the previous step until it finds a state S f minimizing F(S f ) and that is a final state (lines 11 to 13). From this point, the algorithm carries on but ignores any state S c such that F(S c ) > F(S f ), which cannot lead to a less costly solution. It stops when there is no more states that can lead to a less costly solution (line 9). Finally, all final states S f minimizing F(S f ) are returned in the form of tableaux branches (line 22), that is for each state S f defined by (L f , M f ), the branch containing the literals L f ∪ M f is returned.

revise(ψ, µ, AK, cost) Input: ψ and µ, two propositional formulae in NNF. ψ has to be revised by µ.

AK, the set of adaptations rules to perform the adaptation operation. cost, a function that associates to every literal flip and adaptation rule a positive real number.

Solutions ← ∅ solutionCost ← +∞ while {S | S ∈ open-states, F(S) ≤ solutionCost} = ∅ do // (L c , M c ) is the current state. (L c , M c ) ← a S ∈ open-states minimizing F(S) if (L c ∩ M ¬ c ) = ∅ then Solutions ← Solutions ∪ {L c ∪ M c } solutionCost ← F((L c , M c )) else for each σ ∈ AK ∪ {F for every literal } such that σ is applicable on L c do open-states ← open-states ∪ {(σ(L c ), M c )} G((σ(L c ), M c )) ← min(G((σ(L c ), M c )), G((L c , M c )) + cost(σ))

Heuristics

The function H used in the algorithm is defined by: for S = (L, M),H(S) = ERC(L ∩ M ¬ ) where ERC is defined as follows (ERC stands for Estimated Repair Cost):

ERC({ }) = min{cost(F )} ∪ cost(R) |repairs(R)| R ∈ AK, such that ∈ repairs(R) for any literal ERC(L) = ∈L ERC({ }) for any set of literals L Proposition. H is admissible. Proof. A heuristic H is consistent if it verifies H(S x ) ≤ c(S x , S y )+H(S y )
, where c(S x , S y ) is the minimal cost for paths from S x to S y . A consistent heuristic is also admissible [Pearl, 1984]. The consistency of H can be inductively proven, as shown below. In this proof the notation X \ Y is used, where X and Y are two sets of literals.

X \ Y = X ∩ Y , where Y = { | ∈ V ∪ V ¬ , ∈ Y }.
Base Case. Let σ be a one-step transition from S x = (L x , M) to S y = (L y , M): S x σ -→ S y . The goal of the base case proof is to show that H(S x ) ≤ c(S x , S y ) + H(S y ), where c(S x , S y ) = cost(σ). Two situations are considered:

• σ is a literal flip F . In this case ∈ (L x ∩ M ¬ ) and L y = L x \ { }. Thus:

H(S y ) = ERC((L x \ { }) ∩ M ¬ ) = ERC((L x ∩ M ¬ ) \ { }) Because ∈ (L x ∩ M ¬ ): H(S y ) = ERC((L x ∩ M ¬ ) \ { }) ≥ ERC(L x ∩ M ¬ ) -ERC({ }) Then, H(S x ) ≤ H(S y ) + ERC({ }) which entails that H(S x ) ≤ cost(F ) + H(S y ). • σ is an adaptation rule R = left right, with: left ⊆ L x , since R is applicable on S x ; repairs(R) = left \ right = ∅; and L y = (L x \ left) ∪ right. H(S x ) -H(S y ) = ERC(L x ∩ M ¬ ) -ERC(L y ∩ M ¬ ) ≤ ERC((L x ∩ M ¬ ) \ (L y ∩ M ¬ )). (L x ∩ M ¬ ) \ (L y ∩ M ¬ ) ⊆ repairs(R
) can be proven as shown below:

(L x ∩ M ¬ ) \ (L y ∩ M ¬ ) = (L x ∩ M ¬ ) \ ((L x \ left) ∪ right ∩ M ¬ ) by def. of L y = L x ∩ M ¬ ∩ ((L x ∩ left) ∪ right) ∩ M ¬ = L x ∩ M ¬ ∩ (((L x ∪ left) ∩ right) ∪ M ¬ ) = (L x ∩ M ¬ ∩ ((L x ∪ left) ∩ right)) ∪ (L x ∩ M ¬ ∩ M ¬ ∅ ) = (L x ∩ M ¬ ∩ L x ∩ right ∅ ) ∪ (L x ∩ M ¬ ∩ left ∩ right) = L x ∩ M ¬ ∩ (left \ right) = L x ∩ M ¬ ∩ repairs(R) ⊆ repairs(R) Thus, H(S x ) -H(S y ) ≤ ERC((L x ∩ M ¬ ) \ (L y ∩ M ¬ )) ≤ ERC(repairs(R)), and H(S x ) ≤ ERC(repairs(R)) + H(S y ). Therefore it is sufficient to prove that ERC(repairs(R)) ≤ cost(R), which is proven below. For ∈ repairs(R), ERC({ }) ≤ cost(R) |repairs(R)|
according to the definition of ERC.

Therefore:

ERC(repairs(R)) = ∈repairs(R) ERC({ }) ≤ ∈repairs(R) cost(R) |repairs(R)| = cost(R)
So, in any case, if S x σ -→ S y , H(S x ) ≤ c(S x , S y ) + H(S y ), which proves the base case. Inductive Step. It is assumed that the property is true for a given n ≥ 1:

For any path of length n, from S to T, H(S) ≤ c(S, T) + H(T)

(5.1)

Now, let S x = S 0 σ 1 -→ . . . σn -→ S n σ n+1 ---→ S n+1 = S y be a path of length n + 1. S x σ 1 -→ . . . σn -→
S n is a path of length n, so, according to (5.1):

H(S x ) ≤ c(S x , S n ) + H(S n ) (5.2)
S n σ n+1 ---→ S y is a path of length 1, so, according to the base case:

H(S n ) ≤ c(S n , S y ) + H(S y ) (5.3)
Finally, since c is additive:

c(S x , S y ) = c(S x , S n ) + c(S n , S y ) (5.4)
From (5.2), (5.3) and (5.4) it comes that H(S x ) ≤ c(S x , S y ) + H(S y ) for any path from S x to S y of length n + 1. Therefore, the proposition is proven.

Execution on the Running Example

This section details the execution of the algorithm for the running example defined in Section 5.2:

ψ = a ∧ b AK = {R 1 , R 2 } cost(R 1 ) = cost(R 2 ) = 0.5 µ = ¬a ∧ ¬c R 1 = a ∧ b b ∧ c cost(F ) = 1 for = a R 2 = b ∧ c a ∧ b cost(F a ) = 2
As computed previously, min-branches(ψ) = {{a, b}} and min-branches(µ) = {{¬a, ¬c}}. Figure 5.2 shows the different branches developed by the algorithm. At the initial state S 0 , the cost is 0. The algorithm repairs the clash on the variable a, for a minimal cost of 0.5. Two branches are developed, the first using a flip on a and the second using the rule R 1 . The state S 1 is a final state with a cost of 2. The variable solutionCost is set to that cost of 2. That cost is defined as the best final cost. The state S 2 has a clash on the variable c. To repair that clash, the minimal cost is 0.5. Adding the cost of that state, the cost is lower than solutionCost. Thus, the clash is repaired to possibly find the solution with a lower final cost. To repair the clash on the variable c, the rule R 2 and the flip F c are used. The use of F c leads to a final state S 3 with a final cost of 1.5. That cost becomes the best final cost. The use of R 2 gets back to a state S 4 equivalent to the initial state S 0 but with a cost of 1. To repair the clash on the variable a, the minimal cost is 0.5. As the cost to reach that state plus the cost to repair that clash is equal to solutionCost, the clash on the variable a is again repaired. The state S 5 is reached using F a . That final state is not a best solution because the cost of that state is higher than solutionCost.

The state S 6 is not final but that branch is not developed because the cost to reach that state plus the cost to repair the clash on the variable c is higher than solutionCost. The algorithm returns the solution L 3 ∪ M 3 , i.e. {b, ¬a, ¬c}.

Termination and Complexity

In this section, the termination and complexity of the algorithm are studied when no heuristics is used (H = 0). Since the heuristics introduced in Section 5.4 is admissible, the complexity without heuristics is an upper bound for the complexity with heuristics.

Proposition.

The previously presented adaptation algorithm always terminates. Its complexity in the worst case is in O(4 n × t +1 × (n + log(t))), where n is the number of variables, t = |AK| + |V|, and is the sum of each flip cost divided by the minimum transition cost.

According to [START_REF] Eiter | On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals[END_REF], the complexity of a revision operator is P NP[O(log n)] -hard1 hence this high worst-case complexity of the algorithm is not a surprise.

Proof. Let G be the graph generated by the algorithm: it is a directed acyclic labeled graph (that corresponds to the union of exploration trees from each initial state), whose vertices are labeled by states, and edges are labeled by transitions: if (v, w) is an edge of G, then S x σ -→ S y is a transition where S x = λ(v), S y = λ(w) and σ = λ((v, w)) (λ is the label function associated with G). The roots of G (vertices of rank 0) correspond to the s 0 initial states. Let s k be the numbers of vertices of rank k. s k verifies s k ≤ s 0 t k , where t = n + |AK| is an upper bound of the number of transitions from a given state S (recall that there are n propositional variables and that if a flip F is applicable on S, then F ¬ is not). In order to prove the termination of the algorithm, it is sufficient to prove that G is finite: each step of the loop is executed in finite time and each node of G is considered exactly once.

There exists a solution, i.e. a path p from a vertex labeled by an initial state to another one labeled by a final state. Indeed, let (L 0 , M) be an initial state. Then, the application of all the flips

F for ∈ (L 0 ∩ M ¬ ) ⊆ L 0 leads to a state (L 0 \ (L 0 ∩ M ¬ ), M) = (L 0 ∩ M ¬ , M) which is consistent because L 0 ∩ M ¬ ∩ M ¬ = ∅. Let C F = cost(p).
This involves that there exists (at least) one optimal solution p * : the set {p | p is a path with cost(p) ≤ C F } is finite, so its infimum is reached. Let C * = cost(p * ) and v * be the final vertex of p * . It can be proven that the rank of v * , r * , verifies: cost(σ i ), where σ i is the i th transition of p * . Therefore, C * ≥ r * × mc and then, r * ≤ C * mc ≤ . Since r * is an integer, inequation (5.5) follows. Therefore, each optimal solution has a length that is less or equal to C * mc . Since the graph G is searched by increasing cost G(S) (admitting H = 0), every vertex v of G has a rank lower to this constant. This involves that G is finite and so, the algorithm terminates. Moreover, this involves that the number of vertices N G verifies:

r * ≤ C * mc ≤ C F mc ≤ fc mc = (
N G ≤ r * k=0 s k ≤ r * k=0 s 0 t k = s 0 t r * +1 -1 t -1 ≤ s 0 t r * +1 ≤ s 0 t +1
which gives an upper bound for the number of iterations of the loop in the algorithm. The count of rank 0 vertices, s 0 , is bounded by |min-branches(ψ)| × |min-branches(µ)|, which in the worst case is no greater than 2 n ×2 n = 4 n . It is assumed that each vertex v is stored on a sorted structure using an ordering on F(λ(v)). As such, finding the state S minimizing F(S) is done in constant time, while creating a state is done in logarithmic time w.r.t. the size of the structure, in order of N G . Thus, the complexity of the algorithm is in O(N G log(N G )), and N G is of order O(4 n × t +1 ). More precisely, the complexity of the algorithm is in O(4 n × t +1 × (n + log(t))).

Chapter 6

Implementation

One of the tasks of this internship was to implement the adaptation operator presented in this report. REVISOR [START_REF] Cojan | REVISOR : un ensemble de moteurs d'adaptation de cas par révision des croyances[END_REF] is a Java software library providing several revision engines for different formalisms, available for download on the site http://revisor.loria.fr. Its first version contained three revision engines:

• REVISOR/CLC, that performs revision on Conjunctions of Linear Constraints [START_REF] Blansché | TAAABLE 3: Adaptation of ingredient quantities and of textual preparations[END_REF]. REVISOR/CLC has been implemented by Julien Cojan, Cynthia Florentin and Sophie Pierrat.

• REVISOR/PL, that performs implicant-based revision on Propositional Logic formulae.

• REVISOR/QA, that performs revision in Qualitative Algebra [START_REF] Dufour-Lussier | Text adaptation using formal concept analysis[END_REF]. REVISOR/QA has been implemented by Valmi Dufour-Lussier.

In its second version, REVISOR introduces a new revision engine, REVISOR/PLAK, that performs rule-based and revision-based adaptation on Propositional Logic formulae [START_REF] Personeni | Adaptation de cas propositionnels par réparations fondées sur des connaissances d'adaptation[END_REF], as defined previously in this report. Java version 7 is required to use the REVISOR engines. REVISOR/CLC and REVISOR/QA also require respectively additional libraries and a Perl environment in order to operate properly. Section 6.1 presents the REVISOR/PL revision engine, then Section 6.2 presents REVISOR/PLAK. For both revision engines, a detailed example is presented. Section 6.3 provides an evaluation of REVISOR/PLAK computing time and explain its results.

REVISOR/PL

REVISOR/PL is a revision engine in the Propositional Logic formalism: it implements an implicant-based revision operator using semantic tableaux as defined in Section 2.6. It can also perform -adaptation using that revision operator. Figure 6.1 presents an example in Java code of how REVISOR/PL can be used to compute adaptation of propositional cases. Note that in REVISOR/PL, the ∧, ∨, ¬ and ⇒ connectives are respectively replaced by &, |, ! and >. The code presented solves the following adaptation problem: µ in the form of the disjunction of their prime implicants, REVISOR/PLAK computes ψ AK µ. That means REVISOR/PLAK has not yet an implementation of the min-branches function and prime implicants must be computed through other means.

Figure 6.2 presents an example in Java code on how REVISOR/PLAK can be used to compute adaptation using adaptation rules. Note that the syntax of adaption rules differs from the left right syntax introduced in this report. In REVISOR/PLAK, rules are written as triples of conjunctions of literals in the form context : left * = right. In this example, the goal is to produce a pie recipe without pear, cinnamon or eggs. To this end, a pear pie recipe containing eggs will be used:

Source = pie ∧ pie_shell ∧ pear ∧ sugar ∧ egg Target = pie ∧ ¬pear ∧ ¬cinnamon ∧ ¬egg
REVISOR/PLAK is tasked with the adaptation of Source to solve Target, using the following domain knowledge: DK = (apple ∨ peach ∨ pear) ⇔ fruit Apples, peaches and pears are fruits and, conversely, the only available fruits are apples, peaches and pears. Two recipes are proposed. In both, pears have been replaced by apples and eggs by flour and cider vinegar. For the cinnamon, two choices were available: either vanilla sugar or orange blossom could replace it: since cost(R 5 ) = cost(R 6 ), the disjunction of this possibilities is presented; if cost(R 5 ) < cost(R 6 ), only the orange blossom alternative would be given.

AK = {R 1 , R 2 , R 3 , R 4 , R 5 , R 6 } R 1 = cake ∧ egg cake ∧ banana R 4 = pear apple ∧ cinnamon R 2 = pie ∧ egg pie ∧ flour ∧ cider_vinegar R 5 = cinnamon orange_blossom R 3 = pear peach R 6 =
In order to propose these two recipe REVISOR/PLAK uses either the rules {R 2 , R 4 , R 5 } or {R 2 , R 4 , R 6 }. Note that the order in which the rules can be applied does not affect the results, however R 5 and R 6 cannot be applied before R 4 . Indeed, both R 5 and R 6 needs the presence of the literal cinnamon to be applied, and it is only introduced by the rule R 4 . Thus, 6 adaptations paths are proposed by REVISOR/PLAK:

R 2 , R 4 , R 5 R 2 , R 4 , R 6 R 4 , R 2 , R 5 R 4 , R 2 , R 6 R 4 , R 5 , R 2 R 4 , R 6 , R 2

Evaluation

So far, empirical data shows that the computing time is largely dependent upon (that is the sum of each flip divided by the minimum transition cost, as defined in Section 5.6). However, a million-fold increase of may result in only a tenfold increase of computing time, despite worst-case complexity being exponential with respect to . This shows that actual performance is far better than worse-case complexity may suggest. The current implementation is vulnerable to sets of rules {(left i , right i ) | i ∈ {0, 1, . . . , n}} such that left i ⊆ right i-1 for i ∈ {1, . . . , n} and left 0 ⊆ right n , that is, rules that could potentially create infinitely looping paths. While the algorithm always terminate, the algorithm could generate very long finite paths using such rules, if the total cost of the loop is very small compared to the cost of the solution. The most important factor for computing time is the distance between ψ and µ. That is, having an adequate source case to solve the target case make the adaptation problem much easier to solve. REVISOR/PLAK computing time has been evaluated on randomly generated adaptation problems where the source case is a conjunction of literals and the target case is a formula in DNF. Formulae have been generated with a set of 50 variables. 40 adaptation rules have been provided to perform the adaptation. The current implementation solves 87.5% (with a standard deviation of 4.6 points on series of 50 tests) of tested adaptation problems in less than one second, on a computer with a 2.13Ghz processor and 3GB of available memory. Problems which could not be solved in less than one second usually did not have enough memory available to terminate, while others terminate in 19 milliseconds on average.

Chapter 7

Conclusion and Future Work

Conclusion

The objective of this internship was to design and implement an adaptation algorithm to be used in a case-based reasoning process. Given a problem or target case, and a source case retrieved by the case-based reasoning system, the algorithm had to adapt the latter to solve the problem posed by the target case.

As a result of this internship, an original algorithm for revision-based and rule-based adaptation based on tableaux repairs in propositional logic has been proposed. This algorithm modifies minimally the source case so that it becomes consistent with the target case. The semantic tableaux method is applied separately on the source and target cases. Then the consistent branches are combined, which leads to a set of branches, each of them containing one or more clashes (unless the source case is consistent with the target case and need not to be adapted). Those clashes are repaired with adaptation rules which modify the source case. Adaptation rules allow to substitute a given part of the source case by a formula. If no rule is available a flip on the literal deletes it from the source case. Flips allows the algorithm to always find a solution.

The algorithm is based on the A * procedure: for each literal , the minimal cost to repair a clash on is computed. The heuristic H for a state is defined as the sum, for each clash in this state, of the minimal cost to repair that clash. Thus, at each step, the state developed is the one for which the cost plus the estimated cost to repair the clash is the lowest. Once a solution is found, only states whose cost is lower or equal to the best final cost are developed. This adaptation algorithm has been implemented in the REVISOR/PLAK tool.

Future Work

Belief revision is one of the operations of belief change. There are other ones (see [Peppas, 2008], for a synthesis) such as contraction (ψ • -µ is a belief base obtained by minimally modifying ψ so that it does not entail µ) or integrity constraint belief merging [START_REF] Konieczny | Merging information under constraints: a logical framework[END_REF] (∆ µ ({ψ 1 , . . . , ψ n }) is a belief base obtained by minimally modifying the belief bases ψ i into ψ i such that µ ∧ i ψ i is consistent). A future work consists in studying how the tableaux repair approach presented in this report can be modified for such

••

  Non-negativity: d(x, y) ≥ 0 Identity of indiscernibles: d(x, y) = 0 iff x = y • Symmetry: d(x, y) = d(y, x) • Subadditivity: d(x, z) ≤ d(x, y) + d(y, z)

  Figure 2.3: Applying the tableaux method to ψ = a ∧ b and µ = ¬a ∨ ¬b.

Figure 5 . 1 :

 51 Figure 5.1: Computing the initial states of the running example.

  Output: ψ AK µ in DNF begin // open-states is initiated by initial states with cost 0. open-states ← min-branches(ψ) × min-branches(µ) G(S) evaluates to +∞ by default G(S) ← 0 for each S ∈ open-states F(S) evaluates to G(S) + H(S)

  ← open-states \ {(L c , M c )} end return Solutions end Algorithm 1: Algorithm of adaptation based on tableaux repairs.

Figure 5 . 2 :

 52 Figure 5.2: Application of the algorithm on the running example.

  5.5) where mc = min{cost(σ) | σ ∈ AK ∪ {F for every literal }}, fc = ∈V∪V ¬ cost(F ), and x is the integer part of x Indeed, C * = r * i=1

Figure 6 . 2 :

 62 Figure 6.2: Adapting a pear pie recipe with REVISOR/PLAK.

  cinnamon vanilla_sugarEach rule has a cost of 0.3 except R 3 which has a cost of 0.7. Indeed, pears are more similar to apples than peaches. Each flip has a cost of 1.REVISOR/PLAK gives the following result (in less than 20ms):((cider_vinegar & flour & orange_blossom & fruit & !cinnamon & pie_shell & !pear & pie & !egg & sugar & apple) | (cider_vinegar & flour & vanilla_sugar & fruit & !cinnamon & pie_shell & !pear & pie & !egg & sugar & apple))Which can be expressed in propositional logic as:pie ∧ pie_shell ∧ sugar ∧ fruit ∧ ¬egg ∧ flour ∧ cider_vinegar ∧ ¬pear ∧ apple ∧ ¬cinnamon ∧ (vanilla_sugar ∨ orange_blossom)

Note that revision-based adaptation does not takes its name from the Revise step of the R4 Model, but rather from the belief revision process described in Section 1.2.

Here, the size of a formula relates to the total amount of literals occurrences in that formula. For example, the formula a is of size 1, a ∧ a is of size

2, a ∧ (b ∨ ¬a) is of size 3.

Solving a problem with several initial states, represented by the set S0, is equivalent to solving this problem with only one initial state, and null-cost transitions from this initial state to each state of S0.

More precisely, the complexity of the Dalal revision operator Dalal is P NP[O(log n)] -complete and the presented algorithm can be used for computing Dalal : Dalal = AK with AK = ∅ and cost(F ) = 1 for each literal .

Chapter 5

Algorithm of Adaptation Based on Tableaux Repairs

The adaptation algorithm is based on the revision of the source case by the target case, both w.r.t. the domain knowledge. As such, the algorithm performs the revision of a formula ψ by a formula µ, with: ψ = DK ∧ Source µ = DK ∧ Target and so:

CompletedTarget = ψ AK µ Section 5.1 presents the inputs and outputs of the algorithm. Then a running example is introduced in Section 5.2, and its execution its detailed throughout this Chapter. Section 5.3 presents the algorithm, which uses an heuristic function H, that is defined and proven to be admissible in Section 5.4. Section 5.5 details an example and Section 5.6 studies the termination and the complexity of the algorithm.

Inputs and Output

The inputs of the algorithm are:

• Two propositional formulae ψ and µ in NNF.

• A set AK of adaptation rules.

• A function cost that associates to each adaptation rule and each literal flip a positive real number.

The algorithm outputs ψ AK µ in DNF.

That is, REVISOR/PL has to produce a pie recipe without apple, through minimal modifications of an apple pie recipe. To this end, it uses the domain knowledge that apples and pears are fruits and, conversely, the only available fruits are apples and pears.

// Set the cost of variable flip to 1 RevisorPL.resetWeights (); // Initialize the source and target cases, and the domain knowledge PLFormula source = RevisorPL.parseFormula ("pie & apple & pie_shell & sugar"); PLFormula target = RevisorPL.parseFormula ("pie & !apple"); PLFormula dk = RevisorPL.parseFormula ("(pear | apple > fruit) & (fruit > pear | apple)"); // Compute the adaptation of the source case to solve the target case PLFormula result = RevisorPL.adapt (source, target, dk); RevisorPL.print (result); Thus the result of the adaptation is:

That is, a pear pie recipe. Apples are removed from the original recipe. However, the original recipe is a fruit pie recipe (according to the domain knowledge: REVISOR/PL must either replace the apples with another fruit, or solve the contradiction that a fruit pie contains no fruit. Adding pears to the recipe does not cause a contradiction, and does not add any costs. Then the best solution is to replace apples with pears.

REVISOR/PLAK

REVISOR/PLAK is a revision engine in the Propositional Logic formalism, based on the previous engine REVISOR/PL. REVISOR/PLAK implements the algorithm revise previously presented in Section 5.3. Given a set of adaptation rules AK and two propositional formulae ψ and belief change operations. This would have an impact on case-based reasoning; in particular, integrity constraint belief merging can be used for multiple case adaptation (i.e., combining several source cases to solve the target case), see [START_REF] Cojan | Belief Merging-based Case Combination[END_REF] for details.

Optimizing the algorithm. One downside of the algorithm is that in many practical situations, the order in which rules are applied does not affect the result: then the algorithm explores redundant adaptation paths. A future work may consist in finding a way to generate less equivalent adaptation paths, which would importantly decrease the computing time. For example, the order in which two consecutive flips are applied does not change the result obtained. Thus, it could be possible to apply consecutive flips only in one arbitrarily chosen order. Then, a similar approach could be used on some sets of adaptation rules.

Currently, the implemented algorithm may generate states already explored, as shown in the running example (see figure 5.2). Because A * is a best-first search algorithm and cost are strictly positive, cycles are often ignored quickly. Still, exploring states no more than once would result in an improvement in computing time. Though, checking if a state has already been explored is not inexpensive in memory and computing time: that implies storing every explored state in a data structure, and comparing every newly generated state to the states in that structure. A future work may consist in evaluating the benefits and drawbacks of implementing that feature. Another possible approach to not explore cycles would be to detect which rules of AK create cycles, and to check for pre-exploration only when those rules are used.