de Marneffe & Nivre 2019: UD enhanced dependencies for English LD and coordination

[dMN19]

Worked English examples illustrating Universal Dependencies' basic vs enhanced representations (cf. §4.2 and Figure 9 of [dMN19]). The substrate — gap-filling (DepGrammar.LongDistance.fillGap) and shared-dependent propagation (DepGrammar.Coordination.enhanceSharedDeps) — lives in the corresponding substrate files.

Examples

Long-distance dependencies

• exWhatDidJohnSee, exWhoSawMary, exWhoDidJohnSee — wh-question fixtures (object extraction, subject question, object with who).
• exTheBookThatJohnRead / _enhanced — object relative clause and its enhanced graph.
• exJohnThinksThatMarySleeps, exJohnThinksMarySleeps, exJohnWondersIfMarySleeps, exJohnWondersWhatMarySaw — complement clauses with and without overt complementizer, with and without embedded extraction.

Coordination

• exJohnAndMarySleep, exJohnSleepsAndMarySleeps — NP and S coordination (no shared-dependent propagation needed).
• exJohnSeesAndHearsMary / _enhanced — VP coordination; the enhanced graph adds obj from hears to Mary.
• exOldAndWiseMan — adjective coordination.
• exRNR / _enhanced — Right Node Raising; the enhanced graph adds obj to the second-conjunct verb.

Implementation notes

Fixtures use Word.mk' (featureless); the worked theorems are structural (hasUniqueHeads, edge counts, decide over UD relation labels) and agreement / valence checks pass vacuously. A future revision could add feature-tagged fixtures if richer parallelism theorems are wanted.

Wh-question fixtures

def DeMarneffeNivre2019.exWhatDidJohnSee : DepGrammar.DepTree

"What did John see?" — object wh-question (basic tree). Words: what(0) did(1) John(2) see(3). The wh-word attaches as obj of the main verb.

Equations

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

def DeMarneffeNivre2019.exWhoSawMary : DepGrammar.DepTree

"Who saw Mary?" — subject wh-question (no gap needed).

Equations

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

def DeMarneffeNivre2019.exWhoDidJohnSee : DepGrammar.DepTree

"Who did John see?" — object wh-question with who.

Equations

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

Relative-clause fixtures

def DeMarneffeNivre2019.exTheBookThatJohnRead : DepGrammar.DepTree

"the book that John read" — object relative clause (basic tree). In UD the relative clause attaches via acl from head noun to RC verb; the gap (book as obj of read) is implicit.

Equations

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

def DeMarneffeNivre2019.exTheBookThatJohnRead_enhanced : DepGrammar.DepGraph

Enhanced graph for "the book that John read": book is added as obj of read.

Equations

• DeMarneffeNivre2019.exTheBookThatJohnRead_enhanced = DepGrammar.LongDistance.fillGap DeMarneffeNivre2019.exTheBookThatJohnRead 1 4 DepGrammar.LongDistance.GapType.objGap

Complement-clause fixtures

def DeMarneffeNivre2019.exJohnThinksThatMarySleeps : DepGrammar.DepTree

"John thinks that Mary sleeps" — that-complement (no gap).

Equations

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

def DeMarneffeNivre2019.exJohnThinksMarySleeps : DepGrammar.DepTree

"John thinks Mary sleeps" — bare complement (that-omission, no gap).

Equations

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

def DeMarneffeNivre2019.exJohnWondersIfMarySleeps : DepGrammar.DepTree

"John wonders if Mary sleeps" — if-complement (no gap).

Equations

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

def DeMarneffeNivre2019.exJohnWondersWhatMarySaw : DepGrammar.DepTree

"John wonders what Mary saw" — embedded wh-question. Words: John(0) wonders(1) what(2) Mary(3) saw(4).

Equations

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

Coordination fixtures

def DeMarneffeNivre2019.exJohnAndMarySleep : DepGrammar.DepTree

"John and Mary sleep" — NP coordination.

Equations

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

def DeMarneffeNivre2019.exJohnSleepsAndMarySleeps : DepGrammar.DepTree

"John sleeps and Mary sleeps" — S coordination.

Equations

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

def DeMarneffeNivre2019.exJohnSeesAndHearsMary : DepGrammar.DepTree

"John sees and hears Mary" — VP coordination (basic tree). Mary attaches as obj of sees only; hears is conj of sees.

Equations

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

def DeMarneffeNivre2019.exJohnSeesAndHearsMary_enhanced : DepGrammar.DepGraph

Enhanced graph for "John sees and hears Mary": Mary is obj of both sees and hears (shared-dep propagation).

Equations

• DeMarneffeNivre2019.exJohnSeesAndHearsMary_enhanced = DepGrammar.Coordination.enhanceSharedDeps DeMarneffeNivre2019.exJohnSeesAndHearsMary

def DeMarneffeNivre2019.exOldAndWiseMan : DepGrammar.DepTree

"the happy and smart boy" — adjective coordination.

Equations

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

def DeMarneffeNivre2019.exRNR : DepGrammar.DepTree

"John likes and Mary hates pizza" — Right Node Raising (basic tree). pizza attaches to likes only.

Equations

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

def DeMarneffeNivre2019.exRNR_enhanced : DepGrammar.DepGraph

Enhanced graph for RNR: pizza is obj of both verbs.

Equations

• DeMarneffeNivre2019.exRNR_enhanced = DepGrammar.Coordination.enhanceSharedDeps DeMarneffeNivre2019.exRNR

Smoke tests

Worked theorems — long-distance dependencies

