tailieunhanh - Báo cáo khoa học: "The Complexity of Recognition of Linguistically Adequate Dependency Grammars"

Results of computational complexity exist for a wide range of phrase structure-based grammar formalisms, while there is an apparent lack of such results for dependency-based formalisms. We here adapt a result on the complexity 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. | The Complexity of Recognition of Linguistically Adequate Dependency Grammars Peter Neuhaus Norbert Broker Gf Computational Linguistics Research Group Freiburg University FriedrichstraBe 50 D-79098 Freiburg Germany email @ Abstract Results of computational complexity exist for a wide range of phrase structure-based grammar formalisms while there is an apparent lack of such results for dependency-based formalisms. We here adapt a result on the complexity 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 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 understanding of semantically motivated dependency relations. 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 dependency grammarians view Gaifman s conception as an unfortunate one cf. Section 2 . To our knowledge there has been no other formal study of 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 capacity will correspond to equally slight increases in computational 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 separation of dominance and precedence as a major part of current DG theorizing. Thus no current .