Gómez-Rodríguez, Carlos, Carroll, John and Weir, David (2011) Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing. Computational Linguistics, 37 (3). 541-586.. ISSN 0891-2017
![]() |
PDF
Restricted to SRO admin only Download (663kB) |
Abstract
We introduce dependency parsing schemata, a formal framework based on Sikkel's parsing schemata for constituency parsers, which can be used to describe, analyze, and compare dependency parsing algorithms. We use this framework to describe several well-known projective and non-projective dependency parsers, build correctness proofs, and establish formal relationships between them. We then use the framework to dene new polynomial-time parsing algorithms for various mildly non-projective dependency formalisms, including well-nested structures with their gap degree bounded by a constant k in time O(n 5+2k), and a new class that includes all gap degree k structures present in several natural language treebanks (which we call mildly ill-nested structures for gap degree k) in time O(n 4+3k). Finally, we illustrate how the parsing schema framework can be applied to Link Grammar, a dependency-related formalism.
Item Type: | Article |
---|---|
Schools and Departments: | School of Engineering and Informatics > Informatics |
Depositing User: | John Carroll |
Date Deposited: | 06 Feb 2012 21:27 |
Last Modified: | 02 Jul 2019 22:49 |
URI: | http://sro.sussex.ac.uk/id/eprint/31287 |
View download statistics for this item
📧 Request an update