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

HAL
open science

# A Knowledge Representation Approach for Reasoning with Adaptation Rules (extended version)

Nicolas François, Jean Lieber

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

## To cite this version:

Nicolas François, Jean Lieber. A Knowledge Representation Approach for Reasoning with Adaptation Rules (extended version). Loria. 2025. hal-04961604v2

HAL Id: hal-04961604

https://hal.science/hal-04961604v2

Submitted on 26 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# A Knowledge Representation Approach for Reasoning with Adaptation Rules (extended version)

Nicolas François¹ et Jean Lieber²

¹ Lycée public Chopin, F-54000 Nancy, France

² Université de Lorraine, CNRS, LORIA, F-54000 Nancy, France

February 26, 2025

## 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 article 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 from 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 [9]) community as a key step for this type of reasoning. This article follows that tradition and considers it from a knowledge representation perspective: how can the representation of adaptation knowledge be useful for CBR?

To address this question, the starting point have 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 [3]. It is in general based on what is called the *difference heuristics* in [4]: 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:

$$ \{ \text{dessert}^{=1}, \text{#eggs}^{-2}, \text{#bananas}^{+1} \} $$

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 [7]. 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 article. Its second objective is to explain how such a logic can benefit to CBR.

Section 2 presents some preliminaries about CBR. The case base and the knowledge base can be represented in a so-called *static logic*; Section 3 presents the static logic ($GL, \models$) that is expressive enough to represent attribute-value pairs (with both Boolean and numerical attributes) and taxonomies (and beyond). Section 4 defines the variation logic ($\Delta GL, \models$), which is based on ($GL, \models$): 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 performing single case retrieval is presented in Section 6, that 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 to the adaptation rules). Second, when every attribute has a Boolean range, its time complexity is independent from the size of the case base. Section 7 discusses this contribution, concludes and briefly presents some future directions of work.

# 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). Z is the set of (positive and negative) integers. For $a, b \in Z$ with $a \le b$, $[a, b] = \{n \in Z | a \le n \le b\}$. Q is the set of rational numbers.

An abelian group is a pair $(G, +)$ where $G$ is a nonempty set and $+$ is an internal binary operation on $G \ (+ : (r, s) \in G \mapsto r + s \in G)$ such that (1) it has an identity element denoted by $0$ (for each $r \in G$, $r + 0 = 0 + r = r$), (2) every $r \in 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 G$), and (4) $+$ is commutative ($r + s = s + r$ for every $r, s \in G$). For $r, s \in 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 article, a case is considered as a problem-solution pair. A *problem* is, by definition, an element x of a given set *P*. A *solution* is, by definition, an element y of a given set *S*. It is assumed that a relation $\rightsquigarrow$ is defined on *P* × *S* that is not completely known to the CBR system, and that is read “has for solution”. A *case* is an ordered pair $(x, y) \in *P* \times *S*. A *correct case* is a case $(x, y)$ such that $x \rightsquigarrow y$.

**Process model.** A CBR session consists in solving a problem called the *target problem* and denoted by $x^{\text{tgt}}$. One 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, that are not considered in this article. In many systems, several cases are retrieved and then adapted; in this article, only single case retrieval and single case adaptation are considered.

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

The 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 instance if “apple” and “fruit” belongs 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 knowledge about case retrieval. It often takes the form of a dis-similarity measure *diss* between source cases and the target problem: to $(x^s, y^s) \in CB$ and $x^{\text{tgt}} \in *P*
is associated a nonnegative number *diss*((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>), and retrieval aims at finding the (x<sup>s</sup>, y<sup>s</sup>) ∈ CB that minimizes this value.

The adaptation knowledge AK is used during adaptation. In this article, it takes the forme of a finite set of adaptation rules *ar*. Generally speaking, such a rule can be interpreted as a mapping associating to ((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>) ∈ (*P* × *S*) × *P* a y<sup>tgt</sup> ∈ *S* ∪ {failure}. If y<sup>tgt</sup> = *failure*, that means that the adaptation rule is not applicable to the adaptation problem ((x<sup>s</sup>, y<sup>s</sup>), x<sup>tgt</sup>). In other situations, the case (x<sup>tgt</sup>, y<sup>tgt</sup>) is not necessarily correct: CBR is in general a hypothetical reasoning and the result is not certainly correct. In order to increase the chances of correctness, a positive value *cost* associated to *ar* is given: the lower *cost* is, the higher (x<sup>tgt</sup>, y<sup>tgt</sup>) is likely to be correct.

An adaptation can be performed in several steps, using *adaptation paths*, i.e. sequences of adaptation rules [5]: given an adaptation problem ((x<sup>s</sup>, y<sup>s</sup>), y<sup>tgt</sup>), it may be solved using an adaptation path AP = ar<sup>1</sup>; ar<sup>2</sup>; ... ; ar<sup>q</sup> if the sequential application of ar<sup>k</sup> (k taking values 1 to q) starting from (x<sup>s</sup>, y<sup>s</sup>) leads to a case (x<sup>tgt</sup>, y<sup>tgt</sup>). 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<sup>k</sup>.

**Knowledge representation.** CB and DK are knowledge containers about what *is*, or *is not*, a case: an (x<sup>s</sup>, y<sup>s</sup>) ∈ CB indicates that y<sup>s</sup> *is* a (correct) solution of x<sup>s</sup>, 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 comparison of cases and the adaptation knowledge AK is about transformations, about how a case *changes* into another case.

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

In this article, the static logic considered is (GL, |=), presented in Section 3 and used for both CB and DK. The variation logic (ΔGL, |=) for representing adaptation knowledge is based on the former logic and is presented in Section 4.

# 3 The static logic (GL, |=)

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 article is about the logic (GL, |=) described below, together with a discussion about its expressivity. This logic is parametrized by G such that either (G, +) is an infinite group (e.g. G = Q or G = Z) or G is a subset of H such that (H, +) is an infinite group (e.g. G = B: in this case, (GL, |=) corresponds to propositional logic).<fnref n="1" />

## 3.1 Syntax of (GL, |=)

Let $\mathcal{V}$ be a given finite nonempty set of symbols: an $a \in \mathcal{V}$ is called a *variable*. An *atom* of $(\mathcal{G}\mathcal{L}, \models)$ is an expression of the form $(a = r)$ where $a \in \mathcal{V}$ and $r \in \mathcal{G}$. A formula of $(\mathcal{G}\mathcal{L}, \models)$ is either an atom or of 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 instance, the $\rightarrow$ connective is defined by $\alpha \rightarrow \beta = \neg\alpha \vee \beta$. $\mathcal{G}\mathcal{L}$ is the set of the formulas of this logic. The set of variables occurring in $\alpha \in \mathcal{G}\mathcal{L}$ 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. Actually, it is not difficult to extend the approach to finite groups, though it would make the explanations more tedious.</footnote>
## 3.2 Semantics of ($\mathcal{GL}, \models$)

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 \perp$ 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 $M(\alpha)$ be the set of models of $\alpha$. $\alpha$ is satisfiable (or consistent) if $M(\alpha) \neq \emptyset$ and $\alpha$ is a tautology if $M(\alpha) = \Omega$. For instance, $\perp$ is unsatisfiable and $\top$ is a tautology. The relation $\models \alpha \models \beta$ means that $M(\alpha) \subseteq M(\beta)$. The relation $\models \alpha \models \beta$ means that $M(\alpha) = M(\beta)$. If $B$ is a set of formulas, $M(B) = \bigcap \{M(\alpha) \mid \alpha \in B\}$. Then, $B \models \alpha$ means that $M(B) \subseteq M(\alpha)$.

## 3.3 Basic properties of ($\mathcal{GL}, \models$).

**Proposition 1** For $a \in \mathcal{V}$ and $r, s \in \mathcal{G}$,

* $(a = r) \wedge (a = s) \equiv \begin{cases} (a = r) & \text{if } r = s \\ \perp & \text{else} \end{cases}$

* $(a = r) \wedge \neg(a = s) \equiv \begin{cases} (a = r) & \text{if } r \neq s \\ \perp & \text{else} \end{cases}$

* $\neg(a = r) \wedge \neg(a = s) \equiv \begin{cases} \neg(a = r) & \text{if } r = s \\ \neg(a = r) \wedge \neg(a = s) & \text{else} \end{cases}$

Hence a satisfiable cube in ($\mathcal{GL}, \models$) can be put in one of those two normalized forms:

* $(a = r)$, with $r \in \mathcal{G}$,

* $\bigwedge_{i=1}^{p} \neg(a = r_i)$ with $r_1, \dots, r_p$, $p$ distinct elements of $\mathcal{G}$.

It is assumed in this report that any cube ($\mathcal{GL}, \models$) is in such a form. A formula of $\mathcal{GL}$ is said to be in DNFNC (disjunctive normal form with normal cubes) if it is in DNF and all its cubes are normalized as described above.

Every formula of ($\mathcal{GL}, \models$) can be put under DNF: if $\alpha \in \mathcal{GL}$, there exists $\beta \in \mathcal{GL}$ such that $\alpha \equiv \beta$ and $\beta$ is under DNF.<fnref n="2" />

Finally, for $\mathcal{I} \in \Omega$, there exists a formula $\alpha_{\mathcal{I}}$ such that $M(\alpha_{\mathcal{I}}) = \{\mathcal{I}\}$ (the formulas $\alpha_{\mathcal{I}}$ are the most specific satisfiable formulas of ($\mathcal{GL}, \models$) for the relation $\models$). This formula can be expressed as a conjunction of atoms on every variable: $\alpha_{\mathcal{I}} \equiv \bigwedge_{a \in \mathcal{V}} (a = \mathcal{I}(a))$.

**Proof.** It is sufficient to prove that $\mathcal{I}$ is the only model of $\alpha_{\mathcal{I}}$. First $\mathcal{I}$ is a model of $\alpha_{\mathcal{I}}$, because $\mathcal{I} \models (a = \mathcal{I}(a))$ for all $a \in \mathcal{V}$. And if $\mathcal{J} \models \alpha_{\mathcal{I}}$, then $\mathcal{J} \models (a = \mathcal{I}(a))$ for all $a \in \mathcal{V}$, so $\mathcal{J}(a) = \mathcal{I}(a)$, and $\mathcal{J} = \mathcal{I}$.

<footnote n="2">²This can be proven using the classical approach to put a formula under DNF in many formalisms. Technically, applying from left to right the following equivalences until none of them is applicable leads any formula using the connectives $\neg$, $\wedge$ and $\vee$ to a formula under DNF (for $\alpha, \beta, \gamma \in \mathcal{GL}$): $\neg\neg\alpha \equiv \alpha$, $\neg(\alpha\wedge\beta) \equiv \neg\alpha\vee\neg\beta$, $\neg(\alpha\vee\beta) \equiv \neg\alpha\wedge\neg\beta$, $\alpha\wedge(\beta\vee\gamma) \equiv (\alpha\wedge\beta)\vee(\alpha\wedge\gamma)$, and $(\alpha\vee\beta)\wedge\gamma \equiv (\alpha\wedge\gamma)\vee(\beta\wedge\gamma)$.</footnote>
## 3.4 About the expressivity of ($\mathcal{GL}, \models$)

Each variable $a$ of ($\mathcal{GL}, \models$) has the same range $\mathcal{G}$: for every $\mathcal{I} \in \Omega$, $\mathcal{I}(a) \in \mathcal{G}$. A slight modification of ($\mathcal{GL}, \models$) consists in precising 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. ($\mathbb{apple} = 1) \rightarrow (\mathbb{fruit} = 1$) states that every apple is a fruit). For the sake of simplicity, in this study, we stick to the static logic ($\mathcal{GL}, \models$), considering that the extension with variable types should not be difficult to integrate.

## 3.5 Representing cases in ($\mathcal{GL}, \models$)

According to Section 2, the sets $\mathcal{P}$ and $\mathcal{S}$ are assumed to be disjoint. This suggests to partition the set of variables in $\{\mathcal{V}_P, \mathcal{V}_S\}$: $\mathcal{V}_P$ (resp., $\mathcal{V}_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}_P$ (resp., in $\mathcal{V}_S$). So a case $(x, y) \in \mathcal{P} \times \mathcal{S}$ can be written $x \wedge y$: finding the problem part $x$ and the solution part $y$ of $x \wedge y$ is easy since $\mathcal{V}_P \cap \mathcal{V}_S = \emptyset$.

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

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

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\mathcal{GL}, \models$) built from the static logic ($\mathcal{GL}, \models$): 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\mathcal{GL}, \models$)

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

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

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

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

