TY - JOUR
T1 - On the limits of forgetting in Answer Set Programming
AU - Gonçalves, Ricardo
AU - Knorr, Matthias
AU - Leite, João
AU - Woltran, Stefan
N1 - R. Goncalves, M. Knorr and J. Leite were partially supported by FCT project FORGET (PTDC/CCI-INF/32219/2017);
NOVA LINCS (UIDB/04516/2020).
S. Woltran was supported by the Austrian Science Fund (FWF): Y698, P25521.
PY - 2020/9
Y1 - 2020/9
N2 - Selectively forgetting information while preserving what matters the most is becoming an increasingly important issue in many areas, including in knowledge representation and reasoning. Depending on the application at hand, forgetting operators are defined to obey different sets of desirable properties. It turns out that, of the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence, which imposes certain conditions on the correspondence between the answer sets of the program pre- and post-forgetting, and a certain independence from non-forgotten atoms, seems to best capture its essence, and be desirable in general. However, it has remained an open problem whether it is always possible to forget a set of atoms from a program while obeying strong persistence. In this paper, we investigate the limits of forgetting in Answer Set Programming. After showing that it is not always possible to forget a set of atoms from a program while obeying this property, we move forward and precisely characterize what can and cannot be forgotten from a program, by presenting a necessary and sufficient criterion. This characterization allows us to draw some important conclusions regarding the existence of forgetting operators for specific classes of logic programs, to characterize the class of forgetting operators that achieve the correct result whenever forgetting is possible, and investigate the related question of determining what we can forget from some specific logic program. Subsequently, we address the issue of what to do when we must forget a set of atoms, but cannot without violating this property. To this end, we investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different natural possible relaxations of the characterization of strong persistence. Additionally, before concluding, we address computational complexity issues – namely of checking whether the novel criterion holds and whether a certain program is a result according to the different classes of forgetting operators we introduce – and discuss the related literature.
AB - Selectively forgetting information while preserving what matters the most is becoming an increasingly important issue in many areas, including in knowledge representation and reasoning. Depending on the application at hand, forgetting operators are defined to obey different sets of desirable properties. It turns out that, of the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence, which imposes certain conditions on the correspondence between the answer sets of the program pre- and post-forgetting, and a certain independence from non-forgotten atoms, seems to best capture its essence, and be desirable in general. However, it has remained an open problem whether it is always possible to forget a set of atoms from a program while obeying strong persistence. In this paper, we investigate the limits of forgetting in Answer Set Programming. After showing that it is not always possible to forget a set of atoms from a program while obeying this property, we move forward and precisely characterize what can and cannot be forgotten from a program, by presenting a necessary and sufficient criterion. This characterization allows us to draw some important conclusions regarding the existence of forgetting operators for specific classes of logic programs, to characterize the class of forgetting operators that achieve the correct result whenever forgetting is possible, and investigate the related question of determining what we can forget from some specific logic program. Subsequently, we address the issue of what to do when we must forget a set of atoms, but cannot without violating this property. To this end, we investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different natural possible relaxations of the characterization of strong persistence. Additionally, before concluding, we address computational complexity issues – namely of checking whether the novel criterion holds and whether a certain program is a result according to the different classes of forgetting operators we introduce – and discuss the related literature.
KW - Answer Set Programming
KW - Computational complexity
KW - Forgetting
KW - Relativized equivalence
KW - Strong equivalence
UR - http://www.scopus.com/inward/record.url?scp=85086439385&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2020.103307
DO - 10.1016/j.artint.2020.103307
M3 - Article
AN - SCOPUS:85086439385
SN - 0004-3702
VL - 286
JO - Artificial Intelligence
JF - Artificial Intelligence
M1 - 103307
ER -