Abstract
This paper addresses the challenge of belief change within logic programming, a domain where the non-monotonic nature of rules complicates traditional update frameworks. By adapting the "partial meet" construction from classical AGM belief change theory, the authors propose new revision and contraction operators that bridge the gap between purely semantic and purely syntactic approaches. These operators respect the underlying rule structure of a program while maintaining logical consistency. Furthermore, the authors introduce the MODCHANGE algorithm, which utilizes modularity to localize changes, significantly improving computational efficiency without sacrificing logical soundness.
Introduction
In Knowledge Representation, belief change explores how an agent should modify their existing knowledge base when presented with new, potentially conflicting information. The Alchourrón, Gärdenfors, and Makinson (AGM) framework provides the standard postulates for such changes in classical logic. However, applying AGM to logic programs is difficult because logic programming is non-monotonic: adding a new rule can invalidate previous conclusions.
Existing research typically bifurcates into two approaches. Purely semantic methods utilize SE-models (Strong Equivalence models) to characterize programs monotonically, but often ignore the procedural dependencies of rules. Conversely, purely syntactic methods treat programs as simple sets of formulas (belief bases), often overlooking the deeper logical relationships between atoms. This paper proposes a middle ground: a model-based approach that remains "rule-aware."
The Partial Meet Framework for Logic Programs
The authors adapt the Partial Meet construction—a classic technique in belief change—to the specific requirements of logic programming. This involves several key components:
Compatible Sets and Selection Functions
Rather than attempting to revise the entire program at once, the framework identifies compatible sets. These are maximal subsets of the original program that remain consistent with the new information under SE-model semantics. Because multiple compatible sets may exist (representing different ways to resolve a conflict), the authors employ a selection function ($\gamma$) to choose the most preferred sets. The final revised program is defined as the intersection of these selected sets combined with the new information.
Contraction Operators
The paper introduces the first model-based contraction operator for logic programs. Contraction allows an agent to "forget" or remove a specific belief while ensuring minimal disruption to the rest of the knowledge base. This is critical for maintaining the integrity of a program when certain assumptions are proven false.
Algorithmic Efficiency: The MODCHANGE Algorithm
A significant hurdle in belief change is the exponential cost of checking every possible combination of rules in a large program. To address this, the authors introduce the MODCHANGE algorithm, which leverages the concept of modules.
Modules are subsets of rules related by shared atoms. By identifying which atoms are actually affected by a change—a process known as language-splitting—the algorithm performs revision or contraction only on the relevant modules. Theorem 3 in the paper proves that this localized approach is sound, producing the exact same result as a global partial meet operation while significantly pruning irrelevant rules and improving performance.
Theoretical Insights
The Rule-Level Perspective
The authors argue that a logic program is more than the sum of its models; the rules themselves encode vital dependencies. For example, if a belief $b$ depends on $a$, and $a$ is removed, their approach ensures that $b$ is also retracted. This preserves the internal logic of the program better than purely semantic updates.
Weak Independence of Syntax
In classical logic, if two sets of beliefs are logically equivalent, their revisions should be identical. The authors argue this is too restrictive for logic programming. They propose Weak Independence of Syntax, allowing the specific structure of rules to influence the outcome. This reflects the procedural nature of logic programming, where the way a rule is written carries semantic weight.
Postulate Compliance
The proposed operators are shown to satisfy the major adapted AGM postulates, including Success, Inclusion, and Vacuity. Notably, the authors address the controversial Recovery postulate—which suggests that removing and then re-adding a belief should return the original state—by showing their operator satisfies the more modern and intuitive Relevance postulate.
Conclusion and Future Work
This work provides a robust theoretical foundation for updating logic programs by combining the strengths of semantic modeling with syntactic sensitivity. While the paper establishes how to use selection functions, future research is needed to determine specific strategies for rule preference (e.g., based on reliability or timestamps). Additionally, the authors suggest exploring the relationship between these operators and "SE-forgetting," as well as incorporating epistemic entrenchment to allow systems to automatically prioritize certain rules during conflicts.
Summary updated