SFB 378 Einstiegsseite Postscript File BibTeX Entry

C
NEP
NEGRA

Configuration Of Labeled Trees Under Lexicalized Constraints And Principles

Author: Denys Duchier

Editor:

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 \textit``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.

SFB 378 Einstiegsseite Postscript File BibTeX Entry