本文中,我们将关注于异常演绎的一种替代方法:减缩并研究经过限制的 DLs,在 ALC 到 ALCIO 和 ALCQO 之间寻找出推理的确切计算复杂度,范围从 NExpTime^NP 到不可判定。
Jan, 2014
本文研究 DL 中具有传递性角色的联接查询的可决定性和复杂度问题,并证明了在 SHIQ 中允许传递性角色的联接查询有一个完美的单指数时间算法及共 NP 复杂性。
Oct, 2011
本文通过广泛探究 Circumscription 与 DL-lite_R、EL 及其片段相结合的知识库的计算复杂性,确定了其复杂度范围从 P 到多项式层次的第二层,以及复杂度上升至 PSPACE 及以上的片段。
本篇研究针对 OWL 1 和 OWL 2 DL 中的名词、反向角色和数字限制问题,提出了在 DL ALCHOIQb 中的联合查询包含了所有三个构造的可决定性结果。
本研究从参数复杂性角度研究了在有界团宽度的数据库上对本体中介查询 (OMQ) 的评估,研究了原子查询 (AQ)、连通查询 (CQ) 和连通查询的联合,发现所有 OMQ 问题都是固定参数线性 (FPL) 的,其参数是 OMQ 大小加上团宽度,我们的主要贡献是详细分析了运行时间对参数的依赖,展示了几个有趣的影响。
May, 2022
本文研究了利用概率语义来处理 Description Logics Knowledge Bases 中的不一致性问题,使之能够在查询时处理不一致的 KBs,且与传统的修复语义进行了比较。
Jun, 2023
提出一种将抽象级别作为一等公民并提供概念和角色的抽象和细化的显式运算符的 DLs 扩展,它可以支持多个抽象级别上的知识表示,并证明在这个扩展的 DLs 家族中推理是可判定的,而一些看似无害的变化则是不可判定的。
本文介绍了一种算法,能够在考虑一般性概念包含公理和角色层级的情况下,决定具有传递和逆角色以及功能约束的 DL ALC 的可满足性,同时研究了这类 DL 的可决定性的限制,并描述了一系列优化技术,这些技术对于获得具有实际问题良好性能的决策过程实现至关重要。
May, 2000
该论文研究了使用 Angluin 等人的准确查询学习框架来学习描述逻辑本体的问题,证明了可以用多项式大小的多项式查询来学习用 DL-Lite 描述逻辑和某些和 OWL 2 RL 相关的 EL 片段描述的本体,但即使只允许非循环本体,也不能用多项式大小的查询来学习用 EL 描述逻辑描述的本体。
Sep, 2017
本文提出了一个算法,用于决定具有传递性和逆作用的角色,角色层次结构和限定数量限制的 A LC 的可满足性,并研究了这种 DL 族的决策能力极限。