The Complexity of Recognition of Linguistically Adequate Dependency Grammars

Details The Complexity of Recognition of Linguistically Adequate Dependency Grammars The Complexity of Recognition of Linguistically Adequate Dependency Grammars

1997-09-08

arxiv.org/abs/cmp-lg/9709001v1

Proc. ACL-EACL 1997, Madrid, Spain, pp.337-343

Computer Science

Computation and Language

8 pages, requires LaTeX2e, epsfig, latexsym, amsmath

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Recognition of Linguistically Adequate Dependency Grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Recognition of Linguistically Adequate Dependency Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Recognition of Linguistically Adequate Dependency Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-24809