non-terminal that generates a substring from the domains of variables Xi**, . . . , X**i+j−1 that can be extended to a solution of the constraint using the domains of the other variables. The table V produced by the propagator for Example 1 is given in Figure 1.

Fig. 1. Dynamic programming table produced by the propagator of the GRAMMAR constraint.

Pointers correspond to possible derivations.

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

An alternative view of the dynamic programming table produced by this propagator is as an AND/OR graph [4]. This is a layered DAG, with layers alternating between AND-NODES or OR-NODES. Each OR-NODE in the AND/OR graph corresponds to an entry A ∈ V [**i, j**]. An OR-NODE has a child AND-NODE for each production A → BC so that A ∈ V [i, j], B ∈ V [**i, k**] and C ∈ V [i + **k, j** − k]. The children of this AND-NODE are the OR-NODES that correspond to the entries B ∈ V [**i, k**] and C ∈ V [i + **k, j** − k]. Note that the AND/OR graph constructed in this manner is equivalent to the table V [4], so we use them interchangeably in this paper.

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

Every derivation of a string s ∈ L(G) can be represented as a tree that is a subgraph of the AND/OR graph and therefore can be represented as a trace in V . Since every possible derivation can be represented this way, both the table V and the corresponding AND/OR graph are a compilation of all solutions of the GRAMMAR constraint.

## 4 Reformulation Into An Automaton

The time complexity of propagating a GRAMMAR constraint is O(n 3|G|), as opposed to O(n|δ|) for a REGULAR constraint. Therefore, reformulating a GRAMMAR con-