论文标题
查询使用及传递和线性订购的数据回答
Query Answering with Transitive and Linear-Ordered Data
论文作者
论文摘要
我们考虑涉及强大约束语言的必要问题，例如边境保护的存在规则，在这些规则中，我们对一组杰出关系施加了其他语义限制。我们考虑将关系限制为传递性，将关系限制为另一种关系的及物封闭，并将关系限制为线性秩序。我们提供了一些自然的保护性变体，可以在每种情况下推断推断，并隔离相应决策问题的复杂性。最后，我们表明，这些条件的轻微变化导致了不可证明的性能。
We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.
