Minimal-length linearizations for mildly context-sensitive dependency trees
Y. Albert Park, Roger Lévy · 2009
The extent to which the organization of natural language grammars reflects a drive to minimize dependency length remains little explored.We present the first algorithm polynomial-time in sentence length for obtaining the minimal-length linearization of a dependency tree subject to constraints of mild context sensitivity.For the minimally contextsensitive case of gap-degree 1 dependency trees, we prove several properties of minimallength linearizations which allow us to improve the efficiency of our algorithm to the point that it can be used on most naturallyoccurring sentences.We use the algorithm to compare optimal, observed, and random sentence dependency length for both surface and deep dependencies in English and German.We find in both languages that analyses of surface and deep dependencies yield highly similar results, and that mild contextsensitivity affords very little reduction in minimal dependency length over fully projective linearizations; but that observed linearizations in German are much closer to random and farther from minimal-length linearizations than in English.