Some Structural Properties of the Logic of Rules

Jean-François Baget 1, 2 Marie-Laure Mugnier 2 Michel Leclère 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 : We study the properties of semantic consequence in a particular subset of first-order logic with equality and no function symbols, under the unique name assumption. Formulas in this subset of logic are rules of form $\forall \vec x (H \rightarrow \exists \vec y C) where the hypothesis $H$ and the conclusion $C$ are conjunctions of atoms (possibly with equality), $\vec x$ contains the variables in $H$ and $\vec y$ the variables in $C$ that are not in $H$. This subset is particularly expressive since it can encode a universal Turing machine, at the cost of decidability of reasoning. We propose new decidable subclasses of this problem, by combining restrictions on both the structure of the rules themselves and the structure of the interactions between rules, encoded in the graph of rule dependencies. The most general decidable subclass presented here is based on a mixed forward/backward chaining algorithm. Finally, we relate our rules to other notions (tuple-generating dependencies in databases, conceptual graph rules, the TBox in description logics) and explain how the associated deduction problems could benefit from our results.
Type de document :
RR-08016, 2008
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Jean-François Baget <>
Soumis le : vendredi 20 juin 2008 - 10:24:14
Dernière modification le : mercredi 12 décembre 2018 - 14:38:02
Document(s) archivé(s) le : vendredi 28 mai 2010 - 18:36:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : lirmm-00289250, version 1


Jean-François Baget, Marie-Laure Mugnier, Michel Leclère, Eric Salvat. Some Structural Properties of the Logic of Rules. RR-08016, 2008. 〈lirmm-00289250〉



Consultations de la notice


Téléchargements de fichiers