In the last few years, there has been a large effort for analyzing the computational properties of reasoning in fuzzy description logics. This has led to a number of papers studying the complexity of these logics, depending on the chosen semantics. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics w.r.t. witnessed models over the Gödel t-norm. We show that in the logic G-IALC, reasoning cannot be restricted to finitely-valued models in general. Despite this negative result, we also show that all the standard reasoning problems can be solved in exponential time, matching the complexity of reasoning in classical ALC.

Borgwardt, S., Distel, F., Penaloza, R. (2014). Decidable Gödel description logics without the finitely-valued model property. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14) (pp.228-237). AAAI Press.

Decidable Gödel description logics without the finitely-valued model property

Penaloza, R
2014

Abstract

In the last few years, there has been a large effort for analyzing the computational properties of reasoning in fuzzy description logics. This has led to a number of papers studying the complexity of these logics, depending on the chosen semantics. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics w.r.t. witnessed models over the Gödel t-norm. We show that in the logic G-IALC, reasoning cannot be restricted to finitely-valued models in general. Despite this negative result, we also show that all the standard reasoning problems can be solved in exponential time, matching the complexity of reasoning in classical ALC.
paper
fuzzy logic, description logics
English
International Conference on Principles of Knowledge Representation and Reasoning, KR 2014
2014
Baral, C; De Giacomo, G; Eiter, T
Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14)
978-1-57735-657-8
2014
228
237
open
Borgwardt, S., Distel, F., Penaloza, R. (2014). Decidable Gödel description logics without the finitely-valued model property. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14) (pp.228-237). AAAI Press.
File in questo prodotto:
File Dimensione Formato  
BoDP-KR14.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 328.59 kB
Formato Adobe PDF
328.59 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/257707
Citazioni
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 12
Social impact