The Complexity of Recognition of Linguistically Adequate Dependency Grammars
<|reference_start|>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 NP-complete.<|reference_end|>
@article{neuhaus1997the,
    title={The Complexity of Recognition of Linguistically Adequate Dependency
  Grammars},
    author={Peter Neuhaus, Norbert Broeker (University of Freiburg)},
    journal={Proc. ACL-EACL 1997, Madrid, Spain, pp.337-343},
    year={1997},
    archivePrefix={arXiv},
    eprint={cmp-lg/9709001},
    primaryClass={cmp-lg cs.CL}
}