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.
