liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-100297DOI: 10.1162/COLI_a_00125ISI: 000318556900004OAI: diva2:661421
Available from: 2013-11-04 Created: 2013-11-04 Last updated: 2014-10-08Bibliographically approved

Open Access in DiVA

fulltext(714 kB)33 downloads
File information
File name FULLTEXT01.pdfFile size 714 kBChecksum SHA-512
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: 33 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

Altmetric score

Total: 40 hits
ReferencesLink to record
Permanent link

Direct link