HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Configuration of Labeled Trees under Lexicalized Constraints and Principles

Denys Duchier 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Trees with labeled edges have widespread applicability, for example for the representation of dependency syntax trees. Given a fixed number of nodes and constraints on how edges may be drawn between them, the task of finding solution trees is known as a configuration problem. In this paper, we formalize the configuration problem of labeled trees and argue that it can be regarded as a constraint satisfaction problem which can be solved directly and efficiently 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 finite sets and a new family of `selection' constraints, is especially well-suited for the compact representation and efficient 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 efficient processing and characterize the services expected of a constraint programming system: we define 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 (Duchier, 1999a) and extends naturally to our corresponding treatment of linear precedence (Duchier and Debusmann, 2001) based on a notion of topological rather than syntactic dependencies.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:40:06 AM
Last modification on : Friday, February 11, 2022 - 6:44:04 PM


  • HAL Id : inria-00099678, version 1



Denys Duchier. Configuration of Labeled Trees under Lexicalized Constraints and Principles. Research on Language and Computation, Springer Verlag, 2003, 1 (3-4), pp.307-336. ⟨inria-00099678⟩



Record views