TL;DR
This paper introduces a more efficient way to compute "presuppositions" in natural language by treating context as a nested structure rather than a flat set of facts. By integrating an in-predicate into a tableau calculus, the author avoids the redundant theorem-proving steps common in traditional computational semantics.
What Problem Does This Paper Address?
In linguistics, a presupposition is an implicit assumption about the world required for a sentence to make sense. For example, "Hank likes his wife" presupposes that Hank is married. However, in the sentence "Every man who has a wife likes his wife," the presupposition is "trapped" or satisfied locally by the first half of the sentence, so it doesn't "project" to the global context.
Computational systems like DORIS use Discourse Representation Theory (DRT) to resolve these. To decide if a presupposition should be accepted (accommodated), the system must run several inference tasks to check for "local informativity" (is this new information?) and "consistency" (does it contradict what we know?).
The problem is redundancy. Standard approaches treat global, intermediate, and local contexts as independent proof tasks. If a discourse is 100 sentences long, the system might re-prove the facts of the first 99 sentences five different times just to resolve a single pronoun in the 100th sentence.
Methods
The author proposes a way to "nest" these inference tasks using a specialized logic:
- The
in-predicate: Borrowing from formal theories of context, the author introduces anin(K, φ)operator. This means "formula φ is true in context K." This allows the system to represent the relationship between global and local contexts within a single logical expression. - The $\mathcal{L}^{con}$ Language: A new formal language that extends standard Discourse Representation Structures (DRS) with this context-aware predicate.
- The $\tau$ Function: An algorithm that takes a standard linguistic representation (a DRS with unresolved presuppositions) and "compresses" all the necessary informativity checks into one $\mathcal{L}^{con}$ formula.
- Labeled Tableau Calculus: The core technical contribution is a deduction system (a tableau) where each node is tagged with a label $(i, \sigma)$.
- $i$ is the current context ID.
- $\sigma$ is the set of "parent" contexts that are currently accessible.
- This allows the theorem prover to "remember" what it has already proved in a parent context when it moves into a nested sub-context.
Datasets
Not discussed in the paper. As a theoretical paper in formal semantics and logic, it uses illustrative linguistic examples (e.g., the "Hank and his wife" sentences) rather than large-scale empirical benchmarks or training datasets.
Key Insights and Ideas
- Context as a First-Class Citizen: Instead of seeing context as a static background, the paper treats it as a dynamic, nested structure that can be manipulated by the logic itself.
- Proof Sharing: The "aha moment" is realizing that if you prove something in the global context, you shouldn't have to prove it again when checking a local sub-context. By using labels to track accessibility, the tableau calculus naturally "inherits" truths from parent contexts.
- Non-Redundant Informativity: By stating all five typical inference tasks (for different types of accommodation) in a single formula, the system only processes the shared global information once.
Key Results
The paper provides a formal proof system rather than quantitative benchmarks. The primary result is the Tableau rules for $\mathcal{L}^{con}$, which demonstrate that:
- Contextual nesting can be explicitly tracked during deduction.
- The system can distinguish between different levels of accommodation (global vs. local) without restarting the proof engine for each level.
- The proposed method is qualitatively more efficient for large discourses because it eliminates the need to re-process the "global" part of the discourse for every local presupposition trigger.
Limitations and Future Work
- Focus on Informativity: The paper primarily focuses on "local informativity" (checking if information is redundant). It does not yet fully integrate "local consistency" (checking for contradictions), though the author suggests this could be handled similarly.
- Implementation Depth: While the theory is robust, the paper does not provide performance metrics from a live implementation in a system like DORIS to quantify the exact speedup.
- Complexity of $\tau$: The function used to extract tasks from DRSs is described as "rather complex," which might present an implementation hurdle for very large-scale linguistic grammars.
- Future Direction: The author aims to combine this with "model generation" to handle satisfiability tasks more effectively.
Summary updated