KB K and a goal Q, the deduction problem asks whether Q can be deduced from K (we note Q ≥ K). If we impose some of the sets R, E or C to be empty, one obtains specific reasoning models. Note that in the absence of constraints ( C = 0), inference and evolution rules have the same behavior, thus R and E can be confused. The SG family is then composed of the six following models.

$$\bullet{\mathrm{~the~}}{\mathcal{S G}}{\mathrm{~model~for~}}{\mathcal{K}}=\left({\mathcal{G}},\ \varnothing,\ \varnothing,\ \varnothing\right)$$
* the $\mathcal{SR}$ model for $\mathcal{K}=(\mathcal{G},\ \mathcal{R},\ \mathcal{E},\ \emptyset)$
* the $\mathcal{S}\mathcal{C}$ model for $\mathcal{K}=(\mathcal{G},\ \emptyset,\ \emptyset,\ \mathcal{C})$ * the $\mathcal{S}\mathcal{R}\mathcal{C}$ model for $\mathcal{K}=(\mathcal{G},\ \mathcal{R},\ \emptyset,\ \mathcal{C})$ * the $\mathcal{S}\mathcal{E}\mathcal{C}$ model for $\mathcal{K}=(\mathcal{G},\ \emptyset,\ \mathcal{E},\ \mathcal{C})$ * the $\mathcal{S}\mathcal{R}\mathcal{E}\mathcal{C}$ model for $\mathcal{K}=(\mathcal{G},\ \mathcal{R},\ \mathcal{E},\ \mathcal{C})$
Since a fact has the same semantics as a rule with an empty hypothesis, the set G is used in models names only when both rule sets R and E are empty. The hierarchy of these models is represented in Fig. 9. It highlights the decidability properties and the complexity of the associated deduction problem. Notice we divide non decidable problems into semi-decidable and truly undecidable problems. In the first case, an answer can be computed in finite time for all positive instances but not for all negative ones. In the second case, there is no finite procedure, neither for all positive instances, nor for all negative ones.

Sfrag replacements

![0_image_0.png](0_image_0.png)

## 4. Sgs And Rules: The Sr Model

A simple graph rule (SG rule) embeds knowledge of form "if A then B". The following definition as a colored SG is equivalent to the more traditional definition of a rule as an object composed of two SGs related with coreference links used by Gosh and Wuwongse
(1995), or Salvat and Mugnier (1996)