This course demonstrates how constraint programming can be used effectively in practice, for linguistic applications. It shows how many
forms of ambiguity arising in linguistic can be represented compactly
and elegantly, and processed efficiently with constraints.
A key idea to derive the most benefit from constraint propagation
is that intended models should be characterized as solutions of emphConstraint
Satisfaction Problems (CSPs) rather than defined inductively or in a
generative fashion.
We examine several topics in detail: encodings of finite domains,
tree descriptions using dominance constraints, and parsing with
dependency grammars. In each case, we present a formal characterization
of the problem as a CSP and illustrate how to derive a corresponding
constraint program. The course includes 4 complete interactive
applications written in Oz, with full code supplied.
Through these programmatic vignettes the reader is exposed to the
practice of constraint programming with emphfinite domain and
emphfinite set variables, and introduced to some of the more powerful
types of constraints available today, such as reified constraints,
disjunctive propagators, and selection constraints.