Publication details

Saarland University Computer Science

Configuration Of Labeled Trees Under Lexicalized Constraints And Principles

Denys Duchier

December 2000

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, to find 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. Our approach takes advantage of constraints on finite sets as well as of a new family of `selection' constraints. We further entertain various refinements of interest to the computational linguist such as lexical ambiguity, valency constraints, and grammatical principles.
This framework generalizes our MOL6 presentation extit``Axiomatizing Dependency Parsing Using Set Constraints'' which addressed the treatment of immediate syntactic dependence when parsing with a dependency grammar and paves the way for a corresponding treatment of linear precedence based on a notion of topological rather than syntactic dependencies.

Download PDF        Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009