Non-expansive Fuzzy ALC

Stefan Gebhart, Lutz Schröder, Paul WildIJCAI 2025 · DOI

TL;DR

This paper introduces "non-expansive fuzzy ALC," a new fuzzy description logic that balances expressiveness with computational tractability. It achieves the same reasoning complexity as classical description logic (EXPTIME) while offering more expressive power than existing fuzzy logics, particularly for knowledge bases with general rules.

What Problem Does This Paper Address?

Fuzzy description logics (DLs) are designed to represent vague knowledge using truth degrees, typically in the [0, 1] interval. Different "propositional bases" (how logical connectives like AND, OR, NOT are interpreted) lead to trade-offs between expressiveness and computational complexity. The Zadeh base is simple and efficient but lacks expressive power, closely mirroring classical logic. The Łukasiewicz base is more expressive and logically robust but suffers from high computational complexity, even leading to undecidability for certain reasoning tasks with general rules (TBoxes). This paper aims to bridge this gap by creating a fuzzy DL that is more expressive than Zadeh-based fuzzy DLs but retains the computational efficiency of classical DLs, even when dealing with complex TBoxes.

Methods

The authors propose "non-expansive fuzzy ALC," which extends the Zadeh base with "constant shift operators." These operators allow for expressions like C ⊕ c (concept C shifted by a rational constant c), which can model nuanced relationships like "dampened inheritance of properties." The core technical contribution is an unlabelled tableau calculus designed for this new logic. This calculus uses a global caching mechanism to ensure termination and achieve EXPTIME complexity, even for reasoning with general TBoxes. They also introduce specific rules and definitions for handling concept assertions and TBoxes within this fuzzy context.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Expressiveness-Complexity Gap: The key insight is that by carefully extending the Zadeh base with constant shifts, they can gain significant expressive power (especially for TBoxes) without sacrificing the EXPTIME complexity of classical ALC. This is a significant improvement over existing fuzzy DLs where increased expressiveness often leads to undecidability.
  • Constant Shifts as a Sweet Spot: The introduction of constant shift operators (C ⊕ c) is crucial. These operators allow for modeling relationships that are more nuanced than simple minimum/maximum conjunction/disjunction (Zadeh) but less computationally demanding than full Łukasiewicz connectives. They enable modeling phenomena like "dampened inheritance."
  • Unlabelled Tableau Calculus: The development of an unlabelled tableau calculus with global caching is a significant technical achievement. This approach allows for efficient reasoning by avoiding redundant computations and ensuring termination, which is critical for practical applications.
  • TBox Handling: The paper demonstrates that their approach can handle general concept inclusions (GCIs) within TBoxes efficiently, a problem that is notoriously difficult for other fuzzy DLs.

Key Results

  • EXPTIME Completeness: The paper proves that reasoning problems for non-expansive fuzzy ALC, including satisfiability with general TBoxes, are EXPTIME-complete. This matches the complexity of classical ALC and is a substantial improvement over the undecidability of full Łukasiewicz fuzzy ALC with TBoxes.
  • Increased Expressiveness: The logic is shown to be more expressive than Zadeh fuzzy ALC, particularly in its ability to handle complex TBoxes and model nuanced relationships like dampened inheritance. Examples are provided to illustrate this increased expressiveness in domains like social influence and scientific citation networks.

Limitations and Future Work

  • Future Work: The authors mention that future work will involve extending the logic and tableau calculus to accommodate additional features like transitive roles, inverses, and nominals. They note that these features have been integrated into Zadeh-based fuzzy DLs and believe they can be accommodated in non-expansive fuzzy ALC, though the adaptation process needs to be explored.
  • ABoxes: While the technical development focuses on TBoxes, the authors briefly mention that ABoxes can be handled by extending the tableau procedure with additional root nodes for individuals, without affecting the complexity.

Summary updated

BibTeX
@inproceedings{gebhart2025non,
  author = {Stefan Gebhart and Lutz Schröder and Paul Wild},
  title = {{Non-expansive Fuzzy ALC}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/502},
}
Figure