A Theory of Forgetting in Logic Programming

Abstract

The study of forgetting for reasoning has attracted consider-able attention in AI. However, much of the work on forget-ting, and other related approaches such as independence, ir-relevance and novelty, has been restricted to the classical log-ics. This paper describes a detailed theoretical investigation of the notion of forgetting in the context of logic program-ming. We first provide a semantic definition of forgetting un-der the answer sets for extended logic programs. We then dis-cuss the desirable properties and some motivating examples. An important result of this study is an algorithm for comput-ing 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 up-dates.