David W. Etherington

AAAI Conference 1996 Conference Paper

Toward Efficient Default Reasoning

• David W. Etherington

Early work on default reasoning aimed to formalize the notion of quickly jumping to conclusions. Unfortunately, the resulting formalisms have proven more computationally complex than classical logics. This has dramatically limited the applicability of formal methods to real problems involving defaults. The complexity of consistency checking is one of the two problems that must be addressed to reduce the complexity of default reasoning. We propose to approximate consistency checking using a novel synthesis of limited contexts and fast incomplete checks, and argue that this combination overcomes the limitations of its component parts. Our approach trades correctness for speed, but we argue that the nature of default reasoning makes this trade relatively inexpensive and intuitively plausible. We present a prototype implementation of a default reasoner based on these ideas, and a preliminary empirical evaluation.

AIJ Journal 1991 Journal Article

Nonmonotonicity and the scope of reasoning

• David W. Etherington
• Sarit Kraus
• Donald Perlis

Circumscription, default logic, and autoepistemic logic capture aspects of the nonmonotonicity of human commonsense reasoning. However, Perlis has shown that circumscription suffers from certain counterintuitive limitations, concerning exceptions or “counterexamples” to defaults. We observe that the unfortunate limitations of circumscription are even broader than Perlis originally pointed out. Moreover, these limitations are not peculiar to circumscription; they appear to be endemic in nonmonotonic reasoning formalisms. We develop a general solution, involving restricting the scope of nonmonotonic reasoning, and show that it remedies these problems in a variety of formalisms. Our solution has a number of attractive aspects in addition to its generality. Most importantly, no modification of the underlying formalisms is required, and the result is semantically compatible with existing approaches. Furthermore, the necessary machinery is intuitively plausible and, arguably, useful for other purposes. Finally, the solution is robust: it is relatively tolerant of imprecise determinations of scope.

AAAI Conference 1990 Conference Paper

Nonmonotonicity and the Scope of Reasoning: Preliminary Report

• David W. Etherington

Existing formalisms for default reasoning capture some aspects of the nonmonotonicity of human commonsense reasoning. However, Perlis has shown that one of these formalisms, circumscription, is subject to certain counterintuitive limitations. Kraus and Perlis suggested a partial solution, but significant problems remain. In this paper, we observe that the unfortunate limitations of circumscription are even broader than Perlis originally pointed out. Moreover, these problems are not confined to circumscription; they appear to be endemic in current nonmonotonic reasoning formalisms. We develop a much more general solution than that of Kraus and Perlis, involving restricting the scope of nonmonotonic reasoning, and show that it remedies these problems in a variety of formalisms.

IJCAI Conference 1989 Conference Paper

Vivid Knowledge and Tractable Reasoning:

• David W. Etherington
• Alex Borgida
• Ronald). Brachman
• Henry Kautz

IJCAI Conference 1987 Conference Paper

A Semantics for Default Logic

• David W. Etherington

AIJ Journal 1987 Journal Article

Formalizing nonmonotonic reasoning systems

• David W. Etherington

In recent years, there has been considerable interest in nonmonotonic reasoning systems. Unfortunately, formal rigor has not always kept pace with the enthusiastic propagation of new systems. The argument has long been made that, because of the general intractability of formal systems, it is unreasonable to consider them for practical applications. This is taken as support for the use of systems such as semantic networks which, although not completely understood, can compute quickly. We suggest that this argument is not entirely convincing, and that formalizing such systems may yield dividends in terms of both clarity and correctness. We argue that formal systems, such as Reiter's default logic, provide useful tools for the specification and description of nonmonotonic systems. We present new results which enhance this usefulness. To illustrate the benefits of this approach, a theory of inheritance networks is developed. This yields a notion of correct inference, and sufficient conditions for the coherence of network inference representations.

AAAI Conference 1987 Conference Paper

More on Inheritance Hierarchies with Exceptions: Default Theories and Inferential Distance

• David W. Etherington

In Artificial Intelligence, well-understood reasoning systems and tractable reasoning systems have often seemed mutually exclusive. This has been exemplified by nonmonotonic reasoning formalisms and inheritance-with-exceptions reasoners. These have epitomized the two extremes: the former not even semidecidable, the latter completely ad hoc. We previously presented a formal mechanism for specifying inheritance systems, and minimal criteria for acceptable inheritance reasoning. This left open the problem of realizing an acceptable reasoner. Since then, Touretzky has developed a reasoner that appears to meet our criteria. We show that his reasoner is formally adequate, and explore some of the implications of this result vis-a-vis the study of nonmonotonic reasoning.

IJCAI Conference 1987 Conference Paper

Relating Default Logic and Circumscription

• David W. Etherington

NMR Workshop 1984 Conference Paper

On the Adequacy of Predicate Circumscription for Closed-World Reasoning

• David W. Etherington
• Robert E. Mercer
• Raymond Reiter

AAAI Conference 1983 Conference Paper

On Inheritance Hierarchies with Exceptions

• David W. Etherington

Using default logic, we formalize NETL-like inheritance hierar-chies with exceptions. This provides a number of benefits: (1) A precise semantics for such hierarchies. (2) A provably correct (with respect to the proof theory of default logic) inference algorithm for acyclic networks. (3) A guarantee that acyclic networks have extensions. (4) A provably correct quasi-parallel inference algorithm for such networks.