Kuhlmann & Nivre 2006: Mildly Non-Projective Dependency Structures

[KN06]

Figure 2a's planar-but-not-projective structure, and the treebank coverage data of Table 1: prevalence of gap degree, well-nestedness, and planarity in the Prague and Danish dependency treebanks.

Main declarations

• KuhlmannNivre2006.planarNotProjective: Figure 2a, adapted to a single root, separating planarity from projectivity
• KuhlmannNivre2006.TreebankCoverage: coverage row (percentages scaled x100)
• KuhlmannNivre2006.pdt, KuhlmannNivre2006.ddt: Table 1 rows
• KuhlmannNivre2006.wellNested_near_universal: well-nestedness covers ≥99% of both treebanks
• KuhlmannNivre2006.gapDeg_leq1_sufficient: gap degree ≤ 1 covers ≥99% of both treebanks
• KuhlmannNivre2006.planarity_insufficient: planarity covers less than well-nestedness

Figure 2a: planar but not projective

def KuhlmannNivre2006.planarNotProjective : DependencyGrammar.Graph 4

Planar but not projective: no crossing links, yet the positions dominated by 0 are {0, 3}, which is not an interval.

Figure 2a's own witness is a forest, with the skipped position a second root; this adapts it to a single root. The root sits at position 2, inside the gap, and it has to: the paper observes that in a planar tree every gap contains the root, so a planar tree rooted at a sentence boundary is projective.

Equations

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

Table 1: treebank coverage

structure KuhlmannNivre2006.TreebankCoverage : Type

Treebank coverage data from [KN06], Table 1. Percentages scaled x100 for Nat arithmetic.

• name : String
• totalTrees : ℕ
• gapDeg0 : ℕ

  Percentage x100 of trees at gap degree 0 (projective)

• gapDeg1 : ℕ

  Percentage x100 of trees at gap degree 1

• gapDeg2 : ℕ

  Percentage x100 of trees at gap degree 2

• wellNested : ℕ

  Percentage x100 of well-nested trees

• planar : ℕ

  Percentage x100 of planar trees

@[instance_reducible]

instance KuhlmannNivre2006.instReprTreebankCoverage : Repr TreebankCoverage

Equations

• KuhlmannNivre2006.instReprTreebankCoverage = { reprPrec := KuhlmannNivre2006.instReprTreebankCoverage.repr }

def KuhlmannNivre2006.instReprTreebankCoverage.repr : TreebankCoverage → ℕ → Std.Format

Equations

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

def KuhlmannNivre2006.pdt : TreebankCoverage

Prague Dependency Treebank row of [KN06] Table 1.

Equations

• KuhlmannNivre2006.pdt = { name := "Prague Dependency Treebank", totalTrees := 73088, gapDeg0 := 7685, gapDeg1 := 2272, gapDeg2 := 42, wellNested := 9989, planar := 8216 }

def KuhlmannNivre2006.ddt : TreebankCoverage

Danish Dependency Treebank row of [KN06] Table 1.

Equations

• KuhlmannNivre2006.ddt = { name := "Danish Dependency Treebank", totalTrees := 4393, gapDeg0 := 8495, gapDeg1 := 1489, gapDeg2 := 16, wellNested := 9989, planar := 8641 }

theorem KuhlmannNivre2006.wellNested_near_universal : pdt.wellNested ≥ 9900 ∧ ddt.wellNested ≥ 9900

Well-nestedness covers ≥99% of both treebanks ([KN06] Table 1).

theorem KuhlmannNivre2006.gapDeg_leq1_sufficient : pdt.gapDeg0 + pdt.gapDeg1 ≥ 9900 ∧ ddt.gapDeg0 + ddt.gapDeg1 ≥ 9900

Gap degree ≤ 1 covers ≥99% of both treebanks.

theorem KuhlmannNivre2006.planarity_insufficient : pdt.planar < pdt.wellNested ∧ ddt.planar < ddt.wellNested

Planarity covers far less than well-nestedness.