Model Change for Description Logic Concepts

描述逻辑概念的模型变更

Ana Ozaki Affiliation:  University of Oslo, Norway Email:  ana.ozaki@uib.no    Jandson S. Ribeiro Affiliation:  Cardiff University, UK Email:  ribeiroj@cardiff.ac.uk

Abstract

摘要

We consider the problem of modifying a description logic concept in light of models represented as pointed interpretations. We call this setting model change, and distinguish three main kinds of changes: eviction, which consists of only removing models; reception, which incorporates models; and revision, which combines removal with incorporation of models in a single operation. We introduce a formal notion of revision and argue that it does not reduce to a simple combination of eviction and reception, contrary to intuition. We provide positive and negative results on the compatibility of eviction and reception for ${\cal E\!L}_{\bot}$ and ${\cal ALC}$ description logic concepts and on the compatibility of revision for ${\cal ALC}$ concepts.

我们考虑根据以点标解释（pointed interpretation）表示的模型来修改描述逻辑概念的问题。我们把这一设定称为模型变更（model change），并区分三种主要变更：驱逐（eviction）只移除模型；接收（reception）并入模型；修订（revision）在同一次操作中既移除又并入模型。我们引入修订的形式化概念，并论证——与直觉相反——它并不能还原成驱逐与接收的简单组合。我们给出 ${\cal E\!L}_{\bot}$ 与 ${\cal ALC}$ 描述逻辑概念上驱逐与接收相容性的正反结果，以及 ${\cal ALC}$ 概念上修订相容性的结果。

1 Introduction

1 引言

Keeping beliefs updated is a central problem in knowledge representation, that has been investigated in the context of different logics and applications. In the main streams of belief change research, the belief base is finite and the pieces of information expressing how to modify it are expressed as sets of formulae in the underlying logic (Hansson,, 1999; Gärdenfors,, 1988; Alchourrón et al.,, 1985).

保持信念更新是知识表示中的一个核心问题，已在不同逻辑和应用中得到研究。在信念变更研究的主要脉络里，信念库是有限的，而表达如何修改它的信息，则以底层逻辑中的公式集合给出 (Hansson,, 1999; Gärdenfors,, 1988; Alchourrón et al.,, 1985)。

In many scenarios, however, using sets of models to specify the observed change is more suitable than using formulae. This is well studied in the context of learning from interpretations (De Raedt,, 1997), where the goal is to find a concise formula that is consistent with models labelled as positive or negative. In the context of description logic (DL), the process of building an ontology usually goes through stages where the person creating it studies possible models of world, discarding models when they are proven false and adding new models previously not considered. The next examples illustrate model change operations for DL concepts.

不过，在许多场景里，用模型集合来刻画所观察到的变化，比用公式更合适。这一点在从解释中学习（learning from interpretations）的语境中已有充分研究 (De Raedt,, 1997)，其目标是找到一条简洁公式，与被标为正例或负例的模型相一致。在描述逻辑（DL）中，构建本体通常要经历若干阶段：创建者考察可能的世界模型，在模型被证伪时丢弃它们，并加入原先未考虑的新模型。下面的例子说明面向 DL 概念的模型变更操作。

Example 1.

Araci is visiting a zoo in Australia and knows little about Australian animals. She knows that a platypus is a mammal that lays eggs, her belief on platypus is

Example 1.

Araci 正在参观澳大利亚的一座动物园，对澳大利亚的动物所知不多。她知道鸭嘴兽是产卵的哺乳动物，她对鸭嘴兽的信念是

$$\displaystyle\mathsf{Platypus}\equiv\mathsf{Mammal}\sqcap(\exists\mathsf{lays.Egg}).$$

She sees a platypus ‘$d$’ but knows nothing about their diet. So, she entertains the two following possible worlds $(\mathcal{I}_{1},d)$ and $(\mathcal{I}_{2},d)$ with $\{d,e\}\subseteq\Delta^{\mathcal{I}_{1}}=\Delta^{\mathcal{I}_{2}}$:

她看见一只鸭嘴兽‘$d$’，但对它们的食性一无所知。于是她同时考虑下面两个可能世界 $(\mathcal{I}_{1},d)$ 和 $(\mathcal{I}_{2},d)$，其中 $\{d,e\}\subseteq\Delta^{\mathcal{I}_{1}}=\Delta^{\mathcal{I}_{2}}$：

$$\displaystyle\mathcal{I}{1}:\ \boxed{\begin{aligned} d\in&\ \mathsf{Mammal}^{\mathcal{I}{1}}\
d\not\in&\ \mathsf{Herbivore}^{\mathcal{I}{1}}\
(d,e)\in&\ \mathsf{lays}^{\mathcal{I}{1}}\
e\in&\ \mathsf{Egg}^{\mathcal{I}{1}}\
\end{aligned}}\hskip 8.61108pt\mathcal{I}{2}:\boxed{\begin{aligned} d\in&\ \mathsf{Mammal}^{\mathcal{I}{2}}\
d\in&\ \mathsf{Herbivore}^{\mathcal{I}{2}}\
(d,e)\in&\ \mathsf{lays}^{\mathcal{I}{2}}\
e\in&\ \mathsf{Egg}^{\mathcal{I}{2}}\
\end{aligned}}$$

She catches the platypus eating a small insect, which makes Araci retract the pointed interpretation $(\mathcal{I}_{2},d)$. So, she changes her conceptual beliefs about platypuses to

她看见这只鸭嘴兽在吃一只小昆虫，于是收回点标解释 $(\mathcal{I}_{2},d)$。因此，她把关于鸭嘴兽的概念信念改成

$$\displaystyle\mathsf{Platypus}\equiv\mathsf{Mammal}\sqcap(\exists\mathsf{lays.Egg})\sqcap\neg\mathsf{Herbivore}.$$

Ex. 1 illustrates the process of removing a model from the concept, producing a concept closer to the real world. This change operation is called eviction (Guimarães et al., 2023b, ), and should minimally modify the concept. The next example illustrates its dual: the process of adding a model, called reception.

例 1 说明了从概念中移除一个模型、从而得到更接近现实世界的概念的过程。这种变更操作称为驱逐（eviction） (Guimarães et al., 2023b, )，并且应当尽量少地修改该概念。下一个例子说明它的对偶：加入一个模型的过程，称为接收（reception）。

Example 2.

Araci knows that kangaroos and koalas are marsupials, but knows little about Tasmanian devils. So, her beliefs about marsupials are $\mathsf{Marsupial}\equiv\mathsf{Koala}\sqcup\mathsf{Kangaroo}.$ In the Tasmanian devils section, she sees a devil ‘$d^{\prime}$’ and reads a sign with the information that tasmanian devils are marsupials. So, she now admits a world $(\mathcal{I}_{3},d^{\prime})$ where

Example 2.

Araci 知道袋鼠和考拉都是有袋动物，但对袋獾所知不多。因此，她关于有袋动物的信念是 $\mathsf{Marsupial}\equiv\mathsf{Koala}\sqcup\mathsf{Kangaroo}.$ 在袋獾展区，她看见一只袋獾‘$d^{\prime}$’，并读到一块说明牌，写着 袋獾是有袋动物。于是她现在承认一个世界 $(\mathcal{I}_{3},d^{\prime})$，其中

