A Theory of Forgetting in Logic Programming

Kewen Wang, Abdul Sattar, Kaile Su

The study of forgetting for reasoning has attracted considerable attention in AI. However, much of the work on forgetting, and other related approaches such as independence, irrelevance and novelty, has been restricted to the classical logics. This paper describes a detailed theoretical investigation of the notion of forgetting in the context of logic programming. We first provide a semantic definition of forgetting under the answer sets for extended logic programs. We then discuss the desirable properties and some motivating examples. An important result of this study is an algorithm for computing the result of forgetting in a logic program. Furthermore, we present a modified version of the algorithm and show that the time complexity of the new algorithm is polynomial with respect to the size of the given logic program if the size of certain rules is fixed. We show how the proposed theory of forgetting can be used to characterize the logic program updates. %We show %that the proposed theory of forgetting provides a general %framework for the reasoning tasks such as merging, update and %revision of logic programs.

Content Area: 10. Knowledge Representation & Reasoning

Subjects: 3. Automated Reasoning; 3.3 Nonmonotonic Reasoning

Submitted: May 9, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.