Publication details

Saarland University Computer Science

Mildly Context-Sensitive Dependency Languages

Marco Kuhlmann, Mathias Möhl

45th Annual Meeting of the Association for Computational Linguistics (ACL), 2007

Dependency-based representations of natural language syntax require a fine balance between structural flexibility and computational complexity. In previous work, several constraints have been proposed to identify classes of dependency structures that are well-balanced in this sense; the best-known but also most restrictive of these is projectivity. Most constraints are formulated on fully specified structures, which makes them hard to integrate into models where structures are composed from lexical information. In this paper, we show how two empirically relevant relaxations of projectivity can be lexicalized, and how combining the resulting lexicons with a regular means of syntactic composition gives rise to a hierarchy of mildly context-sensitive dependency languages. Our results provide fundamental insights into the relation between structural properties of dependency representations and notions of formal power.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009