An atom of ($\Delta\mathcal{GL}, \models$) is an expression of the form $a^v$ where $a$ is a variable and $v$ is a variation symbol. A formula of ($\Delta\mathcal{GL}, \models$) is either 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\mathcal{GL}$. A variation formula is an element of $\Delta\mathcal{GL}$. The set of variables occurring in $\varphi \in \Delta\mathcal{GL}$ is denoted by $\mathcal{V}(\varphi)$.

A positive literal of ($\Delta\mathcal{GL}, \models$) 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\mathcal{G}\mathcal{L}, \models)$

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

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

Let $\Delta\Omega = \Omega \times \Omega$ be the set of interpretations used to define the semantics of $(\Delta\mathcal{G}\mathcal{L}, \models)$: 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 $\mathcal{IJ}$.

The fact that $\mathcal{IJ} \in \Delta\Omega$ is a model of a $\varphi \in \Delta\mathcal{G}\mathcal{L}$ 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\mathcal{G}\mathcal{L}, \models)$;

* $\mathcal{IJ} \models \neg\varphi$ if $\mathcal{IJ} \not\models \varphi$, for $\varphi \in \Delta\mathcal{G}\mathcal{L}$;

* $\mathcal{IJ} \models \varphi \wedge \psi$ if $\mathcal{IJ} \models \varphi$ and $\mathcal{IJ} \models \psi$, for $\varphi, \psi \in \Delta\mathcal{G}\mathcal{L}$;

* $\mathcal{IJ} \models \varphi \vee \psi$ if $\mathcal{IJ} \models \varphi$ or $\mathcal{IJ} \models \psi$, for $\varphi, \psi \in \Delta\mathcal{G}\mathcal{L}$.

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 has been used: $=r$ (for $r \in \mathcal{G}$). It has the following semantics (for $a \in \mathcal{V}$): $\mathcal{IJ} \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 2** 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^{\bullet r} \wedge a^{s\bullet} & \models & a^{\bullet(r+s)} & & a^{\bullet r} \wedge a^{\bullet s} & \models & a^{(s-r)\bullet} \\ a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(s-r)} & & a^{\bullet r} \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^{\bullet r} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(r-s)} & & a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(s-r)} & & a^{r\bullet} \wedge \neg a^{\bullet s} & \models & \neg a^{\bullet(r+s)} \end{array} \right| \quad (1) $$

**Proof.** Let $\mathcal{IJ} \in \Delta\Omega$. Every assertion is translated into a simple (and correct) arithmetic entailment:

$$
\begin{array}{l@{\qquad}l}
a^{r\bullet} \wedge a^{\bullet s} & \models a^{\bullet(s-r)} & \text{if } \mathcal{I}(a) = r \text{ and } \mathcal{J}(a) = s \text{ then } \mathcal{J}(a) - \mathcal{I}(a) = s-r; \\
a^{\bullet r} \wedge a^{s\bullet} & \models a^{\bullet(r+s)} & \text{if } \mathcal{J}(a) - \mathcal{I}(a) = r \text{ and } \mathcal{I}(a) = s \text{ then } \mathcal{J}(a) = r+s; \\
a^{\bullet r} \wedge a^{\bullet s} & \models a^{(s-r)\bullet} & \text{if } \mathcal{J}(a) - \mathcal{I}(a) = r \text{ and } \mathcal{J}(a) = s \text{ then } \mathcal{I}(a) = s-r; \\
a^{r\bullet} \wedge \neg a^{\bullet s} & \models \neg a^{\bullet(s-r)} & \text{if } \mathcal{I}(a) = r \text{ and } \mathcal{J}(a) \neq s \text{ then } \mathcal{J}(a) - \mathcal{I}(a) \neq s-r; \\
a^{\bullet r} \wedge \neg a^{s\bullet} & \models \neg a^{\bullet(r-s)} & \text{if } \mathcal{J}(a) = r \text{ and } \mathcal{I}(a) \neq s \text{ then } \mathcal{J}(a) - \mathcal{I}(a) \neq r-s; \\
a^{\bullet r} \wedge \neg a^{s\bullet} & \models \neg a^{\bullet(r+s)} & \text{if } \mathcal{J}(a) - \mathcal{I}(a) = r \text{ and } \mathcal{I}(a) \neq s \text{ then } \mathcal{J}(a) \neq r+s; \\
a^{\bullet r} \wedge \neg a^{s\bullet} & \models \neg a^{\bullet(r-s)} & \text{if } \mathcal{J}(a) = r \text{ and } \mathcal{I}(a) \neq s \text{ then } \mathcal{J}(a) - \mathcal{I}(a) \neq r-s; \\
a^{r\bullet} \wedge \neg a^{\bullet s} & \models \neg a^{\bullet(s-r)} & \text{if } \mathcal{I}(a) = r \text{ and } \mathcal{J}(a) \neq s \text{ then } \mathcal{J}(a) - \mathcal{I}(a) \neq s-r; \\
a^{r\bullet} \wedge \neg a^{\bullet s} & \models \neg a^{\bullet(r+s)} & \text{if } \mathcal{I}(a) = r \text{ and } \mathcal{J}(a) - \mathcal{I}(a) \neq s \text{ then } \mathcal{J}(a) \neq r+s. &
\end{array}
$$

