Pickering and Barry (1991): Sentence Processing without Empty Categories

This file formalizes [PB91]'s argument that the processing of an unbounded dependency associates the filler directly with its subcategoriser and never with an empty category. An analysis with empty categories makes two associations per dependency, filler to gap and gap to verb; the gap-free analysis makes one, filler to verb. Each association spans an interval of the sentence, a pattern of associations is nested when one association lies strictly inside another (abba) and disjoint when none overlap (aabb), and nested associations are the ones that must be held open while others are formed.

Under the analysis with empty categories neither pattern lines up with nested constructions in Chomsky's sense or with the reported difficulty (Table 1): the multiple pied-piping sentence (42) has nested filler–gap and nested gap–verb associations yet is as easy as the multiple subject relative. Under the gap-free analysis the one pattern coincides with nestedness in Chomsky's sense (Table 2) and with the reported difficulty (table1, table2, difficulty, trace_prediction_fails), and it stays disjoint however far the pied-piping and the recursive passive are extended, where the empty-category analysis holds every filler to the end of the sentence (peripheralGaps_fillerVerb_disjoint, peripheralGaps_fillerGap_common). The categorial grammar of the paper's later sections derives the embedded questions (82a–c) with no empty category (der82a, der82b, der82c), and (82d) has no derivation in any rule system because the pronoun must fill an argument role of the embedded verb, which is the count invariant of van Benthem (no_der82d).

Implementation notes

Associations are spans between word positions of the paper's annotated strings, empty categories included; a nested construction in Chomsky's sense is the same relation on the lexical spans of the relative clauses, which is where the paper's removal of "nonnull" from the definition shows up. The paper's rule (80a), which combines a subject with a transitive verb before its object, is the composition of the subject's raised category with the verb, so the lexicon carries the raised entry, as in Syntax/CCG/Derivation. The semantic side of the derivations and the discussion of incremental interpretation are not formalized.

References

• [PB91]
• [vB86]

Associations and their patterns

structure PickeringBarry1991.Dependency : Type

A dependency of an annotated sentence records the positions of its filler, of the empty category the trace analysis posits, and of its subcategoriser.

• filler : ℕ
• gap : ℕ
• verb : ℕ

def PickeringBarry1991.instDecidableEqDependency.decEq (x✝ x✝¹ : Dependency) : Decidable (x✝ = x✝¹)

Equations

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

@[instance_reducible]

instance PickeringBarry1991.instDecidableEqDependency : DecidableEq Dependency

Equations

• PickeringBarry1991.instDecidableEqDependency = PickeringBarry1991.instDecidableEqDependency.decEq

def PickeringBarry1991.instReprDependency.repr : Dependency → ℕ → Std.Format

Equations

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

@[instance_reducible]

instance PickeringBarry1991.instReprDependency : Repr Dependency

Equations

• PickeringBarry1991.instReprDependency = { reprPrec := PickeringBarry1991.instReprDependency.repr }

def PickeringBarry1991.span (i j : ℕ) : NonemptyInterval ℕ

The span between two positions.

Equations

• PickeringBarry1991.span i j = { fst := min i j, snd := max i j, fst_le_snd := ⋯ }

@[simp]

theorem PickeringBarry1991.span_fst (i j : ℕ) : (span i j).toProd.1 = min i j

@[simp]

theorem PickeringBarry1991.span_snd (i j : ℕ) : (span i j).toProd.2 = max i j

def PickeringBarry1991.Dependency.fillerGap (d : Dependency) : NonemptyInterval ℕ

The filler–gap association of the trace analysis.

Equations

• d.fillerGap = PickeringBarry1991.span d.filler d.gap

def PickeringBarry1991.Dependency.gapVerb (d : Dependency) : NonemptyInterval ℕ

The gap–verb association of the trace analysis.

Equations

• d.gapVerb = PickeringBarry1991.span d.gap d.verb

def PickeringBarry1991.Dependency.fillerVerb (d : Dependency) : NonemptyInterval ℕ

The filler–verb association of the gap-free analysis.

Equations

• d.fillerVerb = PickeringBarry1991.span d.filler d.verb

