LATPub419: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We investigate the complexity of several decision, enumeration and counting | |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. | ||
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. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 52: | Zeile 38: | ||
year = {2009}, | year = {2009}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Axiom Pinpointing is Hard
Rafael PeñalozaRafael Peñaloza, Barış SertkayaBarış Sertkaya
Rafael Peñaloza, Barış Sertkaya
Axiom Pinpointing is Hard
In Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler, eds., Proceedings of the 2009 International Workshop on Description Logics (DL2009), volume 477 of CEUR-WS, 2009
Axiom Pinpointing is Hard
In Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler, eds., Proceedings of the 2009 International Workshop on Description Logics (DL2009), volume 477 of CEUR-WS, 2009
- KurzfassungAbstract
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. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ PeSe09,
author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
booktitle = {Proceedings of the 2009 International Workshop on Description Logics ({DL2009})},
editor = {Bernardo Cuenca {Grau} and Ian {Horrocks} and Boris {Motik} and Ulrike {Sattler}},
series = {CEUR-WS},
title = {Axiom Pinpointing is Hard},
volume = {477},
year = {2009},
}