$$\displaystyle\mathcal{I}_{3}:\boxed{\begin{aligned} d^{\prime}\in\mathsf{TasDevil}^{\mathcal{I}_{3}},\ d^{\prime}\in\mathsf{Carnivore}^{\mathcal{I}_{3}},\ d^{\prime}\in\mathsf{Marsupial}^{\mathcal{I}_{3}}\end{aligned}}$$

She changes her conceptual beliefs to comply with $(\mathcal{I}_{3},d^{\prime})$:

她修改自己的概念信念，使之符合 $(\mathcal{I}_{3},d^{\prime})$：

$$\displaystyle\mathsf{Marsupial} \\ \displaystyle\equiv\mathsf{Koala}\sqcup\mathsf{Kangaroo}\sqcup\mathsf{TasDevil}.$$

In both examples, Araci minimally modified her concepts. For platypus, she modified only concepts related to the diet, while for the Tasmanian devil, she modified only concepts related to marsupials and devils; no further changes relate to kangaroos or koalas were carried out. Ensuring minimal change in this setting is a challenge, as it is not always possible to retract or incorporate the single input model (Guimarães et al., 2023b, ). A third and more complex kind of operation is illustrated in Ex. 3, where one must add and remove models in a single step.

在这两个例子里，Araci 都只对概念做了最小修改。对鸭嘴兽，她只改了与食性相关的概念；对袋獾，她只改了与有袋动物和袋獾相关的概念，并没有对袋鼠或考拉做进一步改动。在这一设定中保证最小变更是困难的，因为并不总能只收回或只并入那一个输入模型 (Guimarães et al., 2023b, )。第三种、也更复杂的操作见例 3：必须在同一步里既加入又移除模型。

Example 3.

Araci believes that koalas are marsupial mammals that are not placental. So her concept on koalas is:

Example 3.

Araci 相信考拉是有袋的哺乳动物，而且不是有胎盘动物。因此她关于考拉的概念是：

$$\mathsf{Koala}\equiv\mathsf{Mammal}\sqcap\mathsf{Marsupial}\sqcap\neg\mathsf{Placental}.$$

She sees a koala ‘$d^{\prime\prime}$’ in the zoo, so she considers $(\mathcal{I}_{4},d^{\prime\prime})$ possible, but not $(\mathcal{I}_{5},d^{\prime\prime})$.

她在动物园里看见一只考拉‘$d^{\prime\prime}$’，于是认为 $(\mathcal{I}_{4},d^{\prime\prime})$ 是可能的，而 $(\mathcal{I}_{5},d^{\prime\prime})$ 不是。

$$\displaystyle\mathcal{I}{4}:\boxed{\begin{aligned} d^{\prime\prime}\in&\ \mathsf{Mammal}^{\mathcal{I}{4}}\
d^{\prime\prime}\in&\ \mathsf{Marsupial}^{\mathcal{I}{4}}\
d^{\prime\prime}\notin&\ \mathsf{Placental}^{\mathcal{I}{4}}\end{aligned}}\hskip 8.61108pt\mathcal{I}{5}:\boxed{\begin{aligned} d^{\prime\prime}\in&\ \mathsf{Mammal}^{\mathcal{I}{5}}\
d^{\prime\prime}\in&\ \mathsf{Marsupial}^{\mathcal{I}{5}}\
d^{\prime\prime}\in&\ \mathsf{Placental}^{\mathcal{I}{5}}\end{aligned}}$$

She reads a sign informing that koalas are actually placental. So she is compelled to comply with $(\mathcal{I}_{5},d^{\prime\prime})$, whereas retracting $(\mathcal{I}_{4},d^{\prime\prime})$. Therefore, she changes her belief to

她读到一块说明牌，写着考拉其实是有胎盘动物。于是她必须接受 $(\mathcal{I}_{5},d^{\prime\prime})$，同时收回 $(\mathcal{I}_{4},d^{\prime\prime})$。因此，她把信念改成

$$\mathsf{Koala}\equiv\mathsf{Mammal}\sqcap\mathsf{Marsupial}\sqcap\mathsf{Placental}.$$

In Ex. 3, the model $(\mathcal{I}_{4},d^{\prime\prime})$ had to be removed, while $(\mathcal{I}_{5},d^{\prime\prime})$ is added. We call this more complex operation a revision. After providing preliminaries (Sec. 2) and recalling eviction and reception (Sec. 3), we present our main contributions, which are:

在例 3 中，模型 $(\mathcal{I}_{4},d^{\prime\prime})$ 必须被移除，同时加入 $(\mathcal{I}_{5},d^{\prime\prime})$。我们把这种更复杂的操作称为修订（revision）。在给出预备知识（第 2 节）并回顾驱逐与接收（第 3 节）之后，我们给出主要贡献，分别是：

• • a theoretical study on eviction and reception for DL concepts in ${\cal ALC}$ and ${\cal E\!L}_{\bot}$ (Sec. 4); and

• • 对 ${\cal ALC}$ 与 ${\cal E\!L}_{\bot}$ 中 DL 概念的驱逐与接收做理论研究（第 4 节）；以及

• • the introduction of the notion of model revision (Sec. 5), with some results for DL concepts (Sec. 6).

• • 引入模型修订的概念（第 5 节），并给出一些针对 DL 概念的结果（第 6 节）。

Contrary to intuition, revision does not correspond to a serial combination of eviction and reception, as we show in this paper. In general, it may well be impossible to add and remove exactly and only the models of the input.

与直觉相反，修订并不对应于驱逐与接收的串行组合，我们将在本文中证明这一点。一般而言，恰好只加入并只移除输入中的那些模型，完全可能做不到。

Related Work Our contribution is closest to the work by Guimarães et al., 2023b (), with the main differences being that they neither consider revision nor DL concepts. Although their results on eviction and reception of DL ontologies inspired some of our proofs, the settings are considerably different, with the DL concept case that we present here being arguably more natural to the process of modelling concepts, which is fundamental for building ontologies. In this line, there has been work on computing least common subsumers, which generalize a set of concepts with minimal change Baader et al., (2007). Recent work considered learnability of DL concept expressions with pointed interpretations labelled as positive and negative (ten Cate et al.,, 2024). One can see the positive and negative pointed interpretations in their work as the sets of models to be added and removed in our setting. The difference from their work to ours is that here we focus on the existence of operators following minimal change rationality postulates, while they focus on the existence of sets of labelled models that characterize a DL concept, that is, that can be used to distinguish a particular concept from all the others in a DL language for concepts. Ontology learning from interpretations has been investigated by Klarman and Britz, (2015). Other works investigated learnability of DL concepts in a data retrieval setting (Funk et al.,, 2021; Funk et al.,, 2019), using inductive logic programming (Lehmann,, 2009; Fanizzi et al.,, 2008; Lehmann and Haase,, 2009; Lehmann and Hitzler,, 2010), and with counterfactuals (Iannone et al.,, 2007). We also point out works relating learning, epistemic logic, and belief revision  (Baltag et al., 2019b, ; Baltag et al., 2019a, ; Ozaki and Troquard,, 2019; Schwind et al.,, 2025).