theorem PickeringBarry1991.Dependency.fillerVerb_gap (f g g' v : ℕ) : { filler := f, gap := g, verb := v }.fillerVerb = { filler := f, gap := g', verb := v }.fillerVerb

The filler–verb association does not depend on where an empty category would sit, so heavy shift, extraposition and word-order freedom relocate the gap and leave it unchanged.

def PickeringBarry1991.Nested (L : List (NonemptyInterval ℕ)) : Prop

A pattern of associations is nested when one association lies strictly inside another.

Equations

• PickeringBarry1991.Nested L = ∃ a ∈ L, ∃ b ∈ L, a.During b

@[instance_reducible]

instance PickeringBarry1991.instDecidableNested (L : List (NonemptyInterval ℕ)) : Decidable (Nested L)

Equations

• PickeringBarry1991.instDecidableNested L = PickeringBarry1991.instDecidableNested._aux_1 L

def PickeringBarry1991.Disjoint (L : List (NonemptyInterval ℕ)) : Prop

A pattern of associations is disjoint when any two of them are one before the other.

Equations

• PickeringBarry1991.Disjoint L = ∀ a ∈ L, ∀ b ∈ L, a ≠ b → a.Precedes b ∨ b.Precedes a

@[instance_reducible]

instance PickeringBarry1991.instDecidableDisjoint (L : List (NonemptyInterval ℕ)) : Decidable (Disjoint L)

Equations

• PickeringBarry1991.instDecidableDisjoint L = PickeringBarry1991.instDecidableDisjoint._aux_1 L

theorem PickeringBarry1991.Disjoint.not_nested {L : List (NonemptyInterval ℕ)} (h : Disjoint L) : ¬Nested L

A disjoint pattern is not nested.

structure PickeringBarry1991.Analysis : Type

An annotated sentence records its dependencies and the spans of its relative clauses over the lexical positions.

• deps : List Dependency
• clauses : List (NonemptyInterval ℕ)

def PickeringBarry1991.Analysis.fillerGap (A : Analysis) : List (NonemptyInterval ℕ)

The filler–gap associations.

Equations

• A.fillerGap = List.map PickeringBarry1991.Dependency.fillerGap A.deps

def PickeringBarry1991.Analysis.gapVerb (A : Analysis) : List (NonemptyInterval ℕ)

The gap–verb associations.

Equations

• A.gapVerb = List.map PickeringBarry1991.Dependency.gapVerb A.deps

def PickeringBarry1991.Analysis.fillerVerb (A : Analysis) : List (NonemptyInterval ℕ)

The filler–verb associations.

Equations

• A.fillerVerb = List.map PickeringBarry1991.Dependency.fillerVerb A.deps

def PickeringBarry1991.Analysis.IsNestedConstruction (A : Analysis) : Prop

A construction is nested in Chomsky's sense when a clause lies inside another with lexical material on both sides of it.

Equations

• A.IsNestedConstruction = PickeringBarry1991.Nested A.clauses

@[instance_reducible]

instance PickeringBarry1991.Analysis.instDecidableIsNestedConstruction (A : Analysis) : Decidable A.IsNestedConstruction

Equations

• A.instDecidableIsNestedConstruction = PickeringBarry1991.Analysis.instDecidableIsNestedConstruction._aux_1 A

The four sentence types (Tables 1 and 2)

def PickeringBarry1991.subjectRelative : Analysis

The multiple subject relative (44), I saw the farmer [who]ₐ Ø [owned]ₐ the dog [which]ᵦ Ø [chased]ᵦ the cat, annotated as (46) and (56).

Equations

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

def PickeringBarry1991.objectRelative : Analysis

The multiple object relative (45), The cat [which]ₐ the dog [which]ᵦ the farmer [owned]ᵦ Ø [chased]ₐ Ø fled, annotated as (47) and (57).

Equations

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

def PickeringBarry1991.germanSubjectRelative : Analysis

The German multiple subject relative (48), Der Bauer [der]ₐ Ø das Mädchen [das]ᵦ Ø den Jungen [küßte]ᵦ [schlug]ₐ ging, annotated as (49) and (58).

