The Complexity of Finite Model Reasoning in Description Logics
From International Center for Computational Logic
The Complexity of Finite Model Reasoning in Description Logics
Carsten LutzCarsten Lutz, Ulrike SattlerUlrike Sattler, L. TenderaL. Tendera
Carsten Lutz, Ulrike Sattler, L. Tendera
The Complexity of Finite Model Reasoning in Description Logics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-02-05, 2002. LTCS-Report
The Complexity of Finite Model Reasoning in Description Logics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-02-05, 2002. LTCS-Report
- KurzfassungAbstract
We analyze the complexity of finite model reasoning in the description logic ALCQI, i.e. ALC augmented with qualifying number restrictions, inverse roles, and general TBoxes. It turns out that all relevant reasoning tasks such as concept satisfiability and ABox consistency are ExpTime-complete, regardless of whether the numbers in number restrictions are coded unarily or binarily. Thus, finite model reasoning with ALCQI is not harder than standard reasoning with ALCQI. - Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ LutzSattlerTendera-LTCS-02-05,
address = {Germany},
author = {C. {Lutz} and U. {Sattler} and L. {Tendera}},
institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {LTCS-02-05},
title = {The Complexity of Finite Model Reasoning in Description Logics},
type = {LTCS-Report},
year = {2002},
}
