# A Knowledge Representation Approach for Reasoning with Adaptation Rules

Nicolas François<fnref n="1" /> and Jean Lieber<fnref n="2" />

<figure><img src="image_1.png" /></figure>

jean.lieber@loria.fr

**Abstract.** The adaptation knowledge container of a CBR system is often represented by adaptation rules that can be learned from the case base using various approaches proposed in the CBR literature. However, the formal representation of such rules has been much less investigated. This paper introduces a formalism for representing such rules, given a formalism that can be used to express cases in an attribute-value formalism. One benefit of this study is a case retrieval algorithm for which the retrieved case is the best one with respect to adaptation (i.e. the one that requires the least adaptation effort as defined by the cost of adaptation rule sequences). Moreover, when attributes have Boolean range, its complexity is independent of the size of the case base.

**Keywords:** case-based reasoning, knowledge representation, adaptation, adaptation-guided retrieval

## 1 Introduction

Adaptation is considered, for some members of the case-based reasoning (CBR [10]) community as a key step for this type of reasoning. This paper follows that tradition and considers it from a perspective of knowledge representation: How can the representation of adaptation knowledge be useful for CBR?

To address this question, the starting point has been some work on adaptation knowledge learning (AKL). AKL has a long history in the field of CBR, at least since the seminal paper of K. Hanney and M. T. Keane [4]. In general, it is based on what is called the *difference heuristics* in [5]: the differences between pairs of cases in the case base are used to constitute a training set for a machine learning system. In particular, a notation has been introduced to represent such differences: it consists of expressions of the form $a^v$ where a is a case attribute and v is a *variation symbol*. For example, in the cooking domain, to express that, in a dessert recipe, 2 eggs can be substituted by 1 banana, the following set of such expressions can be used:

`{dessert=<fnref n="1" />, #eggs⁻<fnref n="2" />, #bananas⁺<fnref n="1" />}`

<footnote n="1">¹ Lycée public Chopin, F-54000 Nancy, France</footnote>

<footnote n="2">² Université de Lorraine, CNRS, LORIA, F-54000 Nancy, France</footnote>
Here, *dessert* is a Boolean attribute: it takes as potential values 0 and 1 (assimilated to *false* and *true*), whereas *#eggs* and *#bananas* are integer attributes.

This notation has been used in rather old studies [1] as well as in recent
work [8]. To this notation (or syntax), a semantics can be associated, giving
birth to logical formalisms, the *logics of variation*, in which adaptation rules can
be represented: that is the first objective of this paper. Its second objective is to
explain how such a logic can be beneficial to CBR.

Section 2 presents some preliminaries about CBR. The case base and the do-
main knowledge can be represented in a so-called *static logic*; Section 3 presents
the static logic (*G*L, |=) that is expressive enough to represent attribute-value
pairs (with Boolean and numerical attributes) and taxonomies (and beyond).
Section 4 defines the variation logic (ΔG*, |=), which is based on (G*, |=): its
syntax, semantics, and basic properties. Section 5 presents how adaptation rules
can be defined using this logic. Based on these notions, an algorithm for perform-
ing single case retrieval is presented in Section 6, which has two notable features.
First, it guarantees that the retrieved case is the best case for adaptation (the
best in a sense related to the effort of adaptation defined by the cost associated
with the adaptation rules). Second, when every attribute has a Boolean range,
its time complexity is independent of the size of the case base. Section 7 discusses
this contribution, concludes, and briefly presents some future directions of work.

**Remark.** This paper contains some results without their proofs: these latters
can be found in the extended version of this paper, which is available online [3].

## 2 Preliminaries

This section presents some notations and some assumptions, mainly about CBR.

2.1 Mathematical notions and notations

B, the set of Booleans, is assimilated to the pair of integers $B = \{0,1\}$ (0 stands for false and 1, for true). $\mathbb{Z}$ is the set of integers (positive and negative). For $a,b \in \mathbb{Z}$ with $a \le b$, $[[a,b]] = \{n \in \mathbb{Z} | a \le n \le b\}$. $\mathbb{Q}$ is the set of rational numbers.

An *abelian group* is a pair $(\mathcal{G}, +)$ where $\mathcal{G}$ is a nonempty set and $+$ is an internal binary operation on $\mathcal{G}$ ($+ : (r, s) \in \mathcal{G} \mapsto r + s \in \mathcal{G}$) such that (1) it has an identity element denoted by 0 (for each $r \in \mathcal{G}$, $r + 0 = 0 + r = r$), (2) every $r \in \mathcal{G}$ has an inverse element $s$ ($r + s = s + r = 0$), $s$ is denoted by $-r$, (3) $+$ is associative (($r+s)+t = r+(s+t)$ for every $r, s, t \in \mathcal{G}$), and (4) $+$ is commutative ($r+s = s+r$ for every $r, s \in \mathcal{G}$). For $r, s \in \mathcal{G}$, $r-s$ is an abbreviation of $r+(-s)$.

With the usual $+$ on numbers, $(\mathbb{Q}, +)$ and $(\mathbb{Z}, +)$ are groups. $(\{0, 1, 2\}, +)$ is not a group since $+$ is not internal (e.g. $2 \in \{0, 1, 2\}$ but $2 + 2 = 4 \notin \{0, 1, 2\}$).
## 2.2 Notions, notations and assumptions about CBR

These preliminaries on CBR do not reflect the whole variety of CBR systems; in particular, in this paper, a case is considered as a problem-solution pair. A *problem* is, by definition, an element x of a given set $\mathcal{P}$. A *solution* is, by definition, an element y of a given set $\mathcal{S}$. It is assumed that a relation $\rightsquigarrow$ is defined on $\mathcal{P} \times \mathcal{S}$ that is not completely known to the CBR system, and that reads “has for solution”. A *case* is an ordered pair $(x, y) \in \mathcal{P} \times \mathcal{S}$. A *correct case* is a case $(x, y)$ such that $x \rightsquigarrow y$.

*Process model.* A CBR session consists of solving a problem called *target problem* and denoted by $x^{\text{tgt}}$. A common process for CBR consists in (1) selecting a source case $(x^s, y^s)$ that is considered similar to $x^{\text{tgt}}$ (case retrieval), (2) modifying this retrieved case in order to propose a solution $y^{\text{tgt}}$ to $x^{\text{tgt}}$ (case adaptation), and other steps after these problem solving steps, which are not considered in this paper. In many systems, several cases are retrieved and then adapted; in this paper, only single case retrieval and single case adaptation are considered.

*Knowledge model.* A CBR system is based on four knowledge containers. The case base CB is a finite set of correct cases. A case of CB is called *source case* and is denoted by $(x^s, y^s)$. It is assumed that each source case represents a *specific* problem-solving episodes.

Domain knowledge DK expresses knowledge about the vocabulary in which cases are expressed. It can be seen as a set of constraints on this vocabulary. For example, if “apple” and “fruit” belong to this vocabulary, the piece of domain knowledge “Every apple is a fruit.” indicates that a case involving an apple that is not a fruit is incorrect.

The retrieval knowledge expresses the knowledge about case retrieval. It often takes the form of a dissimilarity measure *diss* between the source cases and the target problem: to $(x^s, y^s) \in CB$ and $x^{\text{tgt}} \in \mathcal{P}$ is associated a nonnegative number *diss*($x^s, y^s$), $x^{\text{tgt}}$), and the retrieval aims at finding the $(x^s, y^s) \in CB$ that minimizes this value.

