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
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.
Download PDF Show BibTeX
Login to edit
Wed Sep 16 10:47:00 2009