相关工作 我们的贡献与 Guimarães et al., 2023b () 的工作最为接近，主要差别在于他们既不考虑修订，也不考虑 DL 概念。尽管他们关于 DL 本体驱逐与接收的结果启发了我们的部分证明，但设定有相当大的不同；我们在此给出的 DL 概念情形，对概念建模过程而言 可以说更为自然，而概念建模又是构建本体的基础。沿这条线索，已有工作研究最具体公共上界的计算，它以最小变更来概括一组概念 Baader et al., (2007)。近期工作考虑了用标为正例和负例的点标解释来学习 DL 概念表达式的可学习性 (ten Cate et al.,, 2024)。可以把他们工作中的正、负点标解释，看成我们设定里要加入和要移除的模型集合。他们的工作与我们的差别在于：我们关注是否存在遵循最小变更合理性公设的算子，而他们关注是否存在能够刻画某个 DL 概念的带标签模型集合，也就是能够把某一概念与该 DL 概念语言中所有其他概念区分开来。Klarman and Britz, (2015) 研究了从解释中学习本体。另有工作在数据检索设定中研究 DL 概念的可学习性 (Funk et al.,, 2021; Funk et al.,, 2019)，使用归纳逻辑程序设计 (Lehmann,, 2009; Fanizzi et al.,, 2008; Lehmann and Haase,, 2009; Lehmann and Hitzler,, 2010)，以及使用反事实 (Iannone et al.,, 2007)。我们还指出把学习、认知逻辑和信念修订联系起来的工作  (Baltag et al., 2019b, ; Baltag et al., 2019a, ; Ozaki and Troquard,, 2019; Schwind et al.,, 2025)。

2 Preliminaries

2 预备知识

The power set of a set $A$ is denoted by $\powerset(A)$, while the set of all finite subsets of $A$ is denoted by $\operatorname{\powerset_{f}}(A)$. Given a pre-order $\mathbin{\leqslant}\mathbin{\subseteq}\mathcal{D}\times\mathcal{D}$ on a domain $\mathcal{D}$, and a set $A\subseteq\mathcal{D},$ the set of all maximal and minimal elements of $A$ w.r.t. $\leqslant$ are respectively $\mathsf{max}_{\leqslant}(A)=\{x\in A\mid\mbox{ for all }y\in A\mbox{ if }x\leqslant y,\mbox{ then }y\leqslant x\}$, and $\mathsf{min}_{\leqslant}(A)=\{x\in A\mid\mbox{ for all }y\in A\mbox{ if }y\leqslant x,\mbox{ then }x\leqslant y\}$. We write $\operatorname{\powerset^{\ast}}(A)$ to denote the non-empty subsets of $A$. Following Aiguier et al., (2018); Delgrande et al., (2018), and Guimarães et al., 2023b (), we use satisfaction systems to define logics. A satisfaction system is a triple ${\Lambda}=(\mathcal{L},\mathfrak{M},\models)$, where $\mathcal{L}$ is a non-empty (possibly countably infinite) language , $\mathfrak{M}$ is a set of models, and $\models\subseteq\mathfrak{M}\times\powerset(\mathcal{L})$ is a relation, called the satisfaction relation, which relates models to subsets of the language. We use the infix notation $M\models{\mathcal{B}}$ as a shorthand for $(M,{\mathcal{B}})\in\ \models$ and say that $M$ satisfies ${\mathcal{B}}$. Every subset of $\mathcal{L}$ is called a base (which can be finite or infinite), denoted ${\mathcal{B}}$. We denote by $\mathsf{mod}_{{{\Lambda}}}({{\mathcal{B}}})$ the set $\{M\in\mathfrak{M}\mid M\models{\mathcal{B}}\}.$ We write $\mathsf{mod}({{\mathcal{B}}})$ when the satisfaction system is clear from the context.

集合 $A$ 的幂集记为 $\powerset(A)$，其全部有限子集组成的集合记为 $\operatorname{\powerset_{f}}(A)$。给定域 $\mathcal{D}$ 上的一个预序 $\mathbin{\leqslant}\mathbin{\subseteq}\mathcal{D}\times\mathcal{D}$，以及集合 $A\subseteq\mathcal{D}$，则 $A$ 中关于 $\leqslant$ 的全部极大元与全部极小元分别是 $\mathsf{max}_{\leqslant}(A)=\{x\in A\mid\mbox{ for all }y\in A\mbox{ if }x\leqslant y,\mbox{ then }y\leqslant x\}$，以及 $\mathsf{min}_{\leqslant}(A)=\{x\in A\mid\mbox{ for all }y\in A\mbox{ if }y\leqslant x,\mbox{ then }x\leqslant y\}$。我们写 $\operatorname{\powerset^{\ast}}(A)$ 表示 $A$ 的非空子集。沿用 Aiguier et al., (2018); Delgrande et al., (2018) 以及 Guimarães et al., 2023b ()，我们用满足系统来定义逻辑。一个满足系统（satisfaction system）是一个三元组 ${\Lambda}=(\mathcal{L},\mathfrak{M},\models)$，其中 $\mathcal{L}$ 是非空的（可以可数无限的）语言，$\mathfrak{M}$ 是模型集合，而 $\models\subseteq\mathfrak{M}\times\powerset(\mathcal{L})$ 是一种称为满足关系的关系，把模型与语言的子集联系起来。我们用中缀记号 $M\models{\mathcal{B}}$ 作为 $(M,{\mathcal{B}})\in\ \models$ 的简写，并说 $M$满足 ${\mathcal{B}}$。$\mathcal{L}$ 的每个子集都称为一个库（base，可以有限或无限），记为 ${\mathcal{B}}$。我们把 $\mathsf{mod}_{{{\Lambda}}}({{\mathcal{B}}})$ 记为集合 $\{M\in\mathfrak{M}\mid M\models{\mathcal{B}}\}$。当满足系统可从上下文看出时，我们写 $\mathsf{mod}({{\mathcal{B}}})$。

Satisfaction systems facilitate the generalisation of some results that do not depend on certain properties of the consequence relation of the logic. A set of models $\mathbb{M}\subseteq\mathfrak{M}$ within ${\Lambda}$ is finitely representable iff there is ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$ such that $\mathsf{mod}({{\mathcal{B}}})=\mathbb{M}$. Let ${{\operatorname{FR}}}({\Lambda})$ denote all finitely representable sets of models in ${\Lambda}$, i.e.,

满足系统便于把一些并不依赖于该逻辑后承关系某些性质的结果加以一般化。在 ${\Lambda}$ 中，模型集合 $\mathbb{M}\subseteq\mathfrak{M}$ 是有限可表示的，当且仅当存在 ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$ 使得 $\mathsf{mod}({{\mathcal{B}}})=\mathbb{M}$。令 ${{\operatorname{FR}}}({\Lambda})$ 表示 ${\Lambda}$ 中所有有限可表示的模型集合，即

$${{\operatorname{FR}}}({\Lambda})=\{\mathbb{M}\subseteq\mathfrak{M}\mid\exists{\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L}):\mathsf{mod}({{\mathcal{B}}})=\mathbb{M}\}.$$

