Paper: The Complexity Of Recognition Of Linguistically Adequate Dependency Grammars

ACL ID P97-1043
Title The Complexity Of Recognition Of Linguistically Adequate Dependency Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997
Authors

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.