Eviction and Reception for Description Logic Ontologies (Extended Abstract)⋆

Abstract

In Belief Change, one studies how to adapt the epistemic state of an agent according to some incoming information. Here, we investigate the case in which the epistemic state of the agent is represented as a knowledge base in description logic. Moreover, we consider that the incoming information is in the format of a set of models and investigate eviction (removal of models) and reception (addition of models) in this setting. We briefly present the case of ℒ extended with Boolean operators over the axioms.

1. Introduction

In this work, we generalise the framework by Guimarães et al. [ 4 ] by introducing the notion of “compartments”. A compartment is a pair where the first element is a (potentially infinite) subset of (finite) KBs that can be expressed in a given DL and the second element is a (potentially infinite) set of sets of models taken from the whole set of DL models. This can be used to restrict the more general case of eviction and reception in a given DL, for example, by just considering ifnite models or by just considering a particular set of formulae where eviction and reception can be performed while preserving finiteness of the agent’s epistemic state. There have been works on repairing ontologies, where the goal is both to preserve the syntax of the ontology and perform the change operation [5, 6, 7, 8]. Our work difers from these studies as the goal in our case is to perform the change operation in an optimal way, giving up on the syntax. Regarding earlier approaches within the field of Belief Change focusing on finite representation of the agent’s epistemic state and the format of the incoming information, we refer to the related work section by Guimarães et al. [ 4 ].

In Section 2 we recall the framework by Guimarães et al. [ 4 ] and present our generalised framework, with the already mentioned notion of compartments. In Section 3, we consider the case of ℒ.

2. Eviction and Reception Modulo Compartments

We represent a logic using a satisfaction system Λ( ℒ) [ 7, 9, 4 ], where ℒ is the language of the logic. More specifically, a satisfaction system is a triple Λ = ( ℒ, M, |=), where ℒ is a language, M is a set of models, also called interpretations, and |= is a satisfaction relation which contains all pairs (, ℬ), where is an interpretation and ℬ is a base (that is, a subset of ℒ), such that satisfies ℬ (i.e., |= ℬ).

The belief change framework originally proposed by Guimarães et al. [ 4 ] assumes that an agent’s corpus of beliefs is represented as a finite set of formulae ℬ (a finite base), while incoming information is represented as a set of models M. There are two main kinds of operations addressed in such a framework: eviction, which consists in removing from ℬ all models in M; and reception, which consists in incorporating to ℬ all models from M. In both operations, the output is a finite base.

Both eviction and reception operations are characterized by a set of rationality postulates that capture the notion of minimal change: eviction is characterized by the postulates success, inclusion, finite retainment, and uniformity; while reception is characterized by the postulates success, persistence, finite temperance, and uniformity. These postulates are inspired by the traditional postulates in Belief Change and express desirable (and often expected) properties of operations in this field. For the complete definition and discussion on the rationale of these postulates see [ 4 ].

Here, we give an intuitive explanation of the postulates that characterise eviction and reception There are four postulates for eviction: success, indicating that no input models satisfy the resulting base; inclusion, the new finite base is produced by removing models from the original finite base; finite retainment , models are lost either if they are in the input or if they are necessary to reach a finite base; and uniformity, ensures that the operation is not sensitive to syntax. Analogously, we have four postulates for reception: success, all the new models satisfy the input base; persistence, all the old models satisfy the new base; finite temperance , a model will satisfy the resulting base if it was in the input, if it satisfied the original base, or if it is required to ensure finite representability; and uniformity, the result of the reception depends only on the sets of models that satisfy the input base and the set of input models.

Satisfaction systems in which eviction operations can be defined are called eviction-compatible, while satisfaction systems in which reception can be defined are called reception-compatible [ 4 ]. Unfortunately, there are satisfaction systems that are neither eviction- nor reception-compatible, as it is the case of the DL ℒ [ 4 ]. These impossibility results, however, are proved specifically for each of the investigated logics. We identify suficient conditions for reception-compatibility. Theorem 1. Let ℒ be a monotonic DL with ⊤, that can represent inconsistencies and it is interpreted over an infinite signature. The satisfaction system Λ( ℒ) is not reception-compatible.

The main obstacle to eviction- and reception-compatibility is that eviction and reception functions might be undefined for some inputs in the domain f (ℒ) × (M), for a satisfaction system Λ = ( ℒ, M, |=).

