Dependency Locality as an Explanatory Principle for Word Order

[FLG20]

This file formalizes the worked examples of [FLG20] ("Dependency locality as an explanatory principle for word order", Language 96(2):371–412) — the §2.3–2.4 dependency trees, with every total dependency length checked against the printed figure — and transcribes its Table 2 (per-language head-final proportion and mean dependency length over UD 2.1 corpora). The Monte Carlo corpus studies of §4–5 are not formalized.

English words come from the Fragment lexicon, and the trees follow the paper's drawing convention in which a preposition heads its noun, so arc lengths match the printed diagrams. Mirror-image and reordering claims are stated through Graph.relabel/Graph.mirror, so they hold by the general invariance theorem rather than by inspection of hand-typed twins.

Examples (3)–(4): displacement and nonprojectivity

Displacement produces nonprojective trees: right extraposition in (3), where who you know modifies woman across the intervening verb, and wh-movement in (4), where what is the object of did. Both sit at gap degree 1 — the paper's point that natural languages deviate from context-freeness only mildly.

def FutrellEtAl2020.extraposition : DependencyGrammar.Graph 8

Example (3): "I think a woman arrived who you know".

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.whMovement : DependencyGrammar.Graph 8

Example (4): "I know what he thinks you did yesterday".

Equations

• One or more equations did not get rendered due to their size.

theorem FutrellEtAl2020.displacement_gap_degree_one : extraposition.gapDegree = 1 ∧ whMovement.gapDegree = 1

Displacement stays mildly non-context-free: both trees have gap degree 1.

Examples (7)–(8): short-before-long and its head-final mirror

A head with three dependent phrases of sizes 1, 2, 3. In head-initial contexts (7), placing them short-to-long after the head minimizes total dependency length; the head-final long-before-short preference (8) is its exact mirror — here literally Graph.mirror, so the equal-cost claim is Graph.totalLength_mirror, not an inspection of hand-typed twins.

def FutrellEtAl2020.shortBeforeLong : DependencyGrammar.Graph 7

(7a) A [B] [C D] [E F G]: dependents short-to-long after the head.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.longBeforeShort : DependencyGrammar.Graph 7

(7b) A [B C D] [E F] [G]: dependents long-to-short after the head.

Equations

• One or more equations did not get rendered due to their size.

theorem FutrellEtAl2020.short_before_long_head_initial : shortBeforeLong.totalLength < longBeforeShort.totalLength

(7): short-before-long wins in head-initial contexts.

theorem FutrellEtAl2020.long_before_short_head_final : shortBeforeLong.mirror.totalLength < longBeforeShort.mirror.totalLength

(8): the head-final regime is the mirror image, so long-before-short wins there at exactly the head-initial costs — by the general mirror invariance, no separate fixtures needed.

Examples (9)–(10): head-direction consistency and its exceptions

def FutrellEtAl2020.consistentChain : DependencyGrammar.Graph 4

(9a) chain A → B → C → D linearized consistently: A B C D.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.mixedChain : DependencyGrammar.Graph 4

(9b) the same chain linearized with mixed head direction: A C D B.

Equations

• One or more equations did not get rendered due to their size.

theorem FutrellEtAl2020.consistent_chain_shorter : consistentChain.totalLength < mixedChain.totalLength

(9): consistent head direction minimizes chain dependency length — the DLM route to the Greenbergian harmonic correlations.

def FutrellEtAl2020.dependentsSameSide : DependencyGrammar.Graph 4

(10a) A B C D: both dependents (B and C–D) after the head A.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.dependentsSplit : DependencyGrammar.Graph 4

(10b) B A C D: the one-word dependent moved before the head.

Equations

• One or more equations did not get rendered due to their size.

theorem FutrellEtAl2020.split_beats_consistency : dependentsSplit.totalLength < dependentsSameSide.totalLength

(10): with several short dependents, splitting them across the head beats consistency ([GT10]), predicting the documented exceptions (e.g. prenominal determiners in head-initial Spanish).

Example (11): heavy NP shift

The paper's flagship worked example: the cost of the verb–object–particle order is 1 for a light object (6 vs. 7) and 5 for a heavy one (11 vs. 16), deriving the weight-sensitivity of heavy NP shift (cf. example (6)).

def FutrellEtAl2020.lightParticleEarly : DependencyGrammar.Graph 5

