Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs
Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan · 2017
We study the Maximum Subgraph problem in deep dependency parsing.We consider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2.Our main contribution is an exact algorithm that obtains maximum subgraphs satisfying both restrictions simultaneously in time O(n 5 ).Moreover, ignoring one linguistically-rare structure descreases the complexity to O(n 4 ).We also extend our quartic-time algorithm into a practical parser with a discriminative disambiguation model and evaluate its performance on four linguistic data sets used in semantic dependency parsing.