<< Prev | - Up - | Next >> |

A naïve approach to search for solutions of a description is to non-deterministically fix the relationship between any two variables of 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 . This algorithm is exponential. But, many configurations do not correspond to trees, and/or cannot satisfy . 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

<< Prev | - Up - | Next >> |

Denys Duchier

Version 1.2.0 (20010221)