uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Divisible Transition Systems and Multiplanar Dependency Parsing
Uppsala University, Disciplinary Domain of Humanities and Social Sciences, Faculty of Languages, Department of Linguistics and Philology.
2013 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 39, no 4, 799-845 p.Article in journal (Refereed) Published
Abstract [en]

Transition-based parsing is a widely used approach for dependency parsing that combines high efficiency with expressive feature models. Many different transition systems have been proposed, often formalized in slightly different frameworks. In this article, we show that a large number of the known systems for projective dependency parsing can be viewed as variants of the same stack-based system with a small set of elementary transitions that can be composed into complex transitions and restricted in different ways. We call these systems divisible transition systems and prove a number of theoretical results about their expressivity and complexity. In particular, we characterize an important subclass called efficient divisible transition systems that parse planar dependency graphs in linear time. We go on to show, first, how this system can be restricted to capture exactly the set of planar dependency trees and, secondly, how the system can be generalized to k-planar trees by making use of multiple stacks. Using the first known efficient test for k-planarity, we investigate the coverage of k-planar trees in available dependency treebanks and find a very good fit for 2-planar trees. We end with an experimental evaluation showing that our 2-planar parser gives significant improvements in parsing accuracy over the corresponding 1-planar and projective parsers for data sets with non-projective dependency trees and performs on a par with the widely used arc-eager pseudo-projective parser.

Place, publisher, year, edition, pages
2013. Vol. 39, no 4, 799-845 p.
National Category
Humanities Engineering and Technology
URN: urn:nbn:se:uu:diva-212833DOI: 10.1162/COLI_a_00150ISI: 000327124100001OAI: oai:DiVA.org:uu-212833DiVA: diva2:680466
Available from: 2013-12-18 Created: 2013-12-16 Last updated: 2013-12-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Nivre, Joakim
By organisation
Department of Linguistics and Philology
In the same journal
Computational linguistics - Association for Computational Linguistics (Print)
HumanitiesEngineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
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: 231 hits
ReferencesLink to record
Permanent link

Direct link