Equations

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

def PickeringBarry1991.piedPiping : Analysis

The multiple pied-piping sentence (42), John found the saucer [on which]ₐ Mary [put]ₐ the cup [into which]ᵦ I [poured]ᵦ the tea Ø Ø, annotated as (50) and (59).

Equations

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

def PickeringBarry1991.sentenceTypes : List Analysis

The four sentence types of Tables 1 and 2.

Equations

• PickeringBarry1991.sentenceTypes = [PickeringBarry1991.subjectRelative, PickeringBarry1991.objectRelative, PickeringBarry1991.germanSubjectRelative, PickeringBarry1991.piedPiping]

theorem PickeringBarry1991.table1 : (¬∀ A ∈ sentenceTypes, Nested A.fillerGap ↔ A.IsNestedConstruction) ∧ ¬∀ A ∈ sentenceTypes, Nested A.gapVerb ↔ A.IsNestedConstruction

With empty categories, neither the filler–gap pattern nor the gap–verb pattern tracks the construction type (Table 1).

theorem PickeringBarry1991.table2 (A : Analysis) : A ∈ sentenceTypes → (Nested A.fillerVerb ↔ A.IsNestedConstruction)

Without empty categories, the filler–verb pattern is nested exactly in the nested constructions (Table 2).

def PickeringBarry1991.rows : List (Datum × Analysis)

The four sentence types with their analyses.

Equations

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

def PickeringBarry1991.Hard (e : Datum) : Prop

The paper reports the sentence hard to process. Its examples are grammatical and printed unmarked, so difficulty is a separate observation from the judgment.

Equations

• PickeringBarry1991.Hard e = (e.feature? "difficulty" = some "hard")

@[instance_reducible]

instance PickeringBarry1991.instDecidablePredDatumHard : DecidablePred Hard

Equations

• PickeringBarry1991.instDecidablePredDatumHard x✝ = PickeringBarry1991.instDecidablePredDatumHard._aux_1 x✝

theorem PickeringBarry1991.difficulty (p : Datum × Analysis) : p ∈ rows → (Hard p.1 ↔ Nested p.2.fillerVerb)

Processing difficulty is nesting of the filler–verb associations: the sentences that are hard to process are exactly those whose gap-free pattern is nested.

theorem PickeringBarry1991.trace_prediction_fails : Nested piedPiping.fillerGap ∧ Nested piedPiping.gapVerb ∧ ¬Hard Examples.ex42

The trace analysis predicts difficulty for the multiple pied-piping sentence, whose filler–gap and gap–verb associations are both nested, yet it is easy.

theorem PickeringBarry1991.stranding : ¬Hard Examples.ex15 ∧ Hard Examples.ex16 ∧ { filler := 0, gap := 15, verb := 3 }.fillerVerb.toProd.2 < { filler := 0, gap := 14, verb := 14 }.fillerVerb.toProd.2

Under pied piping (15) the filler associates with the verb, and under preposition stranding (16) with the stranded preposition at the end, a longer association for a harder sentence.

Extending the constructions

def PickeringBarry1991.peripheralGaps (a n : ℕ) : List Dependency

The constructions whose n relative clauses each place a filler and, two words later, its verb, while the trace analysis sites all n gaps at the end of the sentence: multiple pied piping from position 4, (42), (54), (55), and the recursive passive from position 0, (93)–(95).

Equations

• PickeringBarry1991.peripheralGaps a n = List.map (fun (k : ℕ) => { filler := a + 5 * k, gap := a + 5 * n + (n - 1 - k), verb := a + 5 * k + 2 }) (List.range n)

def PickeringBarry1991.localGaps (n : ℕ) : List Dependency

The multiple subject relative with n clauses, (44), (51), each of which places a filler, its gap and its verb in succession.

Equations

• PickeringBarry1991.localGaps n = List.map (fun (k : ℕ) => { filler := 4 + 5 * k, gap := 5 + 5 * k, verb := 6 + 5 * k }) (List.range n)

def PickeringBarry1991.centreEmbedded (n : ℕ) : List Dependency

