A Variable Occurrence-Centric Framework for Inconsistency Handling

Yakoub SalhiAAAI 2025 · DOI

TL;DR

This paper introduces a novel syntactic framework for analyzing and handling inconsistencies in logical knowledge bases. By focusing on the specific occurrences of variables within formulas, rather than just the variables themselves, it offers a more granular way to pinpoint the sources of conflict and develop new methods for reasoning under inconsistency.

What Problem Does This Paper Address?

Logical systems, especially those used for knowledge representation, often suffer from the "explosion principle": a single contradiction can lead to the derivation of any conclusion, rendering the entire knowledge base useless. This is a critical issue in real-world applications where data can be noisy, vague, or come from multiple conflicting sources. Existing approaches to handle inconsistency, like minimal inconsistent subsets (MISes) and maximal consistent subsets (MCSes), often treat formulas as black boxes. They can miss subtle conflicts that arise from how variables are used within those formulas. For example, replacing a formula with an equivalent one might not change its MIS/MCS status, even if the original formula's structure was key to the inconsistency. This paper aims to address this limitation by providing a more detailed, occurrence-aware analysis of inconsistency.

Methods

The core of the paper's contribution lies in its introduction of two dual concepts: Minimal Inconsistency Relations (MIRs) and Maximal Consistency Relations (MCRs). These are equivalence relations defined not on formulas, but on variable occurrences within a knowledge base.

  • MIRs capture the minimal relationships between variable occurrences that cause inconsistency. They are defined by compliance (occurrences must be of the same variable), inconsistency (the relation leads to a contradiction), and minimality (no smaller relation has the same properties).
  • MCRs are the dual concept, representing maximal relationships between variable occurrences that avoid inconsistency.

Using MCRs, the authors propose a new family of non-explosive inference relations. The strategy involves modifying the knowledge base based on an MCR (by renaming variable occurrences according to equivalence classes) and then applying classical inference. This approach aims to restore consistency while retaining all original formulas and variables.

Additionally, the paper introduces an occurrence-based semantics, where truth values are assigned to variable occurrences rather than variables themselves. This semantics is shown to be closely related to the MCR framework.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and uses small, illustrative examples of propositional bases.

Key Insights and Ideas

  • Granularity Matters: The paper convincingly argues that focusing on variable occurrences (e.g., the first 'p' in a formula vs. the second 'p') provides a richer understanding of inconsistency than treating formulas as atomic units.
  • Beyond MIS/MCS: MIRs and MCRs offer a more nuanced way to analyze conflicts, potentially capturing inconsistencies that MIS/MCS approaches might overlook.
  • Syntactic Detail is Crucial: The authors highlight how syntactic details, like the specific context of a variable's appearance, are vital for understanding and resolving conflicts, especially in cases of imprecision or encoding errors.
  • Dual Concepts for Duality: The introduction of MIRs and MCRs, with their formal duality, provides a powerful theoretical foundation for both identifying and resolving inconsistencies.
  • Occurrence-Based Semantics: Assigning truth values to occurrences rather than variables is an unusual but effective way to model inconsistency and connect it to the syntactic framework.

Key Results

  • The paper formally defines MIRs and MCRs and establishes their properties, including duality.
  • It introduces four new non-explosive inference relations based on MCRs and BMCRs (a refined version of MCRs).
  • It demonstrates that these new inference relations coincide with classical inference for consistent knowledge bases.
  • The paper establishes connections between its framework and existing approaches like paraconsistent logic (LPm) and occurrence-based semantics.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that investigating the computational complexity of MIRs, MCRs, and the proposed inference relations is a key area for future work.
  • Broader Logic Systems: The authors express interest in extending the framework to handle non-classical logics and exploring additional inference relations based on specific MCR criteria.
  • Practical Applications: While the theoretical foundation is laid, the paper doesn't delve into specific practical applications or empirical evaluations on large-scale datasets.

Summary updated

BibTeX
@inproceedings{salhi2025variable,
  author = {Yakoub Salhi},
  title = {{A Variable Occurrence-Centric Framework for Inconsistency Handling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33661},
}
Figure