The adaptation knowledge AK is used during adaptation. In this paper, it takes the form of a finite set of adaptation rules *ar*. Generally speaking, such a rule can be interpreted as a mapping associating to $((x^s, y^s), x^{\text{tgt}}) \in (\mathcal{P} \times \mathcal{S}) \times \mathcal{P}$ a $y^{\text{tgt}} \in \mathcal{S} \cup \{\text{failure}\}$. If $y^{\text{tgt}} = \text{failure}$, that means that the adaptation rule is not applicable to the adaptation problem $((x^s, y^s), x^{\text{tgt}})$. In other situations, the case $(x^{\text{tgt}}, y^{\text{tgt}})$ is not necessarily correct: CBR is, in general, a hypothetical reasoning. To increase the chances of correctness, a positive value *cost* associated with *ar* is given: the lower *cost* is, the higher $(x^{\text{tgt}}, y^{\text{tgt}})$ is likely to be correct.

An adaptation can be performed in several steps, using *adaptation paths*, that is, sequences of adaptation rules [6]: given an adaptation problem $((x^s, y^s), y^{\text{tgt}})$, it can be solved using an adaptation path $\text{AP} = \text{ar}^1; \text{ar}^2; \dots; \text{ar}^q$ if the sequential application of $\text{ar}^k$ ($k$ taking values 1 to $q$) starting from $(x^s, y^s)$ leads to the case $(x^{\text{tgt}}, y^{\text{tgt}})$. There may be several adaptation paths for a given adaptation problem, and the selection among them is made according to the cost. The cost
of an adaptation path is assumed to be additive: cost(AP) is the sum of the cost of the ar$^k$.

*Knowledge representation.* CB and DK are knowledge containers about what *is*, or *is not*, a case: an ($x^s$, $y^s$) ∈ CB indicates that $y^s$ is a (correct) solution of $x^s$, whereas a piece of knowledge **α** from DK is a constraint on what a correct case has to be. By contrast, the retrieval knowledge is about comparing cases, and adaptation knowledge AK is about transformations, about how a case *changes* into another case.

For these reasons, two types of logic for representing knowledge in CBR are distinguished: the *static logics* for CB and DK, and the *variation logics* for adaptation knowledge.

In this paper, the static logic considered is ($GL, \models$), presented in Section 3 and used for both CB and DK. The variation logic ($\Delta GL, \models$) for representing adaptation knowledge is based on the former logic and is presented in Section 4.

## 3 The static logic ($GL, \models$)

The static logic can be any classical logic used in knowledge representation, such as propositional logic, a description logic, etc. However, the study presented in this paper is about the logic ($GL, \models$) described below, together with a discussion about its expressivity. This logic is parametrized by $\mathcal{G}$ such that either ($\mathcal{G}, +$) is an infinite abelian group (e.g. $\mathcal{G} = \mathbb{Q}$ or $\mathcal{G} = \mathbb{Z}$) or $\mathcal{G}$ is a subset of $\mathcal{H}$ such that ($\mathcal{H}, +$) is an infinite abelian group (e.g. $\mathcal{G} = \mathbb{B}$: in this case, ($\mathcal{G}\mathcal{L}, \models$) corresponds to propositional logic).<fnref n="1" />

### 3.1 Syntax of ($GL, \models$)

Let $\mathcal{V}$ be a given finite non-empty set of symbols: an $a \in \mathcal{V}$ is called a *variable*. An *atom* of ($GL, \models$) is an expression of the form ($a = r$) where $a \in \mathcal{V}$ and $r \in \mathcal{G}$. A formula of ($GL, \models$) is an atom or one of the forms $\perp$, $\top$, $\neg\alpha$, $\alpha \wedge \beta$ and $\alpha \vee \beta$ where $\alpha$ and $\beta$ are two formulas of this logic. Other connectives can be defined in the usual way as abbreviations. For example, the $\rightarrow$ connective is defined by $\alpha \rightarrow \beta = \neg\alpha \vee \beta$. $GL$ is the set of formulas for this logic. The set of variables that occur in $\alpha \in GL$ is denoted by $\mathcal{V}(\alpha)$.

A *literal* is either an atom (or positive literal) or of the form $\neg\alpha$ where $\alpha$ is an atom (negative literal). A *cube* is a conjunction of literals: it has the form $\ell_1 \wedge \ell_2 \wedge \dots \wedge \ell_p$ where $\ell_k$ is a literal for $k \in [1, p]$. A formula is under DNF (disjunctive normal form) if it is a disjunction of cubes: $\gamma_1 \vee \gamma_2 \vee \dots \vee \gamma_q$ where $\gamma_k$ is a cube for $k \in [1, q]$.

<footnote n="1">¹ The fact that $\mathcal{G}$ is infinite is a technical assumption useful for some proofs. In fact, it is not difficult to extend the approach to finite groups, although it would make the explanations more tedious.</footnote>
## 3.2 Semantics of ($\mathcal{GL}$, $|=$)

An interpretation $\mathcal{I}$ is a mapping from $\mathcal{V}$ to $\mathcal{G}$. Let $\Omega$ be the set of all interpretations. For $\mathcal{I} \in \Omega$ and $\alpha \in \mathcal{GL}$, the relation “$\mathcal{I}$ is a model of $\alpha$” (denoted by $\mathcal{I} \models \alpha$) is defined recursively as follows (for $a \in \mathcal{V}$, $r \in \mathcal{G}$ and $\alpha, \beta \in \mathcal{GL}$):

- $\mathcal{I} \models \bot$ never holds;

- $\mathcal{I} \models \top$ always holds;

- $\mathcal{I} \models (a = r)$ if $\mathcal{I}(a) = r$;

- $\mathcal{I} \models \neg \alpha$ if $\mathcal{I} \not\models \alpha$;

- $\mathcal{I} \models \alpha \wedge \beta$ if $\mathcal{I} \models \alpha$ and $\mathcal{I} \models \beta$;

- $\mathcal{I} \models \alpha \vee \beta$ if $\mathcal{I} \models \alpha$ or $\mathcal{I} \models \beta$.

For $\alpha \in \mathcal{GL}$, let $\mathcal{M}(\alpha)$ be the set of models of $\alpha$. $\alpha$ is satisfiable (or consistent) if $\mathcal{M}(\alpha) \neq \emptyset$ and $\alpha$ is a tautology if $\mathcal{M}(\alpha) = \Omega$. For example, $\bot$ is unsatisfiable and $\top$ is a tautology. The relation $\models \alpha \models \beta$ means that $\mathcal{M}(\alpha) \subseteq \mathcal{M}(\beta)$. The relation $\models \alpha \models \beta$ means that $\mathcal{M}(\alpha) = \mathcal{M}(\beta)$. If $\mathcal{B}$ is a set of formulas, $\mathcal{M}(\mathcal{B}) = \bigcap \{\mathcal{M}(\alpha) \mid \alpha \in \mathcal{B}\}$. Then $\mathcal{B} \models \alpha$ means that $\mathcal{M}(\mathcal{B}) \subseteq \mathcal{M}(\alpha)$.

## 3.3 About the expressivity of ($\mathcal{GL}$, $|=$)

