4.3 Solving Dominance Constraints

A na´ve approach to search for solutions of a description \phi is to non-deterministically fix the relationship x\mathbin{r}y between any two variables of \phi and then (1) verify that there are trees corresponding to this configuration (i.e. essentially that the solved form has a tree-shape), (2) verify that some of these trees also satisfy \phi. This algorithm is exponential. But, many configurations do not correspond to trees, and/or cannot satisfy \phi. This is where constraint propagation can prove very effective: it can deterministically rule out configurations that cannot lead to admissible solutions.

Thus our approach will consist in formulating 2 sets of criteria:

Well-formedness Constraints:

these guarantee that a solved form has a tree-shape, i.e. that it has tree solutions.

Problem-specific Constraints:

these guarantee that a solved form actually satisfies the description

Denys Duchier
Version 1.2.0 (20010221)