论文标题
在线性时间逻辑中确定普通语言和本体学介导的查询
Deciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic
论文作者
论文摘要
我们担心的是确定在线性逻辑LTL（z，z，<）上确定本体介导的查询（OMQ）的数据复杂性的问题，并确定它是否可以重写（<） - 查询，可能带有一些额外的谓词。首先，我们观察到，按照普通语言的电路复杂性和可疑性，OMQ在AC^0，ACC^0和NC^1中回答与FO（<，equiv） - 使用Unary predicates x \ equiv 0（mod n），fo（mod n），fo（<，mod）-mod judrieltionalition flitiase for fo fo fo（<，equiv） - 可启动性使用。我们证明，与识别常规语言的fo（<）确定性的已知pspace完整性相似，决定fo（<，\ equiv） - 和fo（<，mod）-ddedebility也是\ pspace-complete（除非acc^0 = nc^1）。然后，我们使用此结果表明，确定fo（<），fo（<，\ equiv） - 和fo（<，mod） - ltl omqs的可剥削性是expspace compterety的，并且这些问题对OMQ对OMQ来说是pspace-compterety compterty omq compterety omq compterty omq compterty omq compterety contery of the omq compterety consote and a the otomic Query us a Atomic Query，以及在foery中的积极质量（以及fo）（<）<） - <） - <） - <） fo（<，\ equiv） - 剥夺。此外，我们考虑使用二进制子句本体论的OMQ的FO（<） - 确定OMQ类是pspace-，pspace-，pi_2^p-和conp-complete。
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC^0, ACC^0 and NC^1 coincides with FO(<,\equiv)-rewritability using unary predicates x \equiv 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We prove that, similarly to known PSPACE-completeness of recognising FO(<)-definability of regular languages, deciding FO(<,\equiv)- and FO(<,MOD)-definability is also \PSPACE-complete (unless ACC^0 = NC^1). We then use this result to show that deciding FO(<)-, FO(<,\equiv)- and FO(<,MOD)-rewritability of LTL OMQs is EXPSPACE-complete, and that these problems become PSPACE-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,\equiv)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSPACE-, Pi_2^p- and coNP-complete.