Given a set $\mathbb{M}$ of models, the greatest finitely-representable subsets of $\mathbb{M}$ and the least finitely-representable supersets of $\mathbb{M}$ are given respectively by

给定模型集合 $\mathbb{M}$，$\mathbb{M}$ 的最大有限可表示子集以及 $\mathbb{M}$ 的最小有限可表示超集分别由下式给出

$$\displaystyle{\operatorname{MaxFRSubs}}(\mathbb{M},{\Lambda}) \\ \displaystyle=\mathsf{max}_{\subseteq}(\{\mathbb{M}^{\prime}\in{{\operatorname{FR}}}({\Lambda})\mid\mathbb{M}^{\prime}\subseteq\mathbb{M}\}), \\ \displaystyle{\operatorname{MinFRSups}}(\mathbb{M},{\Lambda}) \\ \displaystyle=\mathsf{min}_{\subseteq}(\{\mathbb{M}^{\prime}\in{{\operatorname{FR}}}({\Lambda})\mid\mathbb{M}\subseteq\mathbb{M}^{\prime}\}).$$

We say that a set of formulae ${\mathcal{B}}\subseteq\mathcal{L}$ is finitely representable iff there is ${\mathcal{B}}^{\prime}\in\operatorname{\powerset_{f}}(\mathcal{L})$ with $\mathsf{mod}({{\mathcal{B}}})=\mathsf{mod}({{\mathcal{B}}^{\prime}})$. We write $\times$ for the Cartesian product of two sets. Also, we denote the logical closure of a base in a satisfaction system ${\Lambda}$ by ${\operatorname{Cn}}_{\Lambda}$, omitting the subscript when clear from the context.

我们称公式集合 ${\mathcal{B}}\subseteq\mathcal{L}$ 是有限可表示的，当且仅当存在 ${\mathcal{B}}^{\prime}\in\operatorname{\powerset_{f}}(\mathcal{L})$ 使得 $\mathsf{mod}({{\mathcal{B}}})=\mathsf{mod}({{\mathcal{B}}^{\prime}})$。我们用 $\times$ 表示两个集合的笛卡尔积。此外，我们把满足系统 ${\Lambda}$ 中一个库的逻辑闭包记为 ${\operatorname{Cn}}_{\Lambda}$，在上下文清楚时省略下标。

DL Concepts Let ${\sf N_{C}}$ and ${\sf N_{R}}$ be countable and pairwise disjoint sets of concept names and role names, respectively. In this work, ${\sf N_{C}}$ and ${\sf N_{R}}$ can be finite or infinite. We explicitly indicate when these sets, called signature, are finite (otherwise, they are assumed to be infinite). ${\cal E\!L}$ concepts are built according to the rule: $C,D::=\top\mid A\mid(C\sqcap D)\mid(\exists r.C)$, where $A\in{\sf N_{C}}$ and $r\in{\sf N_{R}}$. ${\cal E\!L}_{\bot}$ concepts extend ${\cal E\!L}$ by allowing $\bot$ (interpreted as the empty set). ${\cal ALC}$ concepts extend ${\cal E\!L}$ concepts with the rule $\neg C$ (recall that $C\sqcap\neg C$ is equivalent to $\bot$, so ${\cal ALC}$ extends ${\cal E\!L}_{\bot}$). We may write $\exists r^{n}.\top$, with $n\in\mathbb{N}$, as a shorthand for the nesting of $n$ existential quantifiers (that is, $\exists r^{n+1}.\top=\exists r.(\exists r^{n}.\top)$) and $\exists r^{0}.\top=\top$.

DL 概念 设 ${\sf N_{C}}$ 与 ${\sf N_{R}}$ 分别是概念名与角色名的可数且两两不交的集合。在本文中，${\sf N_{C}}$ 与 ${\sf N_{R}}$ 可以有限也可以无限。当这些称为签名的集合为有限时，我们会明确指出（否则假定它们是无限的）。${\cal E\!L}$ 概念按如下规则构造：$C,D::=\top\mid A\mid(C\sqcap D)\mid(\exists r.C)$，其中 $A\in{\sf N_{C}}$，$r\in{\sf N_{R}}$。${\cal E\!L}_{\bot}$ 概念在 ${\cal E\!L}$ 上允许 $\bot$（解释为空集）。${\cal ALC}$ 概念在 ${\cal E\!L}$ 概念上增加规则 $\neg C$（注意 $C\sqcap\neg C$ 等价于 $\bot$，因此 ${\cal ALC}$ 扩展了 ${\cal E\!L}_{\bot}$）。我们可以把 $\exists r^{n}.\top$（其中 $n\in\mathbb{N}$）作为 $n$ 层存在量词嵌套的简写（即 $\exists r^{n+1}.\top=\exists r.(\exists r^{n}.\top)$），并且 $\exists r^{0}.\top=\top$。

