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.