Bach, Brown & Marslen-Wilson (1986): crossed vs nested dependencies

Dutch verb clusters cross their NP–verb dependencies (NP₁ NP₂ NP₃ V₁ V₂ V₃), German nests them (NP₁ NP₂ NP₃ V₃ V₂ V₁). Matched Dutch and German sentences are rated equally comprehensible at one level of embedding; from two levels on Dutch is easier on both ratings and probe accuracy (Tables 1, 3) — yet only the nested pattern is parsable by a push-down store, so parsing difficulty does not track stack-parsability ([Eve75], [BKPZ82]).

An NP–verb binding is a permutation σ : Equiv.Perm (Fin n): crossed is Equiv.refl, nested is Fin.revPerm. totalIntegrationCost formalizes the paper's informal argument that crossed orders integrate each NP into the matrix structure as its verb arrives while nested orders hold every NP until the cluster ends.

Main statements

• totalIntegrationCost_refl, totalIntegrationCost_revPerm: closed forms n(n−1)/2 (crossed) and n(n−1) (nested).
• cost_gap: the gap equals the whole crossed cost — 1 at two verbs, where the experiment finds no difference, 3 and 6 at Levels 3–4, where it does.
• nonprojective_is_cheaper: the antitone (stack-parsable) binding is the expensive one.

References

• [BBMW86]: Crossed and nested dependencies in German and Dutch: A psycholinguistic study. Language and Cognitive Processes 1.
• [Eve75]: The transformational cycle in Dutch and German.
• [BKPZ82]: Cross-serial dependencies in Dutch.

def BachBrownMarslenWilson1986.integratedCount {n : ℕ} (σ : Equiv.Perm (Fin n)) (k : ℕ) : ℕ

NPs matrix-integrated after k verbs heard: NP i counts iff every verb on the control chain from its verb V_{σ i} up to the matrix verb V_{σ 0} has been heard, i.e. max (σ 0) (σ i) < k.

Equations

• BachBrownMarslenWilson1986.integratedCount σ_2 k = 0
• BachBrownMarslenWilson1986.integratedCount σ_2 k = List.countP (fun (i : ℕ) => if hi : i < m + 1 then decide (max ↑(σ_2 ⟨0, ⋯⟩) ↑(σ_2 ⟨i, hi⟩) < k) else false) (List.range (m + 1))

def BachBrownMarslenWilson1986.unintegratedCount {n : ℕ} (σ : Equiv.Perm (Fin n)) (k : ℕ) : ℕ

NPs still awaiting matrix-connected integration after k verbs.

Equations

• BachBrownMarslenWilson1986.unintegratedCount σ k = n - BachBrownMarslenWilson1986.integratedCount σ k

theorem BachBrownMarslenWilson1986.integratedCount_refl {n : ℕ} (k : ℕ) : integratedCount (Equiv.refl (Fin n)) k = min k n

Crossed integration: min k n NPs are integrated after k verbs.

theorem BachBrownMarslenWilson1986.integratedCount_revPerm {n : ℕ} (k : ℕ) : integratedCount Fin.revPerm k = if k ≥ n then n else 0

Nested integration: nothing integrates until all n verbs are heard.

theorem BachBrownMarslenWilson1986.unintegratedCount_refl {n : ℕ} (k : ℕ) : unintegratedCount (Equiv.refl (Fin n)) k = n - min k n

theorem BachBrownMarslenWilson1986.unintegratedCount_revPerm {n : ℕ} (k : ℕ) : unintegratedCount Fin.revPerm k = if k ≥ n then 0 else n

def BachBrownMarslenWilson1986.totalIntegrationCost {n : ℕ} (σ : Equiv.Perm (Fin n)) : ℕ

Cumulative unintegrated NPs across the cluster.

Equations

• BachBrownMarslenWilson1986.totalIntegrationCost σ = ∑ k ∈ Finset.range n, BachBrownMarslenWilson1986.unintegratedCount σ (k + 1)

theorem BachBrownMarslenWilson1986.totalIntegrationCost_refl (n : ℕ) : totalIntegrationCost (Equiv.refl (Fin n)) = n * (n - 1) / 2

The crossed (Dutch) cluster costs n(n−1)/2: one NP integrates per verb.

theorem BachBrownMarslenWilson1986.totalIntegrationCost_revPerm (n : ℕ) : totalIntegrationCost Fin.revPerm = n * (n - 1)

The nested (German) cluster costs n(n−1): all n NPs float until the last verb.

theorem BachBrownMarslenWilson1986.totalIntegrationCost_revPerm_eq_two_mul (n : ℕ) : totalIntegrationCost Fin.revPerm = 2 * totalIntegrationCost (Equiv.refl (Fin n))

Nested costs exactly twice crossed, at every cluster size.

theorem BachBrownMarslenWilson1986.crossed_lt_nested {n : ℕ} (hn : 2 ≤ n) : totalIntegrationCost (Equiv.refl (Fin n)) < totalIntegrationCost Fin.revPerm

Crossed is strictly cheaper as soon as the cluster has two verbs.

theorem BachBrownMarslenWilson1986.cost_gap (n : ℕ) : totalIntegrationCost Fin.revPerm - totalIntegrationCost (Equiv.refl (Fin n)) = totalIntegrationCost (Equiv.refl (Fin n))

The gap equals the whole crossed cost n(n−1)/2.

theorem BachBrownMarslenWilson1986.level_costs : (totalIntegrationCost (Equiv.refl (Fin 2)), totalIntegrationCost (Equiv.refl (Fin 3)), totalIntegrationCost (Equiv.refl (Fin 4))) = (1, 3, 6) ∧ (totalIntegrationCost Fin.revPerm, totalIntegrationCost Fin.revPerm, totalIntegrationCost Fin.revPerm) = (2, 6, 12)

Levels 2–4 (clusters of 2–4 verbs): crossed costs 1, 3, 6; nested 2, 6, 12.

theorem BachBrownMarslenWilson1986.nonprojective_is_cheaper {n : ℕ} (hn : 2 ≤ n) : ¬Antitone ⇑(Equiv.refl (Fin n)) ∧ Antitone ⇑Fin.revPerm ∧ totalIntegrationCost (Equiv.refl (Fin n)) < totalIntegrationCost Fin.revPerm

The nested binding is antitone — the projective, stack-parsable pattern ([BKPZ82]) — and the crossed one is not; the costs run the other way, so parsing difficulty does not track stack-parsability.