Extending Decidable Cases for Rules with Existential Variables

Jean-François Baget 1, 2 Michel Leclère 2 Marie-Laure Mugnier 2 Eric Salvat 3
2 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 : In the rules considered, the conclusion may contain existentially quantified variables, which makes reasoning tasks (as deduction) non-decidable. These rules have the same logical form as TGD (tuple generating dependencies) in databases and as conceptual graph rules. We extend known decidable cases by combining backward and forward chaining schemes, in association with a graph that captures exactly the notion of dependency between rules. Finally, we draw a map of known decidable cases, including an extension obtained by combining our approach with very recent results on TGD.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00410130
Contributor : Marie-Laure Mugnier <>
Submitted on : Monday, August 17, 2009 - 7:42:25 PM
Last modification on : Tuesday, June 25, 2019 - 1:26:19 AM

Identifiers

  • HAL Id : lirmm-00410130, version 1

Citation

Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, Eric Salvat. Extending Decidable Cases for Rules with Existential Variables. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. pp.677-682. ⟨lirmm-00410130⟩

Share

Metrics

Record views

355