We study the fuzzy extension of the Description Logic FL0 with semantics based on the Gödel t-norm. We show that subsumption w.r.t. a finite set of primitive definitions, using greatest fixed-point semantics, can be characterized by a relation on weighted automata. We use this result to provide tight complexity bounds for reasoning in this logic, showing that it is PSpace-complete. If the definitions do not contain cycles, subsumption becomesco-NP-complete.
Borgwardt, S., Leyva Galano, J., Penaloza, R. (2014). The fuzzy description logic G-FL0 with greatest fixed-point semantics. In Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA'14) (pp.62-76). Springer Verlag [10.1007/978-3-319-11558-0_5].
The fuzzy description logic G-FL0 with greatest fixed-point semantics
Penaloza, R
2014
Abstract
We study the fuzzy extension of the Description Logic FL0 with semantics based on the Gödel t-norm. We show that subsumption w.r.t. a finite set of primitive definitions, using greatest fixed-point semantics, can be characterized by a relation on weighted automata. We use this result to provide tight complexity bounds for reasoning in this logic, showing that it is PSpace-complete. If the definitions do not contain cycles, subsumption becomesco-NP-complete.File | Dimensione | Formato | |
---|---|---|---|
BoLP-JELIA14.pdf
accesso aperto
Tipologia di allegato:
Author’s Accepted Manuscript, AAM (Post-print)
Dimensione
434.71 kB
Formato
Adobe PDF
|
434.71 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.