
| R fes     | E fes    | R U S   | R& E    | R& E      | R&E      |         |         |
|-----------|----------|---------|---------|-----------|----------|---------|---------|
| General   |          |         |         |           |          |         |         |
| case      | fes      | For r   | r r , C | r r , C ′ |          |         |         |
| SG-DED    | NP C     |         |         |           |          |         |         |
| SGC-CON   | II ? C   | o NP (  | o NP C  | o DP C    |          |         |         |
| n 2 - C   |          |         |         |           |          |         |         |
| SGC- DED  | DP-C     | DP-C    |         |           |          |         |         |
| SR-DED    | NP C     | NP C    | NP-C    |           |          |         |         |
| semi-dec  | dec      |         |         |           |          |         |         |
| SRC- CONS | udnc     | dec     | dec     | l i i , o | s emi de | co-NP-C | co-DP-C |
| n ? C     |          |         |         |           |          |         |         |
| SRC-DED   | undec    | dec     | dec     | undec     | DP-C     |         |         |
| e, c      |          |         |         |           |          |         |         |
| SEC-DED   | sn type  | dec     | dec     | x C       | sn       | L       |         |
| SREC-DED  | undec    | dec     | L 3 C   | E         |          |         |         |
| undec     | semi dec | undec   |         |           |          |         |         |

DEDUCTION (which adds the set Rfes ), and, since these problems are both semi-decidable, so is SEC-DEDUCTION.

## 8. Related Works

One interesting relationship from an algorithmic viewpoint is with the CSP framework. Recall the input of a constraint satisfaction problem (CSP) is a constraint network, composed of a set of variables, sets of possible values for the variables (called their domains) and a set of constraints between the variables. The question is whether there is a solution to the CSP, i.e. an assignment of values to the variables that satisfies the constraints.

The constraints involved in a classical CSP are simpler than ours. Actually, CSP corresponds to the SG-DEDUCTION (projection) problem.

Several authors noticed the strong equivalence between CSP and LABELLED GRAPH
HOMOMORPHISM (Given two labeled graphs G and H, is there a homomorphism from G to H ?). As far as we know, the first paper on this subject was (Feder & Vardi, 1993). In
(Mugnier, 2000) correspondences are detailed from PROJECTION (Given two SGs G and H is there a projection from G to H ?) to CSP, and reciprocally (developing the ones presented in (Mugnier & Chein, 1996)). Let us outline the ideas of the transformation from CSP to Projection, called C2P. Consider a constraint network P. P is transformed into two SGs G and H as follows. G translates the structure of P: each concept node is generic and corresponds to a variable and each relation node corresponds to a constraint (its ith neighbor is the concept node corresponding to the ith variable of the constraint).

H represents the constraint definitions : there is one individual concept node for each value of a variable domain, and one relation node for each tuple of compatible values. Roughly said, there is a solution to P if there is a mapping from variables (concept nodes of G ) to values (concept nodes of H ) that satisfies the constraints (maps relation nodes of G onto relation nodes of H ), i.e. a projection from G to H . The same result has been achieved independently in the Attributed Graph Grammar formalism by Rudolf (1998).

One could also see CSP as a particular case of SGC-CONSISTENCY: indeed, there is a projection from a SG G into a SG H if and only if H satisfies the positive constraint with an empty trigger and G as its obligation.