Stable Model Semantics for Description Logic Terminologies

Federica Di Stefano, Mantas SimkusAAAI 2024 · DOI

Introduction

Description Logics (DLs) are the formal foundation for modern knowledge representation, most notably underpinning the Web Ontology Language (OWL). Traditionally, DLs operate under the Open-World Assumption (OWA): if a fact is not explicitly stated as false, it is considered potentially true. While this is powerful for distributed knowledge like the Semantic Web, many real-world applications—such as healthcare diagnostic systems or the SHACL constraint language for RDF—require Closed-World Assumption (CWA) or default negation. For instance, in a clinical setting, if a patient is not recorded as having an allergy, a system should be able to safely assume the absence of that allergy for immediate decision-making.

This paper introduces a robust "stable model" semantics for DL terminologies, bridging the gap between open-world reasoning and the precision of logic programming. The authors provide a framework that handles cyclic definitions and negation while maintaining computational feasibility for key logic fragments.

The Problem: Circularity and Justification

The primary challenge in applying closed-world reasoning to DLs lies in cyclic definitions. When Concept A is defined by Concept B, and Concept B is defined by Concept A, classical logic can produce "self-supported" models. These models are often counter-intuitive because they lack a "well-founded" justification—a clear chain of reasoning tracing back to base facts.

The goal of this research is to establish a semantics where every truth in a model is justified, even in the presence of complex cycles and negation, effectively adapting the principles of Answer Set Programming (ASP) to the DL context.

Methodological Framework

The authors utilize Quantified Equilibrium Logic (QEL) to provide a formal foundation for stable models in DLs. This approach allows for the elegant handling of "fixed predicates"—base data that should remain minimized. To ensure the robustness of their semantics, they provide three equivalent definitions for stable models:

  1. Equilibrium Logic: A logical foundation based on the logic of here-and-there.
  2. Level Mappings: A method to ensure no infinite chains of justification exist, preventing circular reasoning.
  3. Fixpoint Computation: An algorithmic approach to reaching a stable state through iterative refinement.

To analyze the complexity of these semantics, the authors employ an automata-theoretic approach. Specifically, they use 2-way Alternating Tree Automata (2ATA) to show that $ALCI$ terminologies under stable model semantics possess a "tree-model property." This property allows reasoning tasks to be reduced to an automaton emptiness check.

Key Insights and Complexity Results

The research reveals a significant divide in the computational landscape of stable model semantics for DLs:

  • The Undecidability Barrier: The authors prove that adding nominals (individual names, represented by the 'O' in $ALCIO$) makes minimal model reasoning undecidable. This identifies a sharp boundary for what is computationally feasible when mixing minimization with expressive DLs.
  • Complexity Parity for $ALCI$: Surprisingly, for $ALCI$ terminologies (which include cycles and inverse roles), the stable model semantics does not increase the worst-case complexity. Reasoning remains EXPTIME-complete, the same as under classical descriptive semantics. This suggests that "well-foundedness" can be achieved as a "free" benefit in terms of computational overhead for this fragment.
  • Loss of Finite Model Property: Unlike some simpler classical DLs, the authors demonstrate that under stable model semantics, certain terminologies may only possess infinite models, necessitating specialized reasoning techniques.

Conclusion and Future Work

This paper establishes that stable model semantics is a viable and computationally efficient way to introduce default negation into $ALCI$ terminologies. By providing a well-founded justification for every membership in a defined concept, the framework offers a more intuitive approach to knowledge representation in closed-world scenarios.

Future research directions include:

  • Expressivity vs. Decidability: Exploring how to include nominals or other features without triggering undecidability.
  • Finite Model Reasoning: Investigating reasoning specifically over finite models, which is critical for database applications.
  • SHACL Integration: Mapping the full SHACL standard—including regular expressions over roles—to this stable model framework.
  • Practical Implementation: Developing high-performance reasoners that implement these theoretical bounds for real-world use cases.

Summary updated

BibTeX
@inproceedings{stefano2024stable,
  author = {Federica Di Stefano and Mantas Simkus},
  title = {{Stable Model Semantics for Description Logic Terminologies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28917},
}
Figure