Number Restrictions on Transitive Roles in Description Logics with Nominals

Víctor Gutiérrez-Basulto, Yazmín Angélica Ibáñez-García, Jean Christoph JungAAAI 2017 · DOI

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.
Grid structure used in torus tiling reductions to establish NEXPTIME-hardness.
  • 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

BibTeX
@inproceedings{gutierrezbasulto2017number,
  author = {Víctor Gutiérrez-Basulto and Yazmín Angélica Ibáñez-García and Jean Christoph Jung},
  title = {{Number Restrictions on Transitive Roles in Description Logics with Nominals}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10678},
}
Figure