upper bound u[**i, j, A**] on the maximal weight of a derivation from A of a substring
[Xi**, . . . , X**i+j ]. We mark the element A iff l[i, j, A] ≤ u[**i, j, A**]. The pseudo-code is presented in Algorithm 1. Lines 2–5 initialize l and u. Lines 6–16 compute the first stage, whilst lines 20–29 compute the second stage. Finally, we prune inconsistent values in lines 30–31. Algorithm 1 enforces domain consistency in O(|G|n 3) time.

Algorithm 1 The weighted CYK propagator 1: **procedure** WCYK-ALG(G, W, z, [X1**, . . . , X**n])
2: for j = 1 to n do 3: for i = 1 to n − j + 1 do 4: for each A ∈ G do 5: l[i, j, A] = z + 1; u[i, j, A] = −1; 6: for i = 1 to n do 7: V [i, 1] = {A|A → a ∈ **G, a** ∈ D(Xi)}
8: for A ∈ V [i, 1] s.t A → a ∈ **G, a** ∈ D(Xi) do 9: l[i, 1, A] = min{l[i, 1, A],W[A → a]};
10: for j = 2 to n do 11: for i = 1 to n − j + 1 do 12: V [i, j] = ∅;
13: for k = 1 to j − 1 do 14: V [i, j] = V [i, j] ∪ {A|A → BC ∈ G, B ∈ V [i, k], C ∈ V [i + **k, j** − k]}
15: for each A → BC ∈ G s.t. B ∈ V [i, k], C ∈ V [i + **k, j** − k] do 16: l[i, j, A] = min{l[i, j, A], W[A → BC] + l[i, k, B] + l[i + k, j − **k, C**]}; 17: if S /∈ V [1, n] **then**
18: return 0; 19: mark (1, n, S); u[1, n, S] = z; 20: for j = n **downto** 2 do 21: for i = 1 to n − j + 1 do 22: for A such that (**i, j, A**) is marked do 23: for k = 1 to j − 1 do 24: for each A → BC ∈ G s.t. B ∈ V [i, k], C ∈ V [i + **k, j** − k] do 25: if W[A → BC] + l[i, k, B] + l[i + k, j − k, C] > u[i, j, A] **then**
26: continue; 27: mark (**i, k, B**); mark (i + k, j − **k, C**);
28: u[i, k, B] = max{u[i, k, B], u[i, j, A] − l[i + k, j − **k, C**] − W[A → BC]};
29: u[i + k, j − k, C] = max{u[i + k, j − k, C], u[i, j, A] − l[**i, k, B**] −W[A → BC]};
30: for i = 1 to n do

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

32: return 1;

## 3 Decomposition Of The Weighted Cfg Constraint

As an alternative to this monolithic propagator, we propose a simple decomposition with which we can also enforce domain consistency. A decomposition has several advantages. For example, it is easy to add to any constraint solver. As a second example, decomposition gives an efficient incremental propagator, and opens the door to advanced techniques like nogood learning and watched literals. The idea of the decomposition is to introduce arithmetic constraints to compute l and u. Given the table V
obtained by Algorithm 1, we construct the corresponding **AND/OR** directed acyclic graph (DAG) as in [7]. We label an OR node by n(**i, j, A**), and an AND node by n(**i, j, k, A** → BC). We denote the parents of a node nd as **P RT** (nd) and the children as CHD(nd). For each node two integer variables are introduced to compute l and u.