@article{pitler-etal-2013-finding,
title = "Finding Optimal 1-Endpoint-Crossing Trees",
author = "Pitler, Emily and
Kannan, Sampath and
Marcus, Mitchell",
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.",
}
Markdown (Informal)
[Finding Optimal 1-Endpoint-Crossing Trees](https://aclanthology.org/Q13-1002) (Pitler et al., TACL 2013)
ACL