On the Complexity of Terminological Reasoning

Carsten LutzCarsten Lutz

Carsten Lutz
On the Complexity of Terminological Reasoning
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-04, 1999. LTCS-Report

Details
Bibtex

KurzfassungAbstract
TBoxes are an important component of knowledge representation systems based on description logics DLs since they allow for a natural representation of terminological knowledge. Largely due to a classical result given by Nebel, complexity analyses for DLs have, until now, mostly focused on reasoning without (acyclic) TBoxes. In this paper, we concentrate on DLs, for which reasoning without TBoxes is PSpace-complete, and show that there exist logics for which the complexity of reasoning remains in PSpace if acyclic TBoxes are added and also logics for which the complexity increases. An example for a logic of the former type is ALC while examples for logics of the latter kind include ALC(D) and ALCF. This demonstrates that it is necessary to take TBoxes into account for complexity analyses. Furthermore, we show that reasoning with the description logic ALCRP(D) is NExpTime-complete regardless of whether TBoxes are admitted or not.
Bemerkung: Note: This report is superceded by the LTCS-00-01 technical report and my LPAR'99 paper.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Lutz-LTCS-99-04,
  address = {Germany},
  author = {C. {Lutz}},
  institution = {LuFG Theoretical Computer Science, RWTH Aachen},
  note = {This report is superceded by the LTCS-00-01 technical report and my LPAR'99 paper.},
  number = {LTCS-99-04},
  title = {On the Complexity of Terminological Reasoning},
  type = {LTCS-Report},
  year = {1999},
}