Thus, we will attempt to circumvent the incompatibilities of a satisfaction system by placing restrictions on which bases and sets of models are allowed as input, restricting the domain of the eviction and reception functions. We formalise these additional constraints with the notion of compartment. In the following, the power set of a set is denoted by (), while the set of all finite subsets of is denoted by f ().

Definition 2. A compartment of a satisfaction system Λ = ( ℒ, M, |=) is a pair (B, I) such that B ⊆ f (ℒ) and I ⊆ (M).

We say that a compartment (B, I) of a satisfaction system Λ = ( ℒ, M, |=) is evictioncompatible (resp. reception-compatible) if it defines a subset of f (ℒ) × (M) in which eviction (resp. reception) functions can be defined over B × I. As a result, we can perform eviction and reception functions to potentially interesting portions of satisfaction systems that are, otherwise, incompatible with either eviction or reception. Furthermore, since we preserve the underlying constructions of the operations proposed by Guimarães et al. [10], we also retain their formal characterisation via postulates.

Theorem 3. Let (B, I) be an eviction-compatible compartment of a satisfaction system Λ and evc be a model change operator modulo (B, I). The operator evc is a maxichoice eviction function modulo (B, I) if it satisfies the postulates success, inclusion, finite retainment, and uniformity from Theorem 5 of Guimarães et al. [ 4 ], for all ℬ ∈ B and M ∈ I. Theorem 4. Let (B, I) be a reception-compatible compartment of a satisfaction system Λ and rcp be a model change operator modulo (B, I). The operator rcp is a maxichoice reception function modulo (B, I) if it satisfies success, persistence, finite temperance, and uniformity from Theorem 10 from Guimarães et al. [ 4 ], for all ℬ ∈ B and M ∈ I.

Since the negative result in Theorem 1 involves infinite signatures and several DLs are interpreted over infinite signatures, we consider, unless otherwise stated, only compartments such that (1) bases and models are defined over a finite signature, (2) the class of models is composed of singleton sets, and (3) every singleton corresponds to a finite model. 3. The Case of ℒ The framework we presented is general enough to cover several satisfaction systems without imposing much constraints upon the logics being used to represent an agent’s beliefs. However, there are interesting logics used for knowledge representation that are not reception-compatible, as it is the case of some DLs (Theorem 5). In this section, we investigate how to extend model change operations to one such logic as a study case. We look precisely at the logic ℒ1, which corresponds to the DL ℒ enriched with boolean operators over ℒ axioms. As ℒ is a prototypical DL, it shares many similarities other logics in the of DL family. Our results are built on proofs for the ℒ case without boolean operators over the axioms [ 4 ].

We establish negative results for eviction compatibility. We denote by Λ( ℒ) the satisfaction system with the entailment relation given by the standard semantics of ℒ [11]. Theorem 5. Λ( ℒ) is neither eviction-compatible nor reception-compatible.

Theorem 6 establishes the connection between quasimodels [11] and formulae in ℒ. Theorem 6 (Theorem 2.27 [11]). An ℒ-formula is satisfiable if has a quasimodel.

One can associate a model ℐ to each quasimodel for such that ℐ |= . The class of ℒ-formulae induced by is the class of ℒ-formulae that contains and any ℒ-formulae that is a boolean combination of atoms in .

Theorem 7. Consider the compartment (B , I ) where I is the class of models ℐ with a quasimodel for an ℒ-formula and B is the class of ℒ-formulae induced by . Then, the compartment (B , I ) is both eviction and reception-compatible.

Acknowledgments

The second author is supported by the NFR project “Learning Description Logic Ontologies”, grant number 316022. The third author is supported by the German Research Association (DFG), project number 465447331. 1ℒ is also called ℒ-formula in [11], the former nomenclature facilitates the distinction between the logic and its formulae.

References

[1] C. E. Alchourrón , P. Gärdenfors , D. Makinson , On the Logic of Theory Change: Partial Meet Contraction and Revision Functions , Journal of Symbolic Logic 50 ( 1985 ) 510 - 530 .

[2] H. Katsuno , A. O. Mendelzon , Propositional knowledge base revision and minimal change , Artificial Intelligence 52 ( 1991 ) 263 - 294 .

[3] L. De Raedt , Logical settings for concept-learning , Artificial Intelligence 95 ( 1997 ) 187 - 201 .

[4] R. Guimarães , A. Ozaki , J. S. Ribeiro , Finite based contraction and expansion via models , in: AAAI , 2023 .