Constraint Programming for Natural Language Processing

Denys Duchier

This course demonstrates how constraint programming can be used effectively in practice, for linguistic applications. It shows how many forms of ambiguity arising in computational 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 Constraint 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 finite domain and finite set variables, and introduced to some of the more powerful types of constraints available today, such as reified constraints, disjunctive propagators, and selection constraints.

This course will be taught at ESSLLI 2000 (Birmingham, UK) and exists also in a Postscript version for printing.

Denys Duchier
Version 1.2.0 (20010221)