Multi-Dimensional Graph Configuration for Natural Language Processing

Ralph Debusmann, Denys Duchier, and Marco Kuhlmann. Multi-Dimensional Graph Configuration for Natural Language Processing. In Henning Christiansen, Peter Rossen Skadhauge, and Jørg Villadsen, editors, Constraint Solving and Language Processing. First International Workshop, CSLP 2004, Roskilde, Denmark, September 1–3, 2004. Revised Selected and Invited Papers, volume 3438 of Lecture Notes in Computer Science, pages 104–120. Springer, 2005.


Many tasks in computational linguistics can be regarded as configuration problems. In this paper, we introduce the notion of lexicalised multi-dimensional configuration problems (LMCPs). This class of problems both has a wide range of linguistic applications, and can be solved in a straightforward way using state-of-the-art constraint programming technology. The paper falls into two main parts: We first present examples for linguistic configuration problems and show how to formalise them as constraint satisfaction problems. In the second part, we introduce Extensible Dependency Grammar (XDG), a framework for the development of linguistic resources in the context of LMCPs.