Paper: Dynamic Programming for Higher Order Parsing of Gap-Minding Trees

ACL ID D12-1044
Title Dynamic Programming for Higher Order Parsing of Gap-Minding Trees
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2012
Authors

We introduce gap inheritance, a new struc- tural property on trees, which provides a way to quantify the degree to which intervals of de- scendants can be nested. Based on this prop- erty, two new classes of trees are derived that provide a closer approximation to the set of plausible natural language dependency trees than some alternative classes of trees: unlike projective trees, a word can have descendants in more than one interval; unlike spanning trees, these intervals cannot be nested in ar- bitrary ways. The 1-Inherit class of trees has exactly the same empirical coverage of natural language sentences as the class of mildly non- projective trees, yet the optimal scoring tree can be found in an order of magnitude less time. Gap-minding trees (the second class) have the property that ...