Beth Definability in Expressive Description Logics

Balder ten Cate, Enrico Franconi, Inanç Seylan

TL;DR

This paper investigates the Beth definability property in expressive Description Logics (DLs), which connects implicit and explicit definitions of concepts. The authors provide a complete classification of this property for various DL extensions and develop optimal algorithms for computing explicit definitions, showing that they can be exponentially larger than their implicit counterparts.

What Problem Does This Paper Address?

In logic, the Beth definability property is a fundamental concept that links whether a concept is implicitly defined by a set of other concepts and roles to whether it can be explicitly defined using only those concepts and roles. This property is crucial for optimizing reasoning in knowledge representation systems, particularly in areas like ontology-based data access where queries need to be rewritten in terms of available data. However, not all logics possess this property, and for those that do, understanding the complexity and size of the explicit definitions is vital. This paper addresses the question of which expressive Description Logics (DLs) satisfy the Beth definability property and quantifies the complexity of obtaining explicit definitions when they exist.

Methods

The authors tackle this problem by:

  • Classifying Beth Definability: They provide a complete classification of the Beth definability property for extensions of the basic DL ALC, including features like transitive roles, inverse roles, role hierarchies, and functionality restrictions, considering both arbitrary and finite structures.
  • Developing Tableau-Based Algorithms: They present a constructive, tableau-based algorithm to compute explicit definitions. This algorithm is designed to be optimal in terms of worst-case complexity.
  • Leveraging Interpolation: The core of their positive results on Beth definability relies on establishing an interpolation property for these DLs, which is then used to construct the explicit definitions.
  • Analyzing First-Order Logic Definitions: They also investigate the case where explicit definitions can be expressed in first-order logic, leading to more efficient computation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Beth Definability is Not Universal: Not all expressive DLs possess the Beth definability property. The presence of role hierarchies, for instance, can cause this property to fail. This highlights that expressivity comes at a cost.
  • Explicit Definitions Can Be Huge: Even when a concept is implicitly definable, the smallest explicit definition can be exponentially larger than the implicit definition. This is a crucial insight for understanding the practical implications of reasoning with DLs.
  • Tableau Algorithms are Powerful Tools: The paper demonstrates the effectiveness of tableau-based methods not only for decision problems but also for constructive tasks like computing interpolants and explicit definitions.
  • Finite vs. Infinite Models Matter: The Beth definability property can behave differently when restricted to finite models, posing additional challenges.

Key Results

  • Complete Classification: The paper provides a complete classification of the Beth definability property for various extensions of ALC.
  • Optimal Algorithms: They present algorithms for computing explicit definitions that are optimal in terms of worst-case complexity.
  • For DLs with the Beth definability property, explicit DL-concept definitions can be computed in double exponential time and can be of double exponential size.
  • When explicit definitions are allowed in first-order logic, they can be computed in single exponential time.
  • Lower Bounds: They establish double exponential lower bounds on the size of explicit definitions, showing that the double exponential upper bounds are tight.
  • Failure of Beth Definability: The paper demonstrates that DLs with role hierarchies (like ALCH) do not have the Beth definability property, and even extensions with transitive closure (ALCFI+) fail the finite version of the property (BPF).

Limitations and Future Work

  • Complexity of Nominal and Qualified Number Restrictions: The authors note that extending their upper bound results on the size of explicit definitions to DLs with nominals (O) and qualified number restrictions (Q) is more difficult due to the lack of natural and optimal tableau algorithms for these extensions.
  • First-Order Interpolant Lower Bound: An open problem is whether a matching lower bound exists for first-order explicit definitions, i.e., if there are cases where single exponential size is indeed necessary.
  • Role Conjunction: It remains an open question whether ALCH extended with role conjunction has the Beth definability property.
  • Minimal Extension for BPF: Identifying a minimal extension of ALCFI that possesses the finite Beth definability property (BPF) is also left as future work.

Summary updated

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