The Complexity of Recognition of Linguistically Adequate Dependency Grammars
| dc.creator | Neuhaus, Peter | |
| dc.creator | Broeker, Norbert | |
| dc.date | 1997-09-08 | |
| dc.date.accessioned | 2026-07-07T09:10:58Z | |
| dc.date.available | 2026-07-07T09:10:58Z | |
| dc.description | 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. | |
| dc.description | 8 pages, requires LaTeX2e, epsfig, latexsym, amsmath | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9709001 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9709001 | |
| dc.identifier | Proc. ACL-EACL 1997, Madrid, Spain, pp.337-343 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151519 | |
| dc.subject | Computation and Language | |
| dc.title | The Complexity of Recognition of Linguistically Adequate Dependency Grammars | |
| dc.type | text |