Abstract
This paper describes how automated deduction methods for natural language processing can be applied more efficiently by encoding context in a more elaborate way. Our work is based on formal approaches to context, and we provide a tableau calculus for contextual reasoning. This is explained by considering an example from the problem area of presupposition projection.
Introduction
In natural language processing (NLP), a presupposition is a fact that must be true for a sentence to make sense. For example, the sentence "Sue’s husband is out of town" presupposes that "Sue is married." The challenge arises with presupposition projection: determining which of these background assumptions "leak out" to the global context. In the sentence "If Sue is married, then her husband is out of town," the presupposition that she is married is "trapped" or resolved by the first half of the sentence, so it doesn't project to the listener's global knowledge base.
Standard automated theorem provers are inefficient at solving this. They typically treat every sub-context (like the "if" clause and the "then" clause) as independent problems. If multiple parts of a long sentence share the same background facts, a standard prover will waste time re-proving the same things over and over.
Methods: A Contextual Framework
The author proposes a two-step formal solution to handle these complexities efficiently:
- A New Language ($\mathcal{L}^{con}$): Instead of standard first-order logic, the paper uses a language featuring an
in-predicate. This allows the system to explicitly state that a formula $\phi$ holds within a specific context $\Gamma$. Crucially, these predicates can be nested, mirroring how humans layer information in a conversation. - The Translation Function ($\tau$): The paper provides a formal mapping to convert standard linguistic representations into this efficient, nested format. This translation handles logical operators by checking for presuppositions (
pp) and embedding them within the appropriate context.
Contextual Tableau Calculus
The core technical contribution is a set of reasoning rules (a tableau calculus) designed for this nested language. It uses labeled nodes—each logical statement is tagged with a context identifier ($i$) and a set of accessible contexts ($\sigma$). This allows the reasoner to "look back" at previously established facts in parent contexts to close logical branches quickly, eliminating redundant proofs.
Key Insights and Ideas
- Context as a First-Class Citizen: Rather than viewing context as a static "bag of facts," the paper treats it as a dynamic, hierarchical structure. This allows the logic to "know" when it has entered a sub-story or a conditional statement.
- Efficiency through Sharing: By labeling logical nodes with context IDs, the system can recognize that a fact proven in a "parent" context is automatically available to all "child" contexts. This avoids the "triple inference" problem where the same premise is used multiple times in independent proofs.
- Meta-Reasoning: The
in-predicateacts as a meta-language. It doesn't just say "X is true"; it says "In the world where Y is true, X is also true." This is vital for dialogue systems that need to track what a user believes versus what is objectively known.
Results and Applications
The paper successfully defines $\mathcal{L}^{con}$ and a corresponding tableau calculus specifically tuned for the presupposition projection problem. While the paper does not provide benchmark timings, it demonstrates qualitatively how the nested approach reduces the number of steps required to resolve a discourse.
In practical dialogue applications (like route planners), this logic allows a system to detect when a user has made an assumption that isn't in the database. This triggers the system to ask a clarifying question (e.g., "Wait, you mentioned 'my start'—where are you starting from?") rather than failing or making incorrect assumptions.
Limitations and Future Work
The authors acknowledge that identifying a context simply as a "set of first-order formulas" is a simplification, as real-world language is often more ambiguous. Future work may involve integrating this calculus with more robust linguistic theories, such as Rob van der Sandt’s approach to presupposition as pronoun resolution. Additionally, the scalability of this calculus on massive, real-time knowledge bases remains an open question for future implementation.
Summary updated