Ontology consistency has been shown to be undecidable for a wide variety of fairly inexpressive fuzzy Description Logics (DLs). In particular, for any t-norm "starting with" the Lukasiewicz t-norm, consistency of crisp ontologies (w.r.t. witnessed models) is undecidable in any fuzzy DL with conjunction, existential restrictions, and (residual) negation. In this paper we show that for any t-norm with Gödel negation, that is, any t-norm not starting with Lukasiewicz, ontology consistency for a variant of fuzzy SHOI is linearly reducible to crisp reasoning, and hence decidable in exponential time. Our results hold even if reasoning is not restricted to the class of witnessed models only.
Borgwardt, S., Distel, F., Penaloza, R. (2012). Gödel Negation Makes Unwitnessed Consistency Crisp. In Proceedings of the 2012 International Workshop on Description Logics, June 7-10, 2012, Rome, Italy (pp.103-113). CEUR.
Gödel Negation Makes Unwitnessed Consistency Crisp
Penaloza, R
2012
Abstract
Ontology consistency has been shown to be undecidable for a wide variety of fairly inexpressive fuzzy Description Logics (DLs). In particular, for any t-norm "starting with" the Lukasiewicz t-norm, consistency of crisp ontologies (w.r.t. witnessed models) is undecidable in any fuzzy DL with conjunction, existential restrictions, and (residual) negation. In this paper we show that for any t-norm with Gödel negation, that is, any t-norm not starting with Lukasiewicz, ontology consistency for a variant of fuzzy SHOI is linearly reducible to crisp reasoning, and hence decidable in exponential time. Our results hold even if reasoning is not restricted to the class of witnessed models only.
| File | Dimensione | Formato | |
|---|---|---|---|
|
BoDP-DL12.pdf
accesso aperto
Tipologia di allegato:
Author’s Accepted Manuscript, AAM (Post-print)
Dimensione
359.82 kB
Formato
Adobe PDF
|
359.82 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