Semantics The semantics of ${\cal E\!L}$, ${\cal E\!L}_{\bot}$, and ${\cal ALC}$ concepts is defined using pointed interpretations (Baader et al.,, 2017; Agi et al.,, 2003). An interpretation $\mathcal{I}$ is a pair $(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$, where $\Delta^{\mathcal{I}}$ is a non-empty set, called the domain, and $\cdot^{\mathcal{I}}$ is a function that maps every $A\in{\sf N_{C}}$ to a subset of $\Delta^{\mathcal{I}}$ and every $r\in{\sf N_{R}}$ to a subset of $\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$. It is finite if $\Delta^{\mathcal{I}}$ is finite. A pointed interpretation is a pair $(\mathcal{I},d)$ where $\mathcal{I}=(\cdot^{\mathcal{I}},\Delta^{\mathcal{I}})$ is an interpretation and $d\in\Delta^{\mathcal{I}}$. A pointed interpretation $(\mathcal{I},d)$ satisfies a concept $C$ iff $d\in C^{\mathcal{I}}$. We define tree-shaped pointed interpretations using the notion of unfolding Dummett and Lemmon, (1959) (see also Konev et al., (2016)). We say that a concept $C$ entails a concept $D$ if for all pointed interpretations $(\mathcal{I},d)$ (over the signature), $d\in C^{\mathcal{I}}$ implies $d\in D^{\mathcal{I}}$. Two concepts $C,D$ are equivalent, written $C\equiv D$, iff $C$ entails $D$ and $D$ entails $C$. Given a fixed but arbitrary $r\in{\sf N_{R}}$, we define $M^{n}=(\mathbb{N},\cdot^{M^{n}})$ where $r^{M^{n}}=\{(i,i+1)\mid i\in\mathbb{N},0\leq i<n\}$ and similarly $M^{\infty}=(\mathbb{N},\cdot^{M^{\infty}})$ where $r^{M^{\infty}}=\{(i,i+1)\mid i\in\mathbb{N}\}.$

语义 ${\cal E\!L}$、${\cal E\!L}_{\bot}$ 和 ${\cal ALC}$ 概念的语义用点标解释来定义 (Baader et al.,, 2017; Agi et al.,, 2003)。一个解释 $\mathcal{I}$ 是一对 $(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$，其中 $\Delta^{\mathcal{I}}$ 是一个非空集合，称为论域，而 $\cdot^{\mathcal{I}}$ 是一个函数，把每个 $A\in{\sf N_{C}}$ 映射到 $\Delta^{\mathcal{I}}$ 的一个子集，并把每个 $r\in{\sf N_{R}}$ 映射到 $\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$ 的一个子集。若 $\Delta^{\mathcal{I}}$ 有限，则该解释是有限的。一个点标解释是一对 $(\mathcal{I},d)$，其中 $\mathcal{I}=(\cdot^{\mathcal{I}},\Delta^{\mathcal{I}})$ 是一个解释，且 $d\in\Delta^{\mathcal{I}}$。点标解释 $(\mathcal{I},d)$ 满足概念 $C$，当且仅当 $d\in C^{\mathcal{I}}$。我们用展开（unfolding）的概念来定义树形点标解释 Dummett and Lemmon, (1959)（亦见 Konev et al., (2016)）。我们说概念 $C$ 蕴涵概念 $D$，如果对所有（在该签名上的）点标解释 $(\mathcal{I},d)$，$d\in C^{\mathcal{I}}$ 都蕴涵 $d\in D^{\mathcal{I}}$。两个概念 $C,D$ 等价，记为 $C\equiv D$，当且仅当 $C$ 蕴涵 $D$ 且 $D$ 蕴涵 $C$。给定一个固定但任意的 $r\in{\sf N_{R}}$，我们定义 $M^{n}=(\mathbb{N},\cdot^{M^{n}})$，其中 $r^{M^{n}}=\{(i,i+1)\mid i\in\mathbb{N},0\leq i<n\}$；类似地，$M^{\infty}=(\mathbb{N},\cdot^{M^{\infty}})$，其中 $r^{M^{\infty}}=\{(i,i+1)\mid i\in\mathbb{N}\}.$

DL concepts in Satisfaction Systems In a satisfaction system, we use the term ‘base’ for a subset of formulas in a logic language. We treat a set of concepts and a concept formed by the conjunction of the elements of the set interchangeably. So we may refer to a base as a concept or as a finite set of concepts (in the latter, we mean the concept formed by the conjunction). The notion of a ‘model’ in a satisfaction system corresponds to the notion of a pointed interpretation.

满足系统中的 DL 概念 在满足系统中，我们用“库”一词表示逻辑语言中公式的一个子集。我们把一组概念，与由该组元素合取而成的概念互换使用。因此我们既可以把一个库称为一个概念，也可以把它称为一个有限的概念集合（后者指由合取形成的那个概念）。满足系统中的“模型”概念，对应于点标解释。

3 Model Reception and Eviction

3 模型接收与驱逐

This section addresses the problem of modifying a finite base in light of a set of models, as illustrated in Ex. 1 and Ex. 2. We call such kinds of operators model change operators. Guimarães et al., 2023b () distinguished two main primitive kinds of model change operators:

本节讨论根据一组模型来修改有限库的问题，如例 1 和例 2 所示。我们把这类算子称为模型变更算子。Guimarães et al., 2023b () 区分了两种主要的、作为原语的模型变更算子：

eviction: remove a set $\mathbb{M}$ of models from a base ${\mathcal{B}}$, that is, turn ${\mathcal{B}}$ into a base ${\mathcal{B}}^{\prime}$ whose models are not in $\mathbb{M}$;

驱逐：从库 ${\mathcal{B}}$ 中移除一组模型 $\mathbb{M}$，也就是把 ${\mathcal{B}}$ 变成一个其模型都不在 $\mathbb{M}$ 中的库 ${\mathcal{B}}^{\prime}$；

reception: incorporate all models from the set $\mathbb{M}$ into a base ${\mathcal{B}}$, that is, turn ${\mathcal{B}}$ into a base ${\mathcal{B}}^{\prime}$ such that all models in $\mathbb{M}$ satisfy ${\mathcal{B}}^{\prime}$.

接收：把集合 $\mathbb{M}$ 中的全部模型并入库 ${\mathcal{B}}$，也就是把 ${\mathcal{B}}$ 变成一个库 ${\mathcal{B}}^{\prime}$，使得 $\mathbb{M}$ 中的所有模型都满足 ${\mathcal{B}}^{\prime}$。

In some scenarios, not all sets of models need to be taken into account. For instance, some DLs have the finite model property or the tree-shaped property. So, it makes sense to also consider model change operators that only take into account such classes of models. Formally, a class of models on a satisfaction system ${\Lambda}=(\mathcal{L},\mathfrak{M},\models)$ is a set $\mathcal{C}\subseteq\powerset(\mathfrak{M})$ with sets of interpretations. Model change operators are, therefore, defined on a given class of models.

在某些场景中，并不需要考虑所有模型集合。例如，有些描述逻辑具有有限模型性质或树形性质。因此，也有理由考虑只处理这类模型类的模型变更算子。形式上，满足系统 ${\Lambda}=(\mathcal{L},\mathfrak{M},\models)$ 上的一个模型类，是一个由解释集合组成的集合 $\mathcal{C}\subseteq\powerset(\mathfrak{M})$。因此，模型变更算子是在给定的模型类上定义的。

Definition 4.

A model change operator in a class $\mathcal{C}$ of models is a function $\circ:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$, mapping each finite base ${\mathcal{B}}$ into a finite base ${\mathcal{B}}^{\prime}$ in light of a set of models.

Definition 4.

模型类 $\mathcal{C}$ 上的模型变更算子，是一个函数 $\circ:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$，它根据一组模型，把每个有限库 ${\mathcal{B}}$ 映射成一个有限库 ${\mathcal{B}}^{\prime}$。

For conciseness, we may omit the reference to the class $\mathcal{C}$ of models if $\mathcal{C}$ is clear from the context. The main challenge of model change operators is to guarantee the finiteness of the new base, which presents two main hurdles:

为简洁起见，若模型类 $\mathcal{C}$ 可从上下文看出，我们可省略对它的提及。模型变更算子的主要挑战是保证新库的有限性，这带来两个主要障碍：

1. some sets of models cannot be uniquely added/removed to/from some bases, as Ex. 5 below illustrates.

1. 有些模型集合不能被唯一地加入某些库或从某些库中唯一地移除，如下面的例 5 所示。

2. the simple addition/removal of a set of models might not be finitely representable. This occurs because the language of logic is not expressive enough to distinguish all the models in a set from those which are not in the set. This issue is illustrated at Ex. 6.

2. 简单地加入或移除一组模型，结果也可能不是有限可表示的。这是因为该逻辑的语言没有足够的表达力，把集合中的全部模型与不在该集合中的模型区分开来。这一问题在例 6 中说明。

Example 5.

Consider the ${\cal E\!L}$ concept $\exists r^{3}.\top$, with ${\sf N_{C}}=\emptyset$, ${\sf N_{R}}=\{r\}$, and the pointed models $(\mathcal{I}_{1},d_{1})$ and $(\mathcal{I}_{2},d_{1})$ with domains $\Delta^{\mathcal{I}_{1}}=\{d_{1},d_{2}\}$ and $\Delta^{\mathcal{I}_{2}}=\{d_{1},d_{2},d_{3}\}$, where

Example 5.

考虑 ${\cal E\!L}$ 概念 $\exists r^{3}.\top$，其中 ${\sf N_{C}}=\emptyset$，${\sf N_{R}}=\{r\}$，以及点标模型 $(\mathcal{I}_{1},d_{1})$ 和 $(\mathcal{I}_{2},d_{1})$，其论域为 $\Delta^{\mathcal{I}_{1}}=\{d_{1},d_{2}\}$ 和 $\Delta^{\mathcal{I}_{2}}=\{d_{1},d_{2},d_{3}\}$，其中

$$\displaystyle\mathcal{I}{1}:\boxed{\begin{aligned} r^{\mathcal{I}{1}}=&\ {(d_{1},d_{2})}\
\end{aligned}}\hskip 8.61108pt\mathcal{I}{2}:\boxed{\begin{aligned} r^{\mathcal{I}{2}}=&\ {(d_{1},d_{2}),(d_{2},d_{3})}\end{aligned}}$$

Neither $(\mathcal{I}_{1},d_{1})$ nor $(\mathcal{I}_{2},d_{1})$ are models of $\exists r^{3}.\top$. Suppose that we want to add $(\mathcal{I}_{1},d_{1})$ to the models of $\exists r^{3}.\top$. In ${\cal E\!L}_{\bot}$, however, every concept satisfied by $(\mathcal{I}_{1},d_{1})$ and $\mathsf{mod}({\exists r^{3}.\top})$ is also satisfied by $(\mathcal{I}_{2},d_{1})$. There is no concept separating $(\mathcal{I}_{2},d_{1})$ from $\mathsf{mod}({\exists r^{3}.\top})\cup\{(\mathcal{I}_{1},d_{1})\}$.

$(\mathcal{I}_{1},d_{1})$ 和 $(\mathcal{I}_{2},d_{1})$ 都不是 $\exists r^{3}.\top$ 的模型。假设我们想把 $(\mathcal{I}_{1},d_{1})$ 加入 $\exists r^{3}.\top$ 的模型之中。然而在 ${\cal E\!L}_{\bot}$ 中，凡被 $(\mathcal{I}_{1},d_{1})$ 和 $\mathsf{mod}({\exists r^{3}.\top})$ 满足的概念，也都被 $(\mathcal{I}_{2},d_{1})$ 满足。不存在一个概念能把 $(\mathcal{I}_{2},d_{1})$ 与 $\mathsf{mod}({\exists r^{3}.\top})\cup\{(\mathcal{I}_{1},d_{1})\}$ 分开。

Example 6.

Let ${\mathcal{B}}=\{\exists r.\top\}$ be an ${\cal E\!L}$ concept and let the signature be ${\sf N_{C}}=\{A\},{\sf N_{R}}=\{r\}$. We want to evict the pointed model $(\mathcal{I},d)$ with $\Delta^{\mathcal{I}}=\{d\}$, $r^{\mathcal{I}}=\{(d,d)\}$, and $A^{\mathcal{I}}=\emptyset$. We have that $(\mathcal{I},d)$ satisfies ${\mathcal{B}}$. The removal of $(\mathcal{I},d)$ from $\mathsf{mod}({{\mathcal{B}}})$ yields the base ${\mathcal{B}}^{\prime}=\{\exists r.A,\exists r^{2}.A,\cdots,\exists r^{n}.A,\cdots\}$, which is not finitely representable.

Example 6.

设 ${\mathcal{B}}=\{\exists r.\top\}$ 是一个 ${\cal E\!L}$ 概念，签名为 ${\sf N_{C}}=\{A\},{\sf N_{R}}=\{r\}$。我们想驱逐点标模型 $(\mathcal{I},d)$，其中 $\Delta^{\mathcal{I}}=\{d\}$，$r^{\mathcal{I}}=\{(d,d)\}$，且 $A^{\mathcal{I}}=\emptyset$。我们有 $(\mathcal{I},d)$ 满足 ${\mathcal{B}}$。把 $(\mathcal{I},d)$ 从 $\mathsf{mod}({{\mathcal{B}}})$ 中去掉，得到库 ${\mathcal{B}}^{\prime}=\{\exists r.A,\exists r^{2}.A,\cdots,\exists r^{n}.A,\cdots\}$，它不是有限可表示的。

On both cases 1 and 2, as illustrated respectively on Ex. 5 and Ex. 6, extra models must be added/removed to achieve a finite base. Such addition/removal should be minimised, so only models that do contribute to reaching finiteness are considered. In this case, a “closest” finite base is produced. Such minimality criteria are properly addressed in the form of rationality postulates. The appropriate class of all eviction/reception operators abiding by such postulates are identified.

在分别由例 5 和例 6 说明的情形 1 和情形 2 中，都必须额外加入或移除一些模型，才能得到有限库。这种加入或移除应当被最小化，从而只考虑那些对达到有限性有贡献的模型。此时会得到一个“最近的”有限库。这类最小性标准以合理性公设的形式加以表述，并据此识别出遵守这些公设的全部驱逐/接收算子所构成的适当类别。

We show that in several classes of models, the minimality principles cannot be guaranteed, which is due to the non-existence of a “closest” finite base, known as the compatibility problem (Guimarães et al., 2023b, ). We briefly review reception and eviction, respectively, on Sec. 3.1 and Sec. 3.2.

我们证明，在若干模型类中，最小性原则无法得到保证，原因是不存在“最近的”有限库，这就是所谓的相容性问题 (Guimarães et al., 2023b, )。我们分别在第 3.1 节和第 3.2 节简要回顾接收与驱逐。

3.1 Reception

3.1 接收

We denote belief change operators related to reception as ${{\operatorname{{\sf rcp}}}}$. Guimarães et al., 2023b () proposed the following rationality postulates to govern reception

我们把与接收相关的信念变更算子记为 ${{\operatorname{{\sf rcp}}}}$。Guimarães et al., 2023b () 提出了下列用于约束接收的合理性公设

$\mathbb{M}\subseteq\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})$

