Research map / Continual learning / Online and replay-based
A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces relativized strong A-simplification (a relaxation of strong simplification where context programs range over a set B), gives necessary and sufficient conditions and an operator combining projection with relativized strong persistence forgetting, plus complexity results for ASP.
Problem
Strong persistence forgetting, faithful abstraction and strong simplification in answer set programming have related characterizations via strong equivalence, but it was unclear how these notions unify; existing simplification notions require context programs over the full vocabulary.
Approach
Relativizes strong simplification by restricting the context programs to a vocabulary B, defining B-SE-models and A-B-SE-models, and deriving a criterion Omega_{A,B} so that strong equivalence, relativized strong equivalence, faithful abstraction, strong simplification and strong persistence all become special cases.
Key results
- Gives necessary and sufficient conditions (Delta^r conditions plus non-satisfaction of criterion Omega_{A,B}) for B-relativized A-simplifiability of ASP programs.
- Shows that the Delta^r conditions alone suffice when A is a subset of B, so the difficulty lies in atoms to remove that do not occur in the context programs.
- Complexity: deciding B-relativized A-simplifiability is in Pi^P_3, and checking a given simplification is Pi^P_3-complete (hardness shown for B = emptyset).
Surprising findings
- Relativized simplifiability can fail even when Delta^r holds, e.g. for the program a<-p, b<-q, p<-not q, q<-not p with A={p,q}, B={a,b}.
Limitations
- Operator for relativized forgetting is semantic rather than a fully syntactic operator; a syntactic version is left open.
- Results are for propositional ELPs; the uniform case is left as future work.
Experimental setup
Builds on: strong persistence forgetting strong simplification (Saribatur and Woltran) relativized strong equivalence (Woltran 2004) faithful omission abstraction (Zhang/Zhou) SP-forgetting criterion Omega (Goncalves et al.)
Closest papers by meaning
- Forgetting in Modular Answer Set Programming (AAAI 2019 · similarity 0.90)
- Recursive Aggregates as Intensional Functions in Answer Set Programming: Semantics and Strong Equivalence (AAAI 2025 · similarity 0.90)
- Strong Equivalence for Epistemic Logic Programs Made Easy (AAAI 2019 · similarity 0.89)
- On Equivalence and Inconsistency of Answer Set Programs with External Sources (AAAI 2017 · similarity 0.88)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.86)
- Exact ASP Counting with Compact Encodings (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.