Mildly Context-Sensitive Dependency Languages

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 160–167, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Mildly Context-Sensitive Dependency Languages Marco Kuhlmann Programming Systems Lab Saarland University Saarbrücken, Germany kuhlmann@ps.uni-sb.de Mathias Möhl Programming Systems Lab Saarland University Saarbrücken, Germany mmohl@ps.uni-sb.de Abstract Dependency-based representations of natu- ral language syntax require a fine balance between structural flexibility and computa- tional 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 spec- ified structures, which makes them hard to in- tegrate into models where structures are com- posed from lexical information. In this paper, we show how two empirically relevant relax- ations 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. 1 Introduction Syntactic representations based on word-to-word de- pendencies have a long tradition in descriptive lin- guistics. Lately, they have also been used in many computational tasks, such as relation extraction (Cu- lotta and Sorensen, 2004), parsing (McDonald et al., 2005), and machine translation (Quirk et al., 2005). Especially in recent work on parsing, there is a par- ticular interest in non-projective dependency struc- tures, in which a word and its dependents may be spread out over a discontinuous region of the sen- tence. These structures naturally arise in the syntactic analysis of languages with flexible word order, such as Czech (Veselá et al., 2004). Unfortunately, most formal results on non-projectivity are discouraging: While grammar-driven dependency parsers that are restricted to projective structures can be as efficient as parsers for lexicalized context-free grammar (Eis- ner and Satta, 1999), parsing is prohibitively expen- sive when unrestricted forms of non-projectivity are permitted (Neuhaus and Bröker, 1997). Data-driven dependency parsing with non-projective structures is quadratic when all attachment decisions are assumed to be independent of one another (McDonald et al., 2005), but becomes intractable when this assumption is abandoned (McDonald and Pereira, 2006). In search of a balance between structural flexibility and computational complexity, several authors have proposed constraints to identify classes of non-projec- tive dependency structures that are computationally well-behaved (Bodirsky et al., 2005; Nivre, 2006). In this paper, we focus on two of these proposals: the gap-degree restriction, which puts a bound on the number of discontinuities in the region of a sen- tence covered by a word and its dependents, and the well-nestedness condition, which constrains the ar- rangement of dependency subtrees. Both constraints have been shown to be in very good fit with data from dependency treebanks (Kuhlmann and Nivre, 2006). However, like all other such proposals, they are for- mulated on fully specified structures, which makes it hard to integrate them into a generative model, where dependency structures are composed from elemen- tary units of lexicalized information. Consequently, little is known about the generative capacity …

Content truncated to 500 words