Inverse Roles Make Conjunctive Queries Hard
Inverse Roles Make Conjunctive Queries Hard
复制标题
反向角色使联合查询变得困难
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
C. Lutz
中科院分区：
文献类型：
--
作者：
C. Lutz
联合查询回答是一项重要的深度学习推理任务。尽管这项任务现在已经被很好地理解了，但表达性深度学习中联合查询应答的严格复杂度界限从未获得：所有已知算法都在确定性双指数时间内运行，但现有的下限只是 EXPTIME 时间。在本文中，我们证明 ALCI 中的联合查询应答是 2-EXPTIME-hard（因此是完整的），并且在一些合理的假设下它变成 NEXPTIME-complete。
Conjunctive query answering is an important DL reasoning task. Although this task is by now quite well-understood, tight complexity bounds for conjunctive query answering in expressive DLs have never been obtained: all known algorithms run in deterministic double exponential time, but the existing lower bound is only an EXPTIME one. In this paper, we prove that conjunctive query answering in ALCI is 2-EXPTIME-hard (and thus complete), and that it becomes NEXPTIME-complete under some reasonable assumptions.
影响因子：
5
作者：
Glimm, Birte;Horrocks, Ian;Sattler, Ulrike
通讯作者：
Sattler, Ulrike