The multiple object relative with n clauses, (45), (52), which places the fillers in succession and then the verbs in reverse order, each followed by its gap.

Equations

• PickeringBarry1991.centreEmbedded n = List.map (fun (k : ℕ) => { filler := 2 + 3 * k, gap := 2 + 3 * n + 2 * (n - 1 - k) + 1, verb := 2 + 3 * n + 2 * (n - 1 - k) }) (List.range n)

def PickeringBarry1991.verbFinal (n : ℕ) : List Dependency

The German multiple subject relative with n clauses, (48), (53), which places each filler before its gap and then the verbs in reverse order.

Equations

• PickeringBarry1991.verbFinal n = List.map (fun (k : ℕ) => { filler := 2 + 4 * k, gap := 3 + 4 * k, verb := 2 + 4 * n + (n - 1 - k) }) (List.range n)

theorem PickeringBarry1991.peripheralGaps_fillerVerb_disjoint (a n : ℕ) : Disjoint (List.map Dependency.fillerVerb (peripheralGaps a n))

Without empty categories, extending the pied-piping or the passive construction keeps the pattern disjoint, so there is never an unfinished association to remember.

theorem PickeringBarry1991.peripheralGaps_fillerGap_common (a n : ℕ) (d : Dependency) : d ∈ peripheralGaps a n → a + 5 * n ∈ d.fillerGap

With empty categories, every filler of the extended construction is held until the first gap, the position a + 5n common to all n filler–gap associations.

theorem PickeringBarry1991.peripheralGaps_nested (a n : ℕ) (hn : 2 ≤ n) : Nested (List.map Dependency.fillerGap (peripheralGaps a n)) ∧ Nested (List.map Dependency.gapVerb (peripheralGaps a n))

With empty categories, the extended construction's filler–gap and gap–verb associations are nested as soon as there are two clauses.

theorem PickeringBarry1991.localGaps_disjoint (n : ℕ) : Disjoint (List.map Dependency.fillerGap (localGaps n)) ∧ Disjoint (List.map Dependency.gapVerb (localGaps n)) ∧ Disjoint (List.map Dependency.fillerVerb (localGaps n))

The multiple subject relative stays disjoint on every analysis, however far it is extended.

theorem PickeringBarry1991.centreEmbedded_common (n : ℕ) (d : Dependency) : d ∈ centreEmbedded n → 2 + 3 * n ∈ d.fillerVerb ∧ 2 + 3 * n ∈ d.fillerGap

In the multiple object relative every filler is held until the innermost verb, on either analysis: the associations are nested and difficulty grows with every clause.

theorem PickeringBarry1991.verbFinal_common (n : ℕ) : (∀ d ∈ verbFinal n, 2 + 4 * n ∈ d.fillerVerb ∧ 2 + 4 * n ∈ d.gapVerb) ∧ Disjoint (List.map Dependency.fillerGap (verbFinal n))

In the German multiple subject relative every filler is held until the innermost verb; the trace analysis puts the nesting in the gap–verb associations instead, its filler–gap associations staying disjoint.

Unbounded dependencies in categorial grammar

inductive PickeringBarry1991.Basic : Type

The basic categories of the fragment are declarative sentence, embedded question, noun phrase and prepositional phrase.

• S : Basic
• Q : Basic
• NP : Basic
• PP : Basic

@[instance_reducible]

instance PickeringBarry1991.instDecidableEqBasic : DecidableEq Basic

Equations

• PickeringBarry1991.instDecidableEqBasic x✝ y✝ = if h : x✝.ctorIdx = y✝.ctorIdx then isTrue ⋯ else isFalse ⋯

def PickeringBarry1991.instReprBasic.repr : Basic → ℕ → Std.Format

Equations

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

@[instance_reducible]

instance PickeringBarry1991.instReprBasic : Repr Basic

Equations

• PickeringBarry1991.instReprBasic = { reprPrec := PickeringBarry1991.instReprBasic.repr }

def PickeringBarry1991.sent : CCG.Cat Basic

The sentence category.

Equations

