The Complexity of Reasoning with Concrete Domains (Revised Version)
Aus International Center for Computational Logic
The Complexity of Reasoning with Concrete Domains (Revised Version)
Carsten LutzCarsten Lutz
Carsten Lutz
The Complexity of Reasoning with Concrete Domains (Revised Version)
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-01, 1999. LTCS-Report
The Complexity of Reasoning with Concrete Domains (Revised Version)
Technical Report, LuFG Theoretical Computer Science, RWTH Aachen, volume LTCS-99-01, 1999. LTCS-Report
- KurzfassungAbstract
Description logics are knowledge representation and reasoning formalisms which represent conceptual knowledge on an abstract logical level. Concrete domains are a theoretically well-founded approach to the integration of description logic reasoning with reasoning about concrete objects such as numbers, time intervals or spatial regions. In this paper, the complexity of combined reasoning with description logics and concrete domains is investigated. We extend ALC(D), which is the basic description logic for reasoning with concrete domains, by the operators "feature agreement" and "feature disagreement". For the extended logic, called ALCF(D), an algorithm for deciding the ABox consistency problem is devised. The strategy employed by this algorithm is vital for the efficient implementation of reasoners for description logics incorporating concrete domains. Based on the algorithm, it is proved that the standard reasoning problems for both logics ALC(D) and ALCF(D) are PSpace-complete - provided that the satisfiability test of the concrete domain used is in PSpace. - Bemerkung: Note: See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ Lutz-LTCS-99-01,
address = {Germany},
author = {C. {Lutz}},
institution = {LuFG Theoretical Computer Science, RWTH Aachen},
note = {See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.},
number = {LTCS-99-01},
title = {The Complexity of Reasoning with Concrete Domains (Revised Version)},
type = {LTCS-Report},
year = {1999},
}
