Complexity of Terminological Reasoning Revisited

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

„September 6 -- 10,“ befindet sich nicht in der Liste (Januar, Februar, März, April, Mai, Juni, Juli, August, September, Oktober, ...) zulässiger Werte für das Attribut „Month“.

Toggle side column

Complexity of Terminological Reasoning Revisited

Carsten LutzCarsten Lutz
Carsten Lutz
Complexity of Terminological Reasoning Revisited
Proceedings of the 6th International Conference on Logic for Programming and Automated Reasoning LPAR'99, Lecture Notes in Artificial Intelligence, 181-200,  1999. Springer
  • KurzfassungAbstract
    TBoxes in their various forms are key components 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 failed to take into account the most basic form of TBoxes, so-called 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. This demonstrates that it is necessary to take acyclic TBoxes into account for complexity analyses.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
The final publication is available at Springer.
@inproceedings{ Lutz-LPAR-99,
  author = {C. {Lutz}},
  booktitle = {Proceedings of the 6th International Conference on Logic for Programming and Automated Reasoning {LPAR'99}},
  month = {September 6 -- 10,},
  pages = {181--200},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Complexity of Terminological Reasoning Revisited},
  year = {1999},
}