Parsing Mildly Non-Projective Dependency Structures

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 291–299, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Parsing Mildly Non-projective Dependency Structures∗ Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na, Spain cgomezr@udc.es David Weir and John Carroll Department of Informatics University of Sussex, United Kingdom {davidw,johnca}@sussex.ac.uk Abstract We present parsing algorithms for vari- ous mildly non-projective dependency for- malisms. In particular, algorithms are pre- sented for: all well-nested structures of gap degree at most 1, with the same com- plexity as the best existing parsers for con- stituency formalisms of equivalent genera- tive power; all well-nested structures with gap degree bounded by any constant k; and a new class of structures with gap de- gree up to k that includes some ill-nested structures. The third case includes all the gap degree k structures in a number of de- pendency treebanks. 1 Introduction Dependency parsers analyse a sentence in terms of a set of directed links (dependencies) express- ing the head-modifier and head-complement rela- tionships which form the basis of predicate argu- ment structure. We take dependency structures to be directed trees, where each node corresponds to a word and the root of the tree marks the syn- tactic head of the sentence. For reasons of effi- ciency, many practical implementations of depen- dency parsing are restricted to projective struc- tures, in which the subtree rooted at each word covers a contiguous substring of the sentence. However, while free word order languages such as Czech do not satisfy this constraint, parsing without the projectivity constraint is computation- ally complex. Although it is possible to parse non-projective structures in quadratic time under a model in which each dependency decision is inde- pendent of all the others (McDonald et al., 2005), ∗Partially supported by MEC and FEDER (HUM2007- 66607-C04) and Xunta de Galicia (PGIDIT07SIN005206PR, INCITE08E1R104022ES, INCITE08ENA305025ES, IN- CITE08PXIB302179PR, Rede Galega de Proc. da Linguaxe e RI, Bolsas para Estad´ıas INCITE – FSE cofinanced). the problem is intractable in the absence of this as- sumption (McDonald and Satta, 2007). Nivre and Nilsson (2005) observe that most non-projective dependency structures appearing in practice are “close” to being projective, since they contain only a small proportion of non- projective arcs. This has led to the study of classes of dependency structures that lie be- tween projective and unrestricted non-projective structures (Kuhlmann and Nivre, 2006; Havelka, 2007). Kuhlmann (2007) investigates several such classes, based on well-nestedness and gap degree constraints (Bodirsky et al., 2005), relating them to lexicalised constituency grammar formalisms. Specifically, he shows that: linear context-free rewriting systems (LCFRS) with fan-out k (Vijay- Shanker et al., 1987; Satta, 1992) induce the set of dependency structures with gap degree at most k − 1; coupled context-free grammars in which the maximal rank of a nonterminal is k (Hotz and Pitsch, 1996) induce the set of well-nested depen- dency structures with gap degree at most k − 1; and LTAGs (Joshi and Schabes, 1997) induce the set of …

Content truncated to 500 words