Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Mildly Non-Projective Dependency Grammar
Uppsala universitet, Institutionen för lingvistik och filologi. (Datorlingvistik)ORCID iD: 0000-0002-2492-9872
2013 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 39, no 2, 355-387 p.Article in journal (Refereed) Published
Abstract [en]

Syntactic representations based on word-to-word dependencies have a long-standing tradition in descriptive linguistics, and receive considerable interest in many applications. Nevertheless, dependency syntax has remained somewhat of an island from a formal point of view. Moreover, most formalisms available for dependency grammar are restricted to projective analyses, and thus not able to support natural accounts of phenomena such as wh-movement and cross–serial dependencies. In this article we present a formalism for non-projective dependency grammar in the framework of linear context-free rewriting systems. A characteristic property of our formalism is a close correspondence between the non-projectivity of the dependency trees admitted by a grammar on the one hand, and the parsing complexity of the grammar on the other. We show that parsing with unrestricted grammars is intractable. We therefore study two constraints on non-projectivity, block-degree and well-nestedness. Jointly, these two constraints define a class of “mildly” non-projective dependency grammars that can be parsed in polynomial time. An evaluation on five dependency treebanks shows that these grammars have a good coverage on empirical data.

Place, publisher, year, edition, pages
Cambridge, MA, USA: MIT Press, 2013. Vol. 39, no 2, 355-387 p.
National Category
Language Technology (Computational Linguistics)
Research subject
Computational Linguistics
Identifiers
URN: urn:nbn:se:liu:diva-100297DOI: 10.1162/COLI_a_00125ISI: 000318556900004OAI: oai:DiVA.org:liu-100297DiVA: diva2:661421
Available from: 2013-11-04 Created: 2013-11-04 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

fulltext(714 kB)50 downloads
File information
File name FULLTEXT01.pdfFile size 714 kBChecksum SHA-512
60299b5b04763932f66f78c2f09cf50779a3e4f24b6535b2a6e6b6e5af0be536a2ddfb33b3c2d95305f050c929c1595e588193565ce088c040bc6a984e5ee63b
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Kuhlmann, Marco
In the same journal
Computational linguistics - Association for Computational Linguistics (Print)
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
Total: 50 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 66 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf