Paper: Relationship between Non-Projective Edges Their Level Types and Well-Nestedness

ACL ID N07-2016
Title Relationship between Non-Projective Edges Their Level Types and Well-Nestedness
Venue Human Language Technologies
Session Short Paper
Year 2007
Authors

Dependency analysis of natural language gives rise to non-projective structures. The constraint of well-nestedness on de- pendency trees has been recently shown to give a good fit with empirical linguis- tic data. We present a reformulation of this constraint using properties of non- projective edges and show its formal re- lationship to level types of non-projective edges; we also derive a simple O(n 2 ) al- gorithm for checking well-nestedness.