IRI-9412205 Etherington, David University of Oregon Eugene $62,828 - 12 mos. Toward Efficient Default Reasoning This is the first year finding of a research project involving a three year study of a novel approximation-based, approach to tractable nonmonotonic reasoning. Nonmonotonicity is a critical part of most human reasoning tasks. Despite this, current nonmonotonic reasoning formalisms are inherently undecidable in the general case, and are intractable in all but the most restrictive cases. To address this intractability, two known, weak, techniques-context-limited reasoning and fast, incomplete consistency testing-will be combined to develop a powerful, tractable, approximation mechanism. Neither of these techniques, alone, suffices, however. Since consistency is undecidable in the first-order case, context limited reasoning does not, by itself, guarantee tractability, Furthermore, known fast, incomplete consistency tests generally fail in realistically-complex knowledge bases. The goal of this research is the show that the combination of the two techniques synergistically yields a tractable approximate nonmonotonic reasoning mechanism that overcomes the limitations of either technique alone. The conditions under which this approach gives justifiable results will be formalized, and probabilistic arguments will be developed showing that the approximations induced are reasonable for certain useful types of default reasoning. Formal results will be proved showing that the approximations converge to fully-correct reasoning as additional computational resources are expended. The mechanisms necessary for building and maintaining contexts and for dealing with the errors induced by the approximation will then be studied. Finally, these ideas will be implemented and evaluated empirically against non-trivial knowledge bases.

Agency
National Science Foundation (NSF)
Institute
Division of Information and Intelligent Systems (IIS)
Application #
9412205
Program Officer
Ephraim P. Glinert
Project Start
Project End
Budget Start
1995-04-15
Budget End
1998-06-30
Support Year
Fiscal Year
1994
Total Cost
$201,700
Indirect Cost
Name
University of Oregon Eugene
Department
Type
DUNS #
City
Eugene
State
OR
Country
United States
Zip Code
97403