Walking the Decidability Line for Rules with Existential Variables

Jean-François Baget 1 Michel Leclère 1 Marie-Laure Mugnier 1
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 Deduction) undecidable. These rules, called forall-exist-rules, have the same logical form as TGD (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. We show that Deduction remains undecidable with a single forall-exist--rule; then we show that none of the known abstract decidable classes is recognizable. Turning our attention to concrete decidable classes, we provide new classes and classify all known classes by inclusion. Finally, we study, in a systematic way, the question "given two decidable sets of forall-exist--rules, is their union decidable?", andprovide an answer for all known decidable cases except one.
Type de document :
Communication dans un congrès
KR: Principles of Knowledge Representation and Reasoning, May 2010, Toronto, Canada. AAAI Press, 12th International Conference on the Principles of Knowledge Representation and Reasoning, pp.466-476, 2010, 〈http://www.scs.ryerson.ca/~kr2010/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00535780
Contributeur : Marie-Laure Mugnier <>
Soumis le : vendredi 12 novembre 2010 - 16:45:04
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00535780, version 1

Collections

Citation

Jean-François Baget, Michel Leclère, Marie-Laure Mugnier. Walking the Decidability Line for Rules with Existential Variables. KR: Principles of Knowledge Representation and Reasoning, May 2010, Toronto, Canada. AAAI Press, 12th International Conference on the Principles of Knowledge Representation and Reasoning, pp.466-476, 2010, 〈http://www.scs.ryerson.ca/~kr2010/〉. 〈lirmm-00535780〉

Partager

Métriques

Consultations de la notice

382