theorem DeMarneffeNivre2019.whatDidJohnSee_has_wh : Option.map (fun (x : Word) => x.features.isWh) exWhatDidJohnSee.words[0]? = some true

Object wh-questions have a [wh] filler at index 0.

theorem DeMarneffeNivre2019.whoSawMary_no_gap : DepGrammar.LongDistance.isLDWellFormed exWhoSawMary [] = true

Subject wh-questions don't need gaps (empty gap list).

theorem DeMarneffeNivre2019.relclause_enhanced_has_obj : (exTheBookThatJohnRead_enhanced.deps.any fun (d : DepGrammar.Dependency) => d.headIdx == 4 && d.depIdx == 1 && d.depType == UD.DepRel.obj) = true

The enhanced graph for "the book that John read" has the obj-gap edge.

theorem DeMarneffeNivre2019.relclause_basic_lacks_obj : ¬(exTheBookThatJohnRead.deps.any fun (d : DepGrammar.Dependency) => d.headIdx == 4 && d.depIdx == 1 && d.depType == UD.DepRel.obj) = true

The basic tree of "the book that John read" does NOT have this obj edge.

theorem DeMarneffeNivre2019.relclause_enhanced_more_edges : exTheBookThatJohnRead_enhanced.deps.length > exTheBookThatJohnRead.deps.length

The enhanced graph has strictly more edges than the basic tree.

theorem DeMarneffeNivre2019.relclause_enhanced_not_tree : DepGrammar.hasUniqueHeads { words := exTheBookThatJohnRead_enhanced.words, deps := exTheBookThatJohnRead_enhanced.deps, rootIdx := exTheBookThatJohnRead_enhanced.rootIdx } = false

The enhanced relclause graph violates unique-heads (book has edges from both det and obj), per [dMN19] §4.4.

theorem DeMarneffeNivre2019.relclause_basic_is_tree : DepGrammar.hasUniqueHeads exTheBookThatJohnRead = true

The basic relclause tree IS a tree (unique heads).

theorem DeMarneffeNivre2019.relclause_objExtraction_derived : DepGrammar.LongDistance.extractionLabel exTheBookThatJohnRead exTheBookThatJohnRead_enhanced 1 = some DepGrammar.LongDistance.GapType.objGap

extractionLabel recovers the object-gap label from the basic/enhanced diff at the head-noun index.

theorem DeMarneffeNivre2019.complement_no_gap : DepGrammar.LongDistance.checkNoIslandViolation exJohnThinksThatMarySleeps [] = true

Complement clauses have no filler-gap dependencies (vacuous heuristic island check).

Worked theorems — coordination

theorem DeMarneffeNivre2019.johnAndMary_cat_match : DepGrammar.Coordination.checkCatMatch exJohnAndMarySleep = true

NP coordination has matching categories.

theorem DeMarneffeNivre2019.johnSleepsAndMarySleeps_cat_match : DepGrammar.Coordination.checkCatMatch exJohnSleepsAndMarySleeps = true

S coordination has matching categories.

theorem DeMarneffeNivre2019.seesAndHears_argstr_match : DepGrammar.Coordination.checkArgStrMatch exJohnSeesAndHearsMary = true

VP coordination has matching argument structures (vacuously, since the example uses featureless verbs).

theorem DeMarneffeNivre2019.oldAndWise_cat_match : DepGrammar.Coordination.checkCatMatch exOldAndWiseMan = true

Adjective coordination has matching categories.

theorem DeMarneffeNivre2019.coord_enhanced_has_shared_obj : (exJohnSeesAndHearsMary_enhanced.deps.any fun (d : DepGrammar.Dependency) => d.headIdx == 3 && d.depIdx == 4 && d.depType == UD.DepRel.obj) = true

enhanceSharedDeps adds the missing obj edge from hears to Mary.

theorem DeMarneffeNivre2019.coord_basic_lacks_shared_obj : ¬(exJohnSeesAndHearsMary.deps.any fun (d : DepGrammar.Dependency) => d.headIdx == 3 && d.depIdx == 4 && d.depType == UD.DepRel.obj) = true

The basic VP-coord tree does NOT have the shared obj edge.

theorem DeMarneffeNivre2019.coord_enhanced_more_edges : exJohnSeesAndHearsMary_enhanced.deps.length > exJohnSeesAndHearsMary.deps.length

The coord enhanced graph has strictly more edges than the basic tree.

theorem DeMarneffeNivre2019.coord_enhanced_not_tree : DepGrammar.hasUniqueHeads { words := exJohnSeesAndHearsMary_enhanced.words, deps := exJohnSeesAndHearsMary_enhanced.deps, rootIdx := exJohnSeesAndHearsMary_enhanced.rootIdx } = false

The coord enhanced graph violates unique-heads (Mary has incoming obj from both sees and hears), per [dMN19] §4.4.

theorem DeMarneffeNivre2019.coord_basic_is_tree : DepGrammar.hasUniqueHeads exJohnSeesAndHearsMary = true

The basic coord tree IS a tree (unique heads).

theorem DeMarneffeNivre2019.rnr_enhanced_has_shared_obj : (exRNR_enhanced.deps.any fun (d : DepGrammar.Dependency) => d.headIdx == 4 && d.depIdx == 5 && d.depType == UD.DepRel.obj) = true

RNR enhancement propagates obj to the second-conjunct verb.

theorem DeMarneffeNivre2019.rnr_enhanced_not_tree : DepGrammar.hasUniqueHeads { words := exRNR_enhanced.words, deps := exRNR_enhanced.deps, rootIdx := exRNR_enhanced.rootIdx } = false

RNR enhanced graph violates unique-heads.