<figure><img src="image_4.png" /></figure>
**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 2 (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 3** Every formula $\varphi \in \Delta\mathcal{G}\mathcal{L}$ can be put under DNF and under DNFNC: there exists $\varphi_{\text{DNF}} \in \Delta\mathcal{G}\mathcal{L}$ (resp. $\varphi_{\text{DNFNC}} \in \Delta\mathcal{G}\mathcal{L}$) that is under DNF (resp. DNFNC) such that $\varphi \equiv \varphi_{\text{DNF}}$ (resp. $\varphi \equiv \varphi_{\text{DNFNC}}$).

**Proof.** The fact that $\varphi$ can be put in DNF follows the same principles as the proof that propositional formulas can be put in DNF. It consists in applying from left to right the following equivalences until none of them is applicable: $\neg\neg\varphi \equiv \varphi$, $\neg(\varphi \lor \psi) \equiv \neg\varphi \lor \neg\psi$, $\neg(\varphi \lor \psi) \equiv \neg\varphi \land \neg\psi$, $\varphi \land (\psi \lor \tau) \equiv (\varphi \land \psi) \lor (\varphi \land \tau)$ and $(\varphi \lor \psi) \land \tau \equiv (\varphi \land \tau) \lor (\psi \land \tau)$.

It remains to prove that any cube can be normalized in one of the four forms mentioned above. This relies in particular on proposition 2 along with the trivial inconsistencies the form $A \land \neg A$ where $A$ is an atom, and the not so trivial following inconsistencies (for $a \in \mathcal{V}$ and $r, s \in \mathcal{G}$):

$$a^{r\bullet} \wedge a^{\bullet s} \wedge \neg a^{\bullet (s-r)} \models \perp \quad a^{r\bullet} \wedge a^{\bullet s} \wedge \neg a^{\bullet (r+s)} \models \perp \quad a^{\bullet r} \wedge a^{\bullet s} \wedge \neg a^{(r-s)\bullet} \models \perp \quad (2)$$

If $\Theta = \bigwedge_{a \in \mathcal{V}'} \theta_a$ is a cube of the DNF form of $\varphi$, where $\mathcal{V}'$ is a subset of $\mathcal{V}$, and each $\theta_a$ is a cube on the single variable $a$, the following construction is applied to each $\theta_a$: a new cube $\theta'_a$ equivalent to $\theta_a$ is built, introducing the literals one by one, starting with the positive ones. For each literal, if there is an inconsistency, the process stops and $\theta_a$ is equivalent to $\perp$. If not, the literal is added to $\theta'_a$ along with its possible consequence given by 1.

The cube $\theta'_a$ is by construction equivalent to $\theta_a$, and also by construction of one of the forms described by definition 1. And $\Theta$ is a cube equivalent to $\Theta' = \bigwedge_{a \in \mathcal{V}'} \theta'_a$.

The conjunction of the $\Theta'$ is again in DNF, and as each cube is normalized, it is in DNFNC.

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 \land \varphi_2 \land \neg\psi$ is not satisfiable. Now, the satisfiability problem can be computed using the principles of the tableaux method (see e.g. [10]), 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 4** The following results can be used to determine whether a variation formula is satisfiable or not:
(a) For $\varphi \in \Delta\mathcal{GL}$, 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{GL}$ 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{GL}, \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{GL}, \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).

**Proof.** (a) results from the fact that $\varphi_{\text{DNF}} \equiv \varphi$.

(b) and (c) are just transcriptions of the definitions of conjunctions and disjunctions semantics.

Only (d) requires some thinking. It has to be proven that conditions (ii), (iii) and (iv) define satisfiable cubes. For this result, the fact that $\mathcal{G}$ is infinite is useful (in particular for case (iii)).

(ii) When $\theta = a^{r\bullet} \wedge a^{\bullet s} \wedge a^{+(s-r)}$, $\mathcal{I}\mathcal{J} \models \theta$ if $\mathcal{I}(a) = r$ and $\mathcal{J}(a) = s$. So $\theta$ is satisfiable.

(iii) Three sub-cases have to be distinguished here:

* If $\theta = a^{r\bullet} \wedge \bigwedge_{s \in I} \neg a^{\bullet s} \wedge a^{+(s-r)}$, where $I$ is a finite subset of $\mathcal{G}$, then $\mathcal{I}\mathcal{J} \models \theta$ if $\mathcal{I}(a) = r$, and $\mathcal{J}(a) \notin I$, which is possible since $\mathcal{G}$ is supposed to be infinite.<fnref n="3" />

* If $\theta = a^{\bullet r} \wedge \bigwedge_{s \in I} \neg a^{\bullet s} \wedge a^{+(r-s)}$, then $\mathcal{I}\mathcal{J} \models \theta$ if $\mathcal{I}(a) \notin I$ and $\mathcal{J}(a) = r$.

* If $\theta = a^{\bullet r} \wedge \bigwedge_{s \in I} \neg a^{\bullet s} \wedge a^{+(s+r)}$, then $\mathcal{I}\mathcal{J} \models \theta$ if $\mathcal{I}(a) \notin I$, and $\mathcal{J}(a) = \mathcal{I}(a) + r$.

In each case, there is at least one interpretation satisfying $\theta$.

(iv) Finally, if $\theta = \bigwedge_{r \in I} \neg a^{r\bullet} \wedge \bigwedge_{s \in J} \neg a^{\bullet s} \wedge \bigwedge_{k \in K} \neg a^{\bullet t}$, $\mathcal{I}\mathcal{J} \models \theta$ if $\mathcal{I}(a) \notin I$ and $\mathcal{J}(a) \notin J \cup \{\mathcal{I}(a) + t \mid t \in K\}$, which is again possible because $\mathcal{G}$ is infinite.

So any cube other than $\perp$ is satisfiable, and that finishes the proof. ■

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

This section presents different operators on the logic $(\Delta\mathcal{GL}, \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.

### 4.4.1 The inverse operator

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 5** For every $\varphi \in \Delta\mathcal{GL}$ 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$.

<footnote n="3">³The case where $\mathcal{G}$ is finite is discussed in Section 7.</footnote>
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{\vdash} = -r \qquad \overleftarrow{\vdash\bullet} = \bullet r \qquad \overleftarrow{\vdash} = r\bullet \qquad (\text{for } r \in \mathcal{G}) $$

For example, $a^{\overleftarrow{\vdash}1} \wedge a^{\overleftarrow{\vdash}2} \wedge c^{\overleftarrow{\vdash}2} = a^{-1} \wedge a^{2\bullet} \wedge c^{\overleftarrow{\vdash}2}$.

**Proof.** Let $\varphi \in \Delta\mathcal{GL}$ and $\overleftarrow{\varphi}$ defined by replacing every variation symbol $v$ by $\overleftarrow{v}$ as explained above. Let $\mathcal{IJ} \in \Omega$. The objective of this proof of proposition 5 is to show that $\mathcal{IJ} \models \varphi$ iff $\mathcal{JI} \models \overleftarrow{\varphi}$. The proof is a simple induction on the size $n$ of $\varphi$, this size being given by the number of connectives it contains.

If $n = 0$ then $\varphi$ is an atom $a^v$: $a \in \mathcal{V}$ and $v \in \{\vdash r, r\bullet, \bullet r\}$ for some $r \in \mathcal{G}$.

If $v = \vdash r$ then $\mathcal{IJ} \models \varphi$ iff $\mathcal{J}(a) - \mathcal{I}(a) = r$ iff $\mathcal{I}(a) - \mathcal{J}(a) = -r$ iff $\mathcal{JI} \models a^{-r} = \overleftarrow{\varphi}$.

If $v = r\bullet$ then $\mathcal{IJ} \models \varphi$ iff $\mathcal{I}(a) = r$ iff $\mathcal{JI} \models a^{\bullet r} = \overleftarrow{\varphi}$.

If $v = \bullet r$ then $\mathcal{IJ} \models \varphi$ iff $\mathcal{J}(a) = r$ iff $\mathcal{JI} \models a^{r\bullet} = \overleftarrow{\varphi}$.

In any case, if $n = 0$, $\mathcal{IJ} \models \varphi$ iff $\mathcal{JI} \models \overleftarrow{\varphi}$.

Now, it is assumed that the result is proven for any formula of size $k < n$, for $n \in \mathbb{N}$, $n > 0$. Three cases can be distinguished:

$\varphi = \neg\psi$ **for** $\psi \in \Delta\mathcal{GL}$: since the size of $\psi$ is $n-1$, the results holds for $\psi$. So $\mathcal{IJ} \models \varphi$ iff $\mathcal{IJ} \not\models \psi$ iff $\mathcal{JI} \not\models \overleftarrow{\psi}$ iff $\mathcal{JI} \models \neg\overleftarrow{\psi} = \overleftarrow{\varphi}$.

$\varphi = \psi_1 \wedge \psi_2$ **for** $\psi_1, \psi_2 \in \Delta\mathcal{GL}$: since the sizes of $\psi_1$ and $\psi_2$ are lower than the size of $\varphi$, the result holds for $\psi_1$ and $\psi_2$. So $\mathcal{IJ} \models \varphi$ iff $\mathcal{IJ} \models \psi_1$ and $\mathcal{IJ} \models \psi_2$ iff $\mathcal{JI} \models \overleftarrow{\psi_1}$ and $\mathcal{JI} \models \overleftarrow{\psi_2}$ iff $\mathcal{JI} \models \overleftarrow{\psi_1} \wedge \overleftarrow{\psi_2} = \overleftarrow{\varphi}$.

$\varphi = \psi_1 \vee \psi_2$ **for** $\psi_1, \psi_2 \in \Delta\mathcal{GL}$: since the sizes of $\psi_1$ and $\psi_2$ are lower than the size of $\varphi$, the result holds for $\psi_1$ and $\psi_2$. So $\mathcal{IJ} \models \varphi$ iff $\mathcal{IJ} \models \psi_1$ or $\mathcal{IJ} \models \psi_2$ iff $\mathcal{JI} \models \overleftarrow{\psi_1}$ or $\mathcal{JI} \models \overleftarrow{\psi_2}$ iff $\mathcal{JI} \models \overleftarrow{\psi_1} \vee \overleftarrow{\psi_2} = \overleftarrow{\varphi}$.

In any case, $\mathcal{IJ} \models \varphi$ iff $\mathcal{JI} \models \overleftarrow{\varphi}$.

So, according to the principle of induction, the result holds. ■

### 4.4.2 The cp operator

**Proposition 6** 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 $M(\alpha \triangleright \beta) = M(\alpha) \times M(\beta)$.

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

**Proof.** The following proof provides, as a byproduct, a way to compute $\alpha \triangleright \beta$.

Let $\alpha, \beta \in \mathcal{GL}$. Without loss of generality, $\alpha$ and $\beta$ are assumed to be under DNF, since the characterization of $\triangleright$ in Proposition 6 is independent from syntax. So, a formula $\alpha \triangleright \beta$ is syntactically defined for DNF formulas $\alpha$ and $\beta$ and, after that, it is proven that the semantical characterization of $\alpha \triangleright \beta$ in the proposition holds.

The next equivalences reduce the problem to the definition of the operator $\triangleright$ on cubes (for $\alpha, \beta, \alpha_1, \dots, \alpha_p, \beta_1, \dots, \beta_q \in \mathcal{GL}$):

$$ \left( \bigvee_{i=1}^{p} \alpha_i \right) \triangleright \beta \equiv \bigvee_{i=1}^{p} (\alpha_i \triangleright \beta) \qquad \alpha \triangleright \left( \bigvee_{j=1}^{q} \beta_j \right) \equiv \bigvee_{j=1}^{q} (\alpha \triangleright \beta_j) \qquad (3) $$
This comes from

$$ \begin{array}{l} \mathcal{I}\mathcal{J} \models \left( \bigvee_{i=1}^{p} \alpha_i \right) \triangleright \beta \text{ iff } \mathcal{I} \models \bigvee_{i=1}^{p} \alpha_i \text{ and } \mathcal{J} \models \beta \\ \phantom{\mathcal{I}\mathcal{J} \models \left( \bigvee_{i=1}^{p} \alpha_i \right) \triangleright \beta \text{ iff } \mathcal{I} \models \bigvee_{i=1}^{p} \alpha_i \text{ and } \mathcal{J} \models \beta} \text{iff } ((\text{it exists } i) \mathcal{I} \models \alpha_i) \text{ and } \mathcal{J} \models \beta \\ \phantom{\mathcal{I}\mathcal{J} \models \left( \bigvee_{i=1}^{p} \alpha_i \right) \triangleright \beta \text{ iff } \mathcal{I} \models \bigvee_{i=1}^{p} \alpha_i \text{ and } \mathcal{J} \models \beta} \text{iff } (\text{it exists } i) (\mathcal{I} \models \alpha_i \text{ and } \mathcal{J} \models \beta) \\ \text{iff } \mathcal{I}\mathcal{J} \models \bigvee_{i=1}^{p} (\alpha_i \triangleright \beta) \end{array} $$

For the same reasons,

$$ \left( \bigwedge_{i=1}^{p} \alpha_i \right) \triangleright \beta \equiv \bigwedge_{i=1}^{p} (\alpha_i \triangleright \beta) \qquad \alpha \triangleright \left( \bigvee_{j=1}^{q} \beta_j \right) \equiv \bigwedge_{j=1}^{q} (\alpha \triangleright \beta_j) \qquad (4) $$

so the construction is reduced to the case where $\alpha$ and $\beta$ are literals. And, for any two formulas $\alpha$ and $\beta$ of $\mathcal{GL}$,

$$ \alpha \triangleright \beta \equiv (\alpha \triangleright \top) \wedge (\top \triangleright \beta) \qquad (5) $$

because

$$ \begin{array}{l} \mathcal{I}\mathcal{J} \models \alpha \triangleright \beta \text{ iff } \mathcal{I} \models \alpha \text{ and } \mathcal{J} \models \beta \\ \phantom{\mathcal{I}\mathcal{J} \models \alpha \triangleright \beta \text{ iff }} \text{iff } \mathcal{I}\mathcal{J} \models (\alpha \triangleright \top) \text{ and } \mathcal{I}\mathcal{J} \models (\top \triangleright \beta) \\ \phantom{\mathcal{I}\mathcal{J} \models \alpha \triangleright \beta \text{ iff }} \text{iff } \mathcal{I}\mathcal{J} \models (\alpha \triangleright \top) \wedge (\top \triangleright \beta) \end{array} $$

As this is true if $\alpha$ and $\beta$ are literals, 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{Q}$):

$$ \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} \qquad (6) $$

This is due to the fact that

$$ \mathcal{I}\mathcal{J} \models a^{r\bullet} \text{ iff } \mathcal{I}(a) = r \text{ iff } \mathcal{I} \models (a = r) \text{ iff } \mathcal{I}\mathcal{J} \models (a = r) \triangleright \top $$

and

$$ \mathcal{I}\mathcal{J} \models \neg a^{r\bullet} \text{ iff } \mathcal{I}\mathcal{J} \not\models a^{r\bullet} \text{ iff } \mathcal{I}(a) \neq r \text{ iff } \mathcal{I} \not\models (a = r) \text{ iff } \mathcal{I} \models \neg(a = r) \text{ iff } \mathcal{I}\mathcal{J} \models \neg(a = r) \triangleright \top $$

The other proofs are similar.

Remains to prove that the constructed formula is consistent with the property $\mathcal{M}(\alpha \triangleright \beta) = \mathcal{M}(\alpha) \times \mathcal{M}(\beta)$. This is simply done by structural induction, using the models translations of properties (3), (4) and (6). ■

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\}$.

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

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

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

