AAAI Publications, Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
Forgetting in Logic Programs under Strong Equivalence
Yisong Wang, Yan Zhang, Yi Zhou, Mingyi Zhang

Last modified: 2012-05-17


In this paper, we propose a semantic forgetting for arbitrary logic programs(or propositional theories) under answer set semantics,called HT-forgetting. The HT-forgetting preserves strong equivalence in the sense that strongly equivalent logic programs will remain strongly equivalent after forgetting the same set of atoms. The result of an HT-forgetting is always expressible by a logic program, and in particular, the result of an HT-forgetting in a Horn program is expressible in a Horn program; and a representation theorem shows that HT-forgetting can be precisely characterized by Zhang-Zhou's four forgetting postulates under the logic of here-and-there. We also reveal underlying connections between HT-forgetting and classical forgetting, and provide complexity results for decision problems.


Answer set programs; forgetting; strong equivalence

Full Text: PDF