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
Liste complète des métadonnées

https://hal.inria.fr/inria-00099678
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:40:06 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM

Identifiers

  • HAL Id : inria-00099678, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

85