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

Abstract

Dependency analysis of natural language gives rise to non-projective structures. The constraint of well-nestedness on dependency trees has been recently shown to give a good fit with empirical linguistic data. We present a reformulation of this constraint using properties of non-projective edges and show its formal relationship to level types of non-projective edges; we also derive a simple $\BigO(n^2)$ algorithm for checking well-nestedness.

Keywords

• Relationship
• between
• Non-Projective
• Edges
• Their
• Level
• Types
• Well-Nestedness