Trees with labeled edges have widespread applicability, for examplefor the representation of dependency syntax trees. Given a fixednumber of nodes and constraints on how edges may be drawn betweenthem, the task of finding solution trees is known as a configurationproblem. In this paper, we formalize the configuration problem oflabeled trees and argue that it can be regarded as a constraintsatisfaction problem which can be solved directly and efficiently byconstraint propagation. In particular, we derive and prove correcta formulation of dependency parsing as a constraint satisfactionproblem.
Our approach, based on constraints on finite sets and a new family of`selection' constraints, is especially well-suited for the compactrepresentation and efficient processing of ambiguity. We addressvarious issues of interest to the computational linguist such aslexical ambiguity, structural ambiguity, valency constraints,grammatical principles, and linear precedence. Finally we turn to thechallenge of efficient processing and characterize the servicesexpected of a constraint programming system: we define a formalconstraint language and specify its operational semantics withinference rules of propagation and distribution.
This framework generalizes our presentation of immediate syntacticdependence for dependency parsing (Duchier, 1999a)and extends naturally to our corresponding treatment of linearprecedence (Duchier and Debusmann, 2001) based on a notion of topological ratherthan syntactic dependencies.
configuration - constraint propagation - constraint satisfaction - dependency grammar - labeled trees - parsing - set constraints