The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics

Ian Horrocks, Stephan TobiesJAIR 2000 · DOI

TL;DR

This paper investigates the computational complexity of reasoning in expressive Description Logics (DLs) augmented with cardinality restrictions and nominals. The authors establish tight complexity bounds for these logics, showing that while some extensions remain decidable in EXPTIME, others, particularly those involving both inverse roles and nominals, push the complexity to NEXPTIME-complete. This work clarifies the trade-offs between expressivity and computational cost in DLs.

What Problem Does This Paper Address?

Description Logics (DLs) are foundational for knowledge representation and reasoning, enabling the formalization of concepts and relationships within a domain. Researchers are constantly seeking to increase the expressivity of DLs to better model complex real-world scenarios. Two key features that enhance expressivity are:

  1. Cardinality Restrictions: These allow specifying the exact number of individuals that must be related to an individual via a particular role (e.g., "a parent of at least two children").
  2. Nominals: These are special concepts that refer to specific individuals (e.g., "the concept of Alice").

While adding these features increases modeling power, it also raises concerns about the computational complexity of reasoning tasks like checking concept satisfiability or TBox consistency. The paper aims to precisely characterize the complexity of reasoning for DLs that combine these expressive features, specifically focusing on the DLs ALCQ (with cardinality restrictions) and ALCQI (ALCQ with inverse roles), and their extensions with nominals (ALCQO, ALCQIO). The goal is to understand how these features impact decidability and to establish tight upper and lower bounds for reasoning problems.

Methods

The paper employs a combination of techniques to establish its complexity results:

  • Translation to Two-Variable Logic with Counting (C²): For ALCQI with cardinality restrictions, the authors leverage a known translation to C², a fragment of first-order logic with two variables and counting quantifiers. This translation allows them to inherit existing decidability results for C² (NEXPTIME-complete) and establish an upper bound for the DL problem.
  • Reductions from Bounded Domino Problems: To establish lower bounds (NEXPTIME-completeness), the authors use a standard technique involving reductions from a bounded version of the domino problem. This involves constructing specific DL TBoxes that encode the tiling constraints of the domino problem, thus showing that if the domino problem is hard, so is the DL reasoning problem.
  • Reductions between DL Formalisms: The paper also uses reductions between different DL TBox formalisms. For instance, they show how to express cardinality restrictions using nominals and general axioms, and vice-versa. This allows them to transfer complexity results between logics.
  • Spy-Point Technique: For reasoning with nominals and inverse roles, a "spy-point" technique is used to internalize general inclusion axioms into concepts, simplifying the reasoning problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Cardinality Restrictions Add Significant Complexity: Even for relatively simple DLs like ALCQ, adding cardinality restrictions pushes the complexity from PSPACE-complete (for concept satisfiability without restrictions) to EXPTIME-complete for TBox consistency. This highlights that even seemingly minor additions can have a substantial impact.
  • Nominals Don't Always Increase Complexity (if alone): The paper shows that for ALCQO (ALCQ with nominals), TBox consistency remains EXPTIME-complete. This suggests that nominals, in isolation or with certain other features, might not be the primary driver of higher complexity.
  • The Combination is Key: The real jump in complexity occurs when nominals are combined with inverse roles and cardinality restrictions (ALCQIO). This combination leads to NEXPTIME-completeness for TBox consistency and concept satisfiability, indicating a significant increase in computational difficulty.
  • Loss of Tree-Model Property: The authors suggest that the loss of the "tree-model property" for certain DLs (like ALCQI with cardinality restrictions) might be an explanation for their increased complexity. This property is known to be beneficial for efficient reasoning in many modal logics.
  • Unary vs. Binary Coding Matters: The paper explicitly discusses the impact of number coding. While unary coding is assumed for most results, it's noted that binary coding can lead to higher complexity (e.g., NEXPTIME-hard for ALCQ with cardinality restrictions), and the question of whether this is the tightest bound remains open.

Key Results

The paper establishes the following tight complexity bounds (assuming unary coding of numbers):

  • ALCQI with Cardinality Restrictions: TBox consistency is NEXPTIME-complete.
  • ALCQ with Cardinality Restrictions: TBox consistency is EXPTIME-complete. This improves upon previous NEXPTIME results.
  • ALCQO with General Axioms: TBox consistency is EXPTIME-complete.
  • ALCQIO with General Axioms: TBox consistency is NEXPTIME-complete.
  • ALCQIO Concept Satisfiability: This is also shown to be NEXPTIME-complete, a sharper result than previously known.

Limitations and Future Work

  • Binary Coding of Numbers: The paper notes that for binary coding of numbers, the complexity of some problems (e.g., ALCQ with cardinality restrictions) becomes NEXPTIME-hard, and it's an open question whether this is the tightest bound or if a 2-NEXPTIME algorithm is truly necessary. This is a direct avenue for future research.
  • Dedicated Algorithms: While the paper establishes theoretical complexity, it acknowledges that existing algorithms (like those for C²) might not be the most efficient in practice. The authors suggest that dedicated algorithms for DLs like ALCQI with cardinality restrictions could potentially offer better average-case performance.
  • Practical Applications: The paper mentions applications in reasoning with database schemata. Further work could explore how these complexity results impact the practical feasibility of using these expressive DLs in such systems.
  • Unique Name Assumption: The paper discusses the implications of the unique name assumption for nominals and chooses not to impose it due to counter-intuitive consequences. Further exploration of reasoning with nominals under different assumption sets could be beneficial.

Summary updated

BibTeX
@article{horrocks2000complexity,
  author = {Ian Horrocks and Stephan Tobies},
  title = {{The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics}},
  journal = {JAIR},
  year = {2000},
  doi = {10.1613/jair.705},
}
Figure