

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

G(c) ≥ (G(aba), R(Γ) ∪ E(Γ)) though aba → c (apply R(γ) once, then two times E(γ) using different nodes [a] but the same node [c]).

We thus need the notion of a good application of a rule E(7): it is such that the projection of its destination part is a mapping to a subgraph that was obtained by applying the rule R(7), and that was never used to project the destination part of any rule of &(F), including E(y) itself. Moreover, the origin and destination must be projected into disjoint paths (i.e.

a node of the origin cannot have the same image has a node of the destination). If we restrict ourselves in some way to good applications of rules of E ( Γ), then we can verify that G(m') ≥ (G(m), U(F)) iff G(m') ≥ (G(m), R(F) ∪ (Γ)).

This restriction is obtained by using constraints, that will allow every good application of a rule of E ( Γ ), and be violated by the obtained graph otherwise. Let us note R ′ ( Γ )
and E ′ (Γ) the new sets of inference rules and evolution rules. The new transformation is described in Fig. 16. It allows to obtain the following result: m ~ m ′ 
( G ′ ( m ), R ′ ( Γ ), E ′ ( Γ ), { C + , C − } ). The names of relation types = , E and → have been chosen to give an intuitive idea of their role but they are just types as others. A relation node (€)
from a node [ z j ] to a node [ γ j ] means that the letter z j has been obtained by applying the rule γ i . A relation node ( → ) from [ y k ] to [ γ i ] means that the letter y k belongs to the subword on which the rule γ i has been applied.  = is used to indicate that two concept nodes have to be projected on the same node (in CG terms, we would see it as a co-reference link).

The evolution rule E t ( γ i ), starting from a path representing the subword α i used to apply γ i and from the representation of β i generated by R ′ (γ i ), produces the two relation nodes typed s simulating the application of U ( γ i ), thus γ i , and the relation nodes typed → which mark the representation of α i as used by an application of γ i . The negative constraint C_
prevents an application of E l ( γ i ) in which two nodes of the origin and destination parts have the same image (a node necessarily obtained by some application of the rule R ′ ( γ i )); while the positive constraint C+ prevents such a subgraph to be used twice for applying E'(7i) with different projections of its origin: it says that in this case, the two projections of the origins must be the same.

□

## 7.2 Range Restricted Rules

Let us now focus on the rules that were used to solve the Sisyphus-I problem. A bicolored graph (rule or constraint) is said to be range restricted (r.r.) if its second part (conclusion or obligation) does not comprise any generic concept node. We use this expression by analogy