4.3 Solving Dominance Constraints

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

• 4.3.1 Well-Formedness Constraints
  • Characteristic Set Constraints
  • Well-Formedness Clauses
  • Disjunctive Propagator

• 4.3.2 Problem-Specific Constraints

• 4.3.3 Searching for Solved Forms