Introduction
In the field of knowledge representation, the ability to explicitly define concepts is a cornerstone of efficient reasoning and ontology management. This paper investigates the Beth Definability Property across a wide spectrum of expressive Description Logics (DLs). The property serves as a bridge between semantic determination and syntactic expression: it guarantees that if a concept is implicitly determined by a knowledge base, it can also be expressed explicitly using a specific signature.
While many standard DLs are known to possess this property, the authors demonstrate that the addition of role hierarchies ($H$) fundamentally breaks it. Furthermore, they establish that even when explicit definitions exist, computing them is computationally demanding, often requiring double-exponential time and space.
Implicit vs. Explicit Definability
To understand the significance of this work, one must distinguish between two types of definability:
- Implicit Definability: A semantic property where, in every model of a TBox (theory), the interpretation of a concept is uniquely determined by the interpretations of other basic terms in a given signature.
- Explicit Definability: A syntactic property where there exists a formula (a concept expression) using only the terms in the signature that is equivalent to the concept in question.
The Beth Definability Property (BP) holds for a logic if every implicitly definable concept is also explicitly definable. This is not merely a theoretical curiosity; it has practical implications for Ontology Optimization—transforming complex TBoxes into simpler, acyclic terminologies—and Query Rewriting, where queries over an ontology are translated into standard SQL for direct database execution.
Methodology: Constructive Interpolation
The authors employ a combination of proof-theoretic and model-theoretic techniques to map the landscape of Beth definability. A central contribution is a novel tableau-based algorithm designed for the logic $ALCF$.
This algorithm utilizes Constructive Interpolation based on Craig’s Interpolation Theorem. Rather than just proving a definition exists, the algorithm actively constructs an "interpolant" (the explicit definition) by tracing contradictions found during a tableau search. To extend these results to more complex logics, such as those with transitive roles ($S$) or inverse roles ($I$), the authors use signature-preserving reductions and bisimulation arguments to prove the impossibility of explicit definitions in certain contexts.
The Impact of Role Hierarchies
The paper’s most striking finding is that Role Hierarchies ($H$) destroy the Beth Definability Property. Even if a concept is semantically fixed by a signature, the presence of role inclusions (e.g., "all Surgeons are Doctors") can prevent the formulation of a finite expression for that concept using only the allowed terms.
As shown in the classification table above, logics like $ALC$, $ALCS$, $ALCI$, and $ALCF$ maintain the property. However, any logic containing $H$ fails it. The table also distinguishes between the property holding on all structures (BP) versus only on finite structures (BPF), noting that for logics like $ALCFI$, the property fails specifically when restricted to finite databases.
Complexity and the Price of Explicitness
The research highlights a significant gap in succinctness between implicit and explicit definitions. While an implicit definition might be compact, the corresponding explicit definition can be double-exponentially larger. The authors prove this is a fundamental limit of the logic, not an artifact of their algorithm.
Key complexity results include:
- Decidability: Determining if a concept is implicitly definable is EXPTIME-complete.
- Construction: Computing the explicit definition is 2-EXPTIME.
- FOL Alternative: If the target logic is not expressive enough, definitions can often be found using general First-Order Logic (FOL) more efficiently (in single EXPTIME), though the resulting definitions may still be large.
Conclusion
This work provides a comprehensive map of Beth definability in expressive Description Logics, identifying role hierarchies as a critical boundary for the property. While the 2-EXPTIME complexity represents a daunting worst-case scenario, the constructive algorithms provided lay the groundwork for future heuristic-driven implementations that could optimize real-world ontologies and query rewriting systems.
Summary updated