Role Conjunctions in Expressive Description Logics

Autor:	Yevgeny Kazakov, Birte Glimm
Rok vydání:	2016
Předmět:	Discrete mathematics Transitive relation NEXPTIME Description logic Computational complexity theory Computer Science::Logic in Computer Science EXPTIME Jump Inverse Algorithm Mathematics
Zdroj:	Logic for Programming, Artificial Intelligence, and Reasoning ISBN: 9783540894384 LPAR
Popis:	We show that adding role conjunctions to the Description Logics (DLs) $\mathcal{SHI}$ and $\mathcal{SHOIF}$ causes a jump in the computational complexity of the standard reasoning tasks from ExpTime -complete to 2ExpTime -complete and from NExpTime -complete to N2ExpTime -hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for the DL $\mathcal{SHQ}$ a jump in the computational complexity cannot be observed.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4d8adf491a86fd672e0cd7ac22c365e0 https://ora.ox.ac.uk/objects/uuid:dd5630d9-2fda-454b-ad6f-a0c950431832 Zobrazit plný text záznamu