Topological Dependency Trees: A Constraint-Based Account of Linear Precedence

Topological Dependency Trees: A Constraint-Based Account of Linear Precedence Denys Duchier Programming Systems Lab Universit¨at des Saarlandes, Geb. 45 Postfach 15 11 50 66041 Saarbr¨ucken, Germany duchier@ps.uni-sb.de Ralph Debusmann Computational Linguistics Universit¨at des Saarlandes, Geb. 17 Postfach 15 11 50 66041 Saarbr¨ucken, Germany rade@coli.uni-sb.de Abstract We describe a new framework for de- pendency grammar, with a modular de- composition of immediate dependency and linear precedence. Our approach distinguishes two orthogonal yet mutu- ally constraining structures: a syntactic dependency tree and a topological de- pendency tree. The syntax tree is non- projective and even non-ordered, while the topological tree is projective and partially ordered. 1 Introduction Linear precedence in so-called free word order languages remains challenging for modern gram- mar formalisms. To address this issue, we pro- pose a new framework for dependency gram- mar which supports the modular decomposition of immediate dependency and linear precedence. Duchier (1999) formulated a constraint-based ax- iomatization of dependency parsing which char- acterized well-formed syntax trees but ignored is- sues of word order. In this article, we develop a complementary approach dedicated to the treat- ment of linear precedence. Our framework distinguishes two orthogonal, yet mutually constraining structures: a syntactic dependency tree (ID tree) and a topological de- pendency tree (LP tree). While edges of the ID tree are labeled by syntactic roles, those of the LP tree are labeled by topological fields (Bech, 1955). The shape of the LP tree is a flattening of the ID tree’s obtained by allowing nodes to ‘climb up’ to land in an appropriate field at a host node where that field is available. Our theory of ID/LP trees is formulated in terms of (a) lexicalized con- straints and (b) principles governing e.g. climbing conditions. In Section 2 we discuss the difficulties pre- sented by discontinuous constructions in free word order languages, and briefly touch on the limitations of Reape’s (1994) popular theory of ‘word order domains’. In Section 3 we introduce the concept of topological dependency tree. In Section 4 we outline the formal framework for our theory of ID/LP trees. Finally, in Section 5 we illustrate our approach with an account of the word-order phenomena in the verbal complex of German verb final sentences. 2 Discontinuous Constructions In free word order languages, discontinuous con- structions occur frequently. German, for example, is subject to scrambling and partial extraposition. In typical phrase structure based analyses, such phenomena lead to e.g. discontinuous VPs: (1) (dass) (that) aeinen Mann manacc Maria Marianom tozu lieben love versucht tries whose natural syntax tree exhibits crossing edges: S NP V VP NP V DET N (dass) einen Mann Maria zu lieben versucht Since this is classically disallowed, discontinu- ous constituents must often be handled indirectly through grammar extensions such as traces. Reape (1994) proposed the theory of word or- der domains which became quite popular in the HPSG community and inspired others such as M¨uller (1999) and Kathol (2000). Reape distin- guished two orthogonal tree structures: (a) the un- ordered syntax tree, (b) the …

Content truncated to 500 words