Contexts

People often need to reach conclusions quickly: a potentially wrong answer, now, is often more useful than a definitely right answer, later. To be guaranteed correct, reasoning must explicitly consider everything that is known (no matter how apparently unrelated) to ensure that it does not impact on the decisions at hand. However, even enumerating -- let alone considering -- everything that a system knows can be prohibitively expensive given the massive amounts of information that can be made available.

In some cases, effective reasoning, may require limiting the scope of deliberations to a small context directly associated with the current goals of the system.

CIRL

We have been investigating ways of limiting deduction to restricted contexts. We have shown that one can combine two known weak techniques -- limited contexts and fast, incomplete consistency tests -- to obtain a powerful, tractable, approximation mechanism. We have recently generalized this approach from propositional logic to first-order representations and are working out the details of how contexts and other incomplete reasoning algorithms interact.

Interesting problems involve formalizing the conditions under which this approach gives justifiable results, studying the mechanisms necessary for building and maintaining contexts and for dealing with the errors induced by the approximation, and implementing the ideas and evaluating them empirically against non-trivial knowledge bases.

Pointers

A Non-Deterministic Semantics for Tractable Inference: Characterizes a family of tractable fragments of propositional logic using a non-deterministic 3-valued semantics. Written by James Crawford and David Etherington; appeared in Proc. AAAI in 1998. Compressed postscript document.
Toward Efficient Default Reasoning: A revised version of the extended abstract (below). Further develops the idea of applying context-limited inference to overcome some of the sources of intractability of default reasoning, and includes preliminary experimental data. Written by David Etherington and James Crawford; appeared in Proc. AAAI in 1996. Compressed postscript document.
Toward Efficient Default Reasoning (Extended Abstract): Summarizes an approach to tractable default reasoning by combining limited contexts and fast approximate consistency checks. Written by David Etherington and James Crawford; appeared at the Fourth Nonmonotonic Reasoning Workshop in 1992. Compressed postscript document.
Nonmonotonicity and the Scope of Reasoning: Describes ways to narrow the focus of reasoning to avoid certain troubling paradoxes in ``nonmonotonic'' (i.e., subject to retraction) reasoning. Written by David Etherington, Sarit Kraus, and Donald Perlis; appeared in Artificial Intelligence in 1991. Compressed postscript document.
Parent areas:
Tractable Reasoning

Support

This material is based upon work supported by the National Science Foundation under Grant No. 9412205. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Back to the CIRL Overview Page.