Axiom pinpointing has been introduced in description logics (DLs) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question. Until now, the pinpointing approach has only been applied to the DL ALC and some of its extensions. This paper considers axiom pinpointing in the less expressive DL EL+, for which subsumption can be decided in polynomial time. More precisely, we consider an extension of the pinpointing problem where the knowledge base is divided into a part, which is always present, and a part, of which subsets are taken. We describe an extension of the subsumption algorithm for EL+ that can be used to compute all minimal subsets of (the refutable part of) a given TBox that imply a certain subsumption relationship. The worst-case complexity of this algorithm turns out to be exponential. This is not surprising since we can show that a given TBox may have exponentially many such minimal subsets. However, we can also show that the problem is not even output polynomial, i.e., unless P=NP, there cannot be an algorithm computing all such minimal sets that is polynomial in the size of its input . In addition, we show that finding out whether there is such a minimal subset within a given cardinality bound is an NP-complete problem. In contrast to these negative results, we also show that one such minimal subset can be computed in polynomial time. Finally, we provide some encouraging experimental results regarding the performance of a practical algorithm that computes one (small, but not necessarily minimal) subset that has a given subsumption relation as consequence.

Baader, F., Penaloza, R., Suntisrivaraporn, B. (2007). Pinpointing in the Description Logic EL+. In KI 2007: Advances in Artificial Intelligence ; 30th Annual German Conference on AI, KI 2007, Osnabrück, Germany, September 10-13, 2007. Proceedings (pp.52-67). Springer-Verlag [10.1007/978-3-540-74565-5_7].

Pinpointing in the Description Logic EL+

Penaloza, R;
2007

Abstract

Axiom pinpointing has been introduced in description logics (DLs) to help the user understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question. Until now, the pinpointing approach has only been applied to the DL ALC and some of its extensions. This paper considers axiom pinpointing in the less expressive DL EL+, for which subsumption can be decided in polynomial time. More precisely, we consider an extension of the pinpointing problem where the knowledge base is divided into a part, which is always present, and a part, of which subsets are taken. We describe an extension of the subsumption algorithm for EL+ that can be used to compute all minimal subsets of (the refutable part of) a given TBox that imply a certain subsumption relationship. The worst-case complexity of this algorithm turns out to be exponential. This is not surprising since we can show that a given TBox may have exponentially many such minimal subsets. However, we can also show that the problem is not even output polynomial, i.e., unless P=NP, there cannot be an algorithm computing all such minimal sets that is polynomial in the size of its input . In addition, we show that finding out whether there is such a minimal subset within a given cardinality bound is an NP-complete problem. In contrast to these negative results, we also show that one such minimal subset can be computed in polynomial time. Finally, we provide some encouraging experimental results regarding the performance of a practical algorithm that computes one (small, but not necessarily minimal) subset that has a given subsumption relation as consequence.
paper
axiom pinpointing, description logics
English
German Annual Conference on Artificial Intelligence (KI'07)
2007
Hertzberg, J; Beetz, M; Englert, R
KI 2007: Advances in Artificial Intelligence ; 30th Annual German Conference on AI, KI 2007, Osnabrück, Germany, September 10-13, 2007. Proceedings
978-3-540-74564-8
2007
4667
52
67
reserved
Baader, F., Penaloza, R., Suntisrivaraporn, B. (2007). Pinpointing in the Description Logic EL+. In KI 2007: Advances in Artificial Intelligence ; 30th Annual German Conference on AI, KI 2007, Osnabrück, Germany, September 10-13, 2007. Proceedings (pp.52-67). Springer-Verlag [10.1007/978-3-540-74565-5_7].
File in questo prodotto:
File Dimensione Formato  
Baader2007_Chapter_PinpointingInTheDescriptionLog.pdf

Solo gestori archivio

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

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/234232
Citazioni
  • Scopus 88
  • ???jsp.display-item.citation.isi??? 66
Social impact