The variation from case $(x^k, y^k)$ to case $(x^l, y^l)$ is represented by $\Delta^{k\ell} = x^k \wedge y^k \triangleright x^l \wedge y^l$. According to what is presented above, since the source cases $x^s \wedge y^s$ are
conjunctions of positive literals of ($\mathcal{PL}$, $|=$), 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^{-2} \wedge b^{2\bullet} \wedge b^{\bullet 0} \wedge c^{-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 [6] 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^{-1}, d^{\bullet 2}\}$ can be made explicit, giving birth to the formula $\varphi = a^{\bullet 1} \wedge c^{-1} \wedge d^{\bullet 2}$ that can be used for representing an adaptation rule, as this can be seen further. Notice that $\overleftarrow{\varphi}$ can also be learnt, corresponding to $(k, \ell) \in \{(2, 1), (3, 2)\}$.

### 4.4.3 The L and R operators

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

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

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

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

If $\alpha$ and $\beta$ are two satisfiable formulas of ($\mathcal{GL}$, $|=$) then $L(\alpha \triangleright \beta) \equiv \alpha$ and $R(\alpha \triangleright \beta) \equiv \beta$.

The R operator<fnref n="4" /> has the following properties:

* $R(\varphi \vee \psi) \equiv R(\varphi) \vee R(\psi)$;

