Eviction and Reception for Description Logic Concepts (Extended Abstract) Ana Ozaki1,2 , Jandson S. Ribeiro3 1 University of Oslo, Norway 2 University of Bergen, Norway 3 Cardiff University, United Kingdom Abstract We study belief change for the case in which beliefs are expressed as concepts in description logic. We consider that the incoming information is in the format of a set of pointed interpretations and investigate eviction (removal of pointed models) and reception (addition of pointed models). We provide preliminary results in this setting, establishing whether β„°β„’βŠ₯ and π’œβ„’π’ž-concepts are eviction/reception compatible. 1. Introduction In Belief Change[1, 2, 3], when confronted with a piece of information, an agent must modify its beliefs minimally: only beliefs in conflict with the incoming information can be removed. The principle of minimal change is conceptualised via sets of rationality postulates, whilst several classes of operators that abide by such postulates were proposed. The standard paradigms of belief change, such as the AGM paradigm[1] of belief revision and the KM paradigm[4] of belief update, assume the incoming information to be represented as formulae. In other areas, however, different forms of representing incoming information, such as sets of finite models, have been addressed. In the learning from interpretations setting [5], for example, the goal is to identify a concept that is satisfied by a given set of interpretations, classified as positive, while falsified by another given set of interpretations (classified as negative). Ideally, the concept should also follow the principle of minimal change, in the sense that the identified concept should be as close as possible to the set of positive interpretations. Guimaraes et al. [6] have generalised the belief change paradigm to the setting where the incoming information is expressed as a set of interpretations, while the new corpus of beliefs should be finitely representable. Two main operations were proposed: eviction, which consists in removing the given set of interpretations; and reception, which consists in accommodating the given set of interpretations. Keeping the principle of minimal change and finite representation in this setting is challenging, and the authors have identified that eviction and reception are not definable in some logics. In this work, we deepen this investigation and consider concepts expressed in the β„°β„’βŠ₯ and π’œβ„’π’ž description logics (DLs). We show that while eviction is definable in β„°β„’βŠ₯ , reception is not definable in β„°β„’βŠ₯ nor π’œβ„’π’ž. 2. Eviction and Reception Following [7, 8], and [9], we use satisfaction systems to define logics. A satisfaction system is a triple Ξ› = (β„’, M, |=), where β„’ is a language, M is a set of models, and |= is a satisfaction relation which contains all pairs (𝑀, ℬ), where 𝑀 is a model and ℬ is a base (that is, a subset of β„’), such that 𝑀 satisfies ℬ (i.e., 𝑀 |= ℬ). We denote by modΞ› (ℬ) the set {𝑀 ∈ M | 𝑀 |= ℬ}. We write simply mod(ℬ) when the satisfaction system is clear from the context. Satisfaction systems allow us to be more flexible and precise regarding the precise scope of the operations and constructions we define. DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway $ anaoz@uio.no (A. Ozaki); ribeiroj@cardiff.ac.uk (J. S. Ribeiro) Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings This view also facilitates the generalisation of some results that do not depend on properties of the consequence relation of the logic. The power set of a set 𝐴 is denoted by 𝒫(𝐴), while the set of all finite subsets of 𝐴 is denoted by 𝒫 f (𝐴). We write 𝒫 * (𝐴) to denote the non-empty subsets of 𝐴. An arbitrary set of models M βŠ† M within Ξ› is finitely representable iff there is ℬ ∈ 𝒫 f (β„’) such that mod(ℬ) = M. FR(Ξ›) denotes the collection of all finitely representable sets of models in Ξ›, that is, the set {M βŠ† M | βˆƒβ„¬ ∈ 𝒫 f (β„’) : mod(ℬ) = M}. Also, we say that a set of formulae ℬ βŠ† β„’ is finitely representable iff there is a ℬ β€² ∈ 𝒫 f (β„’) with mod(ℬ) = mod(ℬ β€² ). Eviction turns the current belief state into a new one not satisfied by any of the input models. Reception turns the current belief state into a new one satisfied by all the input models. Definition 1. For all satisfaction systems Ξ› = (β„’, M, |=) and M βŠ† M, β€²β€² β€²β€² MaxFRSubs(M, Ξ›) := {Mβ€² ∈ FR(Ξ›) | Mβ€² βŠ† M and ΜΈ βˆƒM ∈ FR(Ξ›) with Mβ€² βŠ‚ M βŠ† M}. β€²β€² β€²β€² MinFRSups(M, Ξ›) := {Mβ€² ∈ FR(Ξ›) | M βŠ† Mβ€² and ΜΈ βˆƒM ∈ FR(Ξ›) with M βŠ† M βŠ‚ Mβ€² }. Definition 2. An eviction operation for a satisfaction system Ξ› = (β„’, M, |=) is a function evc : 𝒫 f (β„’)×𝒫(M) β†’ 𝒫 f (β„’) that satisfies the following postulates, for all M, Mβ€² βŠ† M and for all ℬ ∈ 𝒫 f (β„’): (success) M ∩ mod(evc(ℬ, M)) = βˆ…. (inclusion) mod(evc(ℬ, M)) βŠ† mod(ℬ). (finite retainment) If mod(evc(ℬ, M)) βŠ‚ Mβ€² βŠ† mod(ℬ) βˆ– M then Mβ€² ̸∈ FR(Ξ›). (uniformity) MaxFRSubs(mod(ℬ) βˆ– M, Ξ›) = MaxFRSubs(mod(ℬ β€² ) βˆ– Mβ€² , Ξ›) implies mod(evc(ℬ, M)) = mod(evc(ℬ β€² , Mβ€² )). Definition 3. A reception operation for a satisfaction system Ξ› = (β„’, M, |=) is a function rcp : 𝒫 f (β„’)×𝒫(M) β†’ 𝒫 f (β„’) that satisfies the following postulates, for all M, Mβ€² βŠ† M and for all ℬ ∈ 𝒫 f (β„’): (success) M βŠ† mod(rcp(ℬ, M)). (persistence) mod(ℬ) βŠ† mod(rcp(ℬ, M)). (finite temperance) If mod(ℬ) βˆͺ M βŠ† Mβ€² βŠ‚ mod(rcp(ℬ, M)) then Mβ€² ̸∈ FR(Ξ›). (uniformity) MinFRSups(mod(ℬ) βˆͺ M, Ξ›) = MinFRSups(mod(ℬ β€² ) βˆͺ Mβ€² , Ξ›) implies mod(rcp(ℬ, M)) = mod(rcp(ℬ β€² , Mβ€² )). For a discussion on the postulates presented in this section, see [6]. Neither reception nor eviction are definable in every logic. Eviction can only be defined in logics where MaxFRSubs(M, Ξ›) ΜΈ= βˆ…, for all sets of models M, whilst reception can only be defined in logics where MinFRSups(M, Ξ›) ΜΈ= βˆ…, for all sets of models M. Such logics are called respectively eviction-compatible and reception-compatible. Incompatibility is a problem inherent in belief change, and even when the incoming information is represented as formulae, some belief change operators, such as contraction[1], cannot be defined in some logics [10, 11, 12]. 3. Description Logic Concepts: Eviction and Reception In this section we establish preliminary results on eviction and reception compatibility for DL concepts. In particular, we show that β„°β„’βŠ₯ is eviction-compatible (Theorem 2). DL Concepts Let NC and NR be countably infinite and pairwise disjoint sets of concept names and role names, respectively. β„°β„’-concepts are built according to the rule: 𝐢, 𝐷 ::= ⊀ | 𝐴 | (𝐢 βŠ“ 𝐷) | (βˆƒπ‘Ÿ.𝐢), where 𝐴 ∈ NC and π‘Ÿ ∈ NR . β„°β„’βŠ₯ -concepts extend β„°β„’ by allowing βŠ₯ (interpreted as the empty set). π’œβ„’π’ž-concepts extend β„°β„’-concepts with the rule ¬𝐢 (recall that 𝐢 βŠ“ ¬𝐢 is equivalent to βŠ₯, so π’œβ„’π’ž extends β„°β„’βŠ₯ ). We may omit parentheses if there is no risk of confusion. A pointed interpretation is a pair (ℐ, 𝑑) where ℐ = (·ℐ , βˆ†β„ ) is an interpretation and 𝑑 ∈ βˆ†β„ . A pointed interpretation (ℐ, 𝑑) satisfies a concept 𝐢 iff 𝑑 ∈ 𝐢 ℐ . The semantics of β„°β„’, β„°β„’βŠ₯ , and π’œβ„’π’ž is defined using interpretations, as usual for DLs [13, 14]. Canonical Model Given a satisfiable β„°β„’βŠ₯ -concept 𝐷, we inductively define the tree-shaped interpre- tation ℐ𝐷 of 𝐷, with the root denoted 𝑑𝐷 , as follows. When 𝐷 is ⊀, we define β„βŠ€ as the interpretation with βˆ†β„βŠ€ := {π‘‘βŠ€ } and all concept and role names interpreted as the empty set. For 𝐷 a concept name 𝐴 ∈ NC we define ℐ𝐴 as the interpretation with βˆ†β„π΄ := {𝑑𝐴 }, 𝐴ℐ𝐴 := {𝑑𝐴 }, and all other concept and role names interpreted as the empty set. For 𝐷 = βˆƒπ‘Ÿ.𝐢, we define ℐ𝐷 as the interpreta- tion with βˆ†β„π· := {𝑑𝐷 } βˆͺ βˆ†β„πΆ . All concept and role name interpretations are as for ℐ𝐢 and we add (𝑑𝐷 , 𝑑𝐢 ) to π‘Ÿβ„π· , and assume 𝑑𝐷 is fresh (i.e., it is not in βˆ†β„πΆ ). Finally, for 𝐷 = 𝐷1 βŠ“ 𝐷2 we define βˆ†β„π· := βˆ†β„π·1 βˆͺ (βˆ†β„π·2 βˆ– {𝑑𝐷2 }), assuming βˆ†β„π·1 and βˆ†β„π·2 are disjoint, and with all concept and role name interpretations as in ℐ𝐷1 and ℐ𝐷2 , except that we connect 𝑑𝐷1 with the elements of βˆ†β„π·2 in the same way as 𝑑𝐷2 is connected. In other words, we identify 𝑑𝐷1 with the root 𝑑𝐷2 of ℐ𝐷2 . Homomorphism Given two pointed interpretations (ℐ, 𝑑0 ), (π’₯ , 𝑒0 ), a homomorphism from (ℐ, 𝑑0 ) to (π’₯ , 𝑒0 ) is a function β„Ž : βˆ†β„ β†’ βˆ†π’₯ that satisfies: (i) β„Ž(𝑑0 ) = 𝑒0 ; (ii) for all 𝐴 ∈ NC , if 𝑑 ∈ 𝐴ℐ then β„Ž(𝑑) ∈ 𝐴π’₯ ; and (iii) for all π‘Ÿ ∈ NR , if (𝑑, 𝑑′ ) ∈ π‘Ÿβ„ then (β„Ž(𝑑), β„Ž(𝑑′ )) ∈ π‘Ÿπ’₯ . Our proof strategy for Theorem 2 is to invoke Theorem 1 (see [6]), which we recall here, together with the two technical lemmas below. Theorem 1 (Theorem 16[6]). A satisfaction system Ξ› is eviction-compatible iff for every M βŠ† M either (i) M ∈ FR(Ξ›), (ii) M has an immediate predecessor in (FR(Ξ›) βˆͺ {M}, βŠ‚), or (iii) there is no Mβ€² ∈ FR(Ξ›) with M βŠ† Mβ€² . [Adapted [15]] For all satisfiable β„°β„’βŠ₯ -concepts 𝐢 and 𝐷, we have that |= 𝐢 βŠ‘ 𝐷 iff there is a homomorphism from (ℐ𝐷 , 𝑑𝐷 ) to (ℐ𝐢 , 𝑑𝐢 ). For all satisfiable β„°β„’βŠ₯ -concepts 𝐢, if 𝐢 is satisfiable then there is an β„°β„’βŠ₯ -concept 𝐢 β€² such that |= βŠ₯ ⊏ 𝐢 β€² ⊏ 𝐢. Let Ξ›(β„°β„’βŠ₯ -concepts) be the satisfaction system for β„°β„’βŠ₯ -concepts. Theorem 2. Ξ›(β„°β„’βŠ₯ -concepts) is eviction-compatible. Proof. We show that every non-empty M βŠ† M has an immediate predecessor in (FR(Ξ›(β„°β„’βŠ₯ -concepts)) βˆͺ {M}, βŠ‚) (the case M is empty is easy as β„°β„’βŠ₯ has the βŠ₯ concept). Recall that an immediate predecessor of M in this case is a set of models Mβ€² ∈ FR(Ξ›(β„°β„’βŠ₯ -concepts)) such that Mβ€² βŠ‚ M and there is no Mβ€²β€² such that Mβ€² βŠ‚ Mβ€²β€² βŠ‚ M. For this, we show that given a finitely representable set of models M, there is no infinite chain M1 βŠ‚ M2 βŠ‚ . . . of sets of models in (FR(Ξ›(β„°β„’βŠ₯ -concepts)) such that M𝑖 βŠ‚ M for all 𝑖 ∈ N. Indeed, given M, Mβ€² ∈ (FR(Ξ›(β„°β„’βŠ₯ -concepts)), with Mβ€² βŠ‚ M, let 𝐢, 𝐷 be β„°β„’βŠ₯ -concepts such that mod(𝐢) = M and mod(𝐷) = Mβ€² . By the semantics of β„°β„’βŠ₯ , we have that |= 𝐷 ⊏ 𝐢. We want to show that there are finitely many β„°β„’βŠ₯ -concepts 𝐸 such that |= 𝐷 ⊏ 𝐸 ⊏ 𝐢. Suppose there is no Mβ€² ∈ MaxFRSubs(Ξ›(β„°β„’βŠ₯ -concepts)) such that Mβ€² βŠ‚ M with Mβ€² ΜΈ= βˆ…. That is, βŠ₯ is the only β„°β„’βŠ₯ -concept such that |= βŠ₯ βŠ‘ 𝐢, or, in other words, there is no (satisfiable) β„°β„’βŠ₯ -concept 𝐢 β€² such that |= βŠ₯ ⊏ 𝐢 β€² ⊏ 𝐢. However, as Mβ€² βŠ‚ M, we have that M ΜΈ= βˆ…, so 𝐢 is satisfiable. This cannot be the case for β„°β„’βŠ₯ -concepts due to Section 3. By Section 3, if 𝐢 is satisfiable then there is 𝐢 β€² such that |= βŠ₯ ⊏ 𝐢 β€² ⊏ 𝐢. Then, there is Mβ€² ∈ (FR(Ξ›(β„°β„’βŠ₯ -concepts)) such that Mβ€² βŠ‚ M and Mβ€² ΜΈ= βˆ…, so 𝐷 is satisfiable. Let 𝐸 be an β„°β„’βŠ₯ -concept such that |= 𝐷 ⊏ 𝐸 ⊏ 𝐢 (if there is no such concept then we are done). Since |= 𝐷 ⊏ 𝐸 we have that 𝐸 is satisfiable. Then, by Lemma 3, there is a homomorphism from (ℐ𝐸 , 𝑑𝐸 ) to (ℐ𝐷 , 𝑑𝐷 ). As 𝐷 is finite, the number of concept and role names that occur in 𝐷 is finite. Denote with sig(𝐷) the set of concept and role names occurring 𝐷. Also, the existence of a homomorphism from (ℐ𝐸 , 𝑑𝐸 ) to (ℐ𝐷 , 𝑑𝐷 ) and the definition of ℐ𝐸 and ℐ𝐷 imply that the set of concept and role names occurring in 𝐸 is a subset of sig(𝐷). That is, there are finitely many concept and role names occurring in 𝐸 and they are subset of sig(𝐷). Moreover, by definition of ℐ𝐸 and ℐ𝐷 , these interpretations correspond to tree-shaped labelled structures where the depth of (the tree corresponding to) ℐ𝐸 is less or equal to the depth 𝑛 of ℐ𝐷 . Since 𝐸 was an arbitrary β„°β„’βŠ₯ -concept such that |= 𝐷 ⊏ 𝐸 this holds for all such concepts. As there are finitely many tree-shaped labelled structures with symbols in sig(𝐷) and depth bounded by 𝑛, there are finitely many β„°β„’βŠ₯ -concepts 𝐸 (up to logical equivalence) such that |= 𝐷 ⊏ 𝐸. Then there are finitely many β„°β„’βŠ₯ -concepts 𝐸 (up to logical equivalence) such that |= 𝐷 ⊏ 𝐸 βŠ‘ 𝐢. This means that, by Theorem 16 in [6], Ξ›(β„°β„’βŠ₯concepts ) is eviction-compatible. The previous result does not hold for β„°β„’ (without βŠ₯) as it cannot express inconsistencies [6]. Let Ξ›(π’œβ„’π’ž-concepts) be the satisfaction system for π’œβ„’π’ž-concepts. Theorem 3. Ξ›(β„°β„’βŠ₯ -concepts) and Ξ›(π’œβ„’π’ž-concepts) are not reception-compatible. The proof of Theorem 4 is based on [6]. Theorem 4. Ξ›(π’œβ„’π’ž-concepts) is not eviction-compatible. Acknowledgments Ana Ozaki is supported by the Research Council of Norway, project number 316022. This work is partly supported by the Research Council of Norway through its Centre of Excellence Integreat - The Norwegian Centre for knowledge-driven machine learning, project number 332645. 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] P. GΓ€rdenfors, Knowledge in flux: Modeling the dynamics of epistemic states., The MIT press, 1988. [3] S. O. Hansson, A Textbook of Belief Dynamics: Theory Change and Database Updating, Applied Logic Series, Kluwer Academic Publishers, 1999. [4] H. Katsuno, A. O. Mendelzon, On the difference between updating a knowledge base and revising it, in: P. GΓ€rdenfors (Ed.), Belief revision, Cambridge University Press, 1992, pp. 183–203. [5] L. D. Raedt, Logical settings for concept-learning, Artif. Intell. 95 (1997) 187–201. URL: https: //doi.org/10.1016/S0004-3702(97)00041-6. doi:10.1016/S0004-3702(97)00041-6. [6] R. GuimarΓ£es, A. Ozaki, J. S. Ribeiro, Finite based contraction and expansion via models, in: AAAI, 2023. [7] M. Aiguier, J. Atif, I. Bloch, C. Hudelot, Belief revision, minimal change and relaxation: A general framework based on satisfaction systems, and applications to description logics, Artificial Intelligence 256 (2018) 160–180. [8] J. P. Delgrande, P. Peppas, S. Woltran, General belief revision, J. ACM 65 (2018) 29:1–29:34. [9] R. GuimarΓ£es, A. Ozaki, J. S. Ribeiro, Finite based contraction and expansion via models, CoRR abs/2303.03034 (2023). [10] G. Flouris, On Belief Change and Ontology Evolution, Ph.D. thesis, University of Crete, 2006. [11] M. M. Ribeiro, R. Wassermann, G. Flouris, G. Antoniou, Minimal change: Relevance and recovery revisited, Artif. Intell. 201 (2013) 59–80. [12] J. S. Ribeiro, A. Nayak, R. Wassermann, Towards Belief Contraction without Compactness, in: KR 2018, AAAI Press, 2018, pp. 287–296. [13] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge University Press, 2017. [14] K. Agi, F. Wolter, M. Zakharyaschev, D. Gabbay, Many-dimensional modal logics : theory and applications, Elsevier North Holland, Amsterdam Boston, 2003. [15] F. Baader, R. KΓΌsters, R. Molitor, Computing least common subsumers in description logics with existential restrictions, in: T. Dean (Ed.), Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages, Morgan Kaufmann, 1999, pp. 96–103. URL: http://ijcai.org/Proceedings/99-1/ Papers/015.pdf.