$\mathsf{mod}({{\mathcal{B}}})\subseteq\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})$

$\mathbb{M}^{\prime}\not\in{{\operatorname{FR}}}({\Lambda})$, if $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}\subseteq\mathbb{M}^{\prime}$ and $\mathbb{M}^{\prime}\subset\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})$

$\mathbb{M}^{\prime}\not\in{{\operatorname{FR}}}({\Lambda})$，若 $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}\subseteq\mathbb{M}^{\prime}$ 且 $\mathbb{M}^{\prime}\subset\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})$

$\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})=\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}}^{\prime},\mathbb{M}^{\prime})})$, if ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})={\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}^{\prime}})\cup\mathbb{M}^{\prime},{\Lambda})$ .

$\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}},\mathbb{M})})=\mathsf{mod}({{{\operatorname{{\sf rcp}}}}({\mathcal{B}}^{\prime},\mathbb{M}^{\prime})})$，若 ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})={\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}^{\prime}})\cup\mathbb{M}^{\prime},{\Lambda})$ 。

Success ensures that each model from $\mathbb{M}$ must be incorporated. The purpose of reception is to accommodate new models. Persistence ensures that no model is removed in the process. Finite temperance ensures that the addition of extra models is minimized, adding only models that contribute to reaching a finite base. Uniformity ensures that reception is neither syntax sensitive nor sensitive to model structure.

