We investigate the complexity of several decision, enumeration and counting problems in axiom pinpointing in Description Logics. We prove hardness results that already hold for the propositional Horn fragment. We show that for this fragment, unless P = NP, all minimal subsets of a given TBox that have a given consequence, i.e. MinAs, cannot be enumerated in a specified lexicographic order with polynomial delay. Moreover, we show that recognizing the set of all MinAs is at least as hard as recognizing the set of all minimal transversals of a given hypergraph, however whether this problem is intractable remains open. We also show that checking the existence of a MinA that does not contain any of the given sets of axioms, as well as checking the existence of a MinA that contains a specified axiom are both np-hard. In addition we show that counting all MinAs and counting the MinAs that contain a certain axiom are both #p-hard.

Peñaloza, R., Sertkaya, B. (2009). Axiom pinpointing is hard. In Proceedings of the 2009 International Workshop on Description Logics (DL'09), Oxford, UK, July 27–30, 2009. CEUR.

Axiom pinpointing is hard

Peñaloza, R
;
2009

Abstract

We investigate the complexity of several decision, enumeration and counting problems in axiom pinpointing in Description Logics. We prove hardness results that already hold for the propositional Horn fragment. We show that for this fragment, unless P = NP, all minimal subsets of a given TBox that have a given consequence, i.e. MinAs, cannot be enumerated in a specified lexicographic order with polynomial delay. Moreover, we show that recognizing the set of all MinAs is at least as hard as recognizing the set of all minimal transversals of a given hypergraph, however whether this problem is intractable remains open. We also show that checking the existence of a MinA that does not contain any of the given sets of axioms, as well as checking the existence of a MinA that contains a specified axiom are both np-hard. In addition we show that counting all MinAs and counting the MinAs that contain a certain axiom are both #p-hard.
Si
paper
axiom pinpointing, description logics, complexity analysis
English
22th International Workshop on Description Logics (DL 2009)
Peñaloza, R., Sertkaya, B. (2009). Axiom pinpointing is hard. In Proceedings of the 2009 International Workshop on Description Logics (DL'09), Oxford, UK, July 27–30, 2009. CEUR.
Peñaloza, R; Sertkaya, B
File in questo prodotto:
File Dimensione Formato  
PeSe09.pdf

accesso aperto

Tipologia di allegato: Author’s Accepted Manuscript, AAM (Post-print)
Dimensione 184.46 kB
Formato Adobe PDF
184.46 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/257915
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
Social impact