Each variable $a$ of ($\mathcal{GL}$, $|=$) has the same range $\mathcal{G}$: for every $\mathcal{I} \in \Omega$, $\mathcal{I}(a) \in \mathcal{G}$. A slight modification of ($\mathcal{GL}$, $|=$) consists in specifying the range of each variable (e.g. $\mathbb{B}$, $\mathbb{Z}$, $\mathbb{Q}$, an integer interval $[m, n]$ or a rational interval $[r, s]$ — $m, n \in \mathbb{Z}$, $r, s \in \mathbb{Q}$). Therefore, this formalism contains attribute-value formalisms (with attribute ranges limited to numbers, Booleans, and enumerated type) and hierarchies (a hierarchy being represented by a set of implications, e.g. $(\mathbf{apple} = 1) \rightarrow (\mathbf{fruit} = 1)$ states that every apple is a fruit). For the sake of simplicity, in this study, we stick to static logic ($\mathcal{GL}$, $|=$), considering that the extension with variable types should not be difficult to integrate.

## 3.4 Representing cases in ($\mathcal{GL}$, $|=$)

According to Section 2, the sets $\mathcal{P}$ and $\mathcal{S}$ are assumed to be disjoint. This suggests partitioning the set of variables into $\{\mathcal{V}_\mathcal{P}, \mathcal{V}_\mathcal{S}\}$: $\mathcal{V}_\mathcal{P}$ (resp., $\mathcal{V}_\mathcal{S}$) is the set of problem variables (resp., solution variables). Thus, a problem (resp., a solution) is represented by a formula whose set of variables is in $\mathcal{V}_\mathcal{P}$ (resp., in $\mathcal{V}_\mathcal{S}$). So, a case $(\mathbf{x}, \mathbf{y}) \in \mathcal{P} \times \mathcal{S}$ can be written $\mathbf{x} \wedge \mathbf{y}$: finding the problem part $\mathbf{x}$ and the solution part $\mathbf{y}$ of $\mathbf{x} \wedge \mathbf{y}$ is easy since $\mathcal{V}_\mathcal{P} \cap \mathcal{V}_\mathcal{S} = \emptyset$.

Moreover, it has been assumed that the source cases $(\mathbf{x}^s, \mathbf{y}^s)$ represent specific pieces of experience. This means that for every $(\mathbf{x}^s, \mathbf{y}^s) \in \mathcal{CB}$, $\mathcal{M}(\mathbf{x}^s \wedge \mathbf{y}^s)$ is a singleton $\{\mathcal{I}^s\}$. Therefore, $\mathbf{x}^s$ and $\mathbf{y}^s$ can be written as atom conjunction on all variables of, respectively, $\mathcal{V}_\mathcal{P}$ and $\mathcal{V}_\mathcal{S}$: $\mathbf{x}^s \equiv \bigwedge_{a \in \mathcal{V}_\mathcal{P}} (a = \mathcal{I}^s(a))$ and $\mathbf{y}^s \equiv \bigwedge_{a \in \mathcal{V}_\mathcal{S}} (a = \mathcal{I}^s(a))$.

# 4 The variation logic ($\Delta\mathcal{GL}$, $|=$)

Given a static logic that can be used to represent cases and domain knowledge, a variation logic can be defined for representing, in particular, adaptation
knowledge. This section describes the variation logic $(\Delta GL, |=$) built from the static logic $(GL, |=$): its syntax, its semantics, some of its properties, and some operators on these logics that are useful for representing adaptation rules.

## 4.1 Syntax of $(\Delta GL, |=$)

To start with an example, let $\varphi = a^{+5} \wedge \neg b^{8\bullet} \wedge b^{\bullet 2}$ be a formula of this logic, for $G = \mathbb{Z}$. $\varphi$ indicates a change in the attribute $a$ from a value $r$, for some $r \in \mathbb{Z}$, to the value $r + 5$, and a change in the attribute $b$ from any value different from 8 to the value 2. The expressions $+5$, $8\bullet$, and $\bullet 2$ that occur in $\varphi$ are called variation symbols.

More generally, the set of variation symbols is defined by:

$$ \mathcal{D} = \{+r, r\bullet, \bullet r \mid r \in G\} $$

An extra variation symbol $-r$ is defined as an abbreviation of $+(-r)$.

An atom of $(\Delta GL, |=$) is an expression of the form $a^v$ where $a$ is a variable and $v$ is a variation symbol. A formula of $(\Delta GL, |=$) is an atom of this logic or of one of the forms $\perp$, $\top$, $\neg\varphi$, $\varphi\wedge\psi$ and $\varphi\vee\psi$ where $\varphi$ and $\psi$ are two formulas of this logic. The other connectives are defined as abbreviations. The set of formulas is denoted by $\Delta GL$. A variation formula is an element of $\Delta GL$. The set of variables that occur in $\varphi \in \Delta GL$ is denoted by $V(\varphi)$.

A positive literal of $(\Delta GL, |=$) is an atom $a^v$ of this logic. A negative literal is of the form $\neg a^v$ where $a^v$ is an atom. A cube of this logic is a conjunction of literals. $\perp$ is also considered as a cube ($\perp$ can be seen as the conjunction $A \wedge \neg A$ where $A$ is a fixed and arbitrarily chosen atom).

## 4.2 Semantics of $(\Delta GL, |=$)

Any variation symbol $v$ is interpreted as a binary relation over $G$. Formally, to every $v \in \mathcal{D}$ is associated $\langle v \rangle \subseteq G \times G$ defined in the following way (for $r \in G$):

$$ \langle +r \rangle = \{(x, y) \in G^2 \mid y = x + r\} \quad \langle r\bullet \rangle = \{(r, x) \mid x \in G\} \quad \langle \bullet r \rangle = \{(x, r) \mid x \in G\} $$

Let $\Delta\Omega = \Omega \times \Omega$ be the set of interpretations used to define the semantics of $(\Delta GL, |=$): an interpretation of $\Delta\Omega$ is therefore an ordered pair $(\mathcal{I}, \mathcal{J})$ of $\Omega$. In the following, $(\mathcal{I}, \mathcal{J})$ is simply written as $\mathcal{IJ}$.

The fact that $\mathcal{IJ} \in \Delta\Omega$ is a model of a $\varphi \in \Delta GL$ is defined recursively as follows:

- $\mathcal{IJ} \models a^v$ if $(\mathcal{I}(a), \mathcal{J}(a)) \in \langle v \rangle$, for any atom $a^v$ of $(\Delta GL, |=$);

- $\mathcal{IJ} \models \neg\varphi$ if $\mathcal{IJ} \not\models \varphi$, for $\varphi \in \Delta GL$;

- $\mathcal{IJ} \models \varphi \wedge \psi$ if $\mathcal{IJ} \models \varphi$ and $\mathcal{IJ} \models \psi$, for $\varphi, \psi \in \Delta GL$;

- $\mathcal{IJ} \models \varphi \vee \psi$ if $\mathcal{IJ} \models \varphi$ or $\mathcal{IJ} \models \psi$, for $\varphi, \psi \in \Delta GL$.
The set of models of $\varphi \in \Delta\mathcal{G}\mathcal{L}$ is denoted by $\mathcal{M}(\varphi)$. For a knowledge base $\mathcal{B}$ of $(\Delta\mathcal{G}\mathcal{L}, \models)$, $\mathcal{M}(\mathcal{B}) = \bigcap\{\mathcal{M}(\varphi) \mid \varphi \in \mathcal{B}\}$. Then, the entailment is defined as usual: $\varphi \models \psi$ if $\mathcal{M}(\varphi) \subseteq \mathcal{M}(\psi)$ and $\mathcal{B} \models \varphi$ if $\mathcal{M}(\mathcal{B}) \subseteq \mathcal{M}(\psi)$. Finally, $\varphi$ is satisfiable (or consistent) means that $\mathcal{M}(\varphi) \neq \emptyset$.

