Semantic forgetting in answer set programming

作     者：Eiter, Thomas Wang, Kewen 

作者机构：Griffith Univ Sch Informat & Commun Technol Brisbane Qld 4111 Australia Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria 

出 版 物：《ARTIFICIAL INTELLIGENCE》 (人工智能)

年 卷 期：2008年第172卷第14期

页      面：1644-1672页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：European Commission, EC, (IST-2003-506779) Australian Research Council, ARC, (DP0666540, DP0666107) FWF, (P18019, P 17212) 

主　　题：answer set programming nonmonotonic logic programs knowledge representation forgetting computational complexity 

摘      要：The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming. (c) 2008 Published by Elsevier B.V.