成功性（Success）保证 $\mathbb{M}$ 中的每个模型都必须被并入。接收的目的就是容纳新模型。持久性（Persistence）保证过程中不会移除任何模型。有限节制（Finite temperance）保证额外加入的模型被最小化，只加入那些对达到有限库有贡献的模型。一致性（Uniformity）保证接收既不对语法敏感，也不对模型结构敏感。

For instance, in Ex. 5, the pointed interpretation $(\mathcal{I}_{1},d_{1})$ cannot be separated from $(\mathcal{I}_{2},d_{1})$ in the presence of the models of ${\mathcal{B}}$, so reception, on ${\mathcal{B}}$, of the sets $\{(\mathcal{I}_{1},d_{1})\}$ and $\{(\mathcal{I}_{1},d_{1}),(\mathcal{I}_{2},d_{1})\}$ must coincide.

例如，在例 5 中，点标解释 $(\mathcal{I}_{1},d_{1})$ 在存在 ${\mathcal{B}}$ 的模型时无法与 $(\mathcal{I}_{2},d_{1})$ 分开，因此对 ${\mathcal{B}}$ 分别接收集合 $\{(\mathcal{I}_{1},d_{1})\}$ 与 $\{(\mathcal{I}_{1},d_{1}),(\mathcal{I}_{2},d_{1})\}$ 必须得到相同结果。

A reception operator on a class $\mathcal{C}$ of models is a model change operator ${{\operatorname{{\sf rcp}}}}:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$ that satisfies success. A reception operator satisfying all rationality postulates is called rational. When there is no finite base for $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}$, some further models must be added in favor of finiteness. Such extra removal must be minimized as finite-temperance demands. This corresponds to picking a least finitely representable superset of $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}$, that is, picking a set from ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})$. However, for some classes of models, such a least finitely representable superset does not exists, that is, ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})$ is empty. In such cases, therefore, finite-temperance cannot be satisfied, which implies in the inexistence of rational reception operators. Classes of models in which such least finitely representable supersets exist are called reception-compatible.

模型类 $\mathcal{C}$ 上的接收算子，是满足成功性的模型变更算子 ${{\operatorname{{\sf rcp}}}}:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$。满足全部合理性公设的接收算子称为合理的。当 $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}$ 没有有限库时，必须为了有限性再加入一些模型。这些额外加入必须按有限节制的要求尽量少。这对应于选取 $\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M}$ 的一个最小有限可表示超集，也就是从 ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})$ 中取一个集合。然而，对某些模型类，这样的最小有限可表示超集并不存在，也就是 ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})$ 为空。因此在这些情形下，有限节制无法被满足，这意味着不存在合理的接收算子。存在这类最小有限可表示超集的模型类，称为接收相容的。

Definition 7.

A class $\mathcal{C}$ of models on a satisfaction system ${\Lambda}$, is reception-compatible iff for all $\mathbb{M}\in\mathcal{C}$ and base ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$, ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})\neq\emptyset$.

Definition 7.

满足系统 ${\Lambda}$ 上的模型类 $\mathcal{C}$ 是接收相容的，当且仅当对所有 $\mathbb{M}\in\mathcal{C}$ 以及库 ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$，都有 ${\operatorname{MinFRSups}}(\mathsf{mod}({{\mathcal{B}}})\cup\mathbb{M},{\Lambda})\neq\emptyset$。

Several classes of all models are not reception-compatible, as we show in Sec. 4. For instance, in the DL ${\cal E\!L}_{\bot}$, the class of all its models is not reception compatible, as Example 8 illustrates.

若干由全部模型组成的类并不是接收相容的，我们将在第 4 节证明。例如，在描述逻辑 ${\cal E\!L}_{\bot}$ 中，其全部模型构成的类不是接收相容的，如例 8 所示。

Example 8.

Consider the concept $\bot$ in ${\cal E\!L}_{\bot}$ and a signature with ${\sf N_{R}}=\{r\}$. Suppose $\mathbb{M}^{+}=\{(M^{\infty},0)\}$ (see def. in Sec. 2). We would like to include an interpretation pointed at an infinite chain but we are not asking the finite chains $M^{n}$ to be included. There is no ${\cal E\!L}_{\bot}$ concept that best represents adding this set to $\bot$. Given a concept $\exists r^{n}.\top$ one can always create another concept $\exists r^{n+1}.\top$ that includes $\mathbb{M}^{+}$ but has strictly less models: $\mathsf{mod}({\exists r.\top})\supset\mathsf{mod}({\exists r^{2}.\top})\supset\cdots\supset\mathsf{mod}({\exists r^{n}.\top})\supset\cdots$.

Example 8.

考虑 ${\cal E\!L}_{\bot}$ 中的概念 $\bot$，签名满足 ${\sf N_{R}}=\{r\}$。设 $\mathbb{M}^{+}=\{(M^{\infty},0)\}$（定义见第 2 节）。我们希望并入一个指向无限链的解释，但并不要求把有限链 $M^{n}$ 也并入。不存在一个能最好表示把该集合加入 $\bot$ 的 ${\cal E\!L}_{\bot}$ 概念。给定概念 $\exists r^{n}.\top$，总可以再构造另一个概念 $\exists r^{n+1}.\top$，它包含 $\mathbb{M}^{+}$，但模型严格更少：$\mathsf{mod}({\exists r.\top})\supset\mathsf{mod}({\exists r^{2}.\top})\supset\cdots\supset\mathsf{mod}({\exists r^{n}.\top})\supset\cdots$。

Example 9 illustrates a reception operation.

例 9 说明一次接收操作。

Example 9.

(continued from Ex. 5). Recall we want the reception of $\exists r^{3}.\top$ with $(\mathcal{I}_{1},d_{1})$. Both $\exists r^{2}.\top$ and $\exists r.\top$. are more general than $\exists r^{3}.\top$. From these, the closest that contains $(\mathcal{I}_{1},d_{1})$ is $\exists r.\top$. So, ${{\operatorname{{\sf rcp}}}}(\{\exists r^{3}.\top\},\{(\mathcal{I}_{1},d_{1})\})=\{\exists r.\top\}$.

Example 9.

（续自例 5）。回顾我们想对 $\exists r^{3}.\top$ 接收 $(\mathcal{I}_{1},d_{1})$。$\exists r^{2}.\top$ 与 $\exists r.\top$ 都比 $\exists r^{3}.\top$ 更一般。在这两者中，包含 $(\mathcal{I}_{1},d_{1})$ 且最近的是 $\exists r.\top$。因此，${{\operatorname{{\sf rcp}}}}(\{\exists r^{3}.\top\},\{(\mathcal{I}_{1},d_{1})\})=\{\exists r.\top\}$。

On reception-compatible classes of models, Guimarães et al., 2023b () have proposed the family of maxichoice reception operators, which chooses one finitely representable base from ${\operatorname{MinFRSups}}$. Maxichoice reception operators coincide with all rational reception operators.

在接收相容的模型类上，Guimarães et al., 2023b () 提出了极大选择（maxichoice）接收算子族，它从 ${\operatorname{MinFRSups}}$ 中选出一个有限可表示的库。极大选择接收算子与全部合理接收算子相一致。

