{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T16:01:25Z","timestamp":1776182485203,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2017,8,30]],"date-time":"2017-08-30T00:00:00Z","timestamp":1504051200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming,<jats:italic>strong persistence<\/jats:italic>naturally captures its essence. Recently, it has been shown that it is not always possible to forget a set of atoms from a program while obeying this property, and a precise criterion regarding what can be forgotten has been presented, accompanied by a class of forgetting operators that return the correct result when forgetting is possible. However, it is an open question what to do when we have to forget a set of atoms, but cannot without violating this property. In this paper, we address this issue and investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different possible relaxations of the characterization of strong persistence. Additionally, we discuss their preferable usage, shed light on the relation between forgetting and notions of relativized equivalence established earlier in the context of Answer Set Programming, and present a detailed study on their computational complexity.<\/jats:p>","DOI":"10.1017\/s1471068417000382","type":"journal-article","created":{"date-parts":[[2017,8,30]],"date-time":"2017-08-30T06:33:08Z","timestamp":1504074788000},"page":"837-854","source":"Crossref","is-referenced-by-count":9,"title":["When you must forget: Beyond strong persistence when forgetting in answer set programming"],"prefix":"10.1017","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4289-7197","authenticated-orcid":false,"given":"RICARDO","family":"GON\u00c7ALVES","sequence":"first","affiliation":[]},{"given":"MATTHIAS","family":"KNORR","sequence":"additional","affiliation":[]},{"given":"JO\u00c3O","family":"LEITE","sequence":"additional","affiliation":[]},{"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,8,30]]},"reference":[{"key":"S1471068417000382_ref21","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1613\/jair.1541","article-title":"On the practical use of variable elimination in constraint optimization problems: \u2018still-life\u2019 as a case study","volume":"23","author":"Larrosa","year":"2005","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068417000382_ref18","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1613\/jair.1113","article-title":"Propositional independence: Formula-variable independence and forgetting","volume":"18","author":"Lang","year":"2003","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068417000382_ref12","unstructured":"Gon\u00e7alves R. , Knorr M. and Leite J. 2016b. The ultimate guide to forgetting in answer set programming. In Proc. of KR, C. Baral , J. Delgrande and F. Wolter , Eds. AAAI Press, 135\u2013144."},{"key":"S1471068417000382_ref25","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018978005636"},{"key":"S1471068417000382_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-010-9187-9"},{"key":"S1471068417000382_ref22","doi-asserted-by":"crossref","unstructured":"Leite J. 2017. A bird's-eye view of forgetting in answer-set programming. In Proc. of LPNMR, M. Balduccini and T. Janhunen , Eds. LNAI, vol. 10377. Springer, 10\u201322.","DOI":"10.1007\/978-3-319-61660-5_2"},{"key":"S1471068417000382_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.02.002"},{"key":"S1471068417000382_ref5","unstructured":"Delgrande J. P. and Wang K. 2015. A syntax-independent approach to forgetting in disjunctive logic programs. In Proc. of AAAI, B. Bonet and S. Koenig , Eds. AAAI Press, 1482\u20131488."},{"key":"S1471068417000382_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.05.002"},{"key":"S1471068417000382_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.06.003"},{"key":"S1471068417000382_ref4","first-page":"14","article-title":"A model-theoretic approach to belief change in answer set programming","volume":"14","author":"Delgrande","year":"2013","journal-title":"ACM"},{"key":"S1471068417000382_ref38","unstructured":"Weber A. 1986. Updating propositional formulas. In Expert Database Conf., 487\u2013500."},{"key":"S1471068417000382_ref30","unstructured":"Rajaratnam D. , Levesque H. J. , Pagnucco M. and Thielscher M. 2014. Forgetting in action. In Proc. of KR, C. Baral , G. D. Giacomo , and T. Eiter , Eds. AAAI Press, 498\u2013507."},{"key":"S1471068417000382_ref27","unstructured":"Liu Y. and Wen X. 2011. On the progression of knowledge in the situation calculus. In Proc. of IJCAI, T. Walsh, Ed. IJCAI\/AAAI, 976\u2013982."},{"key":"S1471068417000382_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00065-5"},{"key":"S1471068417000382_ref11","unstructured":"Gon\u00e7alves R. , Knorr M. and Leite J. 2016a. Forgetting in ASP: The forgotten properties. In Proc. of JELIA, L. Michael and A. C. Kakas , Eds. Lecture Notes in Computer Science, vol. 10021. Springer, 543\u2013550."},{"key":"S1471068417000382_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.07.004"},{"key":"S1471068417000382_ref13","unstructured":"Gon\u00e7alves R. , Knorr M. and Leite J. 2016c. You can't always forget what you want: On the limits of forgetting in answer set programming. In Proc. of ECAI, M. S. Fox and G. A. Kaminka , Eds. IOS Press, 957\u2013965."},{"key":"S1471068417000382_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1244000"},{"key":"S1471068417000382_ref15","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1613\/jair.3552","article-title":"The logical difference for the lightweight description logic EL","volume":"44","author":"Konev","year":"2012","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068417000382_ref10","first-page":"1","article-title":"General data protection regulation","volume":"L119","year":"2016","journal-title":"Official Journal of the European Union"},{"key":"S1471068417000382_ref6","first-page":"721","article-title":"On properties of update sequences based on causal rejection","volume":"2","author":"Eiter","year":"2002","journal-title":"Theory and Practice of Logic Programming (TPLP)"},{"key":"S1471068417000382_ref14","doi-asserted-by":"crossref","unstructured":"Knorr M. and Alferes J. J. 2014. Preserving strong equivalence while forgetting. In Proc. of JELIA, E. Ferm\u00e9 and J. Leite , Eds. Lecture Notes in Computer Science, vol. 8761. Springer, 412\u2013425.","DOI":"10.1007\/978-3-319-11558-0_29"},{"key":"S1471068417000382_ref20","doi-asserted-by":"crossref","unstructured":"Larrosa J. 2000. Boosting search with variable elimination. In Proc. of CP, R. Dechter , Ed. Lecture Notes in Computer Science, vol. 1894. Springer, 291\u2013305.","DOI":"10.1007\/3-540-45349-0_22"},{"key":"S1471068417000382_ref1","doi-asserted-by":"crossref","unstructured":"Alferes J. J. , Knorr M. and Wang K. 2013. Forgetting under the well-founded semantics. In Proc. of LPNMR, P. Cabalar and T. C. Son , Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 36\u201341.","DOI":"10.1007\/978-3-642-40564-8_4"},{"key":"S1471068417000382_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001716"},{"key":"S1471068417000382_ref36","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1613\/jair.4297","article-title":"Knowledge forgetting in answer set programming","volume":"50","author":"Wang","year":"2014","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"S1471068417000382_ref29","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm049"},{"key":"S1471068417000382_ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000100"},{"key":"S1471068417000382_ref39","unstructured":"Wong K.-S. 2009. Forgetting in logic programs. Ph.D. thesis, The University of New South Wales."},{"key":"S1471068417000382_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00044-6"},{"key":"S1471068417000382_ref3","doi-asserted-by":"crossref","unstructured":"Bledsoe W. W. and Hines L. M. 1980. Variable elimination and chaining in a resolution-based prover for inequalities. In Proc. of CADE, W. Bibel and R. A. Kowalski , Eds. Lecture Notes in Computer Science, vol. 87. Springer, 70\u201387.","DOI":"10.1007\/3-540-10009-1_7"},{"key":"S1471068417000382_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00071-0"},{"key":"S1471068417000382_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068417000382_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068417000382_ref32","unstructured":"Slota M. and Leite J. 2012. Robust equivalence models for semantic updates of answer-set programs. In Proc. of KR, G. Brewka , T. Eiter , and S. A. McIlraith , Eds. AAAI Press, 158\u2013168."},{"key":"S1471068417000382_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.023"},{"key":"S1471068417000382_ref35","unstructured":"Wang Y. , Zhang Y. , Zhou Y. and Zhang M. 2012. Forgetting in logic programs under strong equivalence. In Proc of KR, G. Brewka , T. Eiter , and S. A. McIlraith , Eds. AAAI Press, 643\u2013647."},{"key":"S1471068417000382_ref23","doi-asserted-by":"crossref","DOI":"10.1525\/9780520398252","volume-title":"A Survey of Symbolic Logic","author":"Lewis","year":"1918"},{"key":"S1471068417000382_ref34","unstructured":"Wang Y. , Wang K. and Zhang M. 2013. Forgetting for answer set programs revisited. In Proc. of IJCAI, F. Rossi , Ed. IJCAI\/AAAI, 1163\u20131168."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068417000382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,26]],"date-time":"2024-06-26T15:25:11Z","timestamp":1719415511000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068417000382\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,30]]},"references-count":40,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["S1471068417000382"],"URL":"https:\/\/doi.org\/10.1017\/s1471068417000382","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,30]]}}}