* if $\mathcal{V}(\varphi) \cap \mathcal{V}(\psi) = \emptyset$ then $R(\varphi \wedge \psi) \equiv R(\varphi) \wedge R(\psi)$;

* Let $\theta = \ell_1 \wedge \cdots \wedge \ell_n$ be a normal cube, all literals $\ell_i$ being constructed over the same variable $a$. Then

$$ R(\theta) \equiv \bigwedge_{i=1}^{n} R(\ell_i) $$

**Proof.** In all that is to come, the formulas from ($\mathcal{GL}$, $|=$) and ($\Delta\mathcal{GL}$, $|=$) are supposed to be under DNFNC. The construction is only developed for $R(\varphi)$, the construction for $L(\varphi)$ being completely symmetrical.

First, the three properties are proven:

* The set of models of $R(\varphi \vee \psi)$ is just the union of the sets of models of $R(\varphi)$ and $R(\psi)$. So

$$ R(\varphi \vee \psi) \equiv R(\varphi) \vee R(\psi) $$

* If $\mathcal{J} \models R(\varphi \wedge \psi)$, there is an interpretation $\mathcal{I}$ such that $\mathcal{IJ} \models \varphi \wedge \psi$, so $\mathcal{J} \models R(\varphi)$ and $\mathcal{J} \models R(\psi)$. Suppose now that $\mathcal{J} \models R(\varphi) \wedge R(\psi)$. So, there are $\mathcal{I}_1$ and $\mathcal{I}_2$ such that $\mathcal{I}_1 \mathcal{J} \models \varphi$, and $\mathcal{I}_2 \mathcal{J} \models \psi$. Let $\mathcal{I}$ be defined in the following way:

$$ \mathcal{I}(a) = \begin{cases} \mathcal{I}_1(a) & \text{if } a \in \mathcal{V}(\varphi) \\ \mathcal{I}_2(a) & \text{if } a \in \mathcal{V}(\psi) \\ 1 & \text{else} \end{cases} $$

Since an interpretation satisfies $\varphi$ only from its value on $\mathcal{V}(\varphi)$, $\mathcal{I}_1 \mathcal{J} \models \varphi$ leads to $\mathcal{IJ} \models \varphi$, and similarly $\mathcal{IJ} \models \psi$. Hence $\mathcal{IJ} \models \varphi \wedge \psi$, and $\mathcal{J} \models R(\varphi \wedge \psi)$.

<footnote n="4">⁴The L operator has similar properties.</footnote>
• First the following results are obvious:

$$
\begin{align*}
\mathbf{R}(a^{r\bullet}) &= \mathbf{R}(a^{\dagger r}) = \mathbf{R}(\neg a^{r\bullet}) = \mathbf{R}(\neg a^{\dagger r}) = \top, \\
\mathbf{R}(a^{\bullet r}) &= (a = r) \quad \text{and} \quad \mathbf{R}(\neg a^{\bullet r}) = \neg (a = r)
\end{align*}
$$

Now there are three possibilities for a complete cube $\theta$ over a single variable $a$:

- $\theta$ has three (compatible) positive literals: $\theta = a^{r\bullet} \wedge a^{\bullet s} \wedge a^{\dagger s-r}$. The set of models of $\theta$ can be represented as follow:

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

which makes it clear that $R(\theta) \equiv (a = s) \equiv \mathbf{R}(a^{r\bullet}) \wedge \mathbf{R}(a^{\bullet s}) \wedge \mathbf{R}(a^{\dagger s-r})$.

- $\theta$ has one positive literal and several negative literals of a different kind:

* $\theta = a^{r\bullet} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i} \wedge \bigwedge_{i \in I} \neg a^{\dagger (s_i - r)}$, for which the set of interpretations can be represented as:

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

from which it can be concluded that

$$
\mathbf{R} \left( a^{r\bullet} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i} \wedge \bigwedge_{i \in I} \neg a^{\dagger (s_i - r)} \right) = \bigwedge_{i \in I} \neg (a = s_i)
$$

* $\theta = a^{r\bullet} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i} \wedge \bigwedge_{i \in I} \neg a^{\dagger (s_i - r)}$, for which the set of interpretations is:

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

from which it can be inferred that

$$
\mathbf{R} \left( a^{\bullet r} \wedge \bigwedge_{i \in I} \neg a^{s_i \bullet} \wedge \bigwedge_{i \in I} \neg a^{\dagger (r-s_i)} \right) = (a = r)
$$

* $\theta = a^{\dagger r} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i + r}$, for which the set of interpretations is:

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

and therefore

$$
\mathbf{R} \left( a^{\dagger r} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i} \wedge \bigwedge_{i \in I} \neg a^{\bullet s_i + r} \right) = \bigwedge_{i \in I} \neg (a = s_i + r)
$$

- $\theta$ has only negative literals: $\theta = \bigwedge_{i \in I} \neg a^{r_i \bullet} \wedge \bigwedge_{j \in J} \neg a^{\bullet s_j} \wedge \bigwedge_{k \in K} \neg a^{\dagger t_k}$ for which the set of interpretations has the form

<figure><img src="image_9.png" /></figure>
so

$$R\left(\bigwedge_{i \in I} \neg a^{r_i \bullet} \wedge \bigwedge_{j \in J} \neg a^{\bullet s_j} \wedge \bigwedge_{k \in K} \neg a^{\bullet t_k}\right) = \bigwedge_{j \in J} \neg (a = s_j)$$

In all those cases, it can be verified that

$$R\left(\bigwedge_{i \in I} \ell_i\right) = \bigwedge_{i \in I} R(\ell_i)$$

From this emerges an algorithm to compute $R(\varphi)$, if $\varphi$ is in DNFNC:

* the first property shows that if $\varphi = \bigvee_{i \in I} \theta_i$ is a disjunction of (normal) cubes, then

$$R(\varphi) = \bigvee_{i \in I} R(\theta_i)$$

* the second property shows that if $V' \subseteq V$, and if $\theta = \bigwedge_{a \in V'} \theta_a$, where all the $\theta_a$, and therefore $\theta$, are normal cubes, each $\theta_a$ being a cube over the single variable $a$, then