In the introduction, another variation symbol was used: $=r$ (for $r \in \mathcal{G}$). It has the following semantics (for $a \in \mathcal{V}$): $\mathcal{I}\mathcal{J} \models a^{=r}$ if $\mathcal{I}(a) = \mathcal{J}(a) = r$. Thus, $a^{=r}$ can be seen as an abbreviation of the cube $a^{r\bullet} \wedge a^{\bullet r} \wedge a^{\bullet 0}$.

## 4.3 Basic properties of $(\Delta\mathcal{G}\mathcal{L}, \models)$

**Proposition 1.** Given a conjunction of two literals $\ell_1$ and $\ell_2$ on the same variable $a$, a third literal $\ell_3$ can be deduced for some forms of the literals $\ell_1$ and $\ell_2$ (for $r, s \in \mathcal{G}$), thus $\ell_1 \wedge \ell_2 \equiv \ell_1 \wedge \ell_2 \wedge \ell_3$:

$$ \left. \begin{array}{lclcl} a^{r\bullet} \wedge a^{\bullet s} & \models & a^{\bullet(s-r)} & & a^{r\bullet} \wedge a^{s\bullet} & \models & a^{\bullet(r+s)} \\ a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(s-r)} & & a^{r\bullet} \wedge \neg a^{s\bullet} & \models & \neg a^{\bullet(r-s)} \\ a^{\bullet r} \wedge \neg a^{s\bullet} & \models & \neg a^{\bullet(r-s)} & & a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(r+s)} \\ & & & & a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(r+s)} \end{array} \right| \quad (1) $$

**Definition 1 (Normal forms DNF and DNFNC).** A variation formula $\varphi$ is in DNF (disjunctive normal form) if it is a disjunction of cubes: $\varphi = \theta_1 \lor \theta_2 \lor \dots \lor \theta_p$ where $\theta_k$ is a cube.

Let $\theta$ be a $(\Delta\mathcal{G}\mathcal{L}, \models)$ cube with a sole variable $a$. $\theta$ is normal if one of the following conditions holds

(i) $\theta = \perp$;

(ii) $\theta$ contains exactly 3 positive literals, of the forms $a^{r\bullet}$, $a^{\bullet s}$ and $a^{\bullet t}$ with $r, s, t \in \mathcal{G}$ and $t = s - r$, and it does not contain any negative literal;

(iii) $\theta$ contains exactly 1 positive literal $a^v$ and $p$ negative literals ($p \in \mathbb{N}$) $m_1, m_2, \dots, m_p$ that use variation symbols of a different form from the form of $v$ (e.g. if $v = \bullet r$ then $m_k = \neg a^w$ with $w \neq \bullet s$ for any $s \in \mathcal{G}$); furthermore, for every negative literal $\neg a^w$, $\theta$ contains also the consequence $\neg a^x$ of $a^v \wedge \neg a^w$ according to proposition 1 (e.g. if $v = \bullet r$ and $w = s\bullet$, then $x = \bullet (s + r)$);

(iv) $\theta$ contains only negative literals of any kind.

Let $\theta$ be a $(\Delta\mathcal{G}\mathcal{L}, \models)$ cube. For a, a variable occurring in $\theta$, let $\theta_a$ be the conjunction of literals of $\theta$ with variable a. $\theta$ is a normal cube if every $\theta_a$ is normal, for each a, variable of $\theta$.

A formula $\varphi \in \Delta\mathcal{G}\mathcal{L}$ is under DNFNC (DNF with normal cubes) if it is under DNF and if every cube composing it is normal.

**Proposition 2.** Every formula $\varphi \in \Delta\mathcal{G}\mathcal{L}$ can be put under DNF and under DNFNC: there exists $\varphi_{DNF} \in \Delta\mathcal{G}\mathcal{L}$ (resp. $\varphi_{DNFNC} \in \Delta\mathcal{G}\mathcal{L}$) that is under DNF (resp. DNFNC) such that $\varphi \equiv \varphi_{DNF}$ (resp. $\varphi \equiv \varphi_{DNFNC}$).

The fact that $\varphi$ can be put in DNF is proven as it is proven, e.g., in propositional logic. The fact that any cube can be normalized relies in particular on proposition 1.
As in many logics, the entailment problem and the satisfiability problem are tightly linked in $(\Delta\mathcal{G}\mathcal{L}, \models)$. For example, $\{\varphi_1, \varphi_2\} \models \psi$ iff $\varphi_1 \wedge \varphi_2 \wedge \neg\psi$ is not satisfiable. Now, the satisfiability problem can be computed using the principles of the tableaux method (see e.g. [11]), which, with a logic using propositional connectives, amounts to build a DNF formula represented by a tree (each branch of the tree represents a cube). The following proposition is then useful for designing an algorithm based on the tableaux method for $(\Delta\mathcal{G}\mathcal{L}, \models)$:

**Proposition 3.** *The following results can be used to determine whether a variation formula is satisfiable or not:*

(a) For $\varphi \in \Delta\mathcal{G}\mathcal{L}$, let $\varphi_{\text{DNF}}$ be a formula under DNF such that $\varphi_{\text{DNF}} \equiv \varphi$. Then $\varphi$ is satisfiable iff $\varphi_{\text{DNF}}$ is satisfiable.

(b) Let $\varphi \in \Delta\mathcal{G}\mathcal{L}$ be a formula under DNF: $\varphi = \theta_1 \lor \theta_2 \dots \lor \theta_p$ where each $\theta_k$ is a cube of $(\Delta\mathcal{G}\mathcal{L}, \models)$. Then $\varphi$ is satisfiable iff at least one $\theta_k$ is satisfiable ($k \in \llbracket 1, p \rrbracket$).

(c) Let $\theta$ be a normal cube of $(\Delta\mathcal{G}\mathcal{L}, \models)$. For a, any variable occurring in $\theta$, let $\theta_a$ be the conjunction of the literals of $\theta$ having a as variable. Then $\theta$ is satisfiable iff every $\theta_a$ is satisfiable.

(d) A normal cube $\theta_a$ with only one variable is satisfiable iff $\theta_a \neq \perp$ (this means that if any of the conditions (ii), (iii) and (iv) of definition 1 holds, then $\theta_a$ is satisfiable).

## 4.4 Operators on $(\Delta\mathcal{G}\mathcal{L}, \models)$

This section presents different operators on the logic $(\Delta\mathcal{G}\mathcal{L}, \models)$ that are used in the next sections. Each of them has a semantical definition and satisfies the principle of irrelevance of syntax: if a formula occurring in the definition of an operator is replaced with an equivalent formula, then the result of applying the operator is unchanged up to the logical equivalence. Each of these operators is either defined within a classical definition or within a proposition which states its existence. The proofs of the propositions are given in the report [3]. Then, the ways the operators are computed are described when the formulas involved are cubes.

A variation formula $\varphi$ can be seen as a representation of a binary relation on $\Omega$, since $M(\varphi) \subseteq \Omega \times \Omega$. The following proposition shows that the inverse of a relation $M(\varphi)$ can be represented by a variation formula $\overleftarrow{\varphi}$.

**Proposition 4.** For every $\varphi \in \Delta\mathcal{G}\mathcal{L}$ there exists a variation formula denoted by $\overleftarrow{\varphi}$ such that

$$M(\overleftarrow{\varphi}) = \{\mathcal{J}\mathcal{I} \mid \mathcal{I}\mathcal{J} \in M(\varphi)\}$$