3.2 Eviction

3.2 驱逐

Eviction operators, denoted by ${\operatorname{{\sf evc}}}$, are governed by the following postulates:

驱逐算子记为 ${\operatorname{{\sf evc}}}$，受下列公设约束：

$\mathbb{M}\cap\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})=\emptyset$.

$\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})\subseteq\mathsf{mod}({{\mathcal{B}}})$.

$\mathbb{M}^{\prime}\not\in{{\operatorname{FR}}}({\Lambda})$, if $\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})\subset\mathbb{M}^{\prime}$ and $\mathbb{M}^{\prime}\subseteq\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$.

$\mathbb{M}^{\prime}\not\in{{\operatorname{FR}}}({\Lambda})$，若 $\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})\subset\mathbb{M}^{\prime}$ 且 $\mathbb{M}^{\prime}\subseteq\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$.

$\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})=\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}}^{\prime},\mathbb{M}^{\prime})})$, if ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})={\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}^{\prime}})\setminus\mathbb{M}^{\prime},{\Lambda})$

$\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}},\mathbb{M})})=\mathsf{mod}({{{\operatorname{{\sf evc}}}}({\mathcal{B}}^{\prime},\mathbb{M}^{\prime})})$，若 ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})={\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}^{\prime}})\setminus\mathbb{M}^{\prime},{\Lambda})$

Success ensures that each model from $\mathbb{M}$ must be relinquished. As the purpose of eviction is to remove models, inclusion ensures that no models are added. Uniformity, as for reception, guarantees that eviction is neither syntax sensitive nor sensitive to model structure. Finite retainment ensures that the removal of extra models is minimized, retracting only models that contribute to reaching a finite base. An eviction operator on a class $\mathcal{C}$ of models is a model change operator ${{\operatorname{{\sf evc}}}}:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$ that satisfies success. An eviction operator satisfying all rationality postulates is called rational. In the best scenario, to evict a set of models $\mathbb{M}$ from a finite base ${\mathcal{B}}$, one would simply identify a base for the set $\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$. However, as not all sets of models are finitely representable, some further models must be minimally removed in favour of finiteness, as finite-retainment demands. This corresponds to picking a greatest finitely representable subset from $\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$, that is, picking a set from ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})$. This set, in general, is not a singleton, and a choice must be made among the most plausible candidates. The choice, as for reception, is realised by a choice function. Similarly to reception, depending on the underlying class $\mathcal{C}$ of models, ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})$ might be empty. In such a case, finite retainment cannot be satisfied, which means that in such classes rational eviction operators do not exist. Classes of models in which the greatest finitely representable subsets exist are called eviction-compatible.

成功性保证 $\mathbb{M}$ 中的每个模型都必须被放弃。由于驱逐的目的是移除模型，包含性（inclusion）保证不会加入新模型。与接收一样，一致性保证驱逐既不对语法敏感，也不对模型结构敏感。有限保留（Finite retainment）保证额外移除的模型被最小化，只收回那些对达到有限库有贡献的模型。模型类 $\mathcal{C}$ 上的驱逐算子，是满足成功性的模型变更算子 ${{\operatorname{{\sf evc}}}}:\operatorname{\powerset_{f}}(\mathcal{L})\times\mathcal{C}\to\operatorname{\powerset_{f}}(\mathcal{L})$。满足全部合理性公设的驱逐算子称为合理的。在最好的情形下，要从有限库 ${\mathcal{B}}$ 中驱逐模型集合 $\mathbb{M}$，只需为集合 $\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$ 找出一个库。然而，并非所有模型集合都是有限可表示的，因此必须按有限保留的要求，为了有限性再最小地移除一些模型。这对应于从 $\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M}$ 中选取一个最大的有限可表示子集，也就是从 ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})$ 中取一个集合。该集合一般不是单点集，必须在最合理的候选中做出选择。与接收一样，这一选择由选择函数实现。类似于接收，取决于底层模型类 $\mathcal{C}$，${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})$ 可能为空。在这种情形下，有限保留无法被满足，意味着在这类模型类中不存在合理的驱逐算子。存在最大有限可表示子集的模型类，称为驱逐相容的。

Definition 10.

A class $\mathcal{C}$ of models, on a satisfaction system ${\Lambda}$, is eviction-compatible iff for all $\mathbb{M}\in\mathcal{C}$ and base ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$, ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})\neq\emptyset$.

Definition 10.

满足系统 ${\Lambda}$ 上的模型类 $\mathcal{C}$ 是驱逐相容的，当且仅当对所有 $\mathbb{M}\in\mathcal{C}$ 以及库 ${\mathcal{B}}\in\operatorname{\powerset_{f}}(\mathcal{L})$，都有 ${\operatorname{MaxFRSubs}}(\mathsf{mod}({{\mathcal{B}}})\setminus\mathbb{M},{\Lambda})\neq\emptyset$。

On eviction-compatible classes of models, Guimarães et al., 2023b () have proposed the family of maxichoice eviction operators, which chooses one finitely representable base from ${{\operatorname{FR}}}$. Maxihoicde reception operators are characterised by all rationality postulates of reception.

在驱逐相容的模型类上，Guimarães et al., 2023b () 提出了极大选择驱逐算子族，它从 ${{\operatorname{FR}}}$ 中选出一个有限可表示的库。极大选择接收算子由接收的全部合理性公设所刻画。

4 Eviction and Reception: DL Concepts

4 驱逐与接收：DL 概念

Here we investigate eviction and reception on DL concepts, focusing on the prototypical DLs ${\cal ALC}$ and ${\cal E\!L}$. In the following, we denote by ${\Lambda}({\cal E\!L}_{\bot\text{concepts}})$ and ${\Lambda}({\cal ALC}_{\text{concepts}})$ the satisfaction systems for ${\cal E\!L}_{\bot}$ and ${\cal ALC}$ concepts with pointed interpretations as models. Table 1 summarises our results.

这里我们研究 DL 概念上的驱逐与接收，重点考察典型的描述逻辑 ${\cal ALC}$ 和 ${\cal E\!L}$。下面，我们把以点标解释为模型的 ${\cal E\!L}_{\bot}$ 与 ${\cal ALC}$ 概念的满足系统，分别记为 ${\Lambda}({\cal E\!L}_{\bot\text{concepts}})$ 和 ${\Lambda}({\cal ALC}_{\text{concepts}})$。表 1 汇总了我们的结果。

Sat. System	Eviction	Reception
${\Lambda}({\cal E\!L}_{\bot con.})$	yes (Thm. 11)	no (Thm. 13)
${\Lambda}({\cal E\!L}_{\bot con.})^{\dagger}$	yes (Thm. 11)	yes (Thm. 14)
${\Lambda}({\cal ALC}_{con.})$	no (Thm. 12)	no (Thm. 13)
${\Lambda}({\cal ALC}_{con.})^{\ddagger}$	yes (Thm. 16)	yes (Thm. 16)

Table 1: Eviction and reception-compatibility for DL concepts. $\dagger$ is for the case pointed interpretations can only be tree-shaped and $\ddagger$ is for the case they can only be tree-shaped, over finite signatures, and sets of models can only be finite.