BriefGPT - AI 论文速递
·
在可判定的一阶逻辑片段中添加圆谬论：复杂度上下起伏
💡
原文中文，约400字，阅读约需1分钟。
📝
内容提要
本文研究了可判定的一阶逻辑表达性碎片的扩展，包括FO$^2$、C$^2$和GF。证明了一元谓词在规约过程中最小化会保持逻辑蕴含的可判定性。对于FO$^2$，复杂度从coNexp增加到coNExp^NP-complete，对于GF，复杂度从2Exp增加到Tower-complete。对于C$^2$，复杂度未知。查询在本体为GF句子的约束知识库的问题，对于合取查询的并集是可判定的，对于组合复杂度是Tower-complete，对于数据复杂度是元的。对于原子查询和本体是保护存在规则集的情况，无论k大于等于0，存在一种本体和查询是k-Exp在数据复杂度上是困难的。
🎯
关键要点
- 研究了可判定的一阶逻辑表达性碎片的扩展，包括FO$^2$、C$^2$和GF。
- 证明了一元谓词在规约过程中最小化会保持逻辑蕴含的可判定性。
- FO$^2$的复杂度从coNexp增加到coNExp^NP-complete。
- GF的复杂度从2Exp增加到Tower-complete。
- C$^2$的复杂度仍然未知。
- 查询在本体为GF句子的约束知识库的问题中，合取查询的并集是可判定的。
- 合取查询的组合复杂度是Tower-complete，数据复杂度是元的。
- 对于原子查询和本体是保护存在规则集的情况，存在一种本体和查询是k-Exp在数据复杂度上是困难的。
➡️