In other terms, $\mathcal{J}\mathcal{I} \models \overleftarrow{\varphi}$ iff $\mathcal{I}\mathcal{J} \models \varphi$.

The computation of $\overleftarrow{\varphi}$ is linear: it consists in replacing every occurrence of a variation symbol $v$ by $\overleftarrow{v}$ according to the following equalities:

$$\overleftarrow{\cdot}r = -r \qquad \overleftarrow{\cdot}v = \cdot r \qquad \overleftarrow{\cdot}r = r \cdot \qquad (\text{for } r \in \mathcal{G})$$

For example, $\overleftarrow{a^{+1} \wedge a^{\bullet 2} \wedge c^{-2}} = a^{-1} \wedge a^{2 \bullet} \wedge c^{+2}$.
**Proposition 5.** For every $\alpha, \beta \in \mathcal{GL}$ there exists a formula of $(\Delta\mathcal{GL}, \models)$ denoted by $\alpha \triangleright \beta$ and read “$\alpha$ becomes $\beta$”, such that $\mathcal{M}(\alpha \triangleright \beta) = \mathcal{M}(\alpha) \times \mathcal{M}(\beta)$.

In other terms, $\mathcal{I}\mathcal{J} \models \alpha \triangleright \beta$ iff $\mathcal{I} \models \alpha$ and $\mathcal{J} \models \beta$.

Now, let $\bigwedge_{i=1}^p \ell_i$ and $\bigwedge_{j=1}^q m_j$ be two cubes: $\ell_1, \ell_2, \dots, \ell_p, m_1, m_2, \dots, m_q$ are $p+q$ literals. The application of $\triangleright$ on these cubes can be computed this way:

$$ \left( \bigwedge_{i=1}^{p} \ell_i \right) \triangleright \left( \bigwedge_{j=1}^{q} m_j \right) \equiv \left( \bigwedge_{i=1}^{p} \ell_i \triangleright \top \right) \wedge \left( \bigwedge_{j=1}^{q} \top \triangleright m_j \right) \quad (2) $$

Finally, it is sufficient to define $\alpha \triangleright \beta$ when one of $\alpha$ and $\beta$ is a literal and the other one is $\top$ (for $a \in \mathcal{V}$ and $r \in \mathcal{G}$):

$$ \begin{array}{l@{\qquad}l} (a=r) \triangleright \top & \equiv a^{r\bullet} & \neg(a=r) \triangleright \top \equiv \neg a^{r\bullet} \\ \top \triangleright (a=r) & \equiv a^{\bullet r} & \top \triangleright \neg(a=r) \equiv \neg a^{\bullet r} \end{array} \quad (3) $$

The operator $\triangleright$ can be used for adaptation knowledge learning using the difference heuristics, as introduced in Section 1. Let us consider the following source cases expressed in $(\mathcal{GL}, \models)$ with $\mathcal{G} = \mathbb{Z}$ and where $\mathcal{V}_P = \{a, b\}$ and $\mathcal{V}_S = \{c, d\}$.

$$ \mathbf{x}^1 \wedge \mathbf{y}^1 = (a = 1) \wedge (b = 2) \wedge (c = 3) \wedge (d = 4) $$

$$ \mathbf{x}^2 \wedge \mathbf{y}^2 = (a = 2) \wedge (b = 0) \wedge (c = 2) \wedge (d = 6) $$

$$ \mathbf{x}^3 \wedge \mathbf{y}^3 = (a = 3) \wedge (b = 1) \wedge (c = 1) \wedge (d = 8) $$

The variation from case $(\mathbf{x}^k, \mathbf{y}^k)$ to case $(\mathbf{x}^\ell, \mathbf{y}^\ell)$ is represented by $\Delta^{k\ell} = \mathbf{x}^k \wedge \mathbf{y}^k \triangleright \mathbf{x}^\ell \wedge \mathbf{y}^\ell$. According to what is presented above, since the source cases $\mathbf{x}^s \wedge \mathbf{y}^s$ are conjunctions of positive literals of $(\mathcal{PL}, \models)$, the result $\Delta^{k\ell}$ is a conjunction of atoms of the forms $a^{r\bullet}$ and $a^{\bullet r}$ ($r \in \mathcal{G}$). Now, using the first entailment of (1), atoms of the forms $a^{\bullet r}$ are added to $\Delta^{k\ell}$, that highlight the variations. For example

$$ \Delta^{12} \equiv a^{\bullet 1} \wedge a^{1\bullet} \wedge a^{\bullet 2} \wedge b^{\bullet 2} \wedge b^{2\bullet} \wedge b^{\bullet 0} \wedge c^{\bullet 1} \wedge c^{3\bullet} \wedge c^{\bullet 2} \wedge d^{\bullet 2} \wedge d^{4\bullet} \wedge d^{\bullet 6} $$

Using a frequent itemset extraction algorithm [7] on the training set $\{\Delta^{k\ell}\}_{k\ell}$ makes it possible to point out sets of atoms $a^v$ occurring jointly in subsets of the training set. For example, for $(k, \ell) \in \{(1, 2), (2, 3)\}$, the itemset $\{a^{\bullet 1}, c^{\bullet 1}, d^{\bullet 2}\}$ can be made explicit, giving birth to the formula $\varphi = a^{\bullet 1} \wedge c^{\bullet 1} \wedge d^{\bullet 2}$ that can be used for representing an adaptation rule, as this can be seen further. Notice that $\overline{\varphi}$ can also be learnt, corresponding to $(k, \ell) \in \{(2, 1), (3, 2)\}$.

**Proposition 6.** For every $\varphi \in \Delta\mathcal{GL}$, there exist $\mathcal{L}(\varphi) \in \mathcal{GL}$ and $\mathcal{R}(\varphi) \in \mathcal{GL}$ (the left and right projections of $\varphi$) such that:

$$ \mathcal{M}(\mathcal{L}(\varphi)) = \{\mathcal{I} \in \Omega \mid \text{there exists } \mathcal{J} \in \Omega, \mathcal{I}\mathcal{J} \models \varphi\} \quad \text{and} $$

$$ \mathcal{M}(\mathcal{R}(\varphi)) = \{\mathcal{J} \in \Omega \mid \text{there exists } \mathcal{I} \in \Omega, \mathcal{I}\mathcal{J} \models \varphi\} $$

In other terms, $\mathcal{I}\mathcal{J} \models \varphi$ iff $\mathcal{I} \models \mathcal{L}(\varphi)$ and $\mathcal{J} \models \mathcal{R}(\varphi)$.

If $\alpha$ and $\beta$ are two satisfiable formulas of $(\mathcal{GL}, \models)$ then $\mathcal{L}(\alpha \triangleright \beta) \equiv \alpha$ and $\mathcal{R}(\alpha \triangleright \beta) \equiv \beta$.
The computation of the let and right projections of a cube can be performed
by putting this cube into normal form and using the following equivalences:

$$
\begin{align*}
\text{if } \varphi = \bigwedge_{k=1}^{p} \ell_k \text{ is a normal cube, then } L(\varphi) &\equiv \bigwedge_{k=1}^{p} L(\ell_k) \text{ and } R(\varphi) \equiv \bigwedge_{k=1}^{p} R(\ell_k) \\
L(a^{\cdot r}) &\equiv R(a^{\cdot r}) \equiv L(a^{\bullet r}) \equiv R(a^{\bullet \cdot}) \equiv \top \\
L(\neg a^{\cdot r}) &\equiv R(\neg a^{\cdot r}) \equiv L(\neg a^{\bullet r}) \equiv R(\neg a^{\bullet \cdot}) \equiv \top \\
L(a^{\bullet \cdot}) &\equiv (a=r) \quad L(\neg a^{\bullet \cdot}) \equiv \neg (a=r) \quad R(a^{\bullet r}) \equiv (a=r) \quad R(\neg a^{\bullet r}) \equiv \neg (a=r)
\end{align*}
$$

