The Complexity of Finite Model Reasoning in Description Logics

C. LutzC. Lutz, U. SattlerU. Sattler, L. TenderaL. Tendera

Datei:LuSaTe-IandC05.ps.gz

Download

C. Lutz, U. Sattler, L. Tendera
The Complexity of Finite Model Reasoning in Description Logics
Information and Computation, 199:132--171, 2005

Details
Bibtex

KurzfassungAbstract
We analyse 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

@article{ Lutz-et-al-IANDC-05,
  author = {C. {Lutz} and U. {Sattler} and L. {Tendera}},
  journal = {Information and Computation},
  pages = {132--171},
  title = {The Complexity of Finite Model Reasoning in Description Logics},
  volume = {199},
  year = {2005},
}