BriefGPT - AI 论文速递
·
具有路径表达式的表达能力描述逻辑中的数据复杂度
💡
原文中文，约1200字，阅读约需3分钟。
📝
内容提要
本文研究了描述逻辑中的查询回答，提出了基于树模型和自动机算法的解决方案，探讨了不同角色的可满足性及其复杂性，分析了有限本体中介查询的可决定性，并介绍了多种算法和优化技术，为信息系统的发展奠定了基础。
🎯
关键要点
- 研究描述逻辑中支持具有限制的传递和非传递角色的查询回答，提出了一种基于树模型和自动机算法的解决方案。
- 证明 DEL 语言中事件模型的模型检查问题是 PSPACE 完全的，满足性问题是 NEXPTIME-complete 的。
- 提出了一个算法，用于决定具有传递性和逆作用的角色的可满足性，并研究了这种 DL 族的决策能力极限。
- 研究了在有界团宽度的数据库上对本体中介查询的评估，发现所有 OMQ 问题都是固定参数线性 (FPL) 的。
- 介绍了一种基于 PDL 的表达力丰富的逻辑家族 CPDL+，研究了其最小模型检查问题和可满足性问题。
- 探讨了有限本体中介查询应答的问题，显示了 SOIF 的三个适当片段的 FOMQA 具有可决定性。
- 介绍了一种算法，能够在考虑一般性概念包含公理和角色层级的情况下，决定 DL ALC 的可满足性。
- 研究了正 Datalog 上添加整数算术函数的扩展语言 Datalog_Z，并提出了两个限制子语言以解决其不可判定性。
- 证明了分离嵌入式依赖可以精确捕捉基于本体的连词查询应答中的可递归枚举本体类。
❓
延伸问答
描述逻辑中的查询回答是如何实现的？
通过基于树模型和自动机算法的解决方案来实现。
DEL语言中的模型检查问题的复杂性如何？
DEL语言中的模型检查问题是PSPACE完全的，满足性问题是NEXPTIME-complete的。
在有限本体中介查询中，FOMQA的可决定性如何？
研究显示SOIF的三个适当片段的FOMQA具有可决定性。
如何决定具有传递性和逆作用的角色的可满足性？
提出了一种算法来决定具有传递性和逆作用的角色的可满足性。
在有界团宽度的数据库上，OMQ问题的评估结果是什么？
所有OMQ问题都是固定参数线性(FPL)的。
Datalog_Z扩展语言的复杂性如何？
Datalog_Z的不可判定性通过提出两个限制子语言来解决，并证明了相应的NP完全性和ExpTime完全性。
➡️
