The Complexity of Recognition of Linguistically Adequate Dependency Grammars

The Complexity of Recognition of Linguistically Adequate Dependency Grammars Peter Neuhaus Norbert Briiker Computational Linguistics Research Group Freiburg University, Friedrichstrage 50 D-79098 Freiburg, Germany email: { neuhaus,nobi } @ coling.uni-freiburg.de Abstract Results of computational complexity exist for a wide range of phrase structure-based gram- mar formalisms, while there is an apparent lack of such results for dependency-based for- malisms. We here adapt a result on the com- plexity of ID/LP-grammars to the dependency framework. Contrary to previous studies on heavily restricted dependency grammars, we prove that recognition (and thus, parsing) of linguistically adequate dependency grammars is~A/T'-complete. 1 Introduction The introduction of dependency grammar (DG) into modern linguistics is marked by Tesni~re (1959). His conception addressed didactic goals and, thus, did not aim at formal precision, but rather at an intuitive un- derstanding of semantically motivated dependency re- lations. An early formalization was given by Gaifman (1965), who showed the generative capacity of DG to be (weakly) equivalent to standard context-free grammars. Given this equivalence, interest in DG as a linguistic framework diminished considerably, although many de- pendency grammarians view Gaifman's conception as an unfortunate one (cf. Section 2). To our knowledge, there has been no other formal study of DG.This is reflected by a recent study (Lombardo & Lesmo, 1996), which applies the Earley parsing technique (Earley, 1970) to DG, and thereby achieves cubic time complexity for the analysis of DG. In their discussion, Lombardo & Lesmo express their hope that slight increases in generative ca- pacity will correspond to equally slight increases in com- putational complexity. It is this claim that we challenge here. After motivating non-projective analyses for DG, we investigate various variants of DG and identify the sep- aration of dominance and precedence as a major part of current DG theorizing. Thus, no current variant of DG (not even Tesni~re's original formulation) is compatible with Gaifman' s conception, which seems to be motivated by formal considerations only (viz., the proof of equiva- lence). Section 3 advances our proposal, which cleanly separates dominance and precedence relations. This is il- lustrated in the fourth section, where we give a simple en- coding of an A/P-complete problem in a discontinuous DG. Our proof of A/79-completeness, however, does not rely on discontinuity, but only requires unordered trees. It is adapted from a similar proof for unordered context- free grammars (UCFGs) by Barton (1985). 2 Versions of Dependency Grammar The growing interest in the dependency concept (which roughly corresponds to the O-roles of GB, subcatego- rization in HPSG, and the so-called domain of locality of TAG) again raises the issue whether non-lexical cat- egories are necessary for linguistic analysis. After re- viewing several proposals in this section, we argue in the next section that word order -- the description of which is the most prominent difference between PSGs and DGs -- can adequately be described without reference to non- lexical categories. Standard PSG trees are projective, i.e., no branches cross when the terminal nodes are projected onto the input string. In contrast …

Content truncated to 500 words