The Complexity of Recognition of Linguistically Adequate Dependency Grammars

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 is NP-complete.

8 pages, requires LaTeX2e, epsfig, latexsym, amsmath

Cited by in corpus (4)

• Framework and Resources for Natural Language Parser Evaluation
• Message-Passing Protocols for Real-World Parsing -- An Object-Oriented Model and its Preliminary Evaluation
• How to define a context-free backbone for DGs: Implementing a DG in the LFG formalism
• Separating Surface Order and Syntactic Relations in a Dependency Grammar