Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes

Víctor Gutiérrez-Basulto, Jean Christoph Jung, Thomas SchneiderIJCAI 2015

Introduction

Temporal Description Logics (TDLs) are essential for modeling knowledge that evolves over time, particularly in domains like medicine and biology. While standard Description Logics (DLs) handle static relationships, TDLs integrate temporal operators (e.g., from LTL or CTL) to capture dynamic properties. However, the combination of complex TBoxes and "rigid roles"—relationships that remain constant across time—often leads to undecidability or extreme computational complexity.

The Complexity Challenge

The primary hurdle in TDL research is the "computational explosion" that occurs when rigid roles are introduced alongside general TBoxes. In such settings, reasoning often becomes undecidable. This paper explores a path toward tractability by focusing on the lightweight DL $\mathcal{EL}$ and restricting the knowledge base to acyclic TBoxes, where definitions cannot be circular. This restriction is practically relevant, as major ontologies like SNOMED CT and the Gene Ontology (GO) are largely composed of acyclic $\mathcal{EL}$ definitions.

Methodology: Mapping the Landscape

The authors utilize several advanced proof techniques to analyze the complexity of various TDL fragments:

  • Quasimodel Technique: Demonstrates that even the more expressive $\mathcal{ALC}$ logic remains decidable (though nonelementary) under acyclic TBox restrictions.
  • Canonical Models & Expansion Vectors: For $\mathcal{EL}$, the authors employ canonical models to represent concept satisfaction. They introduce "expansion vectors" to manage temporal operators like $E\Diamond$ ("possibly eventually").
  • Completion Algorithms: The researchers adapted standard $\mathcal{EL}$ completion algorithms to incorporate temporal steps, iteratively adding implied facts until a fixed point is reached.
  • Trace-Based Reasoning: To handle the $A\Box$ ("always globally") operator within PSPACE limits, a "trace" algorithm explores paths in the temporal model without storing the entire exponential structure.
Figure 5: Illustration of the concept tree $t_C$ and its corresponding temporal interpretations $\mathfrak{I}_C$ and $\mathfrak{I}_C^{pre}$, used in the canonical model construction.

Key Insights

The study reveals that acyclicity is a critical factor in taming the complexity of TDLs with rigid roles. By preventing circular definitions, the logic avoids encoding the complex problems that lead to undecidability. Furthermore, the use of branching-time logic (CTL) allows for modeling multiple potential futures, which is vital for clinical pathways where outcomes are uncertain. The paper demonstrates that for many $\mathcal{EL}$ + CTL fragments, reasoning remains in PTIME, matching the efficiency of standard $\mathcal{EL}$.

Results and Complexity Table

The research provides a detailed complexity landscape for TDLs with rigid roles and acyclic TBoxes:

Logic Fragment Complexity Significance
$\mathcal{ALC}$ + CTL Nonelementary Decidable, but computationally expensive.
$\mathcal{EL}$ + $E\Diamond$ PTIME Highly efficient; same as standard $\mathcal{EL}$.
$\mathcal{EL}$ + $E\bigcirc$ PTIME Efficient for "next step" reasoning.
$\mathcal{EL}$ + $E\Diamond$ + $E\bigcirc$ coNP-complete Increased complexity with combined operators.
$\mathcal{EL}$ + $E\Diamond$ + $A\Box$ PSPACE-complete Handles global constraints within elementary bounds.

Conclusion and Future Directions

This work identifies "islands of tractability" in the TDL landscape. By combining $\mathcal{EL}$ with acyclic TBoxes, researchers can model rigid roles without sacrificing decidability. Future work may extend these findings to include "rigid concepts" (e.g., "Human") and "temporal roles" that follow specific patterns. Additionally, applying these restrictions to TDLs based on Linear Temporal Logic (LTL) or the $\mu$-calculus remains an open area for exploration.

Summary updated

BibTeX
@inproceedings{gutierrezbasulto2015lightweight,
  author = {Víctor Gutiérrez-Basulto and Jean Christoph Jung and Thomas Schneider},
  title = {{Lightweight Temporal Description Logics with Rigid Roles and Restricted TBoxes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure