### 4.2.1 Models of Dominance Constraints

A model of a dominance constraint is a pair of a tree and an interpretation of mapping variables of to nodes in , and such that is satisfied. We write to say that is satisfied by and define it in the usual Tarskian way as follows:

Solving dominance constraints is NP-hard. This was shown e.g. in [KNT98] by encoding boolean satisfiability as a dominance problem. However, the constraint-based technique first outlined in [DG99] has proven quite successful and solves practical problems of arising e.g. in semantic underspecification very efficiently. The technique is formally studied and proven sound and complete in [DN00]. An extension of this technique to handle general descriptions with arbitrary Boolean connectives was presented in [Duc00].

Denys Duchier
Version 1.2.0 (20010221)