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.
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. AAAI, 21st International Joint Conference on Artificial Intelligence, pp.677-682, 2009, 〈http://ijcai-09.org/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00410130
Contributeur : Marie-Laure Mugnier <>
Soumis le : lundi 17 août 2009 - 19:42:25
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • 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. AAAI, 21st International Joint Conference on Artificial Intelligence, pp.677-682, 2009, 〈http://ijcai-09.org/〉. 〈lirmm-00410130〉

Partager

Métriques

Consultations de la notice

316