Edge-Linear First-Order Dependency Parsing with Undirected Minimum Spanning Tree Inference

Effi Levi, Roi Reichart, Ari Rappoport

The run time complexity of state-of-the-art inference algorithms in graph-based dependency parsing is super-linear in the number of input words (n). Recently, pruning algorithms fo…