⬆️ Top

# Compute span of nodes in a dependency tree

This example illustrates the usage of non-injective matching introduced in version 1.11 (January 2023).

The objective is to add to each node, two new outgoing edges (labeled `span=left`

and `span=right`

) from the given node to its leftmost projection and rightmost projection respectively.

The main idea of the GRS is:

- add to each node two looping links
`span=left`

and`span=right`

(rule`init`

above) - iteratively
*enlarge*the span of one node either on the left or on the right (package`enlarge`

above):*“if one of my daughter node has a left [resp. right] span which is more on the left [resp. right] than mine, it become my new left [resp. right] span”*. When this last rule cannot be applied further, the spans are correcly computed.

The second item (for the left case) can be formulated in the Grew rule below, with nodes:

`N`

: the current node where the span will be enlarge`LN`

: the left span of`N`

before the application of the rule`X`

: the daughter of`N`

having a left span`LX`

which is more on the left than`LN`

`LX`

: the left span of`X`

```
rule left {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> LX; LX << LN }
commands {
del_edge e;
add_edge N -[span=left]-> LX;
}
}
```

The main difficulty is that we have to take into account some superposition subcases (NB: the other superposition cases cannot arise, the proof is left as an exercise!) Possible cases are:

- all nodes are different
`N`

and`LN`

refers to the same node`X`

and`LX`

refers to the same node- (
`N`

and`LN`

refers to the same node) and (`X`

and`LX`

refers to the same node) `LN`

and`X`

refers to the same node

When using only injective matching, we then have to design 10 rules (5 on the left and 5 on the right) for the `enlarge`

package (see below).

With non-injective matching (introduced in version 1.11), the same package can be written with only two rules.

## Solution with non-injective matching

With the grs file non_injective.grs:

```
rule init {
pattern { N [upos] }
without { N -[span=left]-> * }
without { N -[span=right]-> * }
commands {
add_edge N -[span=left]-> N;
add_edge N -[span=right]-> N;
}
}
package enlarge {
rule left {
pattern { e: N -[span=left]-> LN$; N -> X; X -[span=left]-> LX$; LX$ << LN$ }
commands {
del_edge e;
add_edge N -[span=left]-> LX$;
}
}
rule right {
pattern { e: N -[span=right]-> RN$; N -> X; X -[span=right]-> RX$; RN$ << RX$ }
commands {
del_edge e;
add_edge N -[span=right]-> RX$;
}
}
}
strat main { Seq (Onf (init), Onf (enlarge)) }
```

⚠️ In **Grew-web**, dependency graphs are drawn with dep2pict and loops can not be displayed directly.
Loops are replaced by special features with a green background and with double brackets.
See for instance, the final graph computed with the example above:

## Solution with only injective matching

With the grs file injective.grs:

```
rule init {
pattern { N [upos] }
without { N -[span=left]-> * }
without { N -[span=right]-> * }
commands {
add_edge N -[span=left]-> N;
add_edge N -[span=right]-> N;
}
}
package enlarge {
% 4 different nodes
rule left_1 {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> LX; LX << LN }
commands {
del_edge e;
add_edge N -[span=left]-> LX;
}
}
% LN = N
rule left_2 {
pattern { e: N -[span=left]-> N; N -> X; X -[span=left]-> LX; LX << N }
commands {
del_edge e;
add_edge N -[span=left]-> LX;
}
}
% LX = X
rule left_3 {
pattern { e: N -[span=left]-> LN; N -> X; X -[span=left]-> X; X << LN }
commands {
del_edge e;
add_edge N -[span=left]-> X;
}
}
% LN = N & LX = X
rule left_4 {
pattern { e: N -[span=left]-> N; N -> X; X -[span=left]-> X; X << N }
commands {
del_edge e;
add_edge N -[span=left]-> X;
}
}
% LN = X
rule left_5 {
pattern { e: N -[span=left]-> X; N -> X; X -[span=left]-> LX; LX << X }
commands {
del_edge e;
add_edge N -[span=left]-> LX;
}
}
% 4 different nodes
rule right_1 {
pattern { e: N -[span=right]-> RN; N -> X; X -[span=right]-> RX; RX >> RN }
commands {
del_edge e;
add_edge N -[span=right]-> RX;
}
}
% RN = N
rule right_2 {
pattern { e: N -[span=right]-> N; N -> X; X -[span=right]-> RX; RX >> N }
commands {
del_edge e;
add_edge N -[span=right]-> RX;
}
}
% RX = X
rule right_3 {
pattern { e: N -[span=right]-> RN; N -> X; X -[span=right]-> X; X >> RN }
commands {
del_edge e;
add_edge N -[span=right]-> X;
}
}
% RN = N & RX = X
rule right_4 {
pattern { e: N -[span=right]-> N; N -> X; X -[span=right]-> X; X >> N }
commands {
del_edge e;
add_edge N -[span=right]-> X;
}
}
% RN = X
rule right_5 {
pattern { e: N -[span=right]-> X; N -> X; X -[span=right]-> RX; RX >> X }
commands {
del_edge e;
add_edge N -[span=right]-> RX;
}
}
}
strat main { Seq (Onf (init), Onf (enlarge)) }
```