TY - JOUR
T1 - Query answering with transitive and linear-ordered data
AU - Amarilli, Antoine
AU - Benedikt, Michael
AU - Bourhis, Pierre
AU - Boom, Michael Vanden
N1 - Publisher Copyright:
© 2018 AI Access Foundation. All rights reserved.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - We consider entailment problems involving powerful constraint languages such as frontierguarded 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.
AB - We consider entailment problems involving powerful constraint languages such as frontierguarded 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.
U2 - 10.1613/jair.1.11240
DO - 10.1613/jair.1.11240
M3 - Article
AN - SCOPUS:85054913138
SN - 1076-9757
VL - 63
SP - 191
EP - 264
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -