Proof: SGC-INCONSISTENCY belongs to DP, since we must prove that for one constraint there is a projection of its trigger and no projection of its obligation. Completeness is proved with a reduction from SAT/UNSAT (as in proof of Th. 13). SGC-CONSISTENCY is thus co-DP-complete.

Arguments for undecidability of SRC-CONSISTENCY, SRC-DEDUCTION and SREC-DE-
DUCTION, as well as semi-decidability of SEC-DEDUCTION, are the same as in the proof of Th. 10: the constraints we used were already disconnected.

When rules are range-restricted, SRC-INCONSISTENCY belongs to DP: we must prove that the trigger of the constraint can be deduced from ( G, R), but not its obligation, and these problems belong respectively to NP and co-NP. Completeness comes from the particular case where R is empty. SRC-CONSISTENCY is thus co-DP-complete.

SEC-DEDUCTION belongs to Σ 2 when rules involved are range-restricted. Though this property does not appear with an immediate formulation of the problem, it becomes obvious when the problem is stated as follows: "does there exist a sequence of graphs G = G 0 ,  . . ,  G p +1, where G = G 0 ,  . . ,  G p is an E -derivation and G p +1 is the disjoint union of G p and C (1) , a projection from Q to G p and a projection from C (1) to a SG G k ,
0 ≤ k ≤ p + 1 such that for every graph G i , 0 ≤ i < k , ( ∗ ) for every mapping π of C ( 0 )
into G i , π is not a projection ?". Notice that no G i before G k in such a sequence triggers the constraint ( C i0) does not project into G i ) and that all G i, i ≥ k, satisfy it (since C (1) projects to G i ), thus all G i of the sequence are consistent. G p+1 ensures that C (1) projects into at least one graph of the sequence, whi allows the above formulation of the problem. Completeness follows from the particular case of negative constraints.

Proof for SREC-DEDUCTION in the case of range restricted rules is similar: in the expression of the problem above, the derivation is now an ( E UR )-derivation, the G i considered are only the ones obtained after the application of a rule from E , and (*) "for every mapping π of C [0] into G i n is replaced by "for every graph that can be R -derived from G i ".

Unfortunately, range-restricted constraints are trickier to study: intuitively, consistency checking should become easier than with general constraints, but the role of irredundancy is still unclear.  Though it is easy to check that SGC-DEDUCTION with range restricted constraints is at least DP-hard ( transformation from SAT/UNSAT ) and we have proven
(though it is not included in this paper) that it is in ∆ 2 (i.e. P NP ), we did not manage to achieve an exact complexity result for this problem.

We did not either manage to assign a complexity class for the SGC d - DEDUCTION and SR T C d - DEDUCTION problems, though both problems trivially belong to ∆ 2 P.

Complexity results obtained in this paper are summarized in table. 1. We also present in Fig. 19 a "complexity map" emphasizing the relationships between problems. In this figure, if E denotes a set of bicolored graphs (rules or constraints), Efes, Err, Ed respectively denote its restriction to a finite expansion set, range restricted elements, or disconnected elements. C- denotes a set of negative constraints. All problems represented are complete for their class. Edges are directed from bottom to top. An edge from a problem P1 to a problem P2 means that P1 is a particular case of P2.  Moreover, in order that the map remains readable, problems which are intermediate between two problems P1 and P2 of the same complexity class, do not appear in the figure. The complexity of such problems can be obtained by "classifying" them in the hierarchy. For instance, SEC-DEDUCTION is more general than SR-DEDUCTION (which is obtained if C = 0) and more specific than SR fesEC-