Complexity of Terminological Reasoning Revisited
From International Center for Computational Logic
"September 6 -- 10," is not in the list (Januar, Februar, März, April, Mai, Juni, Juli, August, September, Oktober, ...) of allowed values for the "Month" property.
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
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
@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},
}
