When you must forget

Beyond strong persistence when forgetting in answer set programming

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence 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.

Original languageEnglish
Pages (from-to)837-854
Number of pages18
JournalTheory and Practice of Logic Programming
Volume17
Issue number5-6
DOIs
Publication statusPublished - 1 Sep 2017

Fingerprint

Answer Set Programming
Persistence
Atoms
Computational complexity
Computational Complexity
Equivalence
Alternatives
Operator
Context

Keywords

  • Answer Set Programming
  • computational complexity
  • forgetting
  • relativized equivalence
  • strong equivalence

Cite this

@article{6ba8ed3800c34aaa90296ac77fa9ef40,
title = "When you must forget: Beyond strong persistence when forgetting in answer set programming",
abstract = "Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence 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.",
keywords = "Answer Set Programming, computational complexity, forgetting, relativized equivalence, strong equivalence",
author = "Ricardo Gon{\cc}alves and Matthias Knorr and Jo{\~a}o Leite and Stefan Woltran",
note = "sem pdf. partially supported by FCT strategic project NOVA LINCS (UID/CEC/04516/2013). R. Gon{\cc}alves was partially supported by FCT grant SFRH/BPD/100906/2014 and M. Knorr by FCT grant SFRH/BPD/86970/2012.",
year = "2017",
month = "9",
day = "1",
doi = "10.1017/S1471068417000382",
language = "English",
volume = "17",
pages = "837--854",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge Univ Press",
number = "5-6",

}

When you must forget : Beyond strong persistence when forgetting in answer set programming. / Gonçalves, Ricardo; Knorr, Matthias; Leite, João; Woltran, Stefan.

In: Theory and Practice of Logic Programming, Vol. 17, No. 5-6, 01.09.2017, p. 837-854.

Research output: Contribution to journalArticle

TY - JOUR

T1 - When you must forget

T2 - Beyond strong persistence when forgetting in answer set programming

AU - Gonçalves, Ricardo

AU - Knorr, Matthias

AU - Leite, João

AU - Woltran, Stefan

N1 - sem pdf. partially supported by FCT strategic project NOVA LINCS (UID/CEC/04516/2013). R. Gonçalves was partially supported by FCT grant SFRH/BPD/100906/2014 and M. Knorr by FCT grant SFRH/BPD/86970/2012.

PY - 2017/9/1

Y1 - 2017/9/1

N2 - Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence 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.

AB - Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence 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.

KW - Answer Set Programming

KW - computational complexity

KW - forgetting

KW - relativized equivalence

KW - strong equivalence

UR - http://www.scopus.com/inward/record.url?scp=85032588489&partnerID=8YFLogxK

U2 - 10.1017/S1471068417000382

DO - 10.1017/S1471068417000382

M3 - Article

VL - 17

SP - 837

EP - 854

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 5-6

ER -