$$R(\theta) \equiv \bigwedge_{a \in V'} R(\theta_a)$$

* the last property shows how to compute $R(\theta_a)$, where $\theta_a$ is a cube over a single variable $a$.

The fact that the construction mentioned above has the right properties announced in the proposition is straightforward.

Remains to be proven that if $\alpha$ and $\beta$ are two satisfiable formulas of $(GL, \models)$, then $L(\alpha \triangleright \beta) \equiv \alpha$. This comes from the fact that

$$\begin{align*}
M(L(\alpha \triangleright \beta)) &= \{\mathcal{I} \mid \text{there exists } \mathcal{J} \in \Omega \text{ such that } \mathcal{I}\mathcal{J} \models \alpha \triangleright \beta\} \\
&= \{\mathcal{I} \mid \text{there exists } \mathcal{J} \in \Omega \text{ such that } \mathcal{I} \models \alpha \text{ and } \mathcal{J} \models \beta\} \\
&= M(\alpha)
\end{align*}$$

The last equality comes from the fact that $\beta$ is supposed satisfiable (the same $\mathcal{J}$ satisfying $\beta$ for all the models of $\alpha$ can be chosen). ■

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

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

Here is an alternative way to define invariant variables:

**Proposition 8** Let $\varphi \in \Delta GL$ and $a \in V$. a is invariant if and only if the following assertion holds:

for all interpretations $\mathcal{I}\mathcal{J}$ and $\mathcal{I}'\mathcal{J}'$ such that

$\mathcal{I}(x) = \mathcal{I}'(x)$ and $\mathcal{J}(x) = \mathcal{J}'(x)$ for all variable $x \neq a$,

$\mathcal{I}\mathcal{J} \models \varphi \quad \text{iff} \quad \mathcal{I}'\mathcal{J}' \models \varphi$.

Intuitively, $a \in \mathrm{Inv}(\varphi)$ if the truth value of $\varphi$ over an interpretation $\mathcal{I}\mathcal{J}$ does not depend on the value $(\mathcal{I}(a), \mathcal{J}(a))$.
**Proof.** In this proof, $\mathcal{I}\mathcal{J}(x)$ is an abbreviation of $(\mathcal{I}(x), \mathcal{J}(x))$.

If $\varphi \equiv \psi$ and $a \notin \mathcal{V}(\psi)$, then the truth value of $\varphi$ over interpretation $\mathcal{I}\mathcal{J}$ does not depend on the value of $\mathcal{I}\mathcal{J}$ over $a$.

Suppose now that for all interpretations $\mathcal{I}\mathcal{J}$ and $\mathcal{I}'\mathcal{J}'$ such that $\mathcal{I}\mathcal{J}(x) = \mathcal{I}'\mathcal{J}'(x)$ whenever $x \neq a$, $\mathcal{I}\mathcal{J} \models \varphi$ iff $\mathcal{I}'\mathcal{J}' \models \varphi$. The goal is to build a formula $\psi$ such that $\varphi \equiv \psi$ and $a \notin \mathcal{V}(\psi)$.

Without loss of generality, it is assumed that $\varphi$ is in DNFNC:

$$ \varphi = \bigvee_{i=1}^{n} \theta_{i,a} \wedge \Theta_{i} $$

where each $\theta_{i,a}$ is a normal cube over the single variable $a$, and $\Theta_i$ a normal cube such that $a \notin \mathcal{V}(\Theta_i)$.

Now let $\mathcal{L}_a$ be the set of all literals (positive or negative) appearing in any $\theta_{i,a}$, along with their negations and their direct consequences. For example, if $a^{r\bullet}$ and $a^{\bullet s}$ are sub-formulas of $\varphi$, the literals $a^{\bullet(r+s)}$ and $\neg a^{\bullet(r+s)}$ are added to $\mathcal{L}_a$.

Define a set $\mathcal{C}_a$ of cubes formed of literals of $\mathcal{L}_a$, such that:

(1) every $\theta_{i,a}$ can be written as a disjunction of cubes of $\mathcal{C}_a$,

(2) any two cubes of $\mathcal{C}_a$ are mutually incompatible.

$\mathcal{C}_a$ contains three types of cubes:

(a) all the cubes formed of three compatible positive literals of $\mathcal{L}_a$, of the form $a^{r\bullet} \wedge a^{\bullet s} \wedge a^{\bullet(s-r)}$,

(b) all the cubes formed of one positive literal $\ell$ of $\mathcal{L}_a$, and all the negative literals of $\mathcal{L}_a$ using a different variation symbol than $\ell$, such as

$$ a^{r\bullet} \wedge \bigwedge_{s \neq r} a^{\bullet s} \wedge a^{\bullet(s-r)} $$

(c) a unique cube which is the conjunction of all negative literals of $\mathcal{L}_a$.

By construction, if $\theta_1, \theta_2 \in \mathcal{C}_-$ with $\theta_1 \neq \theta_2$, they are inconsistent one with the other. It remains to be proven that any $\theta_{i,a}$ can be written as a disjunction of cubes of $\mathcal{C}_a$.

Since the $\theta_{i,a}$ are normal cubes, three cases are to be considered:

* if $\theta_{i,a}$ is a conjunction of three positive (and compatible) literals, then $\theta_{i,a}$ is already in $\mathcal{C}_a$;

* if $\theta_{i,a}$ is a conjunction of one positive literal and several negative literals with another variation symbol, associated with all the consequences, then $\theta_{i,a}$ can be written as the cube of form (b) of $\mathcal{C}_a$ with the same positive literal, and all the cubes of $\mathcal{C}_a$ of form (a) where one positive literal is the one from $\theta_{i,a}$, and the others are the positive versions of the missing negative literals of $\theta_{i,a}$;

for example, if $\mathcal{L}_a = \{a^{0\bullet}, a^{1\bullet}, a^{\bullet 2}, a^{\bullet 2}, a^{\bullet 3}\}$, then

$$ a^{\bullet 2} \equiv (a^{\bullet 2} \wedge \neg a^{0\bullet} \wedge \neg a^{1\bullet} \wedge \neg a^{\bullet 2} \wedge \neg a^{\bullet 3}) \vee (a^{0\bullet} \wedge a^{\bullet 2} \wedge a^{\bullet 2}) \vee (a^{1\bullet} \wedge a^{\bullet 3} \wedge a^{\bullet 2}) $$

* finally, if $\theta_{i,a}$ is a conjunction of negative literals, then as above $\theta_{i,a}$ can be written as a conjunction of the cube of form (c), and any cube of type (b) of $\mathcal{C}_a$ with one positive literal such as its negation does not appear in $\theta_{i,a}$.

Now, $\varphi$ can be written as a disjunction of the form

$$ \varphi \equiv \varphi' = \bigvee_{c \in \mathcal{C}_a} c \wedge \varphi_c $$
where the $\varphi_c$'s do not contain $a$ as a variable. By the initial hypothesis, the truth value of $\varphi'$ over an interpretation $\mathcal{IJ}$ does not depend on the value of $\mathcal{IJ}$ over $a$.

For any given interpretation $\mathcal{IJ}$, there are interpretations $\mathcal{IJ}_c$, for $c \in C_a$, such that $\mathcal{IJ}_c \models c$, $\mathcal{IJ} \not\models c'$ if $c' \in C_a \setminus \{c\}$, and $\mathcal{IJ}_c(x) = \mathcal{IJ}_{c'}(x)$ for any pair $(c, c') \in C_a^2$ and any variable $x \neq a$.

But for any pair $(c, c') \in C_a^2$, $\mathcal{IJ}_c \models \varphi'$ iff $\mathcal{IJ}_{c'}$. As the $\varphi_c$'s do not contain the variable $a$, they must all be satisfied or not satisfied together under all those interpretations, which means that they are all equivalent to a formula $\psi$ (which does not contain the variable $a$).

To conclude,

$$ \varphi \equiv \bigvee_{c \in C_a} c \wedge \psi \equiv \left( \bigvee_{c \in C_a} c \right) \wedge \psi $$

and as $\{\mathcal{M}(\theta) | \theta \in C_\downarrow\}$, is partition of $\Delta\Omega$, the parenthesis above is equivalent to $\top$, and $\varphi \equiv \psi$, which finishes the proof. ■

# 5 Representing adaptation rules

The $(\Delta\mathcal{G}\mathcal{L}, \models)$ representation formalism has been designed for representing variations 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 operator

Let us consider again the adaptation rule of the cooking domain considered in the introduction. Written conjunctively, it corresponds to the $(\Delta\mathcal{G}\mathcal{L}, \models)$ cube, for $\mathcal{G} = \mathbb{Q}$: $\varphi = \text{dessert}^{=1} \wedge \text{eggs}^{=2} \wedge \text{bananas}^{=1}$. Now, consider a recipe of dessert 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 = \mathbb{R}(\theta)$. Let $\mathcal{IJ}$ 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{IJ} \models \alpha \triangleright \top$. Furthermore, $\theta$ should specialize $\varphi$, i.e. $\theta \models \varphi$, which entails that (b) $\mathcal{IJ} \models \varphi$. If (a) and (b) were the only conditions for $\mathcal{IJ}$ this would entail that $\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 the 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 are invariant in $\varphi$. Now, the following assertion is made: if a variable in 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$ in the same way as in $\beta$; formally $\{\mathcal{I}(a) | \mathcal{IJ} \in \mathcal{M}(\theta)\} = \{\mathcal{J}(a) | \mathcal{IJ} \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 in 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{aligned} \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} \\ &\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) \\ &\wedge (\text{flour}_{\text{gram}} = 50) \wedge (\text{butter}_{\text{gram}} = 20) \end{aligned} $$

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="5" /> of $\varphi$ wrt $W$ is defined by

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

$\mathrm{cp}(\varphi)$ is an abbreviation of $\mathrm{cp}_V(\varphi)$ (every variable is considered in $\mathrm{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 \mathrm{cp}(\varphi)$ and the result of this transformation is $\beta = \mathbb{R}(\theta)$. Now, a constraint can be added on the result of this transformation. If this constraint in represented by $\gamma \in \mathcal{GL}$, then it is possible to define the transformation and 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 transf($\alpha, \varphi, \gamma) \in \Delta\mathcal{GL}$ defined by

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

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

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

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

In practice, the computation of $\mathrm{appl}(\alpha, \varphi, \gamma)$ should only consider the variables occurring in at least one of the formulas $\alpha, \varphi$ and $\gamma$, as the following proposition shows:

**Proposition 9** Let $\alpha, \gamma \in \mathcal{GL}$ and $\varphi \in \Delta\mathcal{GL}$. Then

$$ \mathrm{appl}(\alpha, \varphi, \gamma) \equiv \mathbb{R}((\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi)) \qquad (7) $$

where $W = \mathcal{V}(\alpha) \cup \mathcal{V}(\gamma) \cup \mathcal{V}(\varphi)$.

**Proof.** Since $\mathrm{cp}(\varphi) \equiv \mathrm{cp}_W(\varphi) \wedge \bigwedge_{a \in \mathcal{V} \setminus W} a^{+0}$, it comes that

$$ \begin{align*} \mathrm{appl}(\alpha, \varphi, \gamma) &\equiv \mathbb{R} \left( (\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi) \wedge \bigwedge_{a \in \mathcal{V} \setminus W} a^{+0} \right) \\ &\equiv \mathbb{R}((\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi)) \wedge \bigwedge_{a \in \mathcal{V} \setminus W} \mathbb{R} \left( \bigwedge_{a \in \mathcal{V} \setminus W} a^{+0} \right) \\ &\equiv \mathbb{R}((\alpha \triangleright \gamma) \wedge \mathrm{cp}_W(\varphi)) \wedge \top \end{align*} $$

The two last equivalences come from the fact that the variables of both parts of the formula have disjoint sets of variables, and from $\mathbb{R}(a^{+0}) \equiv \top$. ■

<footnote n="5">⁵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, i.e. the risk taken by applying ar on an adaptation problem (the higher cost is, the riskier the adaptation is).

Below, a proposition of formalizing 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 the 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 is, 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 on 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 = B = {0, 1} (subset of the group (Z, +)). The adaptation of this algorithm for another G (in particular G = Z or G = Q) requires some modification of the algorithm, as briefly explained in the end of the section.

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

The dissimilarity measure associated to AK, denoted by diss<sub>AK</sub>, is the function that associates to (α, β) ∈ GL<sup>2</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. For I, J ∈ Ω, diss<sub>AK</sub>(I, J) is defined by diss<sub>AK</sub>(α<sub>I</sub>, α<sub>J</sub>). Then diss<sub>AK</sub> restricted to Ω<sup>2</sup> satisfies diss<sub>AK</sub>(I, J) = 0 iff I = J.

To avoid the situation diss<sub>AK</sub>(α, β) = ∞ for two consistent static formulas α and β, some adaptation rules can be added to AK to obtain ÂK defined by

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

The additional adaptation rules (a<sup>\star 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, $\mathbf{x}^{\text{tgt}} \in \mathcal{G}\mathcal{L}$.

**Retrieval:** Find $(\mathbf{x}^s, \mathbf{y}^s) \in \text{CB}$ that minimizes $\text{diss}_{\widehat{\mathcal{A}\mathcal{K}}}(\mathbf{x}^s \wedge \mathbf{y}^s, \text{tgt})$, and the corresponding adaptation path AP from $\mathbf{x}^s \wedge \mathbf{y}^s$ to $\mathbf{x}^{\text{tgt}}$.

**Adaptation:** Apply AP on $\mathbf{x}^s \wedge \mathbf{y}^s$ to obtain a consistent formula $\beta$ such that $\beta \models \mathbf{x}^{\text{tgt}}$, and let $\mathbf{y}^{\text{tgt}}$ be such that $\beta \equiv \mathbf{x}^{\text{tgt}} \wedge \mathbf{y}^{\text{tgt}}$. $\mathbf{y}^{\text{tgt}}$ 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 $(\alpha, C)$ where $\alpha \in \mathcal{G}\mathcal{L}$ is consistent, $C \in \mathbb{Q}$ and $C \ge 0$.

* The set of initial states is $\{(\mathbf{x}^s \wedge \mathbf{y}^s, 0) \mid (\mathbf{x}^s, \mathbf{y}^s) \in \text{CB}\}$.

* A successor of a state $(\alpha, C)$ is a state $(\beta, C')$ for which there exists $\mathbf{ar} = (\varphi, \text{cost}) \in \widehat{\mathcal{A}\mathcal{K}}$ such that $\beta = \text{appl}(\alpha, \varphi, \top)$ and $C' = C + \text{cost}$.

* A final state $(\alpha, C)$ is such that $\alpha \wedge \mathbf{x}^{\text{tgt}}$ is consistent.

* The states $(\alpha, C)$ are searched by non-decreasing $C$.

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

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 \le \frac{|\widehat{\mathcal{A}\mathcal{K}}|}{|\mathcal{G}\mathcal{L}|}$ but is much lower in practice if, on the average, only few adaptation rules are applicable on a cube of $(\mathcal{G}\mathcal{L}, \models)$). Under the assumptions of Section 3.5, 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(|\text{CB}| \cdot |\mathcal{V}| \cdot b^q)$, thus proportional to the size of the case base. Case adaptation is fast: it consists mainly in using the value $\beta$ of the application of AP on the retrieved case.

**Proof of complexity of the naive algorithm.** The complexity of the algorithm is in $O(N \times S)$ where $N$ is the number of states generated during the search and $S$ is the complexity of the generation of a single state. The number of initial states is $|\text{CB}|$, the depth of the tree is $q$ and the average branching factor is $b$, so $N$ is in $O(|\text{CB}| \cdot b^q)$.

The generation of a state is made by application of a rule $\mathbf{ar} = (\varphi, \text{cost})$ on a state $(\alpha, C)$, i.e. by computing $\text{appl}(\alpha, \varphi, \top) = \mathbf{R}((\alpha \triangleright \top) \wedge \text{cp}(\varphi))$. Now $\alpha$ and $\varphi$ are cubes: $\alpha$ is a cube because $\mathbf{x}^s \wedge \mathbf{y}^s$ is and because $\text{appl}(\beta, \psi, \top)$ returns a cube whenever $\psi$ and $\beta$ are cubes. The computation of $\alpha \triangleright \top$ and of $\text{cp}(\varphi)$ are in $O(|\mathcal{V}|)$ (and the computation of $\text{cp}(\varphi)$ could be done offline, which might affect the order of complexity if $\varphi$ was not a cube). The computation of $\mathbf{R}(\theta)$ for a cube $\theta$ is also in $O(|\mathcal{V}|)$. So $S$ is in $O(|\mathcal{V}|)$.

Therefore, it can be concluded that the complexity of the naive algorithm is in $O(|\text{CB}| \cdot |\mathcal{V}| \cdot b^q)$. $\blacksquare$

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

* The set of adaptation rules is $\overleftarrow{\widehat{\mathcal{A}\mathcal{K}}} = \{\overleftarrow{\mathbf{ar}} \mid \mathbf{ar} \in \widehat{\mathcal{A}\mathcal{K}}\}$.

* The sole initial state is $\mathbf{x}^{\text{tgt}}$.

* A final state $(\alpha, C)$ is such that there exists $(\mathbf{x}^s, \mathbf{y}^s) \in \text{CB}$ such that $\mathbf{x}^s \wedge \mathbf{y}^s \wedge \alpha$ is consistent. This exact match search can be performed in $O(|\mathcal{V}_P|)$ thanks to an organization of the case base in a binary tree of depth $|\mathcal{V}_P|$.
The output of this search is a retrieved case $(x^s, y^s) \in CB$ and an adaptation path $AP = ar^1;...; ar^q$
from $x^{\text{tgt}}$ to $x^s \wedge y^s$ based on the set of adaptation rules $\overleftarrow{AK}$. Then, the inverse adaptation path $\overrightarrow{AP} =
\overleftarrow{ar^q};...; \overleftarrow{ar^1}$ is computed, resulting in the same adaptation path as the one produced by the naive algo-
rithm. Finally, adaptation consists in sequentially applying $\overleftarrow{AP}$ on $x^s \wedge y^s$ (in $q$ steps) to get $\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 from the size of the case base. 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 10** 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:

$$
\mathrm{appl}(\alpha, \varphi, \gamma) \not\models \perp \quad \text{iff} \quad \mathrm{appl}(\gamma, \overleftarrow{\varphi}, \top) \wedge \alpha \not\models \perp
$$

**Proof.** Let $\alpha$ and $\gamma$ be any formulas of $(\mathcal{G}\mathcal{L}, \models)$ (not just cubes).

Saying that $appl(\alpha, \varphi, \gamma) \not\models \perp$ amounts to saying that there is an interpretation $\mathcal{J}$ satisfying the
formula on the left. Now, the following sequence of equivalences holds:

there exists $\mathcal{J} \in \Omega$ such that $\mathcal{J} \models (\mathbb{R}((\alpha \triangleright \gamma) \wedge \mathrm{cp}(\varphi)))$

iff there exists $\mathcal{I}\mathcal{J} \in \Delta\Omega$ such that $\mathcal{I}\mathcal{J} \models (\alpha \triangleright \gamma) \wedge \mathrm{cp}(\varphi)$

iff there exists $\mathcal{I}\mathcal{J} \in \Delta\Omega$ such that $\mathcal{I}\mathcal{J} \models \alpha \triangleright \gamma$ and $\mathcal{I}\mathcal{J} \models \mathrm{cp}(\varphi)$

iff there exists $\mathcal{I}\mathcal{J} \in \Delta\Omega$ such that $\mathcal{I} \models \alpha$, $\mathcal{J} \models \gamma$ and $\mathcal{I}\mathcal{J} \models \mathrm{cp}(\varphi)$

iff there exists $\mathcal{I}\mathcal{J} \in \Delta\Omega$ such that $\mathcal{J}\mathcal{I} \models \gamma \triangleright \top$, $\mathcal{J}\mathcal{I} \models \mathrm{cp}(\overleftarrow{\varphi})$ and $\mathcal{I} \models \alpha$

iff there exists $\mathcal{I}\mathcal{J} \in \Delta\Omega$ such that $\mathcal{J}\mathcal{I} \models (\gamma \triangleright \top) \wedge \mathrm{cp}(\overleftarrow{\varphi})$ and $\mathcal{I} \models \alpha$

iff there exists $\mathcal{I} \in \Omega$ such that [there exists $\mathcal{J}$ such that $\mathcal{J}\mathcal{I} \models (\gamma \triangleright \top) \wedge \mathrm{cp}(\overleftarrow{\varphi})$] and $\mathcal{I} \models \alpha$

iff there exists $\mathcal{I} \in \Omega$ such that $\mathcal{I} \models \mathbb{R}((\gamma \triangleright \top) \wedge \mathrm{cp}(\overleftarrow{\varphi})) \wedge \alpha$

which is equivalent to the fact that $appl(\gamma, \overleftarrow{\varphi}, \top) \wedge \alpha \not\models \perp$, and that concludes the proof. ■

If $G = \mathbb{Z}$, the algorithm presented above theoretically works, but may be of a complexity too high.
For example, if $a \in V_P$ does not occur in any adaptation rule of AK (thus occurs only in $(a^{*1}, 1)$ and
$(a^{-1}, 1)$), if the case $(x^s, y^s)$ to be retrieved satisfies $x^s \wedge y^s \models (a=r)$ and if $x^{\text{tgt}} \models (a=s)$, then the
length $q$ of the adaptation path AP to be returned by retrieval satisfies $q \ge |s-r|$. Then, the term $b^q$ would
be huge whenever $|s-r|$ is large. Therefore, the proposed approach should be reused as such when the
practical range of variables is reasonably small (this also requires changes in the exact matching step).
Otherwise, or when $G = \mathbb{Q}$, another approach has to be considered: this is left for future work.

7 Discussion and conclusion

This article 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 [11]: 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 to the adaptation knowledge. Moreover, if the attributes have all a Boolean range, the retrieval complexity is independent from the size of the case base. Finally, the retrieval knowledge is determined by the adaptation knowledge: it is defined by the dissimilarity measure diss̃$_{AK}$.

This theoretical work can be continued along several directions.

A first direction of work is to confront this approach to practical applications and/or benchmarks,
using an adaptation knowledge learning system to feed AK.
This work has considered mainly 3 knowledge containers of a CBR system: CB and AK, obviously, but also the retrieval knowledge disŝ$_{AK}$ 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 the static knowledge DK be used for inference in $(\Delta G L, \models)$ and adaptation rules is a question still requiring some consideration.

The theoretical study of the logic $(\Delta G L, \models)$ has mainly been carried out when $(G, +)$ is an infinite group. This impacts in particular the normal form of cubes and thus the DNFNC form of variation formulas. If $(G, +)$ is a finite abelian group, the notion of normal cube has to be changed because a finite conjunction of negative literals can be insatisfiable, which cannot arise if $G$ is infinite. For example, if $G = \mathbb{Z}/2\mathbb{Z}$ (the group with two elements 0 and 1 such that $0 + 0 = 1 + 1 = 0$ and $0 + 1 = 1 + 0 = 1$) then $\neg(a = 0) \wedge \neg(a = 1)$ is insatisfiable.

It can be proven that, for a finite abelian group $(G, +)$, every variation formula can be put in DNFNC form where a normal cube is either $\perp$ or a conjunction of atoms (i.e. without negative literals). To prove this, first, a formula $\varphi$ is put into negative normal form (i.e. the negation connective occurs only before atoms) and the following equivalences are applied on every negative literals: $\neg a^{\star r} \equiv \bigvee_{s \in G \setminus \{r\}} a^{\star s}$, $\neg a^{\star \bullet} \equiv \bigvee_{s \in G \setminus \{r\}} a^{\star \bullet}$ and $\neg a^{\bullet r} \equiv \bigvee_{s \in G \setminus \{r\}} a^{\bullet s}$. So, a negation-free formula is obtained that can be put in DNF with no negation, i.e. with only normal cubes. In particular, for $G = \mathbb{Z}/2\mathbb{Z}$, every formula can be put in DNF form without any negation connective and with only two atoms per variable $a$: $a^{\star 0}$ and $a^{\star 1}$. For example the variation formula $\varphi = \neg(a^{\star 1} \vee b^{\star 0})$ can be put in DNFNC (without negations): $\varphi \equiv \neg a^{\star 1} \wedge \neg b^{\star 0} \equiv a^{\star 0} \wedge b^{\star 1}$ (for $G = \mathbb{Z}/2\mathbb{Z}$).

Olaaf is an adaptation engine based on belief revision in a logic where atoms are linear constraints and which is propositionally closed [2]. The theory on which it is based in mainly centered on the domain knowledge DK and on a dissimilarity measure diss between interpretations. Some adaptation rule are “simulated” in Olaaf by adding pieces of knowledge to DK and/or by modifying diss, though this aspect of Olaaf has not yet been investigated in details. By contrast, the approach proposed in this article in 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] 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

[4] 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

[5] 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
[6] 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

[7] 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

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

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

[10] Smullyan, R.M.: First-order logic. Courier Corporation (1995)

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