Sampath Kannan


pdf bib
Finding Optimal 1-Endpoint-Crossing Trees
Emily Pitler | Sampath Kannan | Mitchell Marcus
Transactions of the Association for Computational Linguistics, Volume 1

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.


Dynamic Programming for Higher Order Parsing of Gap-Minding Trees
Emily Pitler | Sampath Kannan | Mitchell Marcus
Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning