Con Of Labeled Trees Under Lexicalized Constraints And Principles

ABSTRACT: Trees with labeled edges have widespread applicability, for example for the representation of dependency syntax trees. Given a xed number of nodes and constraints on how edges may be drawn between them, the task of nding solution trees is known as a conguration problem. In this paper, we formalize the conguration problem of labeled trees and argue that it can be regarded as a constraint satisfaction problem which can be solved directly and efciently by constraint propagation. In particular, we derive and prove correct a formulation of dependency parsing as a constraint satisfaction problem. Our approach, based on constraints on nite sets and a new family of `selection ' constraints, is especially well-suited for the compact representation and efcient processing of ambiguity. We address various issues of interest to the computational linguist such as lexical ambiguity, structural ambiguity, valency constraints, grammatical principles, and linear precedence. Finally we turn to the challenge of efcient processing and characterize the services expected of a constraint programming system: we dene a formal constraint language and specify its operational semantics with inference rules of propagation and distribution. This framework generalizes our presentation of immediate syntactic dependence for dependency parsing [4] and extends naturally to our corresponding treatment of linear precedence [6] based on a notion of topological rather than syntactic dependencies