• PickeringBarry1991.sent = CCG.Cat.atom PickeringBarry1991.Basic.S

def PickeringBarry1991.quest : CCG.Cat Basic

The embedded-question category.

Equations

• PickeringBarry1991.quest = CCG.Cat.atom PickeringBarry1991.Basic.Q

def PickeringBarry1991.np : CCG.Cat Basic

The noun-phrase category.

Equations

• PickeringBarry1991.np = CCG.Cat.atom PickeringBarry1991.Basic.NP

def PickeringBarry1991.pp : CCG.Cat Basic

The prepositional-phrase category.

Equations

• PickeringBarry1991.pp = CCG.Cat.atom PickeringBarry1991.Basic.PP

def PickeringBarry1991.lexicon : List (String × CCG.Cat Basic)

The lexicon of (82)–(85). The subject pronoun who takes a sentence missing its subject, the object pronoun whom a sentence missing an object, and John carries the raised category through which rule (80a) combines it with a verb before the verb's object.

Equations

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

def PickeringBarry1991.der83 : CCG.Derivation String CCG.RuleSystem.multimodal quest

The derivation (83) of who saw Mary, in which the subject pronoun applies to a sentence missing its subject.

Equations

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

def PickeringBarry1991.der84 : CCG.Derivation String CCG.RuleSystem.multimodal quest

The derivation (84) of whom John saw, in which the raised subject composes with the verb into a sentence missing its object, which the object pronoun takes.

Equations

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

def PickeringBarry1991.der85 : CCG.Derivation String CCG.RuleSystem.multimodal quest

The derivation (85) of whom John talked to, in which two compositions leave the preposition's object missing.

Equations

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

def PickeringBarry1991.wonders (d : CCG.Derivation String CCG.RuleSystem.multimodal quest) : CCG.Derivation String CCG.RuleSystem.multimodal sent

Sue wonders applied to an embedded question.

Equations

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

def PickeringBarry1991.der82a : CCG.Derivation String CCG.RuleSystem.multimodal sent

(82a).

Equations

• PickeringBarry1991.der82a = PickeringBarry1991.wonders PickeringBarry1991.der83

def PickeringBarry1991.der82b : CCG.Derivation String CCG.RuleSystem.multimodal sent

(82b).

Equations

• PickeringBarry1991.der82b = PickeringBarry1991.wonders PickeringBarry1991.der84

def PickeringBarry1991.der82c : CCG.Derivation String CCG.RuleSystem.multimodal sent

(82c).

Equations

• PickeringBarry1991.der82c = PickeringBarry1991.wonders PickeringBarry1991.der85

theorem PickeringBarry1991.embedded_questions : (CCG.Derivation.LexIn lexicon der82a ∧ der82a.yield = ["Sue", "wonders", "who", "saw", "Mary"]) ∧ (CCG.Derivation.LexIn lexicon der82b ∧ der82b.yield = ["Sue", "wonders", "whom", "John", "saw"]) ∧ CCG.Derivation.LexIn lexicon der82c ∧ der82c.yield = ["Sue", "wonders", "whom", "John", "talked", "to"]

The embedded questions (82a–c) are derived from the lexicon, with no empty category.

def PickeringBarry1991.npCount : String → ℤ

The noun phrases each word of the fragment contributes to the count invariant. A verb consumes its arguments and a pronoun supplies the one it fills.

Equations

• PickeringBarry1991.npCount "saw" = -2
• PickeringBarry1991.npCount "talked" = -1
• PickeringBarry1991.npCount "to" = -1
• PickeringBarry1991.npCount "wonders" = -1
• PickeringBarry1991.npCount x✝ = 1

theorem PickeringBarry1991.no_der82d (R : CCG.RuleSystem Basic) (w : String) (hw : w = "who" ∨ w = "whom") : ¬∃ (d : CCG.Derivation String R sent), CCG.Derivation.LexIn lexicon d ∧ d.yield = ["Sue", "wonders", w, "John", "saw", "Mary"]

Sue wonders who John saw Mary (82d) has no derivation, with who or with whom, in any rule system, because the pronoun supplies a noun phrase no verb consumes.