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.
Type de document :
Article dans une revue
Research on Language and Computation, Springer Verlag, 2003, 1 (3-4), pp.307-336
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:40:06
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • 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〉



Consultations de la notice