Paper: Minimal-length linearizations for mildly context-sensitive dependency trees

ACL ID N09-1038
Title Minimal-length linearizations for mildly context-sensitive dependency trees
Venue Human Language Technologies
Session Main Conference
Year 2009
Authors

The extent to which the organization of nat- ural language grammars reflects a drive to minimize dependency length remains little explored. We present the first algorithm polynomial-time in sentence length for obtain- ing the minimal-length linearization of a de- pendency tree subject to constraints of mild context sensitivity. For the minimally context- sensitive case of gap-degree 1 dependency trees, we prove several properties of minimal- length linearizations which allow us to im- prove the efficiency of our algorithm to the point that it can be used on most naturally- occurring sentences. We use the algorithm to compare optimal, observed, and random sentence dependency length for both surface and deep dependencies in English and Ger- man. We find in both languages that anal- yses of s...