We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic SHI, we show that deciding satisfiability and subsumption of concepts, with or without a TBox, are ExpTime-complete problems. In ALCHI and a variant of SI, these decision problems become PSpace-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between ALC and SHI
Borgwardt, S., Penaloza Nyssen, R. (2013). The complexity of lattice-based fuzzy description logics. JOURNAL ON DATA SEMANTICS, 2(1), 1-19 [10.1007/s13740-012-0013-x].
The complexity of lattice-based fuzzy description logics
Penaloza Nyssen, R
2013
Abstract
We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic SHI, we show that deciding satisfiability and subsumption of concepts, with or without a TBox, are ExpTime-complete problems. In ALCHI and a variant of SI, these decision problems become PSpace-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between ALC and SHI
| File | Dimensione | Formato | |
|---|---|---|---|
|
BoPe-JoDS12.pdf
accesso aperto
Tipologia di allegato:
Author’s Accepted Manuscript, AAM (Post-print)
Dimensione
323.93 kB
Formato
Adobe PDF
|
323.93 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