(11a) "John threw out the trash", total dependency length 6.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.lightParticleLate : DependencyGrammar.Graph 5

(11b) "John threw the trash out", total dependency length 7.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.heavyParticleEarly : DependencyGrammar.Graph 9

(11c) "John threw out the trash sitting in the kitchen", total 11.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.heavyParticleLate : DependencyGrammar.Graph 9

(11d) "John threw the trash sitting in the kitchen out", total 16.

Equations

• One or more equations did not get rendered due to their size.

theorem FutrellEtAl2020.dlm_penalty_grows_with_weight : lightParticleLate.totalLength - lightParticleEarly.totalLength < heavyParticleLate.totalLength - heavyParticleEarly.totalLength

The DLM penalty for late particle placement grows with object weight: 1 for the light object, 5 for the heavy one.

Example (13): the random-order baseline

The attested sentence against reorderings of the same structure — stated through Graph.relabel, so "same structure" is by construction, which is what the paper's random-baseline methodology asserts.

def FutrellEtAl2020.attestedOrder : DependencyGrammar.Graph 6

(13a) "this story comes from the AP", the attested order, total 6.

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.reorderingB : DependencyGrammar.Graph 6

(13b) the reordering, as a relabeling of the attested structure.

Equations

• FutrellEtAl2020.reorderingB = FutrellEtAl2020.attestedOrder.relabel FutrellEtAl2020.σB✝

theorem FutrellEtAl2020.attested_below_reordering : attestedOrder.totalLength < reorderingB.totalLength

The attested order beats the reordering — and since reorderingB is a relabel of attestedOrder, that they share a structure is not an assertion but a definition.

Table 2: head-finality and dependency length

For each of the 46 languages measured over UD 2.1 corpora, the proportion of head-final dependencies and the mean dependency length per word at sentence lengths 10, 15, and 20. The paper reads the table together with its scatterplots: more head-final languages have longer dependencies, and the languages with especially long dependencies are predominantly head-final ones such as Japanese, Korean, and Turkish.

Values are scaled integers — permille for the head-final proportion, ×100 for dependency lengths (mirroring the table's two decimal places) — so that downstream list computations kernel-decide. UD language codes are linglib annotation for cross-study joins (Studies/LevshinaEtAl2023); they are not printed in the table, but match the language keys of the paper's analysis pipeline, the CLIQS codebase its footnote cites (https://github.com/langprocgroup/cliqs/, typology3.csv).

structure FutrellEtAl2020.DepLengthRow : Type

One row of Table 2: head-final proportion and mean per-word dependency lengths for one UD 2.1 language.

• language : String

  Language name as printed in the table (e.g. "Norwegian (B)").

• isoCode : String

  UD language code (linglib annotation, not part of the table).

• propHeadFinal1000 : ℕ

  Proportion of head-final dependencies, permille (881 = 0.881).

• depLengthAt10_100 : ℕ

  Mean dependency length per word at sentence length 10, ×100.

• depLengthAt15_100 : ℕ

  Mean dependency length per word at sentence length 15, ×100.

• depLengthAt20_100 : ℕ

  Mean dependency length per word at sentence length 20, ×100.

@[instance_reducible]

instance FutrellEtAl2020.instReprDepLengthRow : Repr DepLengthRow

Equations

• FutrellEtAl2020.instReprDepLengthRow = { reprPrec := FutrellEtAl2020.instReprDepLengthRow.repr }

def FutrellEtAl2020.instReprDepLengthRow.repr : DepLengthRow → ℕ → Std.Format

Equations

• One or more equations did not get rendered due to their size.

@[instance_reducible]

instance FutrellEtAl2020.instDecidableEqDepLengthRow : DecidableEq DepLengthRow

Equations

• FutrellEtAl2020.instDecidableEqDepLengthRow = FutrellEtAl2020.instDecidableEqDepLengthRow.decEq

def FutrellEtAl2020.instDecidableEqDepLengthRow.decEq (x✝ x✝¹ : DepLengthRow) : Decidable (x✝ = x✝¹)

Equations

• One or more equations did not get rendered due to their size.

def FutrellEtAl2020.table2 : List DepLengthRow

Table 2, in the paper's row order (descending head-final proportion).

Equations

• One or more equations did not get rendered due to their size.