Query Answering with Transitive and Linear-Ordered Data
This addresses foundational issues in knowledge representation and reasoning for AI, focusing on decidability in constraint-based query answering, but it is incremental as it builds on existing guardedness frameworks.
The paper tackled the problem of entailment with constraint languages like frontier-guarded existential rules, imposing semantic restrictions such as transitivity or linear orders, and established decidability and complexity results for variants while showing that minor changes lead to undecidability.
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.