Some Structural Properties of the Logic of Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2008

Some Structural Properties of the Logic of Rules


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.
Fichier principal
Vignette du fichier (158.59 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00289250 , version 1 (20-06-2008)


  • 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⟩
133 View
151 Download


Gmail Mastodon Facebook X LinkedIn More