Abstract
This paper explores the computational boundaries of Description Logics (DLs) that combine transitive roles, number restrictions (counting), and nominals. While these features are essential for modeling complex domains such as medical ontologies and the Semantic Web, their interaction often leads to undecidability. The authors map the "decidability frontier," establishing new complexity bounds ranging from EXPTIME to NEXPTIME and identifying specific configurations where the logic becomes undecidable. These results provide critical guidance for the design of expressive yet tractable knowledge representation systems.
Introduction
Description Logics (DLs) provide the formal underpinnings for modern knowledge representation, balancing expressivity with computational tractability. Two highly desirable features—transitive roles (e.g., part-of or descendant-of) and number restrictions (e.g., "a protein has at least three components")—are notoriously difficult to combine. When counting is permitted over transitive relationships, the logic often loses decidability, meaning no algorithm can guarantee a solution in finite time. This research addresses long-standing gaps in our understanding of these combinations, particularly when nominals (names for specific individuals) are introduced into the logic.
Methods
The authors employ several sophisticated proof techniques to establish the complexity of various DL fragments:
- Quasimodels: To prove the complexity of the logic $SOQ$, the authors use a "quasimodel" approach. This involves decomposing complex models into smaller components that interpret a single role, thereby establishing a "small model property."
- Type-Elimination: For $SON$ with unary coding, a type-elimination procedure is used to iteratively remove unsatisfiable sets of concepts (types).
- Torus Tiling Reductions: To establish NEXPTIME-hardness, the authors reduce the tiling problem on an exponential grid to a satisfiability problem in the logic. This requires encoding a complex grid structure directly into the logic's constraints.
- Reduction to Local Reflexivity: For logics involving functionality (counting up to one), the authors show these can be reduced to a logic with a "self" loop concept ($\exists r.self$), which is more amenable to analysis.
Key Insights and Ideas
- The Impact of Number Coding: A significant finding is that the complexity of the logic $SON$ depends on the encoding of numbers. If numbers are written in unary, the problem is EXPTIME-complete. However, if written in binary, it jumps to NEXPTIME-complete because binary coding allows large numbers to be used to encode complex grid structures like a torus.
- Functionality as a Safe Haven: While general counting over transitive roles is computationally dangerous, restricting counting to functionality (at most 1) allows for the inclusion of inverse roles and role hierarchies without losing decidability.
- The "Lite" Trap: The paper demonstrates that even the DL-Lite family—specifically designed for low complexity—becomes undecidable if role inclusions and number restrictions on transitive roles are allowed. This warns developers that "Lite" fragments are not inherently safe when certain features interact.
Results Summary
The paper establishes a complete picture of the complexity for several key DL fragments:
| Logic Fragment | Counting Type | Complexity |
|---|---|---|
| $SOQ$ | Qualified | NEXPTIME-complete |
| $SON$ | Unqualified (Unary) | EXPTIME-complete |
| $SON$ | Unqualified (Binary) | NEXPTIME-complete |
| $SHIF$ / $SHOIF$ | Functionality only | EXPTIME / NEXPTIME-complete |
| $DL-Lite_{core}^{HN}$ | Unqualified | Undecidable |
Conclusion and Future Work
By mapping the decidability frontier, this research provides a roadmap for the development of future knowledge representation languages. The authors identify several remaining "white spots," such as the decidability of logics combining inverse roles with counting greater than 1 over transitive roles. Future work will focus on developing practical "consequence-based" reasoning algorithms and investigating how these transitive counting features affect conjunctive query answering in data-intensive applications.
Summary updated