| << Prev | - Up - | Next >> |
Given a solved form of a constraint it is almost trivial to get to a solution for it. What we don't know yet is how to get to the solved form itself, given an arbitrary constraint. In this section, we'll formulate an algorithm that enumerates the solved forms of arbitrary constraints.
As we have argued before, it is almost trivial to get to a solution from a solved form. What we don't know yet is how to get to the solved form itself, given an arbitrary constraint. In this section, we'll formulate an algorithm that enumerates the solved forms of an arbitrary constraint.
Our overall strategy will be as follows: starting with an arbitrary constraint graph, we'll try to work our way towards a set of constraints in solved form that together have the same solutions as the original constraint. For this, we'll use the algorithm discussed in the following part of this lecture. The set of solved forms will be the output of this algorithm.
If we like to, we can then proceed to enumerate solutions (or just minimal solutions) of the solved forms after this, in the way described in the last section. But we don't have to.
Eliminate double incoming dominance edges
The main property of solved forms that we try to establish in our algorithm is that there are no nodes with two incoming dominance edges. Thus the central task of our algorithm is eliminating such nodes. We will now look in detail at the three steps that make up the algorithm: Applying the so called Choice Rule, Parent Normalization and Redundancy Elimination.
| << Prev | - Up - | Next >> |