**Definition 2.** Let $\varphi \in \Delta\mathcal{G}\mathcal{L}$ and $a \in \mathcal{V}$. $a$ is said to be an invariant variable of $\varphi$ if there exists $\psi \in \Delta\mathcal{G}\mathcal{L}$ such that $\varphi \equiv \psi$ and $a \notin \mathcal{V}(\psi)$. The set of invariant variables of $\varphi$ is denoted by $\mathrm{Inv}(\varphi)$. So, $\mathcal{V} \setminus \mathcal{V}(\varphi) \subseteq \mathrm{Inv}(\varphi) \subseteq \mathcal{V}$.

A variable of a normal cube $\theta$ is invariant iff $a \notin \mathcal{V}(\theta)$. By contrast, there exist variation formulas $\varphi$ such that $\mathrm{Inv}(\varphi) \neq \mathcal{V} \setminus \mathcal{V}(\varphi)$, for example $\varphi = (a^{\cdot 1} \wedge a^{\cdot 2}) \vee b^{\cdot 4} \cdot$: $a \in \mathcal{V}(\varphi)$ but $a \in \mathrm{Inv}(\varphi)$ since $\varphi \equiv b^{\cdot 4} \cdot$.

# 5 Representing adaptation rules

The $(\Delta\mathcal{G}\mathcal{L}, \models)$ representation formalism has been designed to represent varia-
tions between source cases for the purpose of adaptation knowledge learning. If
the output of such a learning process is a set of adaptation rules, these rules
could be represented in this logic, and this is what is examined in this section.

**5.1 Motivating example and introduction of the ceteris paribus**

