Proof: SEC includes SR thus SEC -deduction is not decidable. When Q is deducible from K, a breadth-first search of the tree of all derivations from K, each graph being checked for consistency, ensures that G k is found in finite time. For SRC, we show that ecking consistency is truly undecidable. Let K be a KB where C contains a positive constraint C+
and a negative constraint C − , both with an empty trigger. For proving consistency, one has to prove that C- X (G,R), and the algorithm does not necessarily stop in this case (from semi-decidability of deduction in SR ). The same holds for the complementary problem
(proving inconsistency) taking C+ instead of C+, hence the undecidability.

□
As a generalization of SRC , deduction in SREC is truly undecidable.  Next section studies a decidable fragment of SREC , which in particular was sufficient for the SYSIPHUS-I modelization.

## 7. Decidability And Complexity Of Some Particular Cases

A rule application may add redundant information to a graph. In general, detecting redundancy is difficult (recall determining whether a graph is redundant is an NP-complete problem), but there are some trivial cases, which we will get rid of, since they may create artificially infinite derivations. First, once a rule has been applied to a graph according to a given projection, it can be applied again to the resulting graph, according to the same projection, and this indefinitely. These further applications obviously produce redundant information. They are said to be useless. Another case of trivial redundancy in a graph is that of twin relation nodes, i.e. with exactly the same neighbors in the same order.  Consider for instance a rule of kind " if r(x, y) then r(x, y) ". This rule can be applied indefinitely, en if useless applications are avoided, but all applications create twin relation nodes. In what follows, we consider that the construction of the graph resulting from a rule application prevents the generation of twin relation nodes, and that a derivation does not comprise any useless rule application.

Given a set of rules R and an R -derivation leading to a SG H, H is said to be closed if no rules of R can be applied to H in an original way, i.e.  all applications of any rule of R on H are useless. More formally, H is closed w.r.t. R and w.r.t. an R -derivation H 0 π 1 … π k H k = H , where H i (1 ≤ i ≤ k ) is the graph obtained by the application of a rule of R on H i –1 according to the projection π i , if for every rule R of R , for every projection π from R (0) into H , there exists a projection π i from R (0) to H i − 1 (1 ≤ i ≤ k ), such that 7 = 7, Given a set of rules R and a graph G if a closed graph is R -derivable from G i then it is unique. Moreover, if this graph is derivable with n rule applications, then n is the maximal length of an R-derivation, and all derivations of length n lead to it. When it exists, we call it the closure of G w . r . t . R , which we note G*R
Let us also define another notion, related to the fact that we are interested in irredundant graphs. In this perspective, let us say that an irredundant graph H is full w.r.t. a set of rules R if every graph that can be obtained by applying one of those rules on H is equivalent to H. Assuming that G is an irredundant graph and that graphs obtained by a rule application are put into irredundant form, if a full graph can be derived from G then it is unique.

Informally, the notion of a closed graph translates the fact that nothing can be added that has not been already added, whereas the notion of a full graph says that nothing can