Publication details

Saarland University Computer Science

Axiomatizing Dependency Parsing Using Set Constraints

Denys Duchier

Sixth Meeting on Mathematics of Language, pp. 115--126, July 1999

We propose a new formulation of dependency grammar and develop a corresponding axiomatization of syntactic well-formedness with a natural reading as a concurrent constraint program. We demonstrate the expressivity and effectiveness of set constraints, and describe a treatment of ambiguity with wide applicability. Further, we provide a constraint programming account of dependent disjunctions that is both simple and efficient and additionally provides the benefits of constructive disjunctions. Our approach was implemented in Oz and yields parsers with very good performance for our currently middle scale grammars. Constraint propagation can be observed to be remarkably effective in pruning the search space.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009