Forgetting and Conflict Resolving in Disjunctive Logic Programming

Thomas Eiter, Kewen WangAAAI 2006 · OpenReview

Abstract

We establish a declarative theory of forgetting for disjunctive logic programs. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting is completely captured by the classical forgetting. A transformation-based algorithm is also developed for computing the result of forgetting. We also provide an analysis of computational complexity. As an application of our approach, a fairly general framework for resolving conflicts in inconsistent knowledge bases represented by disjunctive logic programs is defined. The basic idea of our framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.

Introduction

In knowledge representation, the ability to "forget" or discard specific pieces of information is critical for maintaining dynamic knowledge bases. This process is more complex than simple deletion; in logical systems, a single term can influence a vast network of consequences. Simply removing a rule might inadvertently destroy logical dependencies that should remain intact.

This research focuses on Disjunctive Logic Programming (DLP) under answer set semantics, a robust framework for modeling common-sense reasoning. While forgetting has been explored in classical logic, its application to DLP is challenging due to the presence of disjunctions (e.g., "A or B is true") and negation-as-failure. The authors propose a framework to create a version of a program that is independent of a specific literal while remaining logically equivalent regarding all other information.

Methodology

The paper approaches the problem through two primary lenses:

1. Semantic Definition

The authors define forgetting based on "$l$-answer sets." When a literal $l$ is forgotten, the system identifies answer sets that are minimal once $l$ is ignored. This approach preserves the core principle of answer set semantics—minimizing positive information—even after the literal is removed. A key theoretical breakthrough (Theorem 1) proves that forgetting in logic programming is captured by classical forgetting when applied to the program's "completion," bridging the gap between non-monotonic reasoning and classical logic.

2. Transformation-Based Algorithm

A concrete algorithm is developed to compute the result of forgetting. This involves several sophisticated steps:

  • Standard Transformations: Eliminating tautologies and "unfolding" rules.
  • Negative Program Conversion: Converting the program into a "negative" version where negation only appears in rule heads.
  • Semi-Shifting: A novel technique to separate the forgotten literal from disjunctions in rule heads.
  • Literal Replacement: Replacing the forgotten literal with complex nested negations to maintain logical consistency, fixing incompleteness issues found in previous algorithms for simpler programs.

Complexity and Reasoning

The authors provide a rigorous analysis of the computational costs associated with forgetting. Reasoning under forgetting is shown to be significantly harder than standard DLP reasoning. For example, checking if a set is an answer set after forgetting is $\Pi^p_2$-complete, while general skeptical reasoning reaches $\Sigma^p_3$-completeness.

Complexity of model checking and skeptical reasoning across different program types.

As shown in the table above, the complexity varies depending on whether the program is disjunctive, negative, or normal. These results highlight the inherent difficulty of maintaining logical integrity while modifying knowledge bases.

Applications: Conflict Resolution

A primary application of this theory is resolving conflicts in multi-agent systems. If two agents possess conflicting knowledge bases, they can reach a formal compromise by "forgetting" the specific preferences or facts that cause the inconsistency. This provides a mathematically grounded method for preference elicitation and automated negotiation.

Conclusion and Future Work

While the framework provides a solid declarative foundation, it faces practical challenges. The proposed algorithm is worst-case exponential, meaning the resulting programs can become extremely large. Future research will focus on optimizing these algorithms and exploring "strong equivalence," a stricter form of logical equivalence that this current notion of forgetting does not necessarily preserve. Additionally, developing strategies to automatically choose which literals to forget for the "best" compromise remains an open challenge for game theory and social choice applications.

Summary updated

Abstract

We establish a declarative theory of forgetting for disjunctive logic programs. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting is completely captured by the classical forgetting. A transformation-based algorithm is also developed for computing the result of forgetting. We also provide an analysis of computational complexity. As an application of our approach, a fairly general framework for resolving conflicts in inconsistent knowledge bases represented by disjunctive logic programs is defined. The basic idea of our framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.
BibTeX
@inproceedings{eiter2006forgetting,
  author = {Thomas Eiter and Kewen Wang},
  title = {{Forgetting and Conflict Resolving in Disjunctive Logic Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=BkWOSJZ_WH},
}
Figure