Efficient Parsing for Head-Split Dependency Trees

Giorgio Satta, Marco Kuhlmann


Abstract
Head splitting techniques have been successfully exploited to improve the asymptotic runtime of parsing algorithms for projective dependency trees, under the arc-factored model. In this article we extend these techniques to a class of non-projective dependency trees, called well-nested dependency trees with block-degree at most 2, which has been previously investigated in the literature. We define a structural property that allows head splitting for these trees, and present two algorithms that improve over the runtime of existing algorithms at no significant loss in coverage.
Anthology ID:
Q13-1022
Volume:
Transactions of the Association for Computational Linguistics, Volume 1
Month:
Year:
2013
Address:
Venue:
TACL
SIG:
Publisher:
Note:
Pages:
267–278
Language:
URL:
https://www.aclweb.org/anthology/Q13-1022
DOI:
10.1162/tacl_a_00226
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/Q13-1022.pdf