Definite descriptions are expressions of the form "the unique $x$ satisfying property $C$," which allow reference to objects through their distinguishing characteristics. They play a crucial role in ontology and query languages, offering an alternative to proper names (IDs), which lack semantic content and serve merely as placeholders. In this paper, we introduce two extensions of the well-known description logic $\mathcal{ALC}$ with local and global definite descriptions, denoted $\mathcal{ALC}ι_L$ and $\mathcal{ALC}ι_G$, respectively. We define appropriate bisimulation notions for these logics, enabling an analysis of their expressiveness. We show that although both logics share the same tight ExpTime complexity bounds for concept and ontology satisfiability, $\mathcal{ALC}ι_G$ is strictly more expressive than $\mathcal{ALC}ι_L$. Moreover, we present tableau-based decision procedures for satisfiability in both logics, provide their implementation, and report on a series of experiments. The empirical results demonstrate the practical utility of the implementation and reveal interesting correlations between performance and structural properties of the input formulas.


翻译:限定摹状词是形如“满足性质C的唯一x”的表达式,允许通过对象的区分性特征来指称对象。它们在本体论和查询语言中扮演着关键角色,为缺乏语义内容、仅作为占位符使用的专有名称(ID)提供了一种替代方案。本文在著名的描述逻辑ALC基础上,引入了局部和全局两类限定摹状词的扩展,分别记为ALCιL和ALCιG。我们为这些逻辑定义了适当的互模拟概念,从而能够分析其表达能力。我们证明,尽管两种逻辑在概念和本体可满足性上具有相同的紧致ExpTime复杂度界限,但ALCιG的表达能力严格强于ALCιL。此外,我们为两种逻辑的可满足性问题提出了基于表推演(tableau)的判定过程,提供了其实现,并报告了一系列实验。实证结果表明该实现具有实际效用,并揭示了性能与输入公式结构特性之间有趣的相关性。

0
下载
关闭预览

相关内容

描述逻辑(DescriptionLogic)是基于对象的知识表示的形式化,它吸取了KL-ONE的主要思想,是一阶谓词逻辑的一个可判定子集。除了知识表示以外,描述逻辑还用在其它许多领域,它被认为是以对象为中心的表示语言的最为重要的归一形式。描述逻辑的重要特征是很强的表达能力和可判定性,它能保证推理算法总能停止,并返回正确的结果。在众多知识表示的形式化方法中,描述逻辑在十多年来受到人们的特别关注,主要原因在于:它们有清晰的模型-理论机制;很适合于通过概念分类学来表示应用领域;并提供了很多有用的推理服务。
【ICLR2022】GNN-LM基于全局信息的图神经网络语义理解模型
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
42+阅读 · 2021年8月12日
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
基于Lattice LSTM的命名实体识别
微信AI
48+阅读 · 2018年10月19日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关VIP内容
【ICLR2022】GNN-LM基于全局信息的图神经网络语义理解模型
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
42+阅读 · 2021年8月12日
相关资讯
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
基于Lattice LSTM的命名实体识别
微信AI
48+阅读 · 2018年10月19日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员