@article{pitler-etal-2013-finding,
    title = "Finding Optimal 1-Endpoint-Crossing Trees",
    author = "Pitler, Emily  and
      Kannan, Sampath  and
      Marcus, Mitchell",
    editor = "Lin, Dekang  and
      Collins, Michael",
    journal = "Transactions of the Association for Computational Linguistics",
    volume = "1",
    year = "2013",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://aclanthology.org/Q13-1002",
    doi = "10.1162/tacl_a_00206",
    pages = "13--24",
    abstract = "Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8{--}99.8{\%} of dependency parses in various natural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing property can be found with an O(n4) parsing algorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint-Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP.",
}