Much of linguistic theorizing nowadays is concerned with the
formulation of general structural principles that determine
syntactically well-formed entities. Yet, devising effective parsing
mechanisms for such axiomatic frameworks remains a stumbling block
plagued by combinatorial explosion. We propose to take advantage of
the axiomatic nature of such frameworks to obtain constraint-based
formulations. In this fashion, we are able to achieve effective model
elimination through constraint propagation, thus drastically reducing
the need for search. We demonstrate this idea with a formal account
of a dependency grammar for german. The mathematical equations that
we present have a direct interpretation as constraints. Our approach
was implemented in the concurrent constraint programming language Oz
and proved to be surprisingly efficient.
dependency parsing, formal grammars, concurrent
constraint programming, inference, set constraints