Isabelle Bloch
email: isabelle.bloch@sorbonne-universite.fr

Jérôme Lang
email: lang@lamsade.dauphine.fr

Ramón Pino Pérez
email: pinoperez@cril.fr

Carlos Uzcátegui

Morphologic for knowledge dynamics: revision, fusion, abduction

Keywords: Mathematical Morphology, Morphologic, Knowledge Representation, Knowledge Dynamics, Belief Revision, Fusion, Abduction

Several tasks in artificial intelligence require the ability to find models about knowledge dynamics. They include belief revision, fusion and belief merging, and abduction. In this paper we exploit the algebraic framework of mathematical morphology in the context of propositional logic, and define operations such as dilation or erosion of a set of formulas. We derive concrete operators, based on a semantic approach, that have an intuitive interpretation and that are formally well behaved, to perform revision, fusion and abduction. Computation and tractability are addressed, and simple examples illustrate the main results.

Introduction

Several tasks in artificial intelligence require to be able to find models about knowledge dynamics. In particular, how do beliefs change in the light of a new observation, how can we extract a coherent source of information from many sources of information (eventually contradictory), and how can a given observation be explained? All these questions fall more precisely under the following topics: belief revision, belief merging or fusion, and abduction, respectively.

Such tasks have been formalized and axiomatized in various logics. It is out of the scope of this paper to review the huge amount of work done in this direction, and we will rely on existing postulates, now rather widely accepted, such as AGM postulates for revision [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF], integrity constraints postulates for merging and fusion [START_REF] Konieczny | On the Logic of Merging[END_REF][START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF][START_REF] Konieczny | Logic based merging[END_REF], rationality postulates for abduction and explanatory relations [START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF][START_REF] Pino Pérez | Preferences and explanations[END_REF].

Here propositional logic is considered, and propositional formulas are used to encode either pieces of knowledge (which may be generic, for instance integrity constraints, or factual such as observations), or subjective items such as beliefs or preferences. Such formulas are then used for complex reasoning or decision making tasks.

