{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:23:24Z","timestamp":1740122604417,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T00:00:00Z","timestamp":1580169600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T00:00:00Z","timestamp":1580169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Abductive inference derives explanations for encountered anomalies and thus embodies a natural approach for diagnostic reasoning. Yet its computational complexity, which is inherent to the expressiveness of the underlying theory, remains a disadvantage. Even when restricting the representation to Horn formulae the problem is NP-complete. Hence, finding procedures that can efficiently solve abductive diagnosis problems is of particular interest from a research as well as practical point of view. In this paper, we aim at providing guidance on choosing an algorithm or tool when confronted with the issue of computing explanations in propositional logic-based abduction. Our focus lies on Horn representations, which provide a suitable language to describe most diagnostic scenarios. We illustrate abduction via two contrasting problem formulations: direct proof methods and conflict-driven techniques. While the former is based on determining logical consequences, the later searches for suitable refutations involving possible causes. To reveal runtime performance trends we conducted a case study, in which we compared publicly available general purpose tools, established Horn reasoning engines, as well as new variations of known methods as a means for abduction.<\/jats:p>","DOI":"10.1007\/s10489-019-01575-5","type":"journal-article","created":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T06:04:10Z","timestamp":1580191450000},"page":"1558-1572","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Faster horn diagnosis - a performance comparison of abductive reasoning algorithms"],"prefix":"10.1007","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5077-8641","authenticated-orcid":false,"given":"Roxane","family":"Koitz-Hristov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Wotawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,28]]},"reference":[{"key":"1575_CR1","doi-asserted-by":"crossref","unstructured":"Arif MF, Menc\u00eda C, Marques-silva J (2015) Efficient MUS enumeration of Horn formulae with applications to axiom pinpointing. In: International conference on theory and applications of satisfiability testing. Springer, pp 324\u2013342","DOI":"10.1007\/978-3-319-24318-4_24"},{"issue":"1-3","key":"1575_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0004-3702(91)90005-5","volume":"49","author":"T Bylander","year":"1991","unstructured":"Bylander T, Allemang D, Tanner MC, Josephson JR (1991) The computational complexity of abduction. Artif Intell 49(1-3):25\u201360","journal-title":"Artif Intell"},{"issue":"9","key":"1575_CR3","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1016\/j.microrel.2010.07.121","volume":"50","author":"M Catelani","year":"2010","unstructured":"Catelani M, Ciani L, Luongo V (2010) The FMEDA approach to improve the safety assessment according to the IEC61508. Microelectron Reliab 50(9):1230\u20131235","journal-title":"Microelectron Reliab"},{"key":"1575_CR4","unstructured":"Charniak E, Goldman RP (1991) Probabilistic abduction for plan recognition. Brown University, Department of Computer Science"},{"key":"1575_CR5","unstructured":"Charwat G, Wallner JP, Woltran S (2013) Utilizing ASP, for generating and visualizing argumentation frameworks. arXiv:1301.1388"},{"issue":"3","key":"1575_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1111\/j.1467-8640.1991.tb00388.x","volume":"7","author":"L Console","year":"1991","unstructured":"Console L, Torasso P (1991) A spectrum of logical definitions of model-based diagnosis. Comput Intell 7 (3):133\u2013141","journal-title":"Comput Intell"},{"issue":"2","key":"1575_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0004-3702(86)90080-9","volume":"28","author":"J De Kleer","year":"1986","unstructured":"De Kleer J (1986) An assumption-based TMS. Artif Intell 28(2):127\u2013162","journal-title":"Artif Intell"},{"key":"1575_CR8","unstructured":"E\u00e9n N., S\u00f6rensson N (2003) An extensible SAT-solver. In: International conferemce on theory and applications of SAT. Springer, pp 502\u2013518"},{"key":"1575_CR9","unstructured":"Egly U, Eiter T, Tompits H, Woltran S (2000) Solving advanced reasoning tasks using quantified boolean formulas. In: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. AAAI Press, pp 417\u2013422"},{"issue":"1","key":"1575_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/200836.200838","volume":"42","author":"T Eiter","year":"1995","unstructured":"Eiter T, Gottlob G (1995) The complexity of logic-based abduction. J ACM (JACM) 42(1):3\u201342","journal-title":"J ACM (JACM)"},{"issue":"3","key":"1575_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF01536399","volume":"15","author":"T Eiter","year":"1995","unstructured":"Eiter T, Gottlob G (1995) On the computational cost of disjunctive logic programming: Propositional case. Ann Math Artif Intell 15(3):289\u2013323","journal-title":"Ann Math Artif Intell"},{"key":"1575_CR12","unstructured":"Eiter T, Leone N, Mateis C, Pfeifer G, Scarcello F (1998) The KR system dlv: Progress report, comparisons and benchmarks. In: Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann Publishers Inc., pp 406\u2013417"},{"key":"1575_CR13","first-page":"24","volume":"1","author":"A Feldman","year":"2010","unstructured":"Feldman A, Kurtoglu T, Narasimhan S, Poll S, Garcia D (2010) Empirical evaluation of diagnostic algorithm performance using a generic framework. Int J Prognost Health Manag 1:24","journal-title":"Int J Prognost Health Manag"},{"key":"1575_CR14","unstructured":"Felfernig A, Schubert M, Reiterer S (2013) Personalized diagnosis for over-constrained problems. In: Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. AAAI Press, pp 1990\u20131996"},{"issue":"2","key":"1575_CR15","first-page":"129","volume":"3","author":"T Finin","year":"1989","unstructured":"Finin T, Morris G (1989) Abductive reasoning in multiple fault diagnosis. Artif Intell Rev 3(2):129\u2013158","journal-title":"Artif Intell Rev"},{"key":"1575_CR16","unstructured":"Forbus KD, Kleer JD (1988) Focusing the ATMS. In: Proceedings of the Seventh AAAI Conference on Artificial Intelligence. AAAI Press, pp 193\u2013198"},{"key":"1575_CR17","doi-asserted-by":"crossref","unstructured":"Friedrich G, Gottlob G, Nejdl W (1990) Hypothesis classification, abductive diagnosis and therapy. Expert Systems in Engineering Principles and Applications, pp 69\u201378","DOI":"10.1007\/3-540-53104-1_32"},{"key":"1575_CR18","unstructured":"Gebser M, Kaminski R, Kaufmann B, Schaub T (2014) Clingo = ASP + control Preliminary report. In: Leuschel M, schrijvers T (eds) Technical communications of the 30th international conference on logic programming, pp 1\u201313"},{"key":"1575_CR19","doi-asserted-by":"crossref","unstructured":"Gordon AS (2016) Commonsense interpretation of triangle behavior. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press, pp 3719\u20133725","DOI":"10.1609\/aaai.v30i1.9881"},{"issue":"4","key":"1575_CR20","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0954-1810(97)10011-5","volume":"12","author":"PG Hawkins","year":"1998","unstructured":"Hawkins PG, Woollons DJ (1998) Failure modes and effects analysis of complex engineering systems using functional models. Artif Intell Eng 12(4):375\u2013397","journal-title":"Artif Intell Eng"},{"key":"1575_CR21","unstructured":"Ignatiev A, Morgado A, Marques-Silva J (2016) Propositional abduction with implicit hitting sets. arXiv:1604.08229"},{"issue":"2","key":"1575_CR22","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0004-3702(92)90030-2","volume":"56","author":"K Inoue","year":"1992","unstructured":"Inoue K (1992) Linear resolution for consequence finding. Artif Intell 56(2):301\u2013353","journal-title":"Artif Intell"},{"key":"1575_CR23","doi-asserted-by":"crossref","unstructured":"Jannach D, Schmitz T, Shchekotykhin K (2015) Parallelized hitting set computation for model-based diagnosis. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, pp 1503\u20131510","DOI":"10.1609\/aaai.v29i1.9389"},{"issue":"6","key":"1575_CR24","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1093\/logcom\/2.6.719","volume":"2","author":"AC Kakas","year":"1992","unstructured":"Kakas AC, Kowalski RA, Toni F (1992) Abductive logic programming. J Log Comput 2(6):719\u2013770","journal-title":"J Log Comput"},{"key":"1575_CR25","unstructured":"Kakas AC, Van Nuffelen B, Denecker M (2001) A-system: Problem solving through abduction. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pp 591\u2013596"},{"key":"1575_CR26","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. Springer, pp 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1575_CR27","unstructured":"Koitz R, Wotawa F (2015) Finding explanations: An empirical evaluation of abductive diagnosis algorithms. In: Proceedings of the 2015 International Workshop on Defeasible and Ampliative Reasoning-Volume 1423. CEUR-WS. org, pp 36\u201342"},{"key":"1575_CR28","unstructured":"Koitz R, Wotawa F (2015) SAT-based abductive diagnosis. In: 26Th international workshop on principles of diagnosis (DX-2015), pp 1\u20139"},{"key":"1575_CR29","unstructured":"Koitz R, Wotawa F (2016) On structural properties to improve FMEA-based abductive diagnosis. In: Workshop on knowledge-based techniques for problem solving and reasoning, pp 1\u20137"},{"key":"1575_CR30","unstructured":"Koitz-Hristov R (2018) From Theory to Practice: Abductive Model-based Diagnosis and its Industrial Application. PhD thesis, Graz University of Technology"},{"issue":"11","key":"1575_CR31","doi-asserted-by":"publisher","first-page":"3976","DOI":"10.1007\/s10489-018-1171-9","volume":"48","author":"R Koitz-Hristov","year":"2018","unstructured":"Koitz-Hristov R, Wotawa F (2018) Applying algorithm selection to abductive diagnostic reasoning. Appl Intell 48(11):3976\u20133994","journal-title":"Appl Intell"},{"issue":"2","key":"1575_CR32","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10601-015-9183-0","volume":"21","author":"MH Liffiton","year":"2016","unstructured":"Liffiton MH, Previti A, Malik A, Marques-Silva J (2016) Fast, flexible MUS enumeration. Constraints 21(2):223\u2013250","journal-title":"Constraints"},{"issue":"1","key":"1575_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10817-007-9084-z","volume":"40","author":"MH Liffiton","year":"2008","unstructured":"Liffiton MH, Sakallah KA (2008) Algorithms for computing minimal unsatisfiable subsets of constraints. J Autom Reason 40(1):1\u201333","journal-title":"J Autom Reason"},{"issue":"1","key":"1575_CR34","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0004-3702(98)00081-2","volume":"105","author":"PJ Lucas","year":"1998","unstructured":"Lucas PJ (1998) Analysis of notions of diagnosis. Artif Intell 105(1):295\u2013343","journal-title":"Artif Intell"},{"key":"1575_CR35","doi-asserted-by":"crossref","unstructured":"Marquis P (2000) Consequence finding algorithms. In: Handbook of defeasible reasoning and uncertainty management systems. Springer, pp 41\u2013145","DOI":"10.1007\/978-94-017-1737-3_3"},{"key":"1575_CR36","doi-asserted-by":"crossref","unstructured":"McIlraith SA (1994) Generating tests using abduction. In: Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann Publishers Inc., pp 449\u2013460","DOI":"10.1016\/B978-1-4832-1452-8.50137-8"},{"key":"1575_CR37","unstructured":"McIlraith SA (1998) Logic-based abductive inference. Knowledge Systems Laboratory, Technical Report KSL-98-19"},{"issue":"2-3","key":"1575_CR38","doi-asserted-by":"publisher","first-page":"183","DOI":"10.3233\/AIC-2010-0465","volume":"23","author":"H Nabeshima","year":"2010","unstructured":"Nabeshima H, Iwanuma K, Inoue K, Ray O (2010) SOLAR An automated deduction system for consequence finding. AI Commun 23(2-3):183\u2013203","journal-title":"AI Commun"},{"key":"1575_CR39","unstructured":"Ng HT, Mooney RJ (1992) Abductive plan recognition and diagnosis: A comprehensive empirical evaluation. In: Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann Publishers Inc., pp 499\u2013508"},{"key":"1575_CR40","unstructured":"Nica I, Pill I, Quaritsch T, Wotawa F (2013) The route to success - a performance comparison of diagnosis algorithms. In: International joint conference on artificial intelligence (IJCAI), Bejing, China, pp 1039\u20131045"},{"issue":"10","key":"1575_CR41","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/j.artint.2008.02.001","volume":"172","author":"G Nordh","year":"2008","unstructured":"Nordh G, Zanuttini B (2008) What makes propositional abduction tractable. Artif Intell 172(10):1245\u20131284","journal-title":"Artif Intell"},{"key":"1575_CR42","unstructured":"Peischl B, Wotawa F (2003) Computing diagnosis efficiently: A fast theorem prover for propositional Horn theories. In: Proceedings of the 14th International Workshop on Principles of Diagnosis, pp 175\u2013180"},{"key":"1575_CR43","doi-asserted-by":"crossref","unstructured":"Peng Y, Reggia JA (1990) Abductive inference models for diagnostic problem-solving. Springer, Berlin","DOI":"10.1007\/978-1-4419-8682-5"},{"key":"1575_CR44","doi-asserted-by":"crossref","unstructured":"Poole D, Goebel R, Aleliunas R (1987) Theorist: A logical reasoning system for defaults and diagnosis. In: The knowledge frontier. Springer, pp 331\u2013352","DOI":"10.1007\/978-1-4612-4792-0_13"},{"issue":"1","key":"1575_CR45","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R Reiter","year":"1987","unstructured":"Reiter R (1987) A theory of diagnosis from first principles. Artif Intell 32(1):57\u201395","journal-title":"Artif Intell"},{"key":"1575_CR46","unstructured":"Saikko P, Wallner JP, J\u00e4rvisalo M (2016) Implicit hitting set algorithms for reasoning beyond NP. In: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press, pp 104\u2013113"},{"issue":"1-2","key":"1575_CR47","doi-asserted-by":"publisher","first-page":"159","DOI":"10.3233\/FI-2016-1446","volume":"149","author":"P Sch\u00fcller","year":"2016","unstructured":"Sch\u00fcller P (2016) Modeling variations of first-order Horn abduction in answer set programming. Fundamenta Informaticae 149(1-2):159\u2013207","journal-title":"Fundamenta Informaticae"},{"key":"1575_CR48","unstructured":"Shchekotykhin K, Jannach D, Schmitz T (2015) MERGEXPLAIN: fast computation of multiple conflicts for diagnosis. In: Proceedings of the 24th International Conference on Artificial Intelligence. AAAI Press, pp 3221\u20133228"},{"key":"1575_CR49","unstructured":"Simon L, Del Val A (2001) Efficient consequence finding. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence-Volume 1. Morgan Kaufmann Publishers Inc., pp 359\u2013365"},{"key":"1575_CR50","doi-asserted-by":"crossref","unstructured":"Wei-Kleiner F, Dragisic Z, Lambrix P (2014) Abduction framework for repairing incomplete EL ontologies: complexity results and algorithms. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press, pp 1120\u20131127","DOI":"10.1609\/aaai.v28i1.8858"},{"key":"1575_CR51","unstructured":"Wotawa F (2014) Failure mode and effect analysis for abductive diagnosis. In: Proceedings of the International Workshop on Defeasible and Ampliative Reasoning, pp 1\u201313"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-019-01575-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10489-019-01575-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-019-01575-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T02:37:00Z","timestamp":1665628620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10489-019-01575-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,28]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["1575"],"URL":"https:\/\/doi.org\/10.1007\/s10489-019-01575-5","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"type":"print","value":"0924-669X"},{"type":"electronic","value":"1573-7497"}],"subject":[],"published":{"date-parts":[[2020,1,28]]},"assertion":[{"value":"28 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}