Beth Definability in Expressive Description Logics

Balder ten Cate, Enrico Franconi, Inanç Seylan

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$.

Tableau rules for constructive interpolation.

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.

Master Table classifying the Beth property across the ALC family.

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

Abstract

The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.
BibTeX
@inproceedings{cate2011beth,
  author = {Balder ten Cate and Enrico Franconi and Inanç Seylan},
  title = {{Beth Definability in Expressive Description Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-188},
}

Loading related content...

Figure