Annotated Sequent Calculi for Paraconsistent Reasoning and Their Relations to Logical Argumentation

Ofer Arieli, Kees van Berkel, Christian StraßerIJCAI 2022 · DOI

TL;DR

This paper introduces "annotated sequent calculi," a novel proof-theoretic framework for non-monotonic reasoning that integrates conflict handling directly into the proof system. By annotating sequents with their derivation status, these calculi allow for revision of conclusions when new, conflicting information arises, offering a robust way to manage inconsistent knowledge and connect formal logic with argumentation theory.

What Problem Does This Paper Address?

In many real-world scenarios, information is not always consistent. We encounter conflicting statements, and our beliefs need to adapt as new evidence emerges. Traditional logical systems often struggle with inconsistency, as a single contradiction can lead to an explosion of conclusions (e.g., proving anything). Non-monotonic reasoning aims to address this by allowing conclusions to be retracted when new information contradicts them. However, existing approaches often separate the reasoning process from the conflict resolution mechanism. This paper tackles the challenge of developing a unified, proof-theoretic framework where the handling of conflicting information is an intrinsic part of the logical inference process, making it more transparent and integrated.

Methods

The core innovation is the introduction of annotated sequent calculi. These are extensions of standard sequent calculi (like those developed by Gentzen) where each sequent is augmented with an annotation. These annotations, such as [i] (introduced/conditionally accepted), [e] (eliminated/attacked), and [!] (finally accepted), represent the current status of a sequent within a derivation.

The calculi are built upon a standard logic and its calculus, and then augmented with:

  • Attack Rules: These rules allow one sequent to "attack" another, changing its annotation from [i] to [e]. Attacks are restricted to be "S-based," meaning they depend on a specific set of premises.
  • Reactivation Rules: These rules allow a previously eliminated sequent ([e]) to be reactivated ([i]) if its attacker is itself counter-attacked.
  • Retrospective Attack Rules: These extend attack rules to allow eliminated attackers to initiate attacks, crucial for handling cycles of attacks.
  • Final Acceptability Rules: These rules determine when a sequent can be considered "finally accepted" ([!]). A sequent is finally accepted if it's conditionally accepted, all its attackers are present in the derivation, and each of those attackers is itself counter-attacked by a finally accepted sequent.

A key feature is the annotation revision process, which occurs after introducing an attack or retrospective attack rule. This process traverses the derivation backwards, updating annotations as needed, ensuring that the system dynamically adapts to new conflicts.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Conflict Resolution as Object-Level Reasoning: Instead of treating conflict resolution as a meta-level process, these calculi embed it directly into the object-level of proofs through annotations and revision rules. This makes the reasoning process more explicit.
  • Modularity: The framework is modular, allowing it to be based on any standard logic with a sound and complete calculus, and any set of attack rules. This makes it highly adaptable.
  • Paraconsistency by Design: The annotation system and revision process inherently prevent the explosion of conclusions from contradictions, making the resulting systems paraconsistent.
  • Strong Connection to Logical Argumentation: The paper demonstrates a direct correspondence between the derivations in these calculi and argumentation frameworks (as defined by Dung). The annotations and attack rules mirror concepts like arguments, attacks, and acceptability semantics.
  • Handling of Attack Cycles: Retrospective attack rules and the revision process are specifically designed to manage complex scenarios like cycles of attacks, which are common in argumentation.

Key Results

The paper establishes that these annotated sequent calculi provide a robust framework for paraconsistent reasoning. They are shown to be:

  • Paraconsistent: Contradictory premises do not lead to an explosive set of finally accepted conclusions.
  • Faithful to Argumentation Semantics: The calculi's derivations correspond to stable and grounded semantics of argumentation frameworks. For instance, the set of finally accepted sequents in a coherent derivation corresponds to a stable extension of the induced argumentation framework.
  • Integrated Revision: The annotation revision process ensures that the status of sequents is dynamically updated, reflecting a defeasible reasoning process.

Limitations and Future Work

The authors acknowledge that the presented work focuses on "defeat attacks" for simplicity and commonness. Future work could explore other types of attacks (e.g., undercut) and their integration. They also mention that while their approach is modular, further investigation into the specific properties and motivations of different base logics and attack rules is warranted. The paper also hints at connections to other formalisms like adaptive logics and annotated logics, suggesting avenues for deeper comparative analysis.

Summary updated

BibTeX
@inproceedings{arieli2022annotated,
  author = {Ofer Arieli and Kees van Berkel and Christian Straßer},
  title = {{Annotated Sequent Calculi for Paraconsistent Reasoning and Their Relations to Logical Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/351},
}
Figure