On Rules with Existential Variables: Walking the Decidability Line

Jean-François Baget 1 Michel Leclère 1 Marie-Laure Mugnier 1 Eric Salvat 2
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We consider positive rules in which the conclusion may contain existentially quantified variables, which makes reasoning tasks (such as conjunctive query answering or entailment) undecidable. These rules, called forall-exists-rules, have the same logical form as tuple-generating dependencies in databases and as conceptual graph rules. The aim of this paper is to provide a clearer picture of the frontier between decidability and non-decidability of reasoning with these rules. Previous known decidable classes were based on forward chaining. On one hand we extend these classes, on the other hand we introduce decidable classes based on backward chaining. A side result is the definition of a backward mechanism that takes the complex structure of forall-exists-rule conclusions into account. We classify all known decidable classes by inclusion. Then, we study the question of whether the union of two decidable classes remains decidable and show that the answer is negative, except for one class and a still open case. This highlights the interest of studying interactions between rules. We give a constructive definition of dependencies between rules and widen the landscape of decidable classes with conditions on rule dependencies and a mixed forward/backward chaining mechanism. Finally, we integrate rules with equality and negative constraints to our framework.
Type de document :
Article dans une revue
Artificial Intelligence, Elsevier, 2011, 175 (9-10), pp.1620-1654. 〈10.1016/j.artint.2011.03.002〉
Liste complète des métadonnées

Contributeur : Jean-François Baget <>
Soumis le : mardi 19 avril 2011 - 09:51:28
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral




Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, Eric Salvat. On Rules with Existential Variables: Walking the Decidability Line. Artificial Intelligence, Elsevier, 2011, 175 (9-10), pp.1620-1654. 〈10.1016/j.artint.2011.03.002〉. 〈lirmm-00587012〉



Consultations de la notice