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:
Cambridge, MA
Editors:
Dekang Lin, Michael Collins
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
267–278
Language:
URL:
https://aclanthology.org/Q13-1022
DOI:
10.1162/tacl_a_00226
Bibkey:
Cite (ACL):
Giorgio Satta and Marco Kuhlmann. 2013. Efficient Parsing for Head-Split Dependency Trees. Transactions of the Association for Computational Linguistics, 1:267–278.
Cite (Informal):
Efficient Parsing for Head-Split Dependency Trees (Satta & Kuhlmann, TACL 2013)
Copy Citation:
PDF:
https://preview.aclanthology.org/nschneid-patch-1/Q13-1022.pdf