This paper, presented at AAAI-21, explores a fundamental challenge in Description Logics (DLs): what happens when our logics lose the "nice" properties that usually make finding definitions and interpolants easy? Specifically, it tackles logics that include nominals (names for specific individuals) and role inclusions (hierarchies of relationships), proving that while these properties disappear, the problems remain solvable—albeit at a higher computational cost.
The Core Problem: CIP and BDP
In ontology engineering and data management, two properties are highly prized:
- Craig Interpolation Property (CIP): If one concept implies another, there should be a "middle-man" concept (an interpolant) using only the shared vocabulary that bridges the two.
- Beth Definability Property (BDP): If a concept is uniquely determined by other symbols (implicit definability), there must be a way to write out its definition using those symbols (explicit definability).
These properties are useful for tasks like query rewriting, modularizing ontologies, and "concept learning" from data. However, standard Description Logics like $\mathcal{ALCO}$ (with nominals) and $\mathcal{ALCH}$ (with role inclusions) do not satisfy these properties. The gap addressed here is: If the logic doesn't guarantee a definition exists, can we at least decide if one exists for a specific given case? Until this paper, the decidability and complexity of this "existence problem" for these specific logics were unknown.
Methodology: Bisimulations and Mosaics
The authors employ a mix of model theory and complexity analysis to bridge this gap. A central tool is the use of bisimulations to characterize when two models are indistinguishable over a specific signature.
They prove that an interpolant fails to exist if and only if two models can be "jointly consistent" while being bisimilar over a specific signature. To handle the computational complexity, they developed:
- Joint Consistency Modulo Bisimulations: A new model-theoretic characterization.
- Mosaic-style Algorithm: A "double exponential time mosaic-style algorithm" for the upper bound. This involves breaking down models into small, manageable pieces (mosaics) and checking if they can be tiled together to form the required counter-models.
- ATM Reductions: To prove the lower bound (hardness), they reduce the word problem of exponentially space-bounded Alternating Turing Machines (ATMs) to the existence problem.
Key Insights: The "Computational Tax"
- Harder than Deduction: Usually, checking if an implication holds (validity) is the "gold standard" for complexity in DLs (often EXPTIME). This paper shows that checking for the existence of an interpolant is strictly harder—2EXPTIME-complete. We pay a "computational tax" for the logic's lack of nice properties.
- Nominals are "Difficult": Defining a nominal (a specific individual like
{London}) using other symbols is 2EXPTIME-complete. However, defining a general concept name (likeCity) is only EXPTIME-complete in some settings. - Restoring Beth: A surprising insight is that while $\mathcal{ALCO}$ doesn't have the Beth property, adding inverse roles ($\mathcal{I}$) or the universal role ($u$) actually restores the Beth property for concept names, though not for nominals.
Key Results
- Decidability: The existence of interpolants and explicit definitions is decidable for $\mathcal{ALCO}$, $\mathcal{ALCH}$, and their extensions (including inverse roles and the universal role).
- 2EXPTIME-Completeness: This is the main complexity result for interpolant existence and "projective" definition existence (defining a concept using a subset of the vocabulary).
- EXPTIME-Completeness: The authors found an "easier" sub-problem: deciding if a concept name has a non-projective definition (using all other symbols in the ontology) is only EXPTIME-complete.
Limitations and Future Work
The 2EXPTIME result is a "worst-case" theoretical bound. The current mosaic-style algorithm is not intended for direct implementation. Future work includes developing "tableau-like" procedures more suitable for practical DL reasoners and extending these results to even more expressive logics like $\mathcal{SHOIQ}$ used in the OWL 2 standard.
Summary updated