On the complexity of axiom pinpointing in the EL family of description logics
作者： Bariş Sertkaya , Rafael Peñaloza
DOI:
关键词:
摘要: We investigate the computational complexity of axiom pinpointing, which is task finding minimal subsets a Description Logic knowledge base that have given consequence. consider problems enumerating such with and without order, show hardness results already hold for propositional Horn fragment, or EL. several other related decision enumeration these fragments extend to more expressive logics. In particular we depends not only on expressivity fragment but also shape axioms used.
参考文章(30)
Bijan Parsia, Evren Sirin, Aditya Kalyanpur, Debugging OWL ontologies the web conference. pp. 633- 640 ,(2005) , 10.1145/1060745.1060837
Mihalis Yannakakis, Christos H. Papadimitriou, David S. Johnson, On generating all maximal independent sets Information Processing Letters. ,vol. 27, pp. 119- 123 ,(1988) , 10.1016/0020-0190(88)90065-8
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Jin Y. Yen, Finding the K Shortest Loopless Paths in a Network Management Science. ,vol. 17, pp. 712- 716 ,(1971) , 10.1287/MNSC.17.11.712
William F. Dowling, Jean H. Gallier, Linear-time algorithms for testing the satisfiability of propositional horn formulae Journal of Logic Programming. ,vol. 1, pp. 267- 284 ,(1984) , 10.1016/0743-1066(84)90014-1
Franz Baader, Rafael Peñaloza, Automata-Based Axiom Pinpointing Journal of Automated Reasoning. ,vol. 45, pp. 91- 129 ,(2010) , 10.1007/S10817-010-9181-2
Michael L. Fredman, Leonid Khachiyan, On the Complexity of Dualization of Monotone Disjunctive Normal Forms Journal of Algorithms. ,vol. 21, pp. 618- 628 ,(1996) , 10.1006/JAGM.1996.0062
Thomas Eiter, Georg Gottlob, The complexity of logic-based abduction Journal of the ACM. ,vol. 42, pp. 3- 42 ,(1995) , 10.1145/200836.200838
Raymond Reiter, A theory of diagnosis from first principles Artificial Intelligence. ,vol. 32, pp. 352- 371 ,(1987) , 10.1016/0004-3702(87)90062-2
Stefan Schlobach, Ronald Cornet, Non-standard reasoning services for the debugging of description logic terminologies international joint conference on artificial intelligence. pp. 355- 360 ,(2003)