We consider the fuzzy logic ALCI with semantics based on a finite residuated lattice. We show that the problems of satisfiability and subsumption of concepts in this logic are ExpTime-complete w.r.t. general TBoxes and PSpace-complete w.r.t. acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp ALCI.
Borgwardt, S., Peñaloza, R. (2011). Finite Lattices Do Not Make Reasoning in ALCI Harder. In 7th International Workshop on Uncertainty Reasoning for the Semantic Web, collocated with the 10th International Semantic Web Conference, ISWC 2011; Bonn, Germany, October 23, 2011. Proceedings (pp.51-62). CEUR.
Finite Lattices Do Not Make Reasoning in ALCI Harder
Peñaloza, R
2011
Abstract
We consider the fuzzy logic ALCI with semantics based on a finite residuated lattice. We show that the problems of satisfiability and subsumption of concepts in this logic are ExpTime-complete w.r.t. general TBoxes and PSpace-complete w.r.t. acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp ALCI.
| File | Dimensione | Formato | |
|---|---|---|---|
|
BoPe-URSW11.pdf
accesso aperto
Tipologia di allegato:
Author’s Accepted Manuscript, AAM (Post-print)
Dimensione
364.94 kB
Formato
Adobe PDF
|
364.94 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
