Abstract
In the field of Artificial Intelligence, forgetting is a critical process for maintaining efficient knowledge bases by discarding irrelevant information. However, defining forgetting within Logic Programming (LP) and Nonmonotonic Reasoning has historically been challenging due to syntax sensitivity. This paper introduces a robust, semantic-based framework for forgetting within Answer Set Programming (ASP). By shifting the focus from rule manipulation to answer set semantics, the proposed approach ensures that logically equivalent programs yield identical results after forgetting, satisfying key theoretical desiderata and providing a foundation for logic program updates.
Introduction
Knowledge representation systems often accumulate vast amounts of data, much of which becomes redundant or irrelevant over time. "Forgetting" is the formal process of removing specific atoms or literals from a knowledge base while preserving the logical relationships between the remaining elements. While this is well-understood in classical logic, it is notoriously difficult in Logic Programming (LP), particularly within Answer Set Programming (ASP).
Previous attempts to define forgetting in LP—often categorized as "strong" and "weak" forgetting—suffered from a fundamental flaw: they were syntax-sensitive. In these systems, two programs that were semantically identical (equivalent under answer set semantics) could result in entirely different programs after the same literal was forgotten. This lack of semantic consistency made earlier methods unreliable for practical knowledge base management.
A Semantic Foundation for Forgetting
To address the limitations of previous methods, this research proposes a new definition of forgetting rooted in the semantics of ASP rather than the syntax of the rules. The core of this approach involves $l$-minimal models and $l$-answer sets. When a literal $l$ is forgotten in a program $P$, the goal is to identify answer sets that are "closest" to the original ones while ignoring the existence of $l$.
The Five Desiderata (F1-F5)
The authors establish five criteria that any robust forgetting operator should satisfy:
- F1 (Success): The forgotten literal no longer appears in the resulting program.
- F2 (No New Symbols): The process does not introduce auxiliary symbols.
- F3 (Consistency): If the original program is consistent, the result should be consistent (where possible).
- F4 (Syntax Independence): Equivalent programs must result in equivalent programs after forgetting.
- F5 (Persistence): The logical consequences of the original program (that do not involve the forgotten literal) are preserved.
This proposed operator is the first in the field of ASP to satisfy all five properties simultaneously.
Algorithmic Implementation
While the semantic definition provides the theoretical "what," the authors also provide the "how" through two primary algorithms designed to transform programs syntactically while adhering to the semantic definition.
- Canonical Transformation (Algorithm 1): This method uses program transformations, such as unfolding and the elimination of tautologies, to reduce a program to a canonical negative form before removing the target literal.
- Restricted Unfolding (Algorithm 2): A more efficient approach that focuses unfolding specifically on the rules where the literal to be forgotten appears. This minimizes unnecessary computation while maintaining the semantic integrity of the result.
These algorithms bridge the gap between abstract logic and practical application, proving that the semantic definition can be realized through concrete rule manipulation.
Key Insights: Forgetting vs. Deletion
A common misconception is that forgetting a literal is equivalent to simply deleting every rule that contains it. However, this research demonstrates that forgetting requires "re-wiring" the remaining rules. If a literal $l$ acted as a bridge between $a$ and $b$, removing $l$ must preserve the logical flow from $a$ to $b$ if that relationship was independent of $l$ itself.
Furthermore, the paper establishes a profound connection between forgetting and Logic Program Updates. When new information conflicts with an existing knowledge base, the update process can be viewed as a specialized form of forgetting: one "forgets" the specific parts of the old information that create the conflict, allowing the new data to be integrated seamlessly.
Complexity and Performance
Theoretical logic transformations often face the threat of exponential state-space explosion. The authors acknowledge that while general forgetting can be computationally expensive due to the "unfolding" of rules, the process remains polynomial if the number of rules where the literal appears as a "head" is bounded. This provides a pathway for implementing forgetting in specialized, large-scale knowledge bases where such bounds are naturally present.
Conclusion
This paper provides a rigorous theoretical framework that solves the long-standing problem of syntax sensitivity in logic program forgetting. By aligning ASP forgetting with classical logic principles (such as Clark’s completion) and satisfying the F1-F5 desiderata, the authors have created a versatile tool for knowledge base maintenance and program updates. Future research will focus on defining formal concepts of "relevance" and "independence" based on this theory, as well as identifying further classes of logic programs where forgetting remains computationally tractable.
Summary updated