Let us consider again the adaptation rule of the cooking domain considered in
the Introduction. Conjunctively written, it corresponds to the $(\Delta\mathcal{G}\mathcal{L}, \models)$ cube,
for $\mathcal{G} = \mathbb{Q}$: $\varphi = \text{dessert}^{\cdot 1} \wedge \#\text{eggs}^{\cdot 2} \wedge \#\text{bananas}^{\cdot 1}$. Now, consider a dessert
recipe with 2 eggs, no banana, 50 grams of flour, and 20 grams of butter. This
is represented by the $(\mathcal{G}\mathcal{L}, \models)$ formula $\alpha = (\text{dessert} = 1) \wedge (\#\text{eggs} = 2) \wedge
(\#\text{bananas} = 0) \wedge (\text{flour}_{\text{gram}} = 50) \wedge (\text{butter}_{\text{gram}} = 20)$ (not taking into account
any other variable). How could the variation formula $\varphi$ be applied to $\alpha$?

To answer this question, the idea is first to define the variation formula $\theta$ that
represents the transformation of $\alpha$ by $\varphi$: the expected result is then $\beta = R(\theta)$. Let
$\mathcal{I}\mathcal{J}$ be a model of $\theta$. This transformation starts from $\alpha$, so $\mathcal{I}$ should be a model
of $\alpha$, which is equivalent to write that (a) $\mathcal{I}\mathcal{J} \models \alpha \triangleright \top$. Furthermore, $\theta$ should
specialize $\varphi$, i.e. $\theta \models \varphi$, which entails that (b) $\mathcal{I}\mathcal{J} \models \varphi$. If (a) and (b) were the
only conditions for $\mathcal{I}\mathcal{J}$ this would involve $\theta \equiv (\alpha \triangleright \top) \wedge \varphi$ so, in this example,
the result of the application would be $\beta = (\text{dessert} = 1) \wedge (\#\text{eggs} = 0) \wedge
(\#\text{bananas} = 1)$. For variables $\text{flour}_{\text{gram}}$ and $\text{butter}_{\text{gram}}$, this raises a problem:
they are not bound in $\beta$. Indeed, each of these variables is invariant in $\varphi$. Now, the
following statement is made: if a variable is invariant in $\varphi$, then the application
of $\varphi$ on $\alpha$ should leave this variable unchanged. This suggests a third condition:
(c) if $a \in \text{Inv}(\varphi)$ then $a$ is interpreted in $\alpha$ the same way as in $\beta$; formally $\{\mathcal{I}(a) | \mathcal{I}\mathcal{J} \in \mathcal{M}(\theta)\} = \{\mathcal{J}(a) | \mathcal{I}\mathcal{J} \in \mathcal{M}(\theta)\}$. If $\alpha$, as in the example, is a cube, condition (c) means simply that if a literal $\ell$ with variable $a$ occurs in $\alpha$ then $\beta$ contains the same literal $\ell$. Another way of formulating it consists of adding to $\varphi$ the conjuncts $a^{+0}$ for any $a \in \text{Inv}(\varphi)$, leading to a formula denoted by $\text{cp}(\varphi)$, formally defined below, in definition 3.

So, taking into account the additional condition (c) leads to the following transformation $\theta$ and application $\beta$:

$$ 
\begin{align*}
\theta &= \text{dessert}^{1\bullet} \wedge \text{dessert}^{=1} \wedge \text{eggs}^{2\bullet} \wedge \text{eggs}^{-2} \wedge \text{bananas}^{0\bullet} \wedge \text{bananas}^{+1} \\
&\quad \wedge \text{flour}_{\text{gram}}^{50\bullet} \wedge \text{flour}_{\text{gram}}^{+0} \wedge \text{butter}_{\text{gram}}^{20\bullet} \wedge \text{butter}_{\text{gram}}^{+0} \\
\beta &= (\text{dessert} = 1) \wedge (\text{eggs} = 0) \wedge (\text{bananas} = 1) \\
&\quad \wedge (\text{flour}_{\text{gram}} = 50) \wedge (\text{butter}_{\text{gram}} = 20)
\end{align*}
$$

Now, the definition of $\text{cp}(\varphi)$ can be given.

**Definition 3.** Let $\alpha, \gamma \in \mathcal{GL}, \varphi \in \Delta\mathcal{GL}, W \subseteq V$ with $W \neq \emptyset$. The ceteris paribus<fnref n="2" /> of $\varphi$ wrt $W$ is defined by

$$ \text{cp}_W(\varphi) = \varphi \wedge \bigwedge \{a^{+0} \mid a \in \text{Inv}(\varphi) \cap W\} $$

$\text{cp}(\varphi)$ is an abbreviation of $\text{cp}_V(\varphi)$ (every variable is considered in $\text{cp}(\varphi)$).

## 5.2 Applying a variation formula on a static formula

From what precedes, the transformation of $\alpha$ by $\varphi$ is $\theta = (\alpha \triangleright \top) \wedge \text{cp}(\varphi)$ and the result of this transformation is $\beta = \text{R}(\theta)$. Now, a constraint can be added to the result of this transformation. If this constraint is represented by $\gamma \in \mathcal{GL}$, then it is possible to define the transformation and the application taking into account $\gamma$:

**Definition 4.** Let $\alpha, \gamma \in \mathcal{GL}$ and $\varphi \in \Delta\mathcal{GL}$. The transformation on $\alpha$ of $\varphi$ with constraint $\gamma$ is the formula $\text{transf}(\alpha, \varphi, \gamma) \in \Delta\mathcal{GL}$ defined by

$$ \text{transf}(\alpha, \varphi, \gamma) = (\alpha \triangleright \gamma) \wedge \text{cp}(\varphi) $$

The application on $\alpha$ of $\varphi$ with constraint $\gamma$ is the formula $\text{appl}(\alpha, \varphi, \gamma) \in \mathcal{GL}$ defined by

$$ \text{appl}(\alpha, \varphi, \gamma) = \text{R}(\text{transf}(\alpha, \varphi, \gamma)) = \text{R}((\alpha \triangleright \gamma) \wedge \text{cp}(\varphi)) $$

The transformation (resp. application) on $\alpha$ of $\varphi$ without any constraint is simply $\text{transf}(\alpha, \varphi, \top)$ (resp. $\text{appl}(\alpha, \varphi, \top)$).

<footnote n="2">² The Latin expression ceteris paribus means “other things being equal”.</footnote>
## 5.3 Adaptation rule representation

Let adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>) ∈ CB × P be an adaptation problem and ar be an adaptation rule. Three questions are raised: (Q1) Is ar applicable to solve adPb? (Q2) If the answer to the previous question is yes, what is the result y<sup>tgt</sup> ∈ S of applying ar on adPb? (Q3) How reliable is the assertion “y<sup>tgt</sup> solves x<sup>tgt</sup>”? To answer questions (Q1) and (Q2), a variation formula ϕ is used, as explained below. To answer (Q3), a positive number cost is given that characterizes the adaptation effort, that is, the risk taken by applying ar to an adaptation problem (the higher cost, the more risky the adaptation is).

In the following, a proposal to formalize an adaptation rule and the way questions (Q1) to (Q3) are answered is given:

**Definition 5.** An adaptation rule is a pair ar = (ϕ, cost) where ϕ is a variation formula and cost is a positive rational number called cost of ar.

Let adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>) be an adaptation problem. The application of ar on adPb is the following static formula:

$$ \beta = \text{appl}(x^s \wedge y^s, \varphi, x^{\text{tgt}}) $$

The rule ar is said to be applicable on adPb if β is satisfiable.

If ar is applicable on adPb then the application of ar on adPb gives a satisfiable solution y<sup>tgt</sup> such that β ≡ x<sup>tgt</sup> ∧ y<sup>tgt</sup>. The value cost characterizes the reliability of the assertion “y<sup>tgt</sup> solves x<sup>tgt</sup>” (the lower the cost, the more reliable this assertion is supposed to be).

To take the example of Section 5.1, with x<sup>s</sup> ∧ y<sup>s</sup> = α and x<sup>tgt</sup> = (dessert = 1) ∧ (#eggs = 0) (“I want a dessert without eggs.”) then ar = (ϕ, cost) is applicable to the adaptation problem adPb = ((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>) and results in y<sup>tgt</sup> = (#bananas = 1) ∧ (flour<sub>gram</sub> = 50) ∧ (butter<sub>gram</sub> = 20).

# 6 An algorithm for retrieval and adaptation

In this section, a case-based inference algorithm is presented for the particular G = E = {0, 1} (subset of the group (Z, +)).

Let AK be the set of adaptation rules: for ar ∈ AK, ar = (ϕ, cost) where ϕ ∈ ΔG and cost ∈ Q, cost > 0. For practical purposes, it is assumed that, after a normalization process, cost is low compared to 1.

The measure of dissimilarity associated with AK, denoted by diss<sub>AK</sub>, is the function that associates with (α, β) ∈ G<sup>L</sup> the value cost(AP) where AP is the adaptation path of lowest cost relating α to β. Formally, an adaptation path from α to β is a sequence AP = ar<sup>1</sup>; ar<sup>2</sup>; ... ; ar<sup>q</sup> of adaptation rules ar<sup>k</sup> = (ϕ<sub>k</sub>, cost<sub>k</sub>) such that, with α<sub>0</sub> = α, α<sub>k</sub> = appl(α<sub>k-1</sub>, ϕ<sub>k</sub>, ⊤) for k ∈ [1, q], and α<sub>q</sub> is consistent with β. Then cost(AP) = ∑<sub>k=1</sub><sup>q</sup> cost<sub>k</sub>. If there is no similarity path from α to β then diss<sub>AK</sub>(α, β) = ∞. When diss<sub>AK</sub>(α, β) = 0, the corresponding adaptation path is empty (q = 0), thus α ∧ β is consistent.
To avoid the situation diss<sub>AK</sub>(α, β) = ∞ for two consistent static formulas α and β, some adaptation rules can be added to AK to obtain $\widehat{AK}$ defined by

$$ \widehat{AK} = \{(a^{*1}, 1), (a^{-1}, 1) | a \in \mathcal{V}_P\} $$

The additional adaptation rules (a<sup>*1*</sup>, 1) and (a<sup>-1</sup>, 1) have a high cost of 1 (relatively to the costs of the other adaptation rules) and so are triggered mainly when α and β could not be related otherwise. They correspond to null adaptations (as default adaptations) since they have no impact of the interpretation of solution variables.

Now, the specifications of the retrieval and adaptation algorithms are given.

**Input:** CB, AK, x<sup>tgt</sup> ∈ G<sub>L</sub>.

**Retrieval:** Find (x<sup>s</sup>, y<sup>s</sup>) ∈ CB that minimizes diss<sub>AK</sub>(x<sup>s</sup> ∧ y<sup>s</sup>, tgt), and the corresponding adaptation path AP from x<sup>s</sup> ∧ y<sup>s</sup> to x<sup>tgt</sup>.

**Adaptation:** Apply AP to x<sup>s</sup> ∧ y<sup>s</sup> to obtain a consistent formula β such that β |= x<sup>tgt</sup>, and let y<sup>tgt</sup> be such that β ≡ x<sup>tgt</sup> ∧ y<sup>tgt</sup>. y<sup>tgt</sup> is the output solution.

A naive retrieval algorithm (with a discouraging complexity) consists in finding AP by a best-first search in a state space:

- A state is a pair (α, C) where α ∈ G<sub>L</sub> is consistent, C ∈ Q and C ≥ 0.

- The set of initial states is { (x<sup>s</sup> ∧ y<sup>s</sup>, 0) | (x<sup>s</sup>, y<sup>s</sup>) ∈ CB }.

- A successor of a state (α, C) is a state (β, C') for which there exists ar = (φ, cost) ∈ $\widehat{AK}$ such that β = appl(α, φ, ⊤) and C' = C + cost.

- A final state (α, C) is such that α ∧ x<sup>tgt</sup> is consistent.

- The states (α, C) are searched by non-decreasing C.

An A* search algorithm can be used for this purpose [9].

Let q be the length of the similarity path AP relating the retrieved case to the target problem. Let b be the average branching factor of the search (b ≤ |$\widehat{AK}$| but is much lower in practice if, on the average, only few adaptation rules are applicable on a cube of (G<sub>L</sub>, |=)). Under the assumptions of Section 3.4, and assuming also that the variation formulas of adaptation rules are cubes, it can be proven that the complexity of the retrieval algorithm is in O(|CB|·|V|·b<sup>q</sup>), thus proportional to the size of the case base. Case adaptation is fast: it consists mainly in using the value β of the application of AP on the retrieved case.

A less naive algorithm consists in going the other way round: from x<sup>tgt</sup> to source cases. For an adaptation rule ar = (φ, cost), let $\overline{ar} = (\overleftarrow{\varphi}, cost)$. This algorithm consists in modifying the best-first search of the naive algorithm as follows:

- The set of adaptation rules is { $\overline{ar}$ | ar ∈ $\widehat{AK}$ }.

- The sole initial state is x<sup>tgt</sup>.

- A final state (α, C) is such that there exists (x<sup>s</sup>, y<sup>s</sup>) ∈ CB such that x<sup>s</sup> ∧ y<sup>s</sup> ∧ α is consistent. This exact match search can be performed in O(|V<sub>P</sub>|) thanks to an organization of the case base in a binary tree of depth |V<sub>P</sub>| (this point is detailed in [3]).
The output of this search is a retrieved case ($x^s, y^s$) $\in$ CB and an adaptation path $\overleftarrow{AP} = \overleftarrow{ar^1}; \dots; \overleftarrow{ar^q}$ from $x^{\text{tgt}}$ to $x^s \wedge y^s$. Then, the inverse adaptation path $\overrightarrow{AP} = \overrightarrow{ar^q}; \dots; \overrightarrow{ar^1}$ is computed, resulting in the same adaptation path as the one produced by the naive algorithm. Finally, adaptation consists in sequentially applying $\overleftarrow{AP}$ on $x^s \wedge y^s$ (in $q$ steps) to obtain $\beta \equiv x^{\text{tgt}} \wedge y^{\text{tgt}}$.

The complexity of this algorithm is in $O(|V_P| \cdot |V| \cdot b^q)$, thus independent of the size of the case base (whereas the naive algorithm complexity is $|CB|$ times higher because of the $|CB|$ initial states). This is due to the use of a $O(|V_P|)$ exact match step of the algorithm and this is where the application of this algorithm gives another complexity for $G \neq \mathbb{B}$.

The fact that this algorithm fulfills the specification and thus, gives the same result as the naive algorithm, is related to the following result:

**Proposition 7.** Let $\alpha$ and $\gamma$ be two cubes of $(\mathcal{G}\mathcal{L}, \models)$ and $\varphi$ be a cube of $(\Delta\mathcal{G}\mathcal{L}, \models)$. Then $\text{appl}(\alpha, \varphi, \gamma) \not\models \perp \text{iff } \text{appl}(\gamma, \overleftarrow{\varphi}, \top) \wedge \alpha \not\models \perp$.

# 7 Discussion and conclusion

This paper has presented a formal approach to represent variations between cases and adaptation rules, with an algorithm for single retrieval and adaptation. The retrieval is adaptation-guided [12]: the retrieved case is necessarily adaptable to solve the target problem, but beyond that, the retrieved case is the one that requires the least adaptation effort according to the costs associated with adaptation knowledge. Moreover, if all the attributes have a Boolean range, the retrieval complexity is independent of the size of the case base. Finally, the retrieval knowledge is determined by the adaptation knowledge: it is defined by the dissimilarity measure $\text{diss}_{\hat{\mathcal{A}}}$.

Although the approach presented in this paper could be implemented without an explicit representation in the logical formalisms $(\mathcal{G}\mathcal{L}, \models)$ and $(\Delta\mathcal{G}\mathcal{L}, \models)$, studying case-based inference from a logical point of view has at least two advantages. First, it is useful for studying the properties of these inferences at a semantic level (e.g., the properties of the retrieval algorithm). Second, it makes it possible to go beyond attribute value representation (taking into account disjunctions and negations, in particular, which makes it possible to use generalized cases and complex adaptation rules).

This theoretical work can be continued in several directions.

A first direction of work is to confront this approach with practical applications and / or benchmarks, using an adaptation knowledge learning system to feed AK.

This work has mainly considered three knowledge containers of a CBR system: CB and AK, obviously, but also the retrieval knowledge $\text{diss}_{\hat{\mathcal{A}}}$ that is determined by AK. Now, little attention has been given to domain knowledge represented by the set of static formulas DK. For static knowledge (in particular cases), it consists mainly in defining the inferences modulo DK ($\alpha \models_{DK} \beta$ if $DK \cup \{\alpha\} \models \beta$, $\alpha$ is DK-satisfiable if $DK \cup \{\alpha\}$ is satisfiable, etc.). How can static knowledge DK be used for inference in $(\Delta\mathcal{G}\mathcal{L}, \models)$ and adaptation rules is a question still requiring some consideration.
Olaaf is an adaptation engine based on belief revision in a logic where atoms are linear constraints and which is propositionally closed [2]. Olaaf inference engine mainly relies on DK, the domain knowledge, and *diss*, a measure of dissimilarity between interpretations. Some adaptation rules are “simulated” in Olaaf by adding pieces of knowledge to DK and/or by modifying *diss*, although this aspect of Olaaf has not yet been investigated in detail. By contrast, the approach proposed in this paper is centered on AK (and its representation) and the dissimilarity measure $diss_{AK}$ comes as a byproduct. A direction of work worth investigating aims to find an integrated view of these two logic-based approaches to adaptation.

## References

1. d'Aquin, M., Badra, F., Lafrogne, S., Lieber, J., Napoli, A., Szathmary, L.: Case Base Mining for Adaptation Knowledge Acquisition. In Veloso, M.M., ed.: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), Morgan Kaufmann, Inc. (2007) 750-755

2. Diebold, E., Kabrit, Y., Kril, A., Lieber, J., Malvaud, P., Nauer, E., Sipp, J.: Olaaf: A General Adaptation Prototype. In Recio-Garcia, J.A., del Castillo, M.G.O., Bridge, D., eds.: Case-Based Reasoning Research and Development. Volume 14775 of Lecture Notes in Computer Science., Merida, Mexico, J. A. Recio-Garcia and M. G. Orozco-del-Castillo and D. Bridge, Springer Nature Switzerland (July 2024) 223-239

3. François, N., Lieber, J.: A Knowledge Representation Approach for Reasoning with Adaptation Rules (extended version). Technical report, Loria (2025) (This report can be found at https://hal.science/hal-04961604).

4. Hanney, K., Keane, M.T.: Learning adaptation rules from a case-base. In Smith, I., Faltings, B., eds.: Advances in Case-Based Reasoning - Proc. of the Third Eur. Workshop, EWCBR'96. LNAI 1168, Springer Verlag, Berlin (1996) 179-192

5. Jalali, V., Leake, D., Forouzandehmehr, N.: Learning and applying adaptation rules for categorical features: An ensemble approach. AI Communications 30(3-4) (2017) 193-205

6. Lieber, J., Napoli, A.: Using Classification in Case-Based Planning. In Wahlster, W., ed.: Proceedings of the 12th European Conference on Artificial Intelligence (ECAI'96), Budapest, Hungary, John Wiley & Sons, Ltd. (1996) 132-136

7. Luna, J.M., Fournier-Viger, P., Ventura, S.: Frequent itemset mining: A 25 years review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 9(6) (2019) e1329

8. Nauer, E., Lieber, J., d'Aquin, M.: Lazy Adaptation Knowledge Learning Based on Frequent Closed Itemsets. In: Case-Based Reasoning Research and Development. Volume 14141 of Lecture Notes in Computer Science., Aberdeen, United Kingdom, Springer Nature Switzerland (July 2023) 309-324

9. Pearl, J.: Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc. (1984)

10. Riesbeck, C.K., Schank, R.C.: Inside Case-Based Reasoning. Lawrence Erlbaum Associates, Inc., Hillsdale, New Jersey (1989) Available on line.

11. Smullyan, R.M.: First-order logic. Courier Corporation (1995)

12. Smyth, B., Keane, M.T.: Using adaptation knowledge to retrieve and adapt design cases. Knowledge-Based Systems 9(2) (1996) 127-135