Publication details

Saarland University Computer Science

Taming Complexity: Constraint-Based Dependency Parsing

Denys Duchier

Submitted to 6th Meeting on the Mathematics of Language, July 1999

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

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009