IJCAIJun, 2024

具有路径表达式的表达能力描述逻辑中的数据复杂度

PDF
TL;DR探讨了在准林中非常表达性描述逻辑 ZOIQ (即 ALCHb Self reg OIQ) 上满足性问题的数据复杂性，并证明了它是 NP 完备的。这完成了对 ZOIQ 可判定片段的数据复杂性全景的研究，并重新证明了关于 OWL2 可判定片段（SR 系列）的已知结果。利用相同的技术，我们证明了在 ZIQ 中带根查询的蕴涵问题在形式复杂度上是 coNEXPTIME 完备的。
发现论文，激发创造
  • 在 SQ 本体上回答正则路径查询

    研究描述逻辑中支持具有限制的传递和非传递角色的查询回答，提出了一种基于树模型和自动机算法的解决方案。

    Nov, 2020

  • 关于动态认知逻辑的复杂性

    本研究使用合法及完整的插入表技术，证明 DEL 语言中事件模型的模型检查问题是 PSPACE 完全的，并证明了满足性问题是 NEXPTIME-complete 的。

    Oct, 2013

  • 表达能力描述逻辑的实际推理

    本文提出了一个算法，用于决定具有传递性和逆作用的角色，角色层次结构和限定数量限制的 A LC 的可满足性，并研究了这种 DL 族的决策能力极限。

    May, 2000

  • 探索命题动态逻辑的非正则扩展与描述逻辑特征

    在扩展 ALC 描述逻辑的决定性满足性检查和查询中，我们研究了非规则路径表达式的影响。我们重点研究了 ALCreg 和 ALCvpl，它们是使用正则和可见推动语言的路径表达式的扩展。

    Jul, 2023

  • 基于本体的有界团宽数据库查询

    本研究从参数复杂性角度研究了在有界团宽度的数据库上对本体中介查询 (OMQ) 的评估，研究了原子查询 (AQ)、连通查询 (CQ) 和连通查询的联合，发现所有 OMQ 问题都是固定参数线性 (FPL) 的，其参数是 OMQ 大小加上团宽度，我们的主要贡献是详细分析了运行时间对参数的依赖，展示了几个有趣的影响。

    May, 2022

  • PDL on Steroids：关于具有交集和转置的 PDL 表达式的扩展性探讨

    介绍了一种基于 PDL 的表达力丰富的逻辑家族 CPDL+，研究了其最小模型检查问题和可满足性问题，将 CPDL + 的表达能力与树宽相关联，并通过基于树宽的逐步升级证明了其表达能力的严格上升。

    Apr, 2023

  • 具有传递角色的表达能力描述逻辑中的有限查询回答

    该研究探讨了有限本体中介查询应答的问题，使用 DLs 描述逻辑中的联合，当仅考虑本体的有限模型时，研究 FOMQA 是相关的，本研究显示了 SOIF 的三个适当片段的 FOMQA 具有可决定性，这是基于模型的特定规律，开发了自动机决策程序。

    Aug, 2018

  • 用于非常表达性描述逻辑的实用推理

    本文介绍了一种算法，能够在考虑一般性概念包含公理和角色层级的情况下，决定具有传递和逆角色以及功能约束的 DL ALC 的可满足性，同时研究了这类 DL 的可决定性的限制，并描述了一系列优化技术，这些技术对于获得具有实际问题良好性能的决策过程实现至关重要。

    May, 2000

  • 使用极限 Datalog 程序的声明性数据分析基础

    研究了正 Datalog 上添加整数算术函数的扩展语言 Datalog_Z，并提出了两个限制子语言 limit Datalog_Z 和 stable Datalog_Z 以解决其不可判定性，并证明了相应的 NP 完全性和 ExpTime 完全性，最终表明稳定的 Datalog_Z 能够表达许多有用的数据分析任务，为先进信息系统的发展提供了一个坚实的基础。

    May, 2017

  • 本体基于查询回答的存在规则语言表达完备性

    本文证明了分离嵌入式依赖可以精确捕捉基于本体的连词查询应答中的可递归枚举本体类，而关于 “元组生成依赖” 的复杂性类和嵌入式依赖的复杂性类都不能完全表达可递归枚举的 “基于本体的连词查询应答” 本体。

    Apr, 2016