A Paper Abstract by Benjamin Grosof

Sympathetically Solitary Default Theories: a New Case of `Easy' Non-Monotonic Reasoning (June 28 1993)

by Benjamin N. Grosof

Abstract: Expressively rich non-monotonic reasoning is significantly more computationally difficult, in the worst case, than monotonic reasoning (over the same base language). An interesting direction of research, therefore, is to find expressively restricted cases for which it is relatively easy. In this paper (adapted and revised from parts of our PhD thesis), we give a new such case: the class of what we call sympathetically solitary default theories. For this class, we are able to give decidable and tractable methods for the non-monotonic aspect of reasoning. The sympathetically solitary class appears useful for representing reasoning that is shallow in a particular sense. Its tractability (in the non-monotonic aspect) arises from the lack of conflict between multiple defaults, similarly to stratified logic programs with negation by failure (there the minimization of each predicate or ground atom corresponds to a default).

We develop the definition and results about the sympathetically solitary class in terms of circumscription; however, they also apply straightforwardly to Default Logic, Autoepistemic Logic, and several other non-monotonic formalisms as well.

The sympathetically solitary class generalizes Lifschitz' solitary class. It also includes, as a special case, the simple application of the Closed World Assumption to unit-clausal databases, when there is domain closure and a complete theory of equality, e.g., uniqueness of names. However, sympathetically solitary overlaps with, and neither includes nor is included by, the following classes: logic programs with negation by failure; Horn; default inheritance cf. Touretzky; predicate completion; and the general Closed World Assumption.

Last update: 1-8-98

Up to Benjamin Grosof's Papers page
Up to Benjamin Grosof home page

[ IBM Research home page ]