In this paper, we propose to build tools for modeling knowledge dynamics based on mathematical morphology operators applied to propositional formulas. Mathematical morphology is originally based on set theory. It was introduced in 1964 by Matheron [START_REF] Matheron | Eléments pour une théorie des milieux poreux[END_REF][START_REF] Matheron | Random Sets and Integral Geometry[END_REF], in order to study porous media. But this theory evolved rapidly to a general theory of shape and its transformations, and was applied in particular in image processing and pattern recognition [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. Additionally to its set-theoretical foundations, it also relies on topology on sets, on random sets, on topological algebra, on integral geometry, on lattice theory. In particular, the general algebraic framework of lattices allows developing mathematical morphology in various domains of information processing, beyond sets and functions, such as fuzzy sets, logics, graphs, hypergraphs, formal concept analysis, etc. [START_REF] Bloch | Lattices of fuzzy sets and bipolar fuzzy sets, and mathematical morphology[END_REF][START_REF] Bloch | Mathematical morphology on hypergraphs, application to similarity and positive kernel[END_REF][START_REF] Bloch | Mathematical Morphology[END_REF][START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF][START_REF] Ronse | Why Mathematical Morphology Needs Complete Lattices[END_REF].

This paper aims to develop mathematical morphology in propositional logics, called morphologic, and to show that it can capture many tasks or operators in revision, fusion and abduction, some of which are already known in the literature, some others are new. The ambition of our paper is, before all, to show the generality of our framework and its ability to connect automated reasoning or decision tasks and to see them under a generic umbrella.

We will make use of two important operations, dilations and erosions. Intuitively, when applied to a set, the effect of dilation is to expand the set while the effect of erosion is to shrink the set.

The following ideas explain intuitively why morphologic is an adequate tool for knowledge dynamics:

• Belief revision: let ϕ and ψ be two propositional formulas. The models of the revision ϕ • ψ of ϕ by ψ are the models of ψ which are closest (with respect to a given proximity notion) to a model of ϕ. Intuitively, using the language of morphologic, it means that ϕ has to be dilated enough to become consistent with ψ. • Belief merging: finding the best compromise between a finite set of formulas ϕ 1 , ... ϕ n amounts to selecting the models that minimize the aggregation (using some given operator) of the distances to each of the ϕ i . This amounts intuitively to dilating simultaneously all the ϕ i until they constitute a consistent set. • Abductive reasoning: preferred explanations of a formula are defined based on a set of axioms, several of which being close to properties of morphological operators, in particular erosion.

An important noticeable aspect is that the framework of morphologic gives us not only natural and general notions to deal with many tasks of knowledge dynamics, but this approach is also well behaved. Actually, the operators and relations obtained via the morphological tools enjoy good rationality properties. Moreover, last but not least, under certain assumptions there are interesting ways of computing some of our proposed operators.

The main contribution of this work is to propose such models in the framework of morphologic, based on a semantic approach. One interesting aspect is that the proposed operators include some of the existing ones, and also new ones. For each of them, the properties will be analyzed and discussed. Finally, the outcome is a toolbox of operational methods, among which a user can choose according to the required properties.

We have to make it clear, however, that our primary goal is not to develop brand new methods for revision, merging or abduction (even if we do, in Section 6, propose new operators). Neither it is to design specific algorithms for each of these types of reasoning or decision tasks that would perform better than existing algorithms. The originality of our approach is its generality: we develop notions and tools that can be applied to a variety of tasks; we focus on revision, merging, and abduction mainly to demonstrate that it can be successfully applied to various tasks, but it can be more generally applied to other subdomains of AI where distances play a major role (e.g. spatial reasoning [START_REF] Aiello | The Mathematical morpho-logical view on reasoning about space[END_REF][START_REF] Aiguier | Logical dual concepts based on mathematical morphology in stratified institutions: Applications to spatial reasoning[END_REF][START_REF] Bloch | Modal Logics based on Mathematical Morphology for Spatial Reasoning[END_REF][START_REF] Bloch | On some associations between mathematical morphology and artificial intelligence[END_REF]).

This paper is organized as follows: Section 2 is devoted to the presentation of concepts in mathematical morphology and to introduce logical morphology (morphologic). Section 3 shows the general techniques of computation of the operators when the metric over the space of valuations is given by the Hamming distance. Section 4 is devoted to showing how well-known revision operators can be interpreted in the framework of morphologic. Section 5 proposes a similar analysis in the framework of fusion. It shows how belief merging operators can be interpreted in the framework of morphologic. Section 6 is devoted to abduction (explanatory relations) built on morphological operations aiming to capture the notion of the most central part. Based on a common notion of pre-order relation on models, derived from morphological operators, Section 6.3 presents a unified framework for revision and abduction. In Section 7 we finish with some concluding remarks and perspectives for future work.

From mathematical morphology to logical morphology

In this section we recall the main concepts and tools used in mathematical morphology and their interpretation in mathematical logic. This interpretation is possible via the identification between a logical formula and a set of interpretations (its models) in the framework of finite propositional logic.

Algebraic framework: complete lattices

Mathematical morphology relies on concepts and tools from various branches of mathematics: algebra (lattice theory), topology, discrete geometry, integral geometry, geometrical probability, partial differential equations, etc. [START_REF] Matheron | Random Sets and Integral Geometry[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]; in fact any mathematical theory that deals with shapes, their combinations or their evolution, can be brought to contribute to morphological theory. When adopting a logics point of view, the algebraic framework is particularly relevant, and we will concentrate on it in the sequel.

The basic structure in this framework is a complete lattice (L, ≤) 1 . We denote the supremum by , the infimum by , the smallest element by 0 L and the greatest element by 1 L . We have 0 L = L = ∅ and 1 L = L = ∅. The framework of complete lattices is fundamental in mathematical morphology, as explained in [START_REF] Heijmans | The Algebraic Basis of Mathematical Morphology -Part I: Dilations and Erosions[END_REF][START_REF] Ronse | The Algebraic Basis of Mathematical Morphology -Part II: Openings and Closings[END_REF][START_REF] Ronse | Why Mathematical Morphology Needs Complete Lattices[END_REF].

All the following definitions and results are detailed in textbooks on mathematical morphology, such as [START_REF] Heijmans | Morphological Image Operators[END_REF][START_REF]Mathematical morphology: from theory to applications[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology, Part II: Theoretical Advances[END_REF]. We restrict the presentation to operators from (L, ≤) into itself.

An algebraic dilation is defined as an operator δ on L that commutes with the supremum, and an algebraic erosion as an operator ε that commutes with the infimum, i.e. for every family (x i ) i∈I of elements of L (finite or not), where I is an index set, we have:

δ( i∈I x i ) = i∈I δ(x i ), (1)
ε(

i∈I x i ) = i∈I ε(x i ). (2)
These are the two main operators, from which a lot of others can be built. Among the numerous examples of complete lattices, one will be particularly interesting for the extension to logics: (P(E), ⊆), the set of subsets of a set E, endowed with the set-theoretical inclusion. It is a Boolean lattice (i.e. complemented and distributive). The smallest and greatest elements are 0 L = ∅ and 1 L = E, respectively.

Algebraic dilations and erosions in (L, ≤) satisfy the following properties:

• δ(0 L ) = 0 L and ε(1 L ) = 1 L ,
• δ and ε are increasing with respect to the partial ordering on L,

• in (P(E), ⊆), δ(X) = ∪ x∈X δ({x}).
Another important concept is the one of adjunction. A pair of operators (ε, δ) defines an adjunction on (L, ≤) if:

∀(x, y) ∈ L 2 , δ(x) ≤ y ⇔ x ≤ ε(y). (3)
If a pair of operators (ε, δ) defines an adjunction, the following important properties hold:

• δ(0 L ) = 0 L and ε(1 L ) = 1 L ,
• δ is a dilation and ε is an erosion (in the algebraic sense expressed by Equations 1 and 2); • δε ≤ Id, where Id denotes the identity mapping on L (i.e. δε is anti-extensive); • Id ≤ εδ (i.e. εδ is extensive); • δεδε = δε and εδεδ = εδ, i.e. the composition of a dilation and an erosion are idempotent operators (δε is called a morphological opening and εδ a morphological closing).

The following representation theorem holds: an increasing operator δ is an algebraic dilation iff there is an operator ε such that (ε, δ) is an adjunction; the operator ε is then an algebraic erosion and ε(x) = {y ∈ L, δ(y) ≤ x}. Similarly, an increasing operator ε is an algebraic erosion iff there is an operator δ such that (ε, δ) is an adjunction; the operator δ is then an algebraic dilation and δ(x) = {y ∈ L, ε(y) ≥ x}.

Finally, let δ and ε be two increasing operators such that δε is anti-extensive and εδ is extensive. Then (ε, δ) is an adjunction.

Further properties and derived operators can be found in seminal works such as [START_REF] Heijmans | Morphological Image Operators[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology, Part II: Theoretical Advances[END_REF], or in more recent ones [START_REF] Bloch | Mathematical Morphology[END_REF][START_REF]Mathematical morphology: from theory to applications[END_REF].

In this paper, the fact that dilations and erosions are increasing operators that commute with the supremum and the infimum, respectively, will play an important role.

Structuring element and morphological dilations and erosions

Let us now consider the lattice (P(E), ⊆) of the subsets of E. We have δ(X) = ∪ x∈X δ({x}). If E is a vectorial or metric space (e.g. R n ), and if δ and ε are additionally supposed to be invariant under translation, then it can be proved that there exists a subset B, called structuring element, such that

δ(X) = {x ∈ E | Bx ∩ X = ∅} (4)
and

ε(X) = {x ∈ E | B x ⊆ X}, (5)
where B x denotes the translation of B at point x (i.e. x+B), and B is the symmetrical set of B with respect to the origin (i.e. y ∈ B x iff x ∈ By ). The operators are then called morphological dilations and erosions. Details on these definitions and their properties can be found e.g. in [START_REF] Bloch | Mathematical Morphology[END_REF][START_REF] Heijmans | Morphological Image Operators[END_REF][START_REF]Mathematical morphology: from theory to applications[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF].

The structuring element B defines a neighborhood that is considered at each point. This is typically the case in image processing and computer vision, where the underlying lattice is built on sets or functions of the spatial domain. It is a subset of E with fixed shape and size, directly influencing the extent of the morphological operations. It is generally assumed to be compact, so as to guarantee good properties. In the discrete case (that will be considered throughout this paper), we assume that it is connected, according to a discrete connectivity defined on E.

The general principle underlying morphological operators consists in translating the structuring element at every position in space and checking if this translated structuring element satisfies some relation with the original set (intersection for dilation, Equation 4, inclusion for erosion, Equation 5) [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF].

An example on a binary image is displayed in Figure 1. The structuring element can also be seen as a binary relation between points [START_REF] Bloch | Mathematical Morphology[END_REF], i.e. y ∈ B x iff R(x, y) where R denotes a relation on E × E. Dilation and erosion are then expressed as follows:

δ(X) = {x ∈ E | ∃y ∈ X, R(y, x)}, ε(X) = {x ∈ E | ∀y ∈ E, R(x, y) ⇒ y ∈ X}.
These formulas apply for any binary relation R. If and only if R is reflexive (i.e. R(x, x) for all x), then δ is extensive (X ⊆ δ(X)) and ε is anti-extensive (ε(X) ⊆ X). These properties hold in the case illustrated in Figure 1. The objects in the original image are then expanded by dilation, to an extent that depends on the shape and the size of the structuring element, and reduced by erosion. Similar interpretations hold for any relation R, and these properties will also be important in the remainder of this paper.

Lattice of formulas and morphologic

The idea of using mathematical morphology in a logical framework was first introduced in [START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF][START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF]. Let P S be a finite set of propositional symbols, with |P S| = N . The set of formulas (generated by P S and the usual connectives) is denoted by Φ. Well-formed formulas are denoted by Greek letters ϕ, ψ... The set of all interpretations for Φ is denoted by Ω = 2 |P S| , interpretations are denoted by ω, ω ..., and ϕ = {ω ∈ Ω | ω |= ϕ} is the set of all models of ϕ (i.e. all interpretations for which ϕ is true).

The underlying idea for constructing morphological operations on logical formulas is to consider formulas and interpretations from a set-theoretical perspective. Since Φ is isomorphic to 2 Ω up to the syntactic equivalence, i.e., knowing a formula defines completely the set of its models (and conversely, any set of models corresponds to a subset of Φ built of syntactic equivalent formulas), we can identify ϕ with the set of its models ϕ , and then apply set-theoretic morphological operations. We recall that

ϕ ∨ ψ = ϕ ∪ ψ , ϕ ∧ ψ = ϕ ∩ ψ , ϕ ⊆ ψ iff ϕ |= ψ, and ϕ is consistent iff ϕ = ∅. Considering the inclusion relation on 2 Ω , (2 Ω , ⊆) is a Boolean complete lattice.
Similarly, a lattice (which is isomorphic to 2 Ω ) is defined on Φ ≡ , where Φ ≡ denotes the quotient space of Φ by the equivalence relation between formulas (with the equivalence defined as ϕ ≡ ψ iff ϕ = ψ ). In the following, this is implicitly assumed, and we simply use the notation Φ. Any subset {ϕ i , i ∈ I} of Φ, where I is an index set, has a supremum i∈I ϕ i , and an infimum i∈I ϕ i (corresponding respectively to union and intersection in 2 Ω ). The greatest element is and the smallest one is ⊥ (corresponding respectively to 2 Ω and ∅).

Based on this lattice structure, it is straightforward to define a dilation as an operation that commutes with the supremum and an erosion as an operation that commutes with the infimum, as in Equations 1 and 2. They naturally inherit all general properties of the algebraic framework.

Morphological dilation and erosion of logical formulas

Using the previous equivalences, we propose to define morphological dilation and erosion of a formula with a structuring element as follows, according to the preliminary work in [START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF][START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF]. The underlying lattice is (Φ ≡ , |=), or equivalently (2 Ω , ⊆). Since these two lattices are isomorphic, we will use the same notations for morphological operations on each of them. Definition 2.1. A morphological dilation of a formula ϕ with a structuring element B (B ∈ 2 Ω ) is defined through its models as:

δ B (ϕ) = δ B ( ϕ ) = {ω ∈ Ω | Bω ∧ ϕ consistent}. (6)
Similarly, a morphological erosion is defined as:

ε B (ϕ) = ε B ( ϕ ) = {ω ∈ Ω | B ω |= ϕ}. (7)
In these equations, the structuring element B represents a relationship between worlds, i.e. ω ∈ B ω iff ω satisfies some relationship with ω. The condition in Equation 6 expresses that the set of worlds in relation to ω should be consistent with ϕ. The condition in Equation 7 is stronger and expresses that all worlds in relation to ω should be models of ϕ. Note that in this paper we only consider symmetrical structuring elements.

There are several possible ways to define structuring elements in the context of formulas. We suggest a few ones here. The relationship can be any relationship between worlds and defines a "neighborhood" of worlds. If it is symmetrical, it leads to symmetrical structuring elements. If it is reflexive, it leads to structuring elements such that ω ∈ B ω , which leads to interesting properties, as will be seen later. For instance, this relationship can be an accessibility relation as in normal modal logics [START_REF] Hughes | An Introduction to Modal Logic[END_REF] (see [START_REF] Bloch | Modal Logics based on Mathematical Morphology for Spatial Reasoning[END_REF] for its use to define modalities as morphological operators).

An interesting way to choose the relationship is to base it on distances between worlds. This allows defining sequences of increasing structuring elements defined as the balls of a distance. From any distance d between worlds (d : Ω × Ω → R + ), a distance from a world to a formula is derived as a distance from a point to a set: d(ω, ϕ) = min ω |=ϕ d(ω, ω ). Of particular importance is the Hamming distance d H , where d H (ω, ω ) is the number of propositional symbols that are instantiated differently in ω and ω . It is the most commonly used distance between worlds (or more generally members of a combinatorial domain), both in automated reasoning (especially in belief revision [START_REF]Investigations into a Theory of Knowledge Base Revision: Preliminary Report[END_REF], belief update [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF], and merging [START_REF] Konieczny | On the Logic of Merging[END_REF]) and in preference handling (especially in compact preference representation [START_REF] Lafage | Propositional distances and compact preference representation[END_REF] and voting [START_REF] Brams | A minimax procedure for electing committees[END_REF]).

By default, we take d to be d H , and this is the distance we will use in most of the examples developed in this paper. In this case, the distance takes values in N. The extension of what follows to distances taking values in R + is straightforward. Note that all what follows applies for general dilations, not necessarily derived from d H .

Then dilation and erosion of size n are defined from Equations 6 and 7 by using the distance balls of radius n as structuring elements (i.e.

B n ω = {ω | d(ω, ω ) ≤ n}): δ n (ϕ) = {ω ∈ Ω | ∃ω ∈ Ω, ω |= ϕ and d(ω, ω ) ≤ n} = {ω ∈ Ω | d(ω, ϕ) ≤ n}, (8)
ε n (ϕ) = {ω ∈ Ω | ∀ω ∈ Ω, d(ω, ω ) ≤ n ⇒ ω |= ϕ} = {ω ∈ Ω | d(ω, ¬ϕ) > n}. ( 9
)
Note that we have δ 0 (ϕ) = ε 0 (ϕ) = ϕ. By convention, when there is no ambiguity, we will set δ(ϕ) = δ 1 (ϕ) and ε(ϕ) = ε 1 (ϕ). More generally, whatever the operator f , we define

f 1 (ϕ) = f (ϕ) and f n (ϕ) = f (f n-1 (ϕ)) for n > 1.
From operations with the unit ball we define the external (respectively internal) boundary of ϕ as δ 1 (ϕ) ∧ ¬ϕ (respectively ϕ ∧ ¬ε 1 (ϕ)), corresponding to the worlds that are exactly at distance 1 of ϕ (respectively of ¬ϕ).

As an illustrative example, let us consider the case where we have three propositional symbols a, b and c. The set of worlds Ω then has eight elements, which can be represented as the vertices of a cube. In this example, we consider the unit cube of R 3 (for N propositional symbols, this generalizes to the hypercube of R N ). For the sake of simplicity, we assimilate a formula formed by a simple conjunction of symbols with its corresponding model. For instance, a ∧ b ∧ c is assimilated to the corresponding world in 2 Ω , represented by the point (1, 1, 1) in the unit cube. The edges link two worlds differing by one instantiation of a propositional symbol (i.e. at a Hamming distance of 1). For instance, vertices representing a ∧ b ∧ c and ¬a ∧ b ∧ c are linked by an edge (we have d(a ∧ b ∧ c, ¬a ∧ b ∧ c) = 1). This is a convenient representation for graphically illustrating the morphological operations, as shown in Figures 2 and3. The balls of the Hamming distance are used as structuring elements. In Figure 2, we consider a formula ϕ = (a ∧ b ∧ c) ∨ (¬a ∧ ¬b ∧ c). Its dilation (of size 1, i.e. by a ball of radius 1) is then δ

(ϕ) = ¬((a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ b ∧ ¬c)) = (¬a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c).
The dilation of size one just amounts to adding to the vertices representing ϕ the vertices linked by an edge to them. In Figure 3, an example of erosion is illustrated, for

ϕ = (a ∧ b ∧ c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (¬a ∧ ¬b ∧ c) ∨ (¬a ∧ ¬b ∧ ¬c) = c ∨ (¬a ∧ ¬b).
The erosion of size 1 is then ε(ϕ) = ¬a ∧ ¬b ∧ c. It amounts to keeping in the result only the vertices having all their neighbors (according to the graph defined by the cube) in ϕ .

(1, 0, 0) (0, 1, 1)

(1, 1, 1)

(1, 0, 1) (0, 0, 1)

(0, 0, 0) (0, 1, 0) (1, 1, 0) ϕ δ(ϕ) Figure 2. Example of a dilation of size 1: ϕ = (a ∧ b ∧ c) ∨ (¬a ∧ ¬b ∧ c) and δ(ϕ) = (¬a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c).
Note that in all figures, the models of the formulas are represented. Note that this figure and the next ones may be best seen in colors on the online version of the paper.

(0, 0, 0) (0, 0, 1)

(0, 1, 1) (1, 1, 1)
(1, 0, 1) The main properties of dilation and erosion, which are satisfied in mathematical morphology on sets, hold also in the logical setting proposed here. They are summarized below. The proofs are not given here, but they are straightforward based on set/logic equivalences.

(1, 1, 0) (0, 1, 0) (1, 0, 0) ϕ ε(ϕ)
The dilations and erosions defined in Equations 6, 7, 8, and 9 have the following properties:

Adjunction relation: (ε B , δ B ) is an adjunction, i.e. δ B (ψ) |= ϕ iff ψ |= ε B (ϕ), for any structuring element B. This shows that the proposed definitions are a particular case of general algebraic dilations and erosions.

Commutativity with union or intersection: Dilation commutes with union or disjunction (this is a fundamental property of dilation as mentioned in the general algebraic framework, and is derived from the adjunction property): for any family ϕ 1 , ...ϕ m of formulas, we have:

δ B (∨ m i=1 ϕ i ) = ∨ m i=1 δ B (ϕ i ).
Erosion on the other hand commutes with intersection or conjunction. Note that this property is taken as definition in case of a general algebraic dilation or erosion.

In general, dilation (respectively erosion) does not commute with intersection (respectively union), and only an inclusion relation holds:

δ B (ϕ ∧ ψ) |= δ B (ϕ) ∧ δ B (
∀B, B , ∀ϕ, δ B (δ B )(ϕ) = δ δB(B ) (ϕ), ε B (ε B )(ϕ) = ε δB(B ) (ϕ).
For instance, for distance based operations, for a distance satisfying the betweeness property2 , this property can be expressed as:

δ n+n (ϕ) = δ n [δ n (ϕ)] = δ n [δ n (ϕ)], ε n+n (ϕ) = ε n [ε n (ϕ)] = ε n [ε n (ϕ)].
This means that the effect of these operations increases with the size of the structuring element, and that the computation can be done either by successive applications of "small" structuring elements or directly by the sum of the structuring elements. Duality: Dilation and erosion are dual operators with respect to the negation: ε B (ϕ) = ¬δ B (¬ϕ) which allows deducing properties of an operator from those of its dual operator. Relations to distances: Equation 8 shows how to derive a dilation from a distance.

Conversely, from Equation 8we have:

d(ω, ϕ) = min{n ∈ N | ω |= δ n (ϕ)}, and similarly, we have d(ω, ¬ϕ) = min{n ∈ N | ω |= ¬ε n (ϕ)}.
Distances between formulas can also be derived from dilation, as minimum distance and Hausdorff distance3 . For instance, the minimum distance is expressed as:

d min (ϕ, ψ) = min ω|=ϕ,ω |=ψ d H (ω, ω ) = min{n ∈ N | δ n (ϕ) ∧ ψ = ∅ and δ n (ψ) ∧ ϕ = ∅}.
This means that the minimum distance is attained for the minimum size of dilation of both formulas such that they become consistent. The Hausdorff distance is defined as: d Haus (ϕ, ψ) = max(max ω|=ϕ d(ω, ψ), max ω |=ψ d(ω , ϕ)). It can be computed from dilation by d Haus (ϕ, ψ) = min{n ∈ N | ϕ |= δ n (ψ) and ψ |= δ n (ϕ)}. These properties will be used intensively in the applications of these operators for knowledge representation and reasoning.

Some derived operators

Conditional dilation and erosion and reconstruction

In several problems and applications, we may want to restrict the result of an operation to stay within some domain, or to satisfy a particular formula. This is typically the case, for instance, if a result has to satisfy a theory, or a set of integrity constraints. This idea calls for geodesic distances, from which structuring elements are derived, as the balls of this distance. Using these structuring elements in the definitions of dilation and erosion (Equations 6 and 7) leads to the notion of geodesic, or conditional, operators. In the discrete case, that we consider here, the expression of these operators is very simple:

δ n ψ (ϕ) = [δ 1 (ϕ) ∧ ψ] n , (10)
where ψ denotes the conditioning formula, n is the size of the structuring element, δ 1 denotes the dilation using a ball of radius 1 (not geodesic) and the superscript n means that the succession of dilation of size 1 and conjunction has to be performed n times. This equation is a short writing for the following sequence of operations:

begin ϕ 0 := ϕ ∧ ψ; For i = 1...n ϕ i := δ 1 (ϕ i-1 ) ∧ ψ; end for Return ϕ n = δ n ψ (ϕ)
Similarly, the geodesic erosion of ϕ conditionally to ψ can be computed as:

ε n ψ (ϕ) = [ε 1 (ϕ) ∨ ψ] n . (11)
If the conditional dilations are iterated until convergence, then the result is called reconstruction, and is denoted by

R(ϕ | ψ): R(ϕ | ψ) = [δ 1 (ϕ) ∧ ψ] ∞ . ( 12
)
Note that in practice this sequence converges in a finite number of steps, when we consider a finite discrete space, as is the case in this paper. An example is illustrated in Figure 4, with the same type of representation as in the previous figures. The reconstruction results in the only connected component of ψ "marked" by ϕ. In this paper we consider the connectivity of a formula via the discrete connectivity of its models, induced by the distance (i.e. in the sense of the graph used for the illustrations). More precisely, two worlds ω, ω are neighbors if d(ω, ω ) ≤ 1. A path is a sequence of worlds where any two successive worlds in the sequence are neighbors. A connected component of a formula is a set of models of this formula such that there exists a path between any two models that is included in this set, and that is maximal for this property.

( )

ϕ ψ R(ϕ|ψ) ∪ Figure 4
. Reconstruction: only the connected component of ψ which is "marked" by ϕ is reconstructed.

Searching for the most central models satisfying a formula

In some problems, it might be interesting to find the most relevant worlds that are models of a formula. This problem is solved in [START_REF] Lafage | Logical Representation of Preferences for Group Decision Making[END_REF] by taking the absolute maximum of the internal distance function (i.e. the function that associates to each world its distance to ¬ϕ). Mathematical morphology offers other tools that could also be interesting:

Ultimate erosion is one of them. It consists in eroding iteratively ϕ and, at each step n, keeping the connected components of ε n (ϕ) that disappear in ε n+1 (ϕ).

It corresponds exactly to the regional maxima of the internal distance (i.e. the function that assigns to each model of ϕ the distance to its closest model of ¬ϕ). This approach may provide several components, which represent all parts of ϕ, belonging to different connected components, or connected by narrow sets of worlds. This notion can be formalized using the reconstruction operator (Definition 2.2). Last non-empty erosion only keeps track of the largest component. Erosions are iterated and the last result before the erosion becomes empty is the final result. The result is then more restrictive than with ultimate erosion, and some components of ϕ may not be represented. Definition 2.3 formalizes this idea. Morphological skeleton is another approach to represent a formula in a compact and "central" way. It is defined as the union of the centers of maximal balls included in the initial formula (see [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] for definitions on sets and corresponding properties). This approach will not be further investigated in this paper.

Definition 2.2. The ultimate erosion is expressed using the reconstruction operator as:

U E(ϕ) = ∪ n∈N ε n (ϕ) \ R ε n+1 (ϕ) | ε n (ϕ) . (13)
Again in the finite discrete case, the iterative erosion process stops in a finite number of steps.

Definition 2.3. The last erosion of a formula ϕ, denoted by ε (ϕ), is the erosion of ϕ of the largest possible size such that the set of worlds where ε (ϕ) is satisfied is not empty or the smallest size of erosion leading to a fixed point:

ε (ϕ) = ε n (ϕ) ⇔ ε n (ϕ) ⊥, and ∀m > n, ε m (ϕ) ⊥ or ε m (ϕ) = ε n (ϕ), (14)
with n the smallest value for which this holds, and ε 0 (ϕ) = ϕ.

In the example of Figure 3, the first erosion is also the last non-empty erosion.

It is interesting to note that the idea of successive erosions is related to the notions of supermodels [START_REF] Ginsberg | Supermodels and Robustness[END_REF] and of preferred explanations [START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF]. For instance, it is easy to prove that ω |= ε k (ϕ) iff ω is a (k, 0)-supermodel of ϕ. The application to preferred explanations will be further investigated in Section 6.

As a first illustration of the use of ultimate and last non-empty erosion, consider a simple decision making problem, inspired from participatory budgeting [START_REF] Aziz | Participatory Budgeting: Models and Approaches[END_REF]: three projects a, b and c can possibly be built by a city; the aggregated goal of the citizens (perhaps obtained by a merging operator, cf. Section 5

) is ϕ = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) ∨ (¬a ∧ ¬b ∧ ¬c)
. Now, exogenous events might render some assignments unfeasible: some projects may turn out to be unfeasible, but also, some projects may be enforced by the region or the central state. If we want a robust solution, we should target the last non-empty erosion, namely, a ∧ b ∧ c: even in the case of one adverse event (one of the three project becoming unfeasible), we can still change the initial solution into another one which is very close to it (for instance, if a turns out to be unfeasible, then ¬a ∧ b ∧ c will be implemented instead of a ∧ b ∧ c); note that this is not the case with any of the other four models of ϕ. On the other hand, the ultimate erosion gives us a set of diverse, representative solutions: rather than giving all five solutions (which may be too much) to the user or the central authority, one may give her a set of representative solutions, here a ∧ b ∧ c and ¬a ∧ ¬b ∧ ¬c. Any solution is at distance at most one to any of these two solutions. Such a principle is common in recommender systems; it has also been considered in constraint satisfaction [START_REF] Hebrard | Finding diverse and similar solutions in constraint programming[END_REF].

Opening and closing

Two other important operators are opening and closing. An algebraic opening is an operator that is increasing, idempotent and anti-extensive, and an algebraic closing is an operator that is increasing, idempotent and extensive. Typical examples are δε and εδ where (ε, δ) is an adjunction, as seen in the general algebraic framework. An important property is that any disjunction of openings is an opening, and any conjunction of closings is a closing. Opening and closing of a formula ϕ by a structuring element B are defined respectively as:

O B (ϕ) = δ B (ε B (ϕ)), and C B (ϕ) = ε B (δ B (ϕ)).
These two basic morphological filters can be seen as approximation operators, since they "simplify" formulas by either suppressing some irregularities for opening, or adding some parts of ¬ϕ for closing. Families of filters can be built from these two ones. For instance, granulometry [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] consists in applying successively openings with structuring elements of increasing size, thereby decomposing a formula in parts of different characteristic sizes. Another example is alternate sequential filters [START_REF] Serra | Image Analysis and Mathematical Morphology, Part II: Theoretical Advances[END_REF], which consist in building sequences of opening/closing (or closing/opening), with structuring elements of increasing size. Such transformations are increasing and idempotent, and allow filtering progressively parts of ϕ and ¬ϕ.

Note that ε is an anti-extensive and idempotent operator, but it is not increasing (and hence not an opening). The same applies for ultimate erosion.

Morphological ordering

Given a formula, a natural ordering can be derived from the sequence of its successive erosions and dilations, for a given elementary structuring element (of size 1). This idea is illustrated on sets in Figure 5. This will be particularly interesting in the following, when considering a theory, and for defining a partial order on the models satisfying this theory (by identifying a theory with an equivalent formula). 4 We call it morphological ordering. Definition 2.4. Let Σ be a theory (represented by a formula) or a formula. Let n be the maximal size of dilation and m the size of the last non-empty erosion, i.e.:

ε m (Σ) = ε (Σ), δ n (Σ) = δ (Σ),
where δ is defined in a similar way as the last erosion (and δ (Σ) can be either or a fixed point). Then we define the fundamental sequence (T i ) of subsets of Ω associated with Σ, from i = 0 to i = n + m, as follows:

T i = ε m-i (Σ) if i ≤ m δ i-m (Σ) if i > m
The morphological total pre-order associated to Σ is then defined by:

ω f ω def ⇔ ∀k (ω ∈ T k ⇒ ω ∈ T k ). ( 15
)
The fact that this defines a pre-order is easy to check. Note that this ordering depends on the choice of the elementary structuring element.

As an example, let us consider again three propositional symbols, with the same representation as in Figures 2 and3, and Σ = {a → c, b → c} (represented by the same formula ϕ as in the example of Figure 3). The models of Σ are Ω \ {a ∧ b ∧ ¬c, a ∧ ¬b ∧ ¬c, ¬a ∧ b ∧ ¬c}. We have δ(Σ) = Ω, ε(Σ) = {¬a ∧ ¬b ∧ c}, and ε 2 (Σ) = ∅, as illustrated in Figure 6.

(1, 0, 0) (0, 1, 1)

(1, 1, 1)

(1, 0, 1) (0, 0, 1) This provides a stratification of the elements of Ω, as given in Table 1. Note that in case the last dilation yields a fixed point different from , the rank of the models in Ω \ δ (Σ) is set to +∞ by convention. This amounts to ordering only δ (Σ) . Let us briefly comment on the choice of the structuring element used in the morphological operations. When it is taken as a ball of the Hamming distance, as in all examples in this section so far, then the neighborhood it defines is isotropic and all variables are taken into account in the same way. However, different structuring elements could be used, and their choice is a way to impose preferences, for instance, on some variables over other ones. As an example, let us consider the following structuring element, defining the neighborhood of any world ω ∈ Ω:

(0, 0, 0) (0, 1, 0) (1, 1, 0) Σ ε(Σ) δ(Σ) \ Σ
0 ¬a ∧ ¬b ∧ c 1 ¬a ∧ ¬b ∧ ¬c, a ∧ ¬b ∧ c, ¬a ∧ b ∧ c, a ∧ b ∧ c 2 a ∧ ¬b ∧ ¬c, ¬a ∧ b ∧ ¬c, a ∧ b ∧ ¬c
B ab ω = {ω ∈ B ω | ω(c) = ω (c)},
where B denotes the ball of radius 1 of the Hamming distance, and ω(c) = ω (c) means that c is instantiated in the same way in ω and in ω . With this structuring element, c is not handled in the same way as variables a and b. Note that when performing successive erosions (respectively dilations) with such a structuring element, we may not end up with ⊥ (respectively ), but we may converge towards a fixed point (a subset of Ω). Figure 7 illustrates the effect of this structuring element on the same

∧ i∈I ϕ i .
example as in Figure 6. The derived morphological ordering and the corresponding stratification of Ω are now given in Table 2.

(1, 0, 0) (0, 1, 1) (

(1, 0, 1) (0, 0, 1)

(0, 0, 0) (0, 1, 0) (1, 1, 0) Σ ε(Σ) δ(Σ) \ Σ δ 2 (Σ) \ δ(Σ)
Figure 7. Illustration of the morphological ordering (here n = 2, m = 1), using B ab as structuring element. As another way to handle variables differently, let us note that Ω does not need to be "isotropic", i.e. the cube in our illustrations could be a parallelepiped, with different lengths of the edges, representing the elementary distances between worlds. A distance between two worlds can then be defined as the length of a shortest path in this weighted graph. Structuring elements can be defined as balls of this distance. However, in general this distance does not satisfy the betweenness property, which makes is less interesting for our purpose.

0 ¬a ∧ ¬b ∧ c, a ∧ ¬b ∧ c, ¬a ∧ b ∧ c, a ∧ b ∧ c 1 ¬a ∧ ¬b ∧ ¬c 2 a ∧ ¬b ∧ ¬c, ¬a ∧ b ∧ ¬c 3 a ∧ b ∧ ¬c
It is important to note that the ordering of the elements of Ω depends on both Σ and the definition of erosion and dilation, in particular, the choice of the structuring element.

This morphological ordering will be used to unify several reasoning tasks, in particular, abduction and revision, in Section 6.

Computational issues

Unless stated otherwise, for all the operators considered here we assume that the structuring element is the ball of radius 1 for the Hamming distance.

Dilation

The commutativity of dilation with disjunction, along with the iteration property, allows us to recover the results of [START_REF] Lafage | Logical Representation of Preferences for Group Decision Making[END_REF]. In particular, the following result holds. Proposition 3.1. Let ϕ be a consistent conjunction of literals, i.e. ϕ = l 1 ∧l 2 ∧...∧l n , then

δ 1 (ϕ) = ∨ n j=1 (∧ i =j l i ).
Similarly, if ϕ is a disjunction of literals, i.e. ϕ = l 1 ∨ ... ∨ l m , then the erosion is expressed as:

ε 1 (ϕ) = ∧ m j=1 (∨ i =j l i ).
In these equations δ 1 (respectively ε 1 ) denotes the dilation (erosion) using as structuring element a ball of radius 1 of the Hamming distance.

This property, together with the commutation of dilation with disjunction, gives the following result [START_REF] Lafage | Logical Representation of Preferences for Group Decision Making[END_REF]: if k is a fixed integer, then the dilation of size k δ k (ϕ) of a DNF formula ϕ can be computed in time O(n k ) -thus in polynomial time. Similarly, erosion commutes with intersection and can be computed in polynomial time from a CNF formula.

When ϕ is not in DNF, computing δ k (ϕ) directly from ϕ (without rewriting ϕ in DNF first) is a difficult problem.

However, we can prove a slightly general result: Proposition 3.2. If φ 1 , . . . , φ n are such that for all i, j, φ i and φ j do not share variables, then δ(φ 1 ∧ . . .

∧ φ n ) = n j=1 δ(φ j ) ∧ k =j φ k .
Proof: For every interpretation ω let ω i = ω ↓V ar(ϕi) be the projection of ω on the language of ϕ i (V ar(ϕ i )). We have

ω |= δ(ϕ 1 ∧ . . . ∧ ϕ n ) if and only if (1) there exists ω such that ω |= ϕ 1 ∧ . . . ∧ ϕ n and d(ω, ω ) ≤ 1. Now, d(ω, ω ) = i=1,...,n d(ω i , ω i ) (since the ϕ i have

no variable in common)

. Therefore, d(ω, ω ) ≤ 1 if and only if there exists a j, j ≤ n, such that: (a) d(ω j , ω j ) ≤ 1, and (b) for every k = j, ω k = ω k . From this we get that ( 1) is equivalent to:

(2) there exists a j, j ≤ n, such that ω j |= δ(ϕ j ) and for every k = j, ω k |= ϕ k . Now, δ(ϕ j ) is equivalent to a formula on the language V ar(ϕ i ), therefore ω |= δ(ϕ j ) iff ω j |= δ(ϕ j ), Moreover, ω |= ϕ k iff ω k |= ϕ k . Therefore, ω |= δ(ϕ 1 ∧. . .∧ϕ n ) if and only if there exists a j, j ≤ n, such that ω |= δ(ϕ j ) ∧ k =j ϕ k , from which the result follows.

In particular:

• if V ar(ϕ) ∩ V ar(ψ) = ∅, then δ(ϕ ∧ ψ) = (ϕ ∧ δ(ψ)) ∨ (δ(ϕ) ∧ ψ); • if ϕ 1 , .
. . , ϕ n are literals whose associated variables are all different, then we recover the identity δ(l 1 ∧ . . . ∧ l n ) = n j=1 k =j l k . Now, how hard is it to compute dilations (respectively erosions) when ϕ is not in DNF (respectively CNF)? First of all we have the following complexity results. Proposition 3.3.

(1) Given an interpretation ω and a formula ϕ, deciding whether ω |= δ(ϕ) is NPcomplete.

(2) Given an interpretation ω and a formula ϕ, deciding whether ω |= ε(ϕ) is coNPcomplete.

Proof: In both cases membership is straightforward. For hardness for point 1 we consider the following reduction from sat: we map every formula α to ϕ, ω where ϕ = p ∧ α with p = V ar(α), and ω being any interpretation satisfying p. Using Proposition 3.2 we have δ(p ∧ α)

≡ (p ∧ δ(α)) ∨ (δ(p) ∧ α), which is equivalent to α ∨ (p ∧ δ(α)). Now, if α is satisfiable, then so is δ(α). Therefore, ω |= α ∨ (p ∧ δ(α)).
If α is unsatisfiable, then so are δ(α) and α ∨ (p ∧ δ(α)). Therefore ω |= α ∨ (p ∧ δ(α)).

The reduction from unsat for point 2 is similar.

This shows that, a fortiori, computing erosion or dilation in the general case is hard. Moreover, the size of ε(ϕ) and δ(ϕ) is not polysize, except if P = NP. It is not sure that there is a way of computing erosion (dilation) being more efficient than first rewriting ϕ in CNF (DNF).

Note that inference from the dilation of a formula is (theoretically) not harder than inference from the formula itself. Namely, given any two formulas ϕ and ψ and any integer k, determining whether δ k (ϕ) |= ψ is coNP-complete. A similar result holds for inference from erosion.

However, interesting results can be obtained for erosion by decomposing a formula into its connected components. Based on the graph interpretation used throughout this paper, a connected component is classically defined as a connected component in the graph: we say that ψ is a connected component of ϕ if ψ is a connected component of the graph associated with ϕ (whose set of vertices is ϕ ) and whose set of edges is defined by (ω, ω ) whenever d(ω, ω ) ≤ 1). Proof: For any two distinct connected components ϕ i , ϕ j of ϕ we have d(ϕ i , ϕ j ) ≥ 2, therefore, ε( p i=1 ϕ p ) ≡ p i=1 ε(ϕ i ); the fact that ϕ ≡ p i=1 ϕ p enables us to conclude that ε(ϕ) ≡ p i=1 ε(ϕ i ).

Proposition 3.4. If d(ϕ, ψ) ≥ 2, for d being the minimum distance between formulas, then ε(ϕ ∨ ψ) ≡ ε(ϕ) ∨ ε(ψ). Proof: Assume d(ϕ, ψ) ≥ 2. We already know that ε(ϕ) ∨ ε(ψ) |= ε(ϕ ∨ ψ), so it remains to be proven that ε(ϕ ∨ ψ) |= ε(ϕ) ∨ ε(ψ). Let ω |= ε(ϕ ∨ ψ). This implies ω |= ϕ ∨ ψ if the erosion is anti-extensive (
Now, we have to find a way of (a) computing the connected components of ϕ and (b) computing ε(ϕ). The first step is easy when ϕ is in DNF. We first note the following fact: Proposition 3.6. Let ϕ = ψ 1 ∨ . . . ∨ ψ q be a DNF formula. For any i, j ∈ {1, . . . , q}, d(ψ i , ψ j ) is equal to the number of disagreeing literals between ψ i and ψ j .

For instance, we have d(a

∧ ¬b ∧ c, b ∧ ¬c ∧ d) = 2, d(a ∧ ¬b ∧ c, b ∧ c ∧ d) = 1, and d(a ∧ ¬b ∧ c, c ∧ d) = 0.
Proposition 3.7. Let ϕ = ψ 1 ∨ . . . ∨ ψ q be a DNF formula. Let G ϕ be the undirected graph defined by its set of vertices ϕ , which can be grouped into subsets {a 1 , . . . , a q } where a i = ψ i , and containing an edge {a i , a j } iff d(ψ i , ψ j ) ≤ 1. Then the connected components of G ϕ correspond to the connected components of ϕ, and {a i , i 8). The graph G ϕ has 8 vertices, grouped into 4 subsets a i , and its edges are {a 1 , a 2 }, {a 1 , a 3 }, {a 2 , a 3 }, plus the reflexive edges {a 1 , a 1 }, {a 2 , a 2 }, {a 3 , a 3 }, {a 4 , a 4 }. G ϕ has two connected components: {a 1 , a 2 , a 3 } = {(0, 1, 1), (1, 1, 1), (1, 0, 1), (1, 1, 0)} and {a 4 } = {(0, 0, 0)} (the valuation of d is not represented here), therefore ϕ has two connected components:

∈ I ⊆ {1, . . . , q}} is a connected component of G ϕ iff i∈I ψ i is a connected component of ϕ. Example 3.8. Let us consider ϕ = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) ∨ (¬a ∧ ¬b ∧ ¬c ∧ ¬d) (Figure
ϕ 1 = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) and ϕ 2 = ¬a ∧ ¬b ∧ ¬c ∧ ¬d, from which we have ε(ϕ) = ε(ϕ 1 ) ∨ ε(ϕ 2 ) = (a ∧ b ∧ c) ∨ ⊥ = a ∧ b ∧ c. (0, 0, 1) (1, 1, 1) (1, 0, 1) (0, 1, 0) (1, 1, 0) (1, 0, 0) (0, 0, 0) (0, 1, 1) ϕ1 ϕ2 ε(ϕ)

About last erosion and ultimate erosion

Let us consider the last erosion (Definition 2.3). Denote by (ϕ) the number of iterations to reach the last non-empty erosion of ϕ. Proposition 3.9. If |= ϕ and ϕ ≡ then (ϕ) ≤ N -1, where N is the number of propositional symbols in the language.

Proof: Let k = (ϕ). We have ω |= ε k (ϕ) if for all ω |= ¬ϕ we have d(ω, ω ) > k. Therefore, k < N , because it can never be the case that d(ω, ω ) > N .

Actually, we can find a better bound for (ϕ): Proposition 3.10. If |= ϕ and ϕ ≡ then (ϕ) is less than the length of the shortest prime implicate of ϕ (the set of prime implicates being denoted by P I(ϕ)).

Proof: The result follows easily from ϕ ≡ P I(ϕ), from the fact that erosion commutes with conjunction, and from the following expression of the erosion of a disjunction of literals:

ε(l 1 ∨ ... ∨ l m ) = ∧ m j=1 (∨ i =j l i ),
This result is obtained by duality from Proposition 3.1 (or directly by induction on m).

For instance, let us consider ϕ = (a ↔ b). We have P I(ϕ) = {a ∨ ¬b, ¬a ∨ b}, i.e., every prime implicate of ϕ is of length 2; ε 1 (ϕ) = ⊥, therefore (ϕ) = 0. This example shows that (ϕ) can be strictly lower than the bound expressed in Proposition 3.10. Proposition 3.9 enables us to say that deciding whether ω |= ε (ϕ) is in BH 2 in the Boolean hierarchy of NP sets.

Let us now consider ultimate erosion (Definition 2.2). The following result directly follows from Proposition 3.5. Proposition 3.11. Let ϕ 1 , . . . , ϕ p be the connected components of ϕ. Then we have:

U E(ϕ) ≡ p i=1 U E(ϕ i ).
Using Proposition 3.11, the following algorithm computes the ultimate erosion of ϕ.

U E(ϕ): begin decompose ϕ into its connected components ϕ 1 , . . . , ϕ p ;

if p = 1 then if ε(ϕ) ≡ ⊥ then return ϕ else return U E(ε(ϕ)) endif else return U E(ϕ 1 ) ∨ . . . ∨ U E(ϕ n ) endif

About opening and skeleton

A morphological opening is the composition of an erosion followed by a dilation: O(ϕ) = δ(ε(ϕ)). Computing O(ϕ) is not an easy task. If ϕ is in CNF, then δ(ϕ) is computable in polynomial time, and expressible as a polysize CNF, but then δ(ε(ϕ)) is not (and can be exponentially long). If ϕ is in DNF, then ε(ϕ) is not polynomially computable (and can be exponentially long). Proposition 3.4 gives a hint on how to compute O(ϕ), when ϕ is in DNF. Proposition 3.12. Let ϕ 1 , . . . , ϕ p the connected components of ϕ. Then we have:

O(ϕ) ≡ p i=1 O(ϕ i ).
This result directly follows from Proposition 3.5.

Let us now consider the skeleton Sk(ϕ). It is defined as the centers of maximal balls of the Hamming distance included in ϕ. In the finite discrete case, it can be computed by the following algorithm:

begin Sk(ϕ) := ϕ ∧ ¬O(ϕ); ψ = ϕ While ψ ≡ ⊥ do Sk(ϕ) := Sk(ϕ) ∨ (ε(ψ) ∧ ¬O(ε(ψ))); ψ := ε(ψ) end while Return Sk(ϕ)
We note that the number of iterations performed by this algorithm is equal to min{i, ε i (ϕ) ≡ ⊥} and therefore is no larger than N . This is illustrated in Figure 9.

(0, 0,

(1, 0, 1)

(0, 1, 0) (1, 1, 0) (1, 0, 0) (0, 0, 0) (0, 1, 1)
center of maximal ball of radius 0 center of maximal ball of radius 1 ϕ Sk(ϕ) ∪ We see that computing Sk(ϕ) heavily relies on computing O(ϕ). Using the previous results on erosions and openings, we have: Proposition 3.14. Let ϕ 1 , . . . , ϕ p the connected components of ϕ. Then we have: Sk(ϕ) ≡ p i=1 Sk(ϕ i ).

Belief revision

In this section, we briefly survey some existing revision operators, and show that they can be equivalently expressed using morphological dilations. This establishes a first link between the proposed morphologic formalism and some reasoning tools developed for addressing aspects of knowledge dynamics. The morphological expressions will prove useful in Section 6.3 when proposing a unified framework for several reasoning tasks, using both erosions and dilations, and exploiting the morphological ordering introduced in Section 2.6. We start with some basics about belief revision. The aim of belief revision is to model how to incorporate coherently a piece of information to a corpus of beliefs. In the most studied model, the AGM model [START_REF] Alchourrón | On the Logic of Theory Change: Partial Meet Contraction and Revision Functions[END_REF], the corpus of beliefs is represented by a logical (consistent) theory K and the (new) piece of information by a formula ψ. The result of incorporating ψ to K, i.e. the revision of K by ψ, is denoted by K ψ. We give here a very simple presentation of this model in finite propositional logic due to Katsuno and Mendelzon [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF] in which the (old) beliefs K are indeed represented by a consistent formula ϕ (that is, K = Cn(ϕ)) and the revision of ϕ by ψ is denoted ϕ • ψ. Note that • is a function mapping an ordered pair of formulas into a formula. the same time. Since then, five years after, John has no news from Linda. However, he thinks that Linda is for sure an activist in feminism, that she occupies an excellent position in a Philosophy Department of some prestigious university and she maintains her beauty. John meets Peter, a common classmate, who tells him that, surprisingly, Linda is now a bank teller. With this new piece of information John revises his beliefs and he thinks now that Linda is a bank teller who keeps her feminist activism and keeps her beauty.

In this problem, we code by the atoms a, b and c the facts Linda is a feminist activist, Linda is beautiful and Linda is a Professor respectively, and by ¬c the fact that Linda is not a Professor (for instance the fact that Linda is a bank teller). The formula ϕ := a ∧ b ∧ c codes the beliefs of the agent (John) and the formula ψ := ¬c codes the new information. Then, following the previous definition of the revision operator •, we have ϕ • ψ = δ 1 (ϕ) ∧ ¬c. That is because ϕ ∧ ψ is inconsistent and δ 1 (ϕ) ∧ ψ is consistent. We have δ 1 (ϕ) ∧ ¬c = a ∧ b ∧ ¬c, that is Linda keeps her feminist activism, her beauty and she is a bank teller. This example is illustrated in Figure 10, using the same conventions as in Section 2.

(0, 0, 0) (

(0, 0, 1) It is important to point out that within the previous approach, using as structuring element the standard ball of radius 1 (with respect to the Hamming distance in the example), there always exists n such that δ n (ϕ) ≡ (when ϕ is consistent). This is essentially the reason why ϕ • ψ is consistent when ϕ and ψ are consistent. Also it is the reason why the so called success postulate in belief revision (ϕ • ψ ψ) holds.

(0, 1, 1) (1, 1, 1) (1, 1, 0)
We have also remarked that there are some cases (with special structuring elements) in which we have a fixed point for the dilation, which is not necessarily . For instance, we can have ϕ and n such that δ n (ϕ) = δ n+1 (ϕ) and δ n (ϕ) ≡ . What is interesting is that even in such a case we can define interesting and more general revision operators, namely credibility-limited revision operators [START_REF] Booth | Credibility-limited revision operators in propositional logic[END_REF][START_REF] Hansson | Credibility limited revision[END_REF]. The precise way to do that is as follows:

ϕ • ψ = δ n (ϕ) ∧ ψ where n = min{k ∈ N | δ k (ϕ) ∧ ψ is consistent} ϕ if there is no k such that δ k (ϕ) ∧ ψ ⊥
What is interesting to note is that in this general case, we can encode the credible worlds (see [START_REF] Booth | Credibility-limited revision operators in propositional logic[END_REF]) as δ n (ϕ) , where n is the least integer such that δ n (ϕ) = δ n+1 (ϕ).

Let us now consider the more general case, where δ is not necessarily a dilation defined from a distance. We only assume that δ is extensive (i.e. ∀ϕ, ϕ |= δ(ϕ), as defined earlier), and that it is exhaustive. Exhaustive means that δ satisfies the following fillingness property: ∀ϕ, ϕ ⊥ ⇒ ∃n ∈ N, δ n (ϕ) ≡ . We then have the following result (still assuming that ψ is consistent): Proposition 4.3. Let δ be an extensive and exhaustive operator on the lattice of propositional formulas. Then the operator • defined by: ∀ϕ, ψ, ϕ • ψ = δ n (ϕ) ∧ ψ with n = min{k ∈ N | δ k (ϕ) ∧ ψ is consistent} (the existence of n is guaranteed by the fillingness property), δ 0 (ϕ) = ϕ and δ k (ϕ) = δ(δ k-1 (ϕ)) for k ≥ 1, is a revision operator satisfying the postulates R1-R6.

The proof of the previous proposition is based on Theorem 4.1. Actually, the mapping which associates ϕ to ≤ ϕ defined by:

∀ω, ω , ω ≤ ϕ ω ⇔ ∀n ∈ N, ω ∈ δ n (ϕ) ⇒ ω ∈ δ n (ϕ)
is a faithful assignment and it is not hard to see that for all ψ, ϕ • ψ = min( ψ , ≤ ϕ ), which by Theorem 4.1 says that • is a revision operator.

Typically, δ can be any extensive and exhaustive dilation, but this proposition is slightly more general since it does not require δ to commute with the supremum, nor to be increasing.

The minimality property of revision operators has been widely discussed in the literature (see e.g. [START_REF] Konieczny | Taxonomy of improvement operators and the problem of minimal change[END_REF][START_REF] Ribeiro | Minimal change in AGM for non-classical logics[END_REF][START_REF] Ribeiro | Minimal change: Relevance and recovery revisited[END_REF]). Although it is not easy to define in any context in a general way, let us note that, in the particular case of propositional logic, the proposed morphological definition of revision provides a natural way to achieve this minimality in the sense that the set of models is minimally enlarged, which corresponds to the meaning of minimal change in [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF]. The proposed approach also provides sound and precise tools to compute minimal revisions.

Belief merging

In this section, we briefly survey some existing belief merging operators, and show the link with morphological dilations.

We now recall some basics about belief merging 8 . Belief merging [START_REF] Konieczny | On the Logic of Merging[END_REF][START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF][START_REF] Konieczny | Logic based merging[END_REF] aims at combining several pieces of information when there is no strict precedence between them. The agent faces several conflicting pieces of information coming from several sources of equal reliability 9 , and he has to build a coherent description of the world from them.

More precisely the input of a merging problem is a profile Φ = {ϕ 1 , . . . , ϕ n }, defined as a multi-set of propositional formulas encoding the different sources of information, and the integrity constraints encoded by a propositional formula µ. The result of merging Φ under the constraint µ is a propositional formula which will be denoted ∆ µ (Φ) (when µ ≡ , we will write simply ∆(Φ) instead of ∆ (Φ)). Thus, the merging model is based on the study and construction of well behaved functions ∆ mapping a couple (Φ, µ) into a formula ∆ µ (Φ). Such functions are called merging operators. More precisely, an integrity constraint merging operator (an IC merging operator for short) is a function ∆ satisfying the following rationality postulates:

(IC0) ∆ µ (Φ) µ (IC1) If µ is consistent, then ∆ µ (Φ) is consistent (IC2) If Φ is consistent with µ, then ∆ µ (Φ) ≡ Φ ∧ µ (IC3) If Φ 1 ≡ Φ 2 and µ 1 ≡ µ 2 , then ∆ µ1 (Φ 1 ) ≡ ∆ µ2 (Φ 2 ) (IC4) If ϕ 1 µ and ϕ 2 µ, then ∆ µ ({ϕ 1 , ϕ 2 }) ∧ ϕ 1 is consistent if and only if ∆ µ ({ϕ 1 , ϕ 2 }) ∧ ϕ 2 is consistent (IC5) ∆ µ (Φ 1 ) ∧ ∆ µ (Φ 2 ) ∆ µ (Φ 1 Φ 2 ) (IC6) If ∆ µ (Φ 1 ) ∧ ∆ µ (Φ 2 ) is consistent, then ∆ µ (Φ 1 Φ 2 ) ∆ µ (Φ 1 ) ∧ ∆ µ (Φ 2 ) (IC7) ∆ µ1 (Φ) ∧ µ 2 ∆ µ1∧µ2 (Φ) (IC8) If ∆ µ1 (Φ) ∧ µ 2 is consistent, then ∆ µ1∧µ2 (Φ) ∆ µ1 (Φ)
where Φ denotes the conjunction of all the formulas of Φ; Φ 1 ≡ Φ 2 means that there is a bijection f from Φ 1 into Φ 2 such that for any formula ϕ ∈ Φ 1 , we have ϕ ≡ f (ϕ) (in particular, Φ 1 and Φ 2 have the same cardinality as multisets); the symbol stands for the multiset union.

For a detailed explanation of these postulates, see [START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF]. However, let us make a comment about Postulate (IC4), known as the fairness postulate. As a matter of fact, this is a very restrictive postulate. Indeed, the only operators satisfying all the postulates are the operators built from distance and aggregation functions (see [START_REF] Konieczny | Logic based merging[END_REF]). Very natural operators fail to satisfy (IC4). In Section 5.2 of [START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF] there are interesting results around this problem.

An operator ∆ is called an IC quasi-merging operator if it satisfies all the previous postulates except (IC6), but instead of this postulate it satisfies the following one:

(IC6') If ∆ µ (Φ 1 ) ∧ ∆ µ (Φ 2 ) is consistent, then ∆ µ (Φ 1 Φ 2 ) ∆ µ (Φ 1 ) ∨ ∆ µ (Φ 2 )
In order to establish a representation theorem we need to introduce the notion of syncretic assignment. This is a function mapping each profile Φ to a total pre-order ≤ Φ over interpretations such that for any profiles Φ, Φ 1 , Φ 2 and for any belief bases ϕ, ϕ the following conditions hold:

(1) If ω |= Φ and ω |= Φ, then ω Φ ω (2) If ω |= Φ and ω |= Φ, then ω < Φ ω (3) If Φ 1 ≡ Φ 2 , then ≤ Φ1 =≤ Φ2 (4) ∀ω |= ϕ ∃ω |= ϕ ω ≤ ϕ ϕ ω (5) If ω ≤ Φ1 ω and ω ≤ Φ2 ω , then ω ≤ Φ1 Φ2 ω (6) If ω < Φ1 ω and ω ≤ Φ2 ω , then ω < Φ1 Φ2 ω
When the condition ( 6) is replaced by the following condition (6') If ω < Φ1 ω and ω < Φ2 ω , then ω < Φ1 Φ2 ω the assignment is called a quasi-syncretic assignment, that is a function mapping each profile Φ to a total pre-order ≤ Φ over interpretations satisfying (1)-( 5) and (6'). Now we can state the following representation theorem for merging operators: [START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF]). An operator ∆ is an IC merging operator (or IC quasi-merging operator respectively) if and only if there exists a syncretic assignment (or quasisyncretic assignment respectively) that maps each profile Φ to a total pre-order ≤ Φ such that

Theorem 5.1 ([
∆ µ (Φ) = min( µ , ≤ Φ )
A very useful technique to build such operators is based on a distance (actually a pseudo-distance) between interpretations and a numerical aggregation function. We describe how this works more precisely in what follows.

A pseudo-distance10 between interpretations is a function d : Ω × Ω → R + such that for any ω, ω ∈ Ω: d(ω, ω ) = d(ω , ω), and d(ω, ω ) = 0 iff ω = ω .

An aggregation function f is a function mapping, for any positive integer n, each n-tuple of non-negative reals into a positive real such that for any x 1 , . . . , x n , x, y ∈ R + :

• if x ≤ y, then f (x 1 , . . . , x, . . . , x n ) ≤ f (x 1 , . . . , y, . . . , x n ) (monotony) • f (x 1 , . . . , x n ) = 0 iff x 1 = . . . = x n = 0 (minimality) • f (x) = x (identity)
With the help of d and f , a distance between interpretations and an aggregation function respectively, we can construct a total pre-order ≤ Φ on interpretations associated with Φ = {ϕ 1 , ..., ϕ n } in the following way. First, remember that

d(ω, ϕ) is min ω |=ϕ d(ω, ω ). Then, define d(ω, Φ) = f (d(ω, ϕ 1 ) . . . , d(ω, ϕ n )). Finally, ω ≤ Φ ω iff d(ω, Φ) ≤ d(ω , Φ
). This process is, actually, an assignment which is in fact a syncretic (or a quasi-syncretic) assignment when the aggregation function has good additional properties such as symmetry, composition and decomposition (see [START_REF] Konieczny | Logic based merging[END_REF]). For instance when f is the function sum or leximin, we obtain a syncretic assignment by the previous process. When f is the function max, we obtain a quasi-syncretic assignment. Thus, in virtue of Theorem 5.1, the operator defined by the equation ∆ µ (Φ) = min( µ , ≤ Φ ) is an IC merging operator when the aggregation function used is the sum or leximin (Gmax) and is an IC quasi-merging operator when the aggregation function used is the max. They are called in the literature ∆ Σ , ∆ Gmax and ∆ max , respectively 11 .

Let us now establish the links with dilations. Again we consider a dilation δ defined using the balls of the distance d as structuring elements. Then it is not hard to see the following:

∆ max µ (ϕ 1 , ..., ϕ m ) = δ n (ϕ 1 ) ∧ δ n (ϕ 2 ) ∧ ... ∧ δ n (ϕ m ) ∧ µ, (16)
where

n = min{k ∈ N | δ k (ϕ 1 ) ∧ ... ∧ δ k (ϕ m ) ∧ µ is consistent}. ∆ Σ µ (ϕ 1 , ..., ϕ m ) = (n1,...,nm) δ n1 (ϕ 1 ) ∧ δ n2 (ϕ 2 ) ∧ ... ∧ δ nm (ϕ m ) ∧ µ, (17)
where the values n 1 , . . . , n m are such that m i=1 n i is minimal with

δ n1 (ϕ 1 ) ∧ δ n2 (ϕ 2 ) ∧ ... ∧ δ nm (ϕ m ) ∧ µ consistent.
An example illustrating the behavior of ∆ max is displayed in Figure 11, with the same conventions as in Section 2 and the Hamming distance. Let us consider ϕ

= ¬a ∧ ¬b ∧ ¬c, ψ = a ∧ b ∧ ¬c and µ = . While ϕ ∧ ψ is not consistent, δ 1 (ϕ) ∧ δ 1 (ψ) is, and ∆ max (ϕ, ψ) = δ 1 (ϕ) ∧ δ 1 (ψ) = (a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ b ∧ ¬c) (i.e.
the merging provides either a or b, exclusively, and ¬c).

Next we give a less abstract example. show how dilation can help reaching an agreement between agents. Let us assume that Agent 1 prefers to travel in Spain: ϕ 1 = Spain. On the other hand, Agent 2 prefers to travel in Morocco: ϕ 2 = M orocco. Hence the two agents have conflicting preferences. However, each agent is now ready to extend his preferences so that the two agents can travel together. This can be simply modeled by a dilation δ, such that some neighbor countries are included in the preferences:

δ(ϕ 1 ) = Spain ∨ F rance ∨ P ortugal ∨ M orocco δ(ϕ 2 ) = M orocco ∨ Algeria ∨ P ortugal ∨ Spain
Now the preferences are no more conflicting. The merging of the agents' preferences, denoted ∆(ϕ 1 , ϕ 2 ), can be expressed as the conjunction of the dilated preferences:

∆(ϕ 1 , ϕ 2 ) = δ(ϕ 1 ) ∧ δ(ϕ 2 ) = Spain ∨ P ortugal ∨ M orocco.
A solution for traveling can then be found in the set of models of these formulas.

To go one step further, we can add constraints the agents have to satisfy. For instance if Agent 1 has to stay in Europe and Agent 2 has to stay in a Mediterranean country, these constraints can be taken into account by conditional dilations, thus modifying preferences as:

ϕ 1 = δ(ϕ 1 ) ∧ ψ 1 = Spain ∨ F rance ∨ P ortugal, ϕ 2 = δ(ϕ 2 ) ∧ ψ 2 = δ(ϕ 2 ),
where ψ 1 and ψ 2 encode the constraints. Then the new set of consistent preferences is given by ϕ = ϕ 1 ∧ ϕ 2 = Spain ∨ P ortugal. Now suppose that the integrity constraints are encoded by a formula µ, which establishes the fact that one and only one country can be visited except Spain and Morocco. In this case, the merging of ϕ 1 and ϕ 2 under the constraint µ, denoted ∆ µ (ϕ 1 , ϕ 2 ) is exactly δ(ϕ 1 ) ∧ δ(ϕ 2 ) ∧ µ, i.e., ∆ µ (ϕ 1 , ϕ 2 ) = P ortugal Equations 16 and 17 allow defining more general merging operators when δ is an extensive and exhaustive operator congruent with logical equivalence, i.e. if ϕ 1 ≡ ϕ 2 then δ(ϕ 1 ) ≡ δ(ϕ 2 ). We are going also to consider the following symmetry property for δ, related to the fairness postulate: (IC4):

(sym) δ n (ϕ) ∧ ϕ ⊥ iff δ n (ϕ ) ∧ ϕ ⊥
In particular we have the following results: Proposition 5.3. Let δ be an extensive and exhaustive operator which is congruent with logical equivalence on the lattice of propositional formulas. Then ∆ max µ defined by:

∆ max µ (ϕ 1 , ..., ϕ m ) = δ n (ϕ 1 ) ∧ δ n (ϕ 2 ) ∧ ... ∧ δ n (ϕ m ) ∧ µ, where n = min{k ∈ N | δ k (ϕ 1 ) ∧ ... ∧ δ k (ϕ m )
∧ µ is consistent} (the existence of n being guaranteed by the fillingness property), is a merging operator satisfying (IC1-IC3), (IC5), (IC6') and (IC7-IC8). Moreover it satisfies (IC4) iff δ satisfies (sym). Thus, if δ is an extensive and exhaustive operator which is congruent with logical equivalence and satisfies (sym), the operator ∆ max is an IC quasi-merging operator.

Proof:

Define d(ω, ϕ) = n where n = min{k | ω ∈ δ k (ϕ }. This function d is well defined because of exhaustivity of δ. Define d(ω, Φ) = max(d(ω, ϕ 1 ), . . . , d(ω, ϕ n ))) where Φ = {ϕ 1 , . . . , ϕ n }. Now let ω ≤ Φ ω iff d(ω, Φ) ≤ d(ω , Φ). Finally let ∆ µ (Φ)
be a formula satisfying the following equation: ∆ µ (Φ) = min( µ , ≤ Φ ). This is well defined because δ is congruent with logical equivalence. It is easy to see that ∆ max µ (Φ) = ∆ µ (Φ). By the hypothesis about δ and the fact that the aggregation function taken is the max function, it is also easy to check that the assignment Φ →≤ Φ is a quasi-syncretic assignment (property ( 4) is indeed equivalent to property (sym)). Thus, by virtue of Theorem 5.1, ∆ max is an IC quasi-merging operator. Proposition 5.4. Let δ be an extensive and exhaustive operator which is congruent with logical equivalence on the lattice of propositional formulas. Then ∆ Σ defined by:

∆ Σ µ (ϕ 1 , ..., ϕ m ) = (n1,...,nm) δ n1 (ϕ 1 ) ∧ δ n2 (ϕ 2 ) ∧ ... ∧ δ nm (ϕ m ) ∧ µ,
where the numbers n 1 , . . . , n m are such that m i=1 n i is minimal with δ n1 (ϕ 1 )∧δ n2 (ϕ 2 )∧ ... ∧ δ nm (ϕ m ) ∧ µ consistent, is a merging operator satisfying (IC1-IC3), (IC5-IC8). Moreover it satisfies (IC4) iff δ satisfies (sym). Thus, if δ is an extensive and exhaustive operator which is congruent with logical equivalence and satisfies (sym), the operator ∆ Σ is an IC merging operator.

Proof: Similar to the proof of the previous proposition but using the sum (Σ) function instead of the max function.

This approach has been extended in [START_REF] Gorogiannis | Merging First-Order Knowledge using Dilation Operators[END_REF] to first order logic, by combining dilation and comparison ordering operators. The merging postulates are then adapted, and conditions on these two operators are established in order to satisfy these postulates. An implementation using binary decision diagrams has furthermore been proposed in [START_REF] Gorogiannis | Implementing semantic merging operators using binary decision diagrams[END_REF].

Abduction

In this section we show that morphologic can also be used to model abductive reasoning.

The process of inferring the best explanation of an observation is usually known as abduction. In the logic-based approach to abduction, the background theory is given by a consistent set of formulas12 Σ. The notion of a possible explanation is defined by saying that a formula γ that is consistent with Σ is an explanation of α if Σ ∪ {γ} α (this will be written γ Σ α). Since explanations have different degrees of plausibility, a characteristic feature of explanatory reasoning is the search for the most plausible (simple, rational, preferred) explanations.

Despite the absence of a general definition of explanation, there have been several attempts to develop a logical account of explanatory reasoning [START_REF] Aiguier | Explanatory relations in arbitrary logics based on satisfaction systems, cutting and retraction[END_REF][START_REF] Bochman | A causal theory of abduction[END_REF][START_REF] Boutilier | Abduction as belief revision[END_REF][START_REF] Flach | Rationality Postulates for Induction[END_REF][START_REF] Flach | Logical characterisations of inductive learning[END_REF][START_REF] Flach | On the logic of hypothesis generation[END_REF][START_REF] Díaz | Representation theorems for explanatory reasoning based on cumulative models[END_REF][START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF][START_REF] Pino Pérez | Preferences and explanations[END_REF]. The model for explanatory reasoning we use is based on the notion of an explanatory relation, i.e. binary relations on formulas, denoted by £ , where the intended meaning of α £ γ is "γ is a preferred explanation of α".

Similarly to what has been done for belief revision and merging, a set of rationality postulates for explanatory reasoning was proposed and discussed in [START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF][START_REF] Pino Pérez | Preferences and explanations[END_REF]. The basic rationality postulates for explanatory relations are the following:

LLE Σ : If Σ α ↔ α and α £ γ then α £ γ. RLE Σ : If Σ γ ↔ γ and α £ γ then α £ γ . E-CM: If α £ γ and γ Σ β then (α ∧ β) £ γ. E-C-Cut: If (α ∧ β) £ γ and ∀δ [α £ δ ⇒ δ Σ β ] then α £ γ. RS: If α £ γ, γ Σ γ and γ Σ ⊥ then α £ γ . ROR: If α £ γ and α £ δ then α £ (γ ∨ δ). LOR: If α £ γ and β £ γ then (α ∨ β) £ γ. E-DR: If α £ γ and β £ δ then (α ∨ β) £ γ or (α ∨ β) £ δ. E-R-Cut: If (α ∧ β) £ γ and ∃δ [α £ δ & δ Σ β] then α £ γ. E-Reflexivity: If α £ γ then γ £ γ. E-Con Σ :
Σ ¬α iff there is γ such that α £ γ. The intended meaning and motivation for these postulates can be found in [START_REF] Díaz | Representation theorems for explanatory reasoning based on cumulative models[END_REF][START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF][START_REF] Pino Pérez | Preferences and explanations[END_REF]. For the convenience of the reader, we briefly recall the heuristic behind them. Suppose £ is an explanatory relation. We associate to it a consequence relation |∼ ab as follows: α |∼ ab β if γ Σ β for all γ such that α £ γ. We read α |∼ ab β as saying that when α is observed, β is normally also observed. The relation |∼ ab is a nonmonotonic consequence relation in the KLM sense [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Makinson | General patterns in nonmonotonic reasoning[END_REF]. The properties for £ listed above are in tight correspondence with some well known postulates for nonmonotonic consequence relation (applied to |∼ ab ). For instance, E-R-Cut is the counterpart of rational monotony: if α |∼ ab δ and α |∼ ab ¬β, then α ∧ β |∼ ab δ.

It was shown in [START_REF] Díaz | Representation theorems for explanatory reasoning based on cumulative models[END_REF][START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF][START_REF] Pino Pérez | Preferences and explanations[END_REF] that our postulates capture well some natural explanatory processes and also share with nonmonotonic logic, belief revision and merging the feature of having nice representation theorems. To illustrate this claim, let us say that an explanatory relation £ is causal E-rational [START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF] if it satisfies LLE Σ , E-Con Σ , E-CM, E-R-Cut and RS. Then we have the following. Theorem 6.1. [START_REF] Pino Pérez | Jumping to Explanations versus jumping to Conclusions[END_REF] An explanatory relation is causal E-rational if, and only if, there is a total pre-order ≤ of the models of Σ such that for all α and γ the following holds:

α £ γ ⇔ Σ ∪ {γ} ⊆ min( α , ≤).
The total pre-order ≤ given in the previous theorem induces a plausibility order among the possible explanations. Thus the preferred explanations with respect to a causal E-rational explanatory relation are the most plausible ones according to this ordering (see [START_REF] Pino Pérez | Preferences and explanations[END_REF] for a complete development of these ideas).

The aim of this section is threefold: first, to propose very natural explanatory relations using morphologic that in some cases are computationally tractable; secondly, to examine the adequacy of logical postulates presented above, and thirdly, to illustrate the role that the structuring element plays in the proposed models as discussed in Section 2.6.

Explanatory relations based on erosion

Morphologic allows us to define the most central part of a formula, according to the fundamental principles of this theory (see e.g. [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology, Part II: Theoretical Advances[END_REF], and Section 2). Using this notion we define two explanatory relations.

Recall that in Section 2.6 (Definition 2.4 and Equation 15) we have defined a total pre-order f of all models in such a way that the models of Σ occupy the first m levels where m is the size of the last non empty erosion of Σ. This pre-order is approximating the most central part of Σ. Given an observation α, we can select the preferred explanations of α using the minimal models of α (so, the closest to the most central part of Σ) with respect to f .

A second method to select the preferred explanations uses a similar idea. Now we successively erode Σ ∪ {α} instead of Σ alone, in other words, we are going to use the last non empty erosion of Σ ∪ {α} (see Definition 2.3). The results are quite different. The second method depends more heavily on the observation at hand and this has the effect that the corresponding explanatory relation might not satisfy some very basic structural properties.

For an explanatory relation £ and an observation α, we denote its associated set of preferred explanations as follows:

P E £ (α) = {γ | α £ γ}.

Using the last consistent erosion

The first approach for defining a notion of preferred explanation consists in eroding Σ as much as possible but under the constraint that it remains consistent with α. More precisely, consider the following formula

ε c (Σ, α) = ε n (Σ) (18)
where

n = sup{k ∈ N | ε k (Σ) ∧ α ⊥} if n < +∞ n = min{k ∈ N | ∀k > k, ε k (Σ) = ε k (Σ), ε k (Σ) ∧ α ⊥} otherwise.
From this operator, we define the following explanatory relation: Definition 6.2. An explanatory relation derived from the notion of last consistent erosion is defined as:

α £ c γ def ⇔ γ Σ ε c (Σ, α) ∧ α. (19)
This definition has the following interpretation. We consider erosion of Σ, which means that we are looking at the formulas that satisfy α while being the most in the theory, i.e. that can be changed while remaining in the theory. Let us see an illustrative example (see Figure 12). Take Σ = a ∨ b ∨ c, and α = (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c), and balls of the Hamming distance as structuring elements. We have

α Σ ε(Σ) ε 2 (Σ)
ε 1 (Σ) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c), ε 2 (Σ) = a ∧ b ∧ c
, and finally ε 3 (Σ) ⊥. Therefore:

ε 1 (Σ) ∧ α = (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)
and ε 2 (Σ) ∧ α ⊥. The value of n in Equation 18 is then equal to 1.

For Definition 6.2, the following formulas belong to P E £ c (α):

(a ∧ ¬b ∧ c), (a ∧ b ∧ ¬c), (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c).
There is an alternative way of looking at £ c which will be particularly useful in the next section. Considering the morphological ordering f restricted to the models of Σ, it is not difficult to verify that the following holds:

α £ c γ if and only if Σ ∧ γ ⊆ min( Σ ∧ α , f ). ( 20
)
In particular, by Theorem 6.1, we have the following proposition: Proposition 6.3. £ c satisfies LLE Σ , E-Con Σ , E-CM, E-R-Cut and RS.

Using the last non-empty erosion

We now introduce another explanatory relation which uses the last erosion ε (ϕ) of a formula ϕ.

Let us take (see Figure 13) ϕ = (a ∨ ¬b ∨ ¬c) ∧ (a ∨ b ∨ c), and an erosion defined using the balls of the Hamming distance as structuring elements. Using the properties ϕ ε(ϕ) Figure 13. An example of ϕ and its last erosion, equal to ε(ϕ) in this case.

of erosion, and in particular the fact that it commutes with the conjunction, it is easy to derive that:

ε 1 (ϕ) = (a∨¬b)∧(a∨¬c)∧(¬b∨¬c)∧(a∨b)∧(a∨c)∧(b∨c) = (a∧¬b∧c)∨(a∧b∧¬c).
Since ε 2 (ϕ) ⊥, we have ε 1 (ϕ) = ε (ϕ) (its models are in red in Figure 13).

A preferred explanation of α is then defined from this operator applied on Σ ∧ α, more precisely: Definition 6.4. An explanatory relation derived from the last non-empty erosion is defined as follows:

α £ ne γ def ⇔ γ Σ ε (Σ ∧ α). (21)
The idea of taking the last erosion of Σ∧α can be interpreted in terms of robustness. An erosion of size n of a formula is a formula that can be changed while still proving the initial formula. If at most n symbols are changed in ε n (ϕ) then ϕ is always satisfied. Here, considering ε (Σ ∧ α) means that we are looking at the most reduced formula that satisfies Σ ∧ α, i.e. the one that can be changed the most while satisfying Σ ∧ α.

Erosion does not take into account all "parts" of a formula. Let us take for instance: 14). Then we have: ε (Σ ∧ α) = ε (Σ ∧ β) = a ∧ b ∧ c and thus α and β have the same preferred explanations. The set of worlds satisfying Σ ∧ β is disconnected, and the connected component containing only (¬a ∧ ¬b ∧ ¬c) is not represented in the explanations of β. This should not be surprising, since any explanatory relation will select some part of an observation as the most relevant one. However, if this is considered to be a problem, it can be avoided by considering the ultimate erosion instead of the last erosion, which will select at least one element of each connected component of an observation (see Section 2.5).

Σ ∧ α = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c) and Σ ∧ β = ((a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c)) ∨ (¬a ∧ ¬b ∧ ¬c) (Figure
An important difference between £ c and £ ne is that the later is more observation dependent than the former. In fact, for a given α, let α f be the morphological ordering associated with Σ ∪ {α}. Then the preferred explanations of α according to £ ne are obtained using α f instead of f as it was done with £ c . As a consequence of this, £ ne does not satisfies neither E-CM nor E-C-Cut. However, it does satisfy the following weaker form of E-CM:

E-W-CM:

If α £ γ and β £ γ then (α ∧ β) £ γ. It is important to note that £ ne is the first natural non-trivial example we know

Σ ∧ α Σ ∧ β ε(Σ ∧ α) = ε(Σ ∧ β) ∪ Figure 14
. An example of Σ ∧ α and Σ ∧ β that have the same last erosion. Σ ∧ β has two connected components (blue models on the one hand and the cyan one on the other hand), the second one being not represented in the final result.

of that satisfies E-W-CM but does not satisfy neither E-CM nor E-C-Cut13 (for a proof of this claim see Appendix A). The next proposition collects all the facts we know about £ ne . Proposition 6.5. The explanatory relation £ ne satisfies LLE Σ , RLE Σ , ROR, E-W-CM, RS and E-Con Σ .

The proof of this result can be found in Appendix A. Table 3 summarizes the results we obtained so far.

LOR √ × E-DR √ × E-Con Σ √ √
Table 3. Properties of the proposed relations.

The role of the structuring element: an example

In this section we explore some ways of defining structuring elements which are more appropriate for the task of finding explanations. We will analyze the following example through different structuring elements.

Example 6.6. Let us consider the very simple theory Σ 1 = {a → c, b → c} (represented by the same formula ϕ as the one in Figure 3), and suppose that the observation is c. What are the "good" explanations of c? We present three different interpretations where the most natural answers would be different. We usually expect that the causes of c are among a, b. Let us consider the following three interpretations, where different explanations may be expected:

(1) a = rained last night b = sprinkle was on c = grass is wet

The "common sense cautious explanation" of c is a ∨ b.

(2) a = drug b = another drug c = adverse reaction An explanation that an adverse reaction occurs is that one has taken drug a and drug b, the combination of which is not recommended. Hence the "eager" explanation a ∧ b would be preferred.

Note that in this case, it could be argued that the background theory would be a ∧ b → c.

(3) a = book was left somewhere else b = somebody took the book c = book is not in the shelf An explanation based on the principle of the "Ockham's razor" will select either a or b but not both, that is to say, (a ∧ ¬b) ∨ (¬a ∧ b).

In the example above, the expected explanations of c are built only using the atoms a or b. We can introduce this constraint using a distinguished set of atoms Ab (sometimes are called abducibles); in our example, Ab = {a, b}. We can modify the background theory as follows:

Σ 2 = Σ 1 ∪ {a ∨ b}.
Notice that Σ 2 is logically equivalent to {(a ∧ c) ∨ (b ∧ c)}. It models explicitly that a ∨ b is part of the theory, and then, the causes of c can be found among a and b. We can also modify the structuring element to include this new constraint. As before, B ω denotes the ball of radius 1 centered at ω (with respect to the Hamming distance for instance). Let

B ab ω = {ω ∈ B ω | ω(x) = ω (x) for all x ∈ Ab}.
B ab ω contains those valuations in B ω which agree with ω outside Ab.

Example 6.7. Let Σ 2 and Ab be as above. We will work with the notion of explanation given by £ c .

(1) With the standard ball B ω we get ε 1 (Σ 2 ) = ⊥. Thus, ε c (Σ 2 , c) = Σ 2 . In particular, c £ c (a ∨ b).

(

(Σ 2 ) = ε 2 (Σ 2 ) = (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c). Thus, c £ c (a ∧ ¬b) ∨ (¬a ∧ b).
Notice that c £ c (a ∧ b).

In Example 6.7 we get the "expected" solutions, as described in Example 6.6. One way to understand it is as follows. Given Σ and a set of atoms Ab, let AbF orm be the set of formulas that use only atoms from Ab. Given an observation formula α, the cautious explanation of α (with respect to (Σ, Ab)) is defined by: ce(α) = {γ ∈ Abf orm | Σ ¬γ and Σ ∪ {γ} α}.

Since the language is finite, restricting the formulas γ appearing in the definition of ce(α) to be a conjunction of literals from Ab, we get that ce(α) is well defined. For instance, in Example 6.6 we have ce(c) = a∨b. By adding to Σ the cautious explanation of the observation, we are imposing an extra constraint that helps to find some of its "natural" explanations. The expanded theory seems to be a useful tool for the task of finding "correct" explanations. All this is illustrated by Example 6.7, where the choice of an appropriate structuring element allows us to find the expected explanations in the three situations presented in Example 6.6.

Table 4 summarizes the results for the last two examples, for Σ 1 and Σ 2 and the three considered structuring elements (Figure 15). These examples illustrate how different explanations can be obtained using appropriate structuring elements. Roughly speaking, if a and b are incompatible, then the exclusive disjunction is appropriate, and it is obtained using B ab ω,2 . If they are compatible, a parsimonious explanation is the disjunction (as required for instance in model-based diagnosis), obtained for B ω , while a more sure or constrained explanation is the conjunction, obtained for B ab ω .

1 Σ 2 B ω ¬a ∧ ¬b ∧ c a ∨ b B ab ω c a ∧ b B ab ω,2 c (a ∧ ¬b) ∨ (¬a ∧ b)

Unified view using the fundamental pre-order f

We present in this section a unified treatment of abduction and revision. In particular, we propose to put in the same framework some of the results of Sections 4 and 6 (and [START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF][START_REF] Bloch | Explanatory Relations based on Mathematical Morphology[END_REF]), using the fundamental morphological pre-order relation f .

In the following we still assume anti-extensive erosions and extensive dilations.

There is an alternative way of looking at £ c which will be particularly useful in what follows. The iteration of the erosion operator provides a method of linearly pre-ordering the models of Σ. We have already noted that, when α is consistent with Σ, we have a representation of the relation £ c in terms of the morphological order given by the equivalence [START_REF]Investigations into a Theory of Knowledge Base Revision: Preliminary Report[END_REF].

Actually, if we take the following pre-order over the models of Σ:

ω ≤ E ω def ⇔ ∀k (ω ∈ ε k (Σ) → ω ∈ ε k (Σ)), (22)
it is clear that ≤ E and f coincide over Σ . Thus equivalence (20) can be rewritten as:

α £ c γ if and only if γ ∧ Σ ⊆ min( Σ ∧ α , ≤ E ). (23)
Let us now come back to the revision based on dilation. As described in Section 4 (see also [START_REF] Bloch | Towards Mathematical Morpho-Logics[END_REF]), the idea is to dilate Σ (which is not necessarily consistent with α) until it becomes consistent with α. Note that Σ is then no more considered as a fixed theory but rather as a background knowledge, which can evolve. More precisely, we define • as:

Σ • α = δ n (Σ) ∧ α where n = min{k ∈ N | δ k (Σ) ∧ α is consistent} Σ if there is no k such that δ k (ϕ) ∧ ψ ⊥ (24)
The iteration of the dilation operator provides a method of linearly pre-ordering the models of δ (Σ) . Consider the following relation among models:

ω ≤ D ω def ⇔ ∀k (ω ∈ δ k (Σ) → ω ∈ δ k (Σ)). (25)
Indeed, it is clear that ≤ D is a total pre-order over δ (Σ) ; we will call it the total preorder associated with Σ using successive dilations. It is not difficult to verify that the following holds:

Σ • α = min( α , ≤ D ). if α ∧ δ (Σ) ⊥ Σ if α ∧ δ (Σ) ⊥ (26)
Indeed, it is easy to check that over the set δ (Σ) \ Σ the relations ≤ D and f coincide.

By the representation theorem for credibility-limited revision operators (see [START_REF] Booth | Credibility-limited revision operators in propositional logic[END_REF]), i.e. operators that generalize the classical AGM-revision operators [START_REF] Alchourrón | On the Logic of Theory Change: Partial Meet Contraction and Revision Functions[END_REF][START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF], it follows from Equation 26 that • is a credibility-limited revision operator [START_REF] Booth | Credibility-limited revision operators in propositional logic[END_REF][START_REF] Hansson | Credibility limited revision[END_REF].

The pre-order defined by Equations 22 and 25 can be merged in the morphological ordering f introduced in Section 2. By the previous observations, the morphological order f is ≤ E over Σ and ≤ D over the set δ (Σ) \ Σ .

Based on the morphological ordering, we can associate with each observation α the following set of valuations:

M (α) = min( α , f ) if α ∧ δ (Σ) ⊥ Σ if α ∧ δ (Σ) ⊥
Note that the criterion used to define M (α) is based on the morphology operators δ and ε. The interpretation we give to M (α) is that it contains those worlds that are (morphologically) more relevant given the observation α. Therefore for the task of revising Σ or explaining α we only look at M (α). This will be made precise in the result that follows. We will denote by C(α) the formula whose models are exactly M (α).

Theorem 6.8. Let Σ, α and γ consistent formulas.

(1) If α is consistent with Σ, then α £ c γ iff γ C(α).

(

) If α is inconsistent with Σ, then Σ • α = C(α). 2
The previous result suggests the following definitions

α £ f γ def ⇔ γ C(α) (27)
and

Σ • f α = C(α) (28)
where α and γ are consistent formulas.

As an example, let us consider the example in Figure 6 for Σ = Σ 1 . For α = (¬a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c), α is consistent with Σ and its explanation is γ ≡ Σ ¬a ∧ ¬b ∧ c, which corresponds to the rank 0 in Table 1. Now if α is reduced to α = ¬a ∧ b ∧ ¬c, then it is no more consistent with Σ and the revision applies.

Some comments about these definitions should be made. First of all, even when an observation is inconsistent with the background theory Σ there is a formula γ such that α £ f γ. That is to say, we can "explain" more observations with £ f than with £ c . This is related to the idea of abduction as belief revision [START_REF] Boutilier | Abduction as belief revision[END_REF]. The interpretation we give to this fact is that for explaining an observation it is allowed (if necessary) to "change" the background theory. Thus in the explanatory process described by £ f the observation is absolutely reliable. Notice also that £ f makes it explicit that some explanations might not be consistent with Σ.

The operator • f is not an AGM revision operator for Σ (even not a credibilitylimited revision operator), since when the observation α to be incorporated is consistent with Σ we have only Σ • f α Σ ∧ α, not the equivalence (the equivalence in the case where α and Σ are consistent is just the vacuity postulate, usually denoted by K*4, which is equivalent to the minimality R2). The reason for this is that • f is based on preferences on models of Σ, so even when Σ ∧ α is consistent, some sort of central reason for accepting α has to be found. Note that the previous remark says that • f does not satisfy the postulate R2 (alias K*4), which has been criticized by some authors in particular in [START_REF] Ryan | Belief Revision and Ordered Theory Presentations[END_REF]. Unlike Ryan's operators, which are based on ordered theory presentations, R2 and success (R1) are the only postulates which are not satisfied by • f . However, note that • f satisfies the modified version of success of credibility-limited revision operators, that is: Σ • α α or Σ • α ≡ Σ.

Final remarks and perspectives

We have given the fundamental concepts and techniques in mathematical morphology, and have shown how to interpret these techniques in terms of mathematical logic, namely in propositional logic. This connection has originated a new domain called morphologic. We have used dilation operators in order to define belief revision operators and belief merging operators.

We have shown that we can find some operators defined in the literature when the dilation operators come from a distance function. Moreover, we have extended the class of belief revision operators and the class of belief merging operators by using a larger class of operators, in particular having the extensivity and exhaustivity properties.

A similar work has been done using erosion operators. These operators are used in two ways in order to define explanatory relations. It is interesting to note that the use of different structuring elements is determinant in the way the information is structured. The examples in Section 6.2 point out clearly this phenomenon.

Under the assumption that the geometry comes from the Hamming distance between interpretations, we have shown how to compute dilation, erosion, last erosion, ultimate erosion, opening and skeleton operators over formulas. These calculations constitute the basis of our applications to different tasks in knowledge representation.

We have proven that our general operators of revision and fusion are well behaved, in particular they satisfy the AGM postulates and the postulates of integrity constraints belief merging. We have also proven that the explanatory relations defined using morphologic satisfied suitable structural properties.

Potential extensions would be to analyze how minimality criteria could be expressed in the proposed framework, as the ones proposed for abduction [START_REF] Bienvenu | Complexity of abduction in the EL family of lightweight description logics[END_REF][START_REF] Eiter | The complexity of logic-based abduction[END_REF][START_REF] Halland | ABox abduction in ALC using a DL tableau[END_REF], revision for Horn clauses [START_REF] Delgrande | Revising Horn theories[END_REF][START_REF] Delgrande | Belief revision in Horn theories[END_REF][START_REF] Zhuang | Definability of Horn revision from Horn contraction[END_REF] or for description logics [START_REF] Qi | Knowledge base revision in description logics[END_REF][START_REF] Qi | A survey of revision approaches in description logics[END_REF][START_REF] Ribeiro | AGM revision in description logics[END_REF][START_REF] Ribeiro | More about AGM revision in description logics[END_REF][START_REF] Wang | Revising general knowledge bases in description logics[END_REF]. More generally mathematical morphology can be used for revision or abduction in institutions and satisfaction systems [START_REF] Aiguier | Belief revision, minimal change and relaxation: A general framework based on satisfaction systems, and applications to description logics[END_REF][START_REF] Aiguier | Explanatory relations in arbitrary logics based on satisfaction systems, cutting and retraction[END_REF][START_REF] Aiguier | Logical dual concepts based on mathematical morphology in stratified institutions: Applications to spatial reasoning[END_REF].

One interesting feature that is worth to remark is the fact that morphologic allows us to give an ordered structure to the pieces of information. That is, it allows having preferences over the formulas. It is exploited by the morphological total pre-order defined by Equation 15. Note that these preferences depend on the structuring element used for defining dilations and erosions.

Finally, our approach provides a reusable framework for performing numerous op-erations on formulas, and includes computational and axiomatic building blocks, to be applied in different reasoning problems. Future work will aim to apply the tools of morphologic in order to explain multiple observations and for putting dynamics in the explanatory process. We also expect to treat mediation process using the tools developed in this work. which is the last non-empty erosion. It follows that α £ ne (¬a ∧ b ∧ c); moreover (¬a∧b∧c) β, but clearly the formula (¬a∧b∧c) is not a preferred explanation of α∧β.

A counter-example of E-C-Cut for £ ne . Again Σ will be { }. Consider α = a ∨ b ∨ c and β = a ∨ ¬b ∨ ¬c.

We have then: Let us now set γ = (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ c), then (α ∧ β) £ ne γ. On the other hand, we have that α £ ne δ iff δ ≡ a ∧ b ∧ c (in this case there is no noise because Σ = ). Thus if α £ ne δ, then δ Σ β. But it is clear that α £ ne γ. We have:

ε 1 (α) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c), ε 2 (α) = a ∧ b ∧ c = ε (α),
ε 1 (α) = (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ c) = ε (α), ε 1 (β) = a ∧ ¬b ∧ c = ε (β), α ∨ β = a ∨ b ∨ c, ε 1 (α ∨ β) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c), ε 2 (α ∨ β) = a ∧ b ∧ c = ε (α ∨ β).
Let γ = a ∧ ¬b ∧ c. Then α £ ne γ and β £ ne γ, but (α ∨ β) £ ne γ.

Proof of Proposition 6. [START_REF] Alchourrón | On the Logic of Theory Change: Partial Meet Contraction and Revision Functions[END_REF].

In what follows, we detail E-W-CM and E-W-C-Cut for £ ne . The other properties are straightforward. In particular it is clear that £ ne satisfies RS.

(i) E-W-CM. Let us assume that γ Σ ε (Σ∧α) with ε (Σ∧α) = ε n (Σ∧α), γ Σ ε (Σ∧ β) with ε (Σ∧β) = ε m (Σ∧β), and that the next erosions are empty. Let us assume that the last non-empty erosion of Σ ∧ α ∧ β is obtained for k. Since the erosion commutes with the conjunction, we have:

ε (Σ ∧ α ∧ β) = ε k (Σ ∧ α ∧ β) = ε k (Σ ∧ α) ∧ ε k (Σ ∧ β).
We necessarily have k ≤ n and k ≤ m since otherwise either ε k (Σ ∧ α) or ε k (Σ ∧ β) would be inconsistent. This implies, due to the monotonicity property of erosion that:

Σ ε n (Σ ∧ α) → ε k (Σ ∧ α) and Σ ε m (Σ ∧ β) → ε k (Σ ∧ β) from which we derive:

Σ ε (Σ ∧ α) ∧ ε (Σ ∧ β) → ε (Σ ∧ α ∧ β).
This interesting general result proves that γ Σ ε (Σ ∧ α ∧ β). The proof for the other two cases are shown similarly.

(ii) E-W-C-Cut. Assume γ Σ ε (Σ ∧ α ∧ β) = ε n (Σ ∧ α ∧ β).
For all δ such that α £ ne δ, i.e. δ Σ ε (Σ ∧ α) = ε m (Σ ∧ α), we have β £ ne δ, i.e. δ Σ ε (Σ ∧ β) = ε k (Σ ∧ β). Let us detail in which situations we have γ Σ ε m (Σ ∧ α).

First we consider the case where the erosion of the last non-empty erosion is empty. Since Σ ∧ α ∧ β Σ Σ ∧ α we have:

ε n (Σ ∧ α ∧ β) Σ ⊥ ⇒ ε n (Σ ∧ α) Σ ⊥.
Therefore n ≤ m. For the same reason, we necessarily have n ≤ k.

Let us first assume that n < m. Since the set of preferred explanations of α is included in the one of β, we have: ε m (Σ ∧ α) Σ ε k (Σ ∧ β). Since m > n, we have:

ε m (Σ ∧ α ∧ β) = ε m (Σ ∧ α) ∧ ε m (Σ ∧ β) Σ ⊥.
Let us now assume n < k. Then similarly, we have:

ε k (Σ ∧ α ∧ β) = ε k (Σ ∧ α) ∧ ε k (Σ ∧ β) Σ ⊥.
If k > m, we have: ε m (Σ ∧ β) Σ ⊥, and, since the erosion is decreasing with respect to the size of the structuring element: ε k (Σ ∧ β) Σ ε m (Σ ∧ β). Therefore: ε m (Σ ∧ α) Σ ε k (Σ ∧ β) Σ ε m (Σ ∧ β), which implies: ε m (Σ ∧ α ∧ β) Σ ⊥ which leads to a contradiction.

Similarly, if k < m, we have: ε k (Σ∧α) Σ ⊥, and ε m (Σ∧α) Σ ε k (Σ∧α). Therefore, since we had ε m (Σ ∧ α) Σ ε k (Σ ∧ β), we have:

ε k (Σ ∧ α ∧ β) = ε k (Σ ∧ α) ∧ ε k (Σ ∧ β) Σ ⊥
which also leads to a contradiction. From these two contradictions, we can conclude that necessarily k = m. Then ε m (Σ ∧ α) Σ ε k (Σ ∧ β) becomes ε m (Σ ∧ α) Σ ε m (Σ ∧ β) and therefore we have:

ε m (Σ ∧ α ∧ β) = ε m (Σ ∧ α) Σ ⊥
which is in contradiction with n < m. Therefore the case n < m and n < k is not possible.

If n = m. In this case, we have:

ε n (Σ ∧ α ∧ β) Σ ε n (Σ ∧ α) ∧ ε n (Σ ∧ β) = ε m (Σ ∧ α) ∧ ε m (Σ ∧ β) Σ ε m (Σ ∧ α),
and therefore:

γ Σ ε n (Σ ∧ α ∧ β) ⇒ γ Σ ε m (Σ ∧ α),
i.e. α £ ne γ. This shows that in this particular case, the property holds. Finally, in the last possibility where n < m and k = n, the property does not hold, as shown by the following counter-example, illustrated in Figure A1: Σ = , Σ ∧ α ∧ β = Σ ∧ β = ε (Σ ∧ α ∧ β) = ε (Σ ∧ β), this last erosion being obtained for n = k = 0. For α, ε (Σ ∧ α) is obtained for m = 1 and has only one model. It is easy to check that for all δ such that δ Σ ε (Σ ∧ α), we have δ Σ ε (Σ ∧ β). But there is a γ such that γ Σ ε (Σ ∧ α ∧ β) and γ Σ ε (Σ ∧ α). Then ε 1 (Σ ∧ γ) = a ∧ b ∧ c = ε (Σ ∧ γ) (still with B ab as structuring element). However γ Σ a ∧ b ∧ c and therefore γ is not an explanation of γ in this case.

Figure 1 .

 1 Figure 1. (a) Structuring element B (ball of the Euclidean distance). (b) Subset X in the Euclidean plane (in white). (c) Its dilation δ B (X). (d) Its erosion ε B (X).

Figure 3 .

 3 Figure 3. Example of an erosion of size 1: ϕ = (a∧b∧c)∨(¬a∧b∧c)∨(a∧¬b∧c)∨(¬a∧¬b∧c)∨(¬a∧¬b∧¬c) = (c ∨ (¬a ∧ ¬b)) and ε(ϕ) = ¬a ∧ ¬b ∧ c.

Figure 5 .

 5 Figure5. Illustration of a natural partial ordering derived from successive erosions (in blue) and dilations (in red) of Σ. We have x f y f z in this example.

Figure 6 .

 6 Figure 6. Illustration of the morphological ordering (here n = 1, m = 1).

Proposition 2 . 5 .

 25 The following properties hold:• The subsets T i of Ω are nested, i.e. ∀i ∈ [0...(n + m -1)], T i ⊆ T i+1 for the considered dilations and erosions (with structuring elements such that ω ∈ B ω ). • The relation f is reflexive and transitive, i.e. a pre-order, which is moreover total.• Let R e be the relation defined on2 Ω by R e (ω, ω ) iff max{k ∈ [0...(n + m)] | ω ∈ T k } = max{k ∈ [0...(n + m)] | ω ∈ T k }.This relation is an equivalence relation and the ordering induced by f on the quotient space 2 Ω /R e is a total ordering.

Proposition 3 . 5 .

 35 which is the case in this paper). Without loss of generality, assume ω |= ϕ. Because d(ϕ, ψ) ≥ 2, we have d(ω, ψ) ≥ 2. Now, assume that ω |= ε(ϕ), i.e., d(ω, ¬ϕ) ≤ 1; this means that there exists a ω such that ω |= ¬ϕ and d(ω, ω ) = 1 (d(ω, ω ) = 0 is impossible because ω |= ϕ and ω |= ¬ϕ). Now, we must have ω |= ψ; otherwise we would have ω |= ¬ϕ ∧ ¬ψ, hence d(ω, ¬ϕ ∧ ¬ψ) ≤ 1, which contradicts ω |= ε(ϕ ∨ ψ). Therefore, d(ϕ, ψ) ≤ d(ω, ω ) ≤ 1, which contradicts the assumption that d(ϕ, ψ) ≥ 2. Let ϕ 1 , . . . , ϕ p be the connected components of ϕ. Then we have: ε(ϕ) ≡ p i=1 ε(ϕ i ).

Figure 8 .

 8 Figure 8. Decomposition of ϕ into two connected components ϕ 1 and ϕ 2 , and its erosion (only a, b and c are considered in this representation).

Example 3. 13 .

 13 Let us consider again ϕ = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) ∨ (¬a ∧ ¬b ∧ ¬c), as in Figure8. We have:• O(ϕ) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) and ϕ ∧ ¬O(ϕ) = (¬a ∧ ¬b ∧ ¬c) which is the center of a maximal ball of radius 0; • ε(ϕ) = a ∧ b ∧ c, O(ε(ϕ)) = ⊥, and ε(ϕ) ∧ ¬O(ε(ϕ)) = a ∧ b ∧ c,which is the center of a maximal ball of radius 1; • the next erosion provides ⊥, so we stop here and return Sk(ϕ) = (¬a ∧ ¬b ∧ ¬c) ∨ (a ∧ b ∧ c).

Figure 9 .

 9 Figure 9. Sk(ϕ): it is composed of the centers of maximal balls of radius 0 and 1.

Figure 10 .

 10 Figure 10. Example of revision ϕ • ψ, obtained here for a dilation of size n = 1.

Example 5 . 2 (Figure 11 .

 5211 Figure 11. Example of merging ∆ max (ϕ, ψ), obtained for a dilation of size n = 1.

Figure 12 .

 12 Figure 12. An example of last consistent erosion.

)

  Now we use B ab ω . Then ε 1 (Σ 2 ) = a ∧ b ∧ c and ε 2 (Σ 2 ) = ⊥. Thus c £ c (a ∧ b). Notice that c £ c (a ∨ b). (3) Consider the following structuring element B ab ω,2 = {ω} ∪ {ω ∈ Ω | d(ω, ω ) = 2 and ω(x) = ω (x) for all x ∈ Ab} where d denotes the Hamming distance. Then ε 1

Figure 15 .

 15 Figure 15. Illustration of Σ 1 and Σ 2 (left) and of three different structuring elements centered at ω (right).

Σ

ε 1

 1 (β) = (a ∨ ¬b) ∧ (a ∨ ¬c) ∧ (¬b ∨ ¬c), ε 2 (β) = a ∧ ¬b ∧ ¬c = ε (β), α ∧ β = (a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ ¬c), ε(α ∧ β) = (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ c) = ε (α ∧ β).

A

  counter-example of LOR for £ ne .Again in this counter-example Σ will be { }. Consider, for £ ne :α = (a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ ¬c) and β = (¬a ∨ ¬b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (a ∨ b ∨ c).

Σ ∧ α Σ( 1 )

 α1 Figure A1. Counter-example for E-W-C-Cut for £ ne .

  ψ). Monotonicity: Both operators are increasing with respect to ϕ, i.e. if ϕ |= ψ, then δ B (ϕ) |= δ B (ψ) and ε B (ϕ) |= ε B (ψ), for any structuring element B. Dilation is increasing with respect to the structuring element, while erosion is decreasing, i.e. if ∀ω ∈ Ω, B ω ⊆ B ω , then δ B (ϕ) |= δ B (ϕ) and ε B (ϕ) |= ε B (ϕ).

	Extensivity and anti-extensivity: Dilation is extensive (ϕ |= δ B (ϕ)) if and only if B is
	derived from a reflexive relation (as is the case for distance based dilation, since
	if ω |= ϕ, then d(ω, ϕ) = 0), and erosion is anti-extensive (ε B (ϕ) |= ϕ) under the
	same conditions. We will always assume extensive dilations and anti-extensive
	erosions in the following.
	Iteration: Dilation and erosion satisfy an iteration property:

Table 1 .

 1 Stratification of the elements of Ω according to the morphological ordering associated with Σ = {a → c, b → c}.

Table 2 .

 2 Stratification of the elements of Ω according to the morphological ordering associated with Σ = {a → c, b → c}, using B ab as structuring element.

Table 4 .

 4 Explanations of observation c for two background theories and three different structuring elements.

Although mathematical morphology has also been extended to complete semi-lattices and general posets[START_REF] Keshet | Mathematical Morphology on Complete Semilattices and its Applications to Image Processing[END_REF], based on the notion of adjunction, in this paper we only consider the case of complete lattices.

Let d be a discrete metric on a set M . We say that d has the betweenness property if for all x, y ∈ M and all k ∈ {0, 1, . . . , d(x, y)} there exists z ∈ M such that δ(x, z) = k and δ(z, y) = d(x, y)k. The Hamming distance has this property.

Note that, in constrast to the Hausdorff distance, the minimum distance is improperly called distance since it does not satisfy all the properties of a true metric.

In this paper, we do not assume any closure constraint on the theory, which is simply a set of formulas Σ = {ϕ i , i ∈ I}, where I is an index set. To identify a theory with a formula, we will also use Σ to denote

It is is easy to see that we can define an AGM operator starting from •, by letting K ψ = Cn(ϕ • ψ) where ϕ satisfies K = Cn(ϕ).

The notation min(A, ≤) where ≤ is a total pre-order, stands for {ω ∈ A | ∀ω ∈ A, ω ≤ ω }.

This story is inspired by a famous example in Cognitive Psychology of an experiment by Tversky and Kahneman[START_REF] Tversky | Extension versus intuitive reasoning: The conjunction fallacy in probability judgment[END_REF].

In knowledge dynamics the fusion of pieces of information having a logical representation is usually called belief merging[START_REF] Konieczny | On the Logic of Merging[END_REF][START_REF] Konieczny | Merging Information: A Qualitative Framework[END_REF][START_REF] Konieczny | Logic based merging[END_REF].

Actually the sources can have different reliabilities, but we will focus on the case where all the sources have the same reliability; there is already a lot to say in this case.

The triangle inequality is not required.

Strictly, they are called ∆ d,Σ , ∆ d,Gmax and ∆ d,max , respectively, to emphasize the chosen distance d.

Often in this work we will identify a finite set of formulas Σ with the conjunction of all its formulas and, by abuse of language, we continue to call this formula Σ. Thus, for instance, we denote the conjunction of formulas of Σ ∪ {α} by Σ ∧ α.

E-W-CM in fact was already considered by Flach[START_REF] Flach | Rationality Postulates for Induction[END_REF] but he did not provide any example for it not satisfying already the stronger version E-CM.

Acknowledgements

The first author would like to thank the Universidad de los Andes who has given partial funding during a sabbatical visit. This work was also partly supported by her chair in Artificial Intelligence (Sorbonne Université and SCAI), and a part of it was done while she was with LTCI, Télécom Paris. The second author thanks the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). The third author thanks Télécom Paris who has given partial funding during several sabbatical visits. The third author has benefited from the support of the AI Chair BE4musIA of the French National Research Agency (ANR-20-CHIA-0028) and also thanks the CDCHT-ULA who has given partial funding through the Project N • C-1855-13-05-A. A part of this work was done while the third and fourth authors were at the Universidad de Los Andes, Mérida, Venezuela.

This kind of function is called a revision operator 5 when it satisfies the following rationality postulates:

A very powerful tool in order to construct revision operators is the representation theorem [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF], based on the notion of faithful assignment. A faithful assignment is a mapping which associates to each formula ϕ a total pre-order ≤ ϕ on Ω such that the following conditions hold:

The representation theorem proven by Katsuno and Mendelzon [START_REF] Katsuno | Propositional Kowledge Base Revision and Minimal Change[END_REF] is the following one: Theorem 4.1. An operator • is a revision operator •, i.e. that satisfies R1-R6, iff there exists a faithful assignment that maps each formula ϕ to a total pre-order ≤ ϕ such that for every propositional formula ψ we have

Intuitively, the pre-order ≤ ϕ is a qualitative way to express the distance of a world ω to ϕ, i.e., ω ≤ ϕ ω means that ω is closer to ϕ than ω . Actually, a faithful assignment can be defined from a distance d from a world to a formula in the following way: ω ≤ ϕ ω iff d(ω, ϕ) ≤ d(ω , ϕ), where d(ω, ϕ) is defined as min{d(ω, ω ) | ω |= ϕ}. In particular, the revision operator induced by the choice of the distance d H is known as Dalal's revision operator.

In all what follows, we assume that ψ is consistent. Let us consider the morphological dilation δ defined using as structuring element the ball of radius one of the distance d. It can be seen that we have

This approach is very natural since it corresponds to a principle of minimal change. The following example illustrates in a precise manner the behavior of this operator.

Example 4.2 (Revision). John knew Linda 7 when both of them were PhD students in Philosophy in a very prestigious university. He remembers Linda's activism in feminism, her brilliant record and her great beauty. Both obtained their PhD degree at

Appendix A. Proofs

In this appendix, we provide proofs of certain technical claims.

A counter-example of E-CM for £ ne .

In this example Σ will be { }, so we will remove it altogether. Let us consider the following formulas:

Using the computation formulas for erosion of a formula under CNF (Proposition 3.1), we get:

A unique world satisfies this formula, and therefore no further erosion can be performed (ε 3 (α) ⊥). Similarly, we have: