The Complexity of Finite Model Reasoning in Description Logics

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

Toggle side column

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
Proc. of the 19th Conference on Automated Deduction (CADE-19), volume 2741 of Lecture Notes in Artificial Intelligence, 2003. Springer
  • 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.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
The final publication is available at Springer.
@inproceedings{ LST03,
  author = {C. {Lutz} and U. {Sattler} and L. {Tendera}},
  booktitle = {Proc. of the 19th Conference on Automated Deduction (CADE-19)},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {The Complexity of Finite Model Reasoning in Description Logics},
  volume = {2741},
  year = {2003},
}