- Titel
- The Complexity of Finite Model Reasoning in Description Logics
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-790234
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 02-05
- Erstveröffentlichung
- 2002
- DOI
- https://doi.org/10.25368/2022.123
- Abstract (EN)
- 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.
- Freie Schlagwörter (DE)
- TBox, ALCQI-Konzept, Beschreibungslogik, EXPTIME-komplett
- Freie Schlagwörter (EN)
- TBox, ALCQI-concept, description logic, EXPTIME-complete
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-790234
- Veröffentlichungsdatum Qucosa
- 30.05.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0