Source-linked AI summary
Displacement Calculus
Glyn Morrill, Oriol Valentín
TL;DR
Lambek calculus handles concatenation, but natural-language dependencies may be discontinuous, and Lambek categorial grammar requires different types for quantifier positions. Displacement calculus extends the calculus to discontinuity while retaining core proof-theoretic properties. The paper states that it proves cut-elimination, the subformula property, and decidability, and illustrates linguistic applications.
Problem
Lambek calculus cannot account for dependencies that are not peripheral, and Lambek categorial grammar requires distinct types for subject, object, and medial quantifier positions.
Source: §1 · p. 1, §3.2 · p. 8Method
Results
Every theorem of displacement calculus has a Cut-free proof, has a proof using only subformulas of the theorem, and it is decidable whether a (hyper)sequent is a theorem.
Source: §5 · pp. 24–25Takeaways & Limitations
The calculus supports basic analyses of the listed linguistic phenomena while retaining concatenation as its unique primitive composition mode and avoiding structural rules.
Source: §1 · p. 2, §5 · p. 25The parenthetical-adverb analysis assumes that an adverb such as “fortunately” can appear freely.
Source: §3.7 · p. 15
Abstract
from arXiv · showhide
The Lambek calculus provides a foundation for categorial grammar in the form of a logic of concatenation. But natural language is characterized by dependencies which may also be discontinuous. In this paper we introduce the displacement calculus, a generalization of Lambek calculus, which preserves its good proof-theoretic properties while embracing discontinuiity and subsuming it. We illustrate linguistic applications and prove Cut-elimination, the subformula property, and decidability
1. Introduction
The Lambek calculus handles concatenation but cannot account for many dependencies that are not peripheral. Displacement calculus extends this framework to discontinuity while retaining its proof-theoretic properties and offering analyses of the listed phenomena.
1. Introduction
- Lambek calculus cannot account for dependencies that are not peripheral, including discontinuous idioms and quantification.The section also lists VP ellipsis, medial extraction, pied-piping, appositive relativization, parentheticals, gapping, comparative subdeletion, and reflexivization.Source: §1 · pp. 1–2
- Displacement calculus retains a single primitive mode of composition—concatenation—and has no structural rules, like Lambek calculus.It is intuitionistic and supports the standard categorial Curry-Howard type-logical semantics.Source: §1 · p. 2
- The paper claims displacement calculus has Cut-elimination, the subformula property, and decidability, and provides basic analyses of all phenomena listed in (1).The paper defines the calculus, presents linguistic applications, and then proves Cut-elimination.Source: §1 · p. 2
2. Displacement Calculus
Displacement calculus classifies strings and types by the number of separators they contain, and uses hyperconfigurations to represent discontinuous structures. Its rules extend familiar concatenating connectives with wrapping operations.
2. Displacement Calculus
- A type's sort is the number of separators it contains; strings of sort i are punctuated into i + 1 maximal continuous segments.The vocabulary includes a distinguished placeholder called the separator, and types are sorted by mutual recursion.Source: §2 · pp. 2–3
- Types of sort greater than one label mother nodes with multiple subconfigurations, representing a discontinuous type intercalated by those subconfigurations.A hypersequent pairs an antecedent hyperconfiguration and succedent type of the same sort.Source: §2 · p. 3
- A k-ary wrap replaces the kth separator in one configuration with another configuration.Generalized wrap simultaneously replaces successive separators with supplied configurations.Source: §2 · p. 3
- The calculus uses concatenating and wrapping connectives with rules like Lambek calculus, expressed using vectorial and hyperoccurrence notation.Concatenation is represented by the sequent comma; wrapping is defined using k-ary wrap.Source: §2 · p. 4
3. Linguistic Applications
The paper presents displacement-calculus analyses for linguistic phenomena, including discontinuous idioms. In the idiom example, lexical assignment gives “give … the cold shoulder” the non-compositional meaning “shun.”
3. Linguistic Applications
- The parser/theorem-prover is implemented in Prolog and produces analyses for the examples introduced in (1).The paper uses continuous and discontinuous product units I and J instead of unary bridge and split operators in a similar system.Source: §3 · p. 4
3.1. Discontinuous Idioms
- For “Mary gave the man the cold shoulder,” lexical assignment gives the discontinuous idiom the non-compositional meaning “shun.”Lexical insertion yields a semantically labelled sequent, followed by a proof and the resulting semantics.Source: §3.1 · p. 7
3.2. Quantification
Lambek categorial grammar needs distinct types for subject and object quantifiers and would need another type for medial quantifiers. The paper uses one type for quantifier phrases across positions and illustrates scope readings.
3.2. Quantification
- A single type, (S ↑N)↓S, is used for quantifier phrases in all positions, including the medial position that motivates the example.The example is “John gave every book to Mary.”Source: §3.2 · p. 8
- The paper presents both non-specific and specific derivations for “Mary thinks someone left.”The passage identifies these as the two readings under consideration.Source: §3.2 · pp. 8–9
- The scope-ambiguity example “Everyone loves someone” includes an object-wide-scope reading.Its displayed semantics is ∀B[(person B) →∃E[(person E) ∧((love E) B)]].Source: §3.2 · pp. 9–10
3.3. VP Ellipsis
VP ellipsis is analyzed by interpreting an auxiliary such as “did” from an antecedent verb phrase. The section illustrates this in both “before” and “and … too” examples.
3.3. VP Ellipsis
- The section treats “did” as receiving its interpretation from an antecedent verb phrase.This is the stated role of the auxiliary in VP ellipsis.Source: §3.3 · p. 10
- In “John slept before Mary did,” the semantics is ((before (slept m)) (slept j)).The derivation is given for the sentence in Figure 2.Source: §3.3 · p. 10
- A second example combines “John slept” with “Mary did too,” and its proof and semantics are given.The example sentence is identified in the passage; Figure 3 presents its proof.Source: §3.3 · p. 10, Figure 3 · p. 11
3.4. Medial Extraction
The section addresses medial relativization, which the stated Lambek relative-pronoun types do not cover. The displacement calculus type is used to obtain extraction from all positions.
3.4. Medial Extraction
- The stated Lambek types cover subject and clause-final object relativization but do not suffice for medial relativization.The medial example is “dog that Mary saw today.”Source: §3.4 · p. 12
- The section supplies a lexical lookup and proof analysis for “dog that Mary saw today.”The proof analysis follows the lookup.Source: §3.4 · p. 12
- The displacement-calculus type obtains extraction from all positions, including medial relativization.The example is “dog that Mary saw today.”Source: §3.4 · p. 12
3.5. Pied-Piping
The applications include pied-piping, appositive relativization, and parentheticals. The examples use displacement-calculus analyses for each construction, with the parenthetical treatment assuming that “fortunately” can appear freely.
3.5. Pied-Piping
- The pied-piping type subsumes the previous subsection’s type, which is derivable from it, so the lexical lookup needs only the type used here.The example is “mountain the painting of which by Cezanne John sold for $10,000,000.”Source: §3.5 · pp. 12–13
3.6. Appositive Relativization
- Appositive relativization conjoins the relative-clause predication of a noun-phrase head with that head’s propositional content.The section’s example is “John, who jogs, sneezed.”Source: §3.6 · p. 13
3.7. Parentheticals
- The parenthetical analysis assumes “fortunately” can appear freely and gives examples with it in several sentence positions.Examples include “fortunately John has perseverance,” “John fortunately has perseverance,” and “John has perseverance fortunately.”Source: §3.7 · p. 15
3.8. Gapping
Gapping is treated as a construction in which a verb in the left conjunct is understood in the right. The section analyzes “John studies logic, and Charles, phonetics.”
3.8. Gapping
- In gapping coordination, a verb in the left conjunct is understood in the right conjunct.Source: §3.8 · p. 16
- The analyzed example is “John studies logic, and Charles, phonetics.”The passage gives a lexical lookup for the coordinator and the example’s words.Source: §3.8 · p. 16
- The derivation for the gapping example is shown in Figure 5.Source: §3.8 · p. 16, Figure 5 · p. 17
3.9. Comparative Subdeletion
The section illustrates comparative subdeletion with a sentence whose than-clause lacks a determiner, then shows a reflexive receiving its interpretation from the subject.
3.9. Comparative Subdeletion
- Comparative subdeletion compares a clause with a comparative determiner to a than-clause from which a determiner is missing.The example is “John ate more donuts than Mary bought bagels.”Source: §3.9 · p. 17
- Lexical assignments for the comparative example are used in a sequent derivation that yields its semantics.Figure 6 is identified as the derivation for the example.Source: §3.9 · p. 17, Figure 6 · p. 18
3.10. Reflexivization
- In reflexivization, the reflexive receives its interpretation from the subject, as in “John sent himself flowers.”The resulting interpretation is ((sent j) flowers) j.Source: §3.10 · pp. 17, 19
4. Cut-Elimination
The displacement calculus proves Cut-elimination using the strategy for the Lambek calculus, without structural rules. The proof reduces Cut instances and yields the subformula property and decidability.
4. Cut-Elimination
- The displacement calculus has Cut-elimination, proved by the Lambek-calculus strategy; Cut-elimination entails the subformula property and decidability.Like the Lambek calculus, it has no structural rules; structural properties are built into the sequent calculus notation.Source: §4 · p. 19
- The proof assigns weights to types and configurations, then defines a Cut-instance degree used to remove a Cut or replace it with lower-degree Cuts.The weight of a type counts its connective occurrences, including units; configuration weight sums the weights of its types.Source: §4 · pp. 19–20
4.1. The Cut cases
- When a Cut premise is an identity axiom, the Cut can be removed; when the Cut formula is not active in both premises, permutation conversions apply.Source: §4 · p. 20
4.1.1. The active formula in the left premise of the Cut rule is not the Cut formula
- The non-principal cases for the left premise examine ⊙i L, ↑i L, and J L rules.Source: §4.1.1 · p. 21
4.1.2. The active formula in the right premise of the Cut rule is not the Cut formula
- The non-principal cases for the right premise cover ↑i L, ↑i R, ⊙i L, and ⊙i R rules.Source: §4.1.2 · pp. 22–23
4.2. Principal Cut cases
- Principal Cut cases pair ⊙i R with ⊙i L, ↑i R with ↑i L, I R with I L, and J R with J L.Source: §4.2 · pp. 23–24
5. Conclusion
The displacement calculus extends Lambek calculus to generalized discontinuity while retaining concatenation as its sole primitive composition mode and avoiding structural rules. It has Cut-elimination, the subformula property, and decidability; its applications use one discontinuity point, although the full calculus permits arbitrarily many.
5. Conclusion
- Every theorem of displacement calculus D has a Cut-free proof, obtained by successively lowering the degree of Cuts or removing them while preserving the endsequent.Cut degrees are finite and non-negative.Source: §5 · p. 24
- Every theorem of D has a proof containing only subformulas of that theorem.In every rule except Cut, premise formulas are subformulas of conclusion formulas, and Cut is eliminable.Source: §5 · p. 25
- It is decidable whether a (hyper)sequent of D is a theorem, because backward-chaining Cut-free hypersequent proof search is finite.Each hypersequent matches rules in finitely many ways and generates finitely many subgoals, so theoremhood is determined in finite time.Source: §5 · p. 25
- The calculus accounts for generalized discontinuity, with Section 3 applications limited to one point of discontinuity while the full calculus allows arbitrarily many.The account follows earlier proposals concerning sorts and unboundedly many discontinuity positions.Source: §5 · p. 25
- D extends Lambek calculus with families of non-concatenative multiplicative connectives while keeping concatenation as the unique primitive mode and using no structural rules.These features contribute to the simplicity of displacement-calculus parsing-as-deduction.Source: §5 · p. 25