{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:29:32Z","timestamp":1773930572355,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T00:00:00Z","timestamp":1498780800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LY16F020004"],"award-info":[{"award-number":["LY16F020004"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61003101, 61272208, and 61472369"],"award-info":[{"award-number":["61003101, 61272208, and 61472369"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10489-017-0971-7","type":"journal-article","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T02:43:01Z","timestamp":1498790581000},"page":"257-270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computing all minimal hitting sets by subset recombination"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5870-5730","authenticated-orcid":false,"given":"Xiangfu","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dantong","family":"Ouyang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,30]]},"reference":[{"key":"971_CR1","volume-title":"Proceedings of the 8th symposium on abstraction, reformulation, and approximation (SARA-09). AAAI Press, pp 2\u20139","author":"R Abreu","year":"2009","unstructured":"Abreu R, van Gemund A (2009) A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In: Proceedings of the 8th symposium on abstraction, reformulation, and approximation (SARA-09). AAAI Press, pp 2\u20139"},{"key":"971_CR2","first-page":"183","volume-title":"Proceedings of the 36th international colloquium on automata, languages and programming (ICALP-09)","author":"E Boros","year":"2009","unstructured":"Boros E, Makino K (2009) A fast and simple parallel algorithm for the monotone duality problem. In: Proceedings of the 36th international colloquium on automata, languages and programming (ICALP-09). Springer, Berlin, Heidelberg, pp 183\u2013 194"},{"key":"971_CR3","volume-title":"Proceedings of the 1985 IEEE international symposium on circuits and systems (ISCAS-85), pp 695\u2013698. IEEE","author":"F Brglez","year":"1985","unstructured":"Brglez F, Fujiwara H (1985) A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran. In: Proceedings of the 1985 IEEE international symposium on circuits and systems (ISCAS-85). IEEE, pp 695\u2013698"},{"key":"971_CR4","volume-title":"Proceedings of the 2nd international conference on multicore software engineering, performance, and tools (MUSEPAT-13), pp 25\u201336","author":"N Cardoso","year":"2013","unstructured":"Cardoso N, Abreu R (2013) MHS 2: a map-reduce heuristic-driven minimal hitting set search algorithm. In: Proceedings of the 2nd international conference on multicore software engineering, performance, and tools (MUSEPAT-13), pp 25\u201336"},{"key":"971_CR5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TCYB.2015.2394471","volume":"46","author":"W Chan","year":"2016","unstructured":"Chan W, Chen C (2016) Consensus control with failure \u2013 wait or abandon? IEEE Trans Cybern 46:75\u201384. doi: 10.1109\/TCYB.2015.2394471","journal-title":"IEEE Trans Cybern"},{"key":"971_CR6","doi-asserted-by":"crossref","unstructured":"Crama Y, Hammer PL (2011) Boolean functions - theory, algorithms, and applications, encyclopedia of mathematics and its applications, vol 142. Cambridge University Press","DOI":"10.1017\/CBO9780511852008"},{"issue":"1","key":"971_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S (2008) MapReduce: simplified data processing on large clusters. Commun ACM 51 (1):107\u2013113","journal-title":"Commun ACM"},{"issue":"11","key":"971_CR8","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T Eiter","year":"2008","unstructured":"Eiter T, Makino K, Gottlob G (2008) Computational aspects of monotone dualization: a brief survey. Discret Appl Math 156(11):2035\u20132049","journal-title":"Discret Appl Math"},{"key":"971_CR9","volume-title":"Proceedings of the 23rd national conference on artificial intelligence (AAAI-08). AAAI Press, pp 911\u2013918","author":"A Feldman","year":"2008","unstructured":"Feldman A, Provan G, van Gemund A (2008) Computing minimal diagnoses by greedy stochastic search. In: Proceedings of the 23rd national conference on artificial intelligence (AAAI-08). AAAI Press, pp 911\u2013918"},{"key":"971_CR10","volume-title":"Proceedings of the winter international symposium on information and communication technologies (WISICT-04), pp 1\u201310","author":"A Fijany","year":"2004","unstructured":"Fijany A, Vatan F (2004) New approaches for efficient solution of hitting set problem. In: Proceedings of the winter international symposium on information and communication technologies (WISICT-04), pp 1\u201310"},{"key":"971_CR11","volume-title":"Proceedings of the 3rd international conference on principles of knowledge representation and reasoning (KR-92). Morgan Kaufmann, pp 521\u2013531","author":"H Freitag","year":"1992","unstructured":"Freitag H, Friedrich G (1992) Focusing on independent diagnosis problems. In: Nebel B, Rich C, Swartout WR (eds). In: Proceedings of the 3rd international conference on principles of knowledge representation and reasoning (KR-92). Morgan Kaufmann, pp 521\u2013531"},{"key":"971_CR12","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA"},{"issue":"1","key":"971_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0004-3702(89)90079-9","volume":"41","author":"R Greiner","year":"1989","unstructured":"Greiner R, Smith BA, Wilkerson RW (1989) A correction to the algorithm in reiter\u2019s theory of diagnosis. Artif Intell 41(1):79\u201388","journal-title":"Artif Intell"},{"key":"971_CR14","volume-title":"Proceedings of the 25th international workshop on principles of diagnosis (DX-14)","author":"D Jannach","year":"2014","unstructured":"Jannach D, Schmitz T, Shchekotykhin K (2014) Parallelized hitting set computation for model-based diagnosis. In: Proceedings of the 25th international workshop on principles of diagnosis (DX-14)"},{"key":"971_CR15","volume-title":"Proceedings of the 29th AAAI conference on artificial intelligence (AAAI-15), pp 1503\u20131510","author":"D Jannach","year":"2015","unstructured":"Jannach D, Schmitz T, Shchekotykhin K (2015) Parallelized hitting set computation for model-based diagnosis. In: Proceedings of the 29th AAAI conference on artificial intelligence (AAAI-15), pp 1503\u20131510"},{"key":"971_CR16","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1613\/jair.5001","volume":"55","author":"D Jannach","year":"2016","unstructured":"Jannach D, Schmitz T, Shchekotykhin K (2016) Parallel model-based diagnosis on multi-core computers. J Artif Intell Res 55:835\u2013887","journal-title":"J Artif Intell Res"},{"key":"971_CR17","volume-title":"Proceedings of the 19th national conference on artifical intelligence (AAAI-04). AAAI Press, pp 167\u2013172","author":"U Junker","year":"2004","unstructured":"Junker U (2004) Quickxplain: preferred explanations and relaxations for over-constrained problems. In: Proceedings of the 19th national conference on artifical intelligence (AAAI-04). AAAI Press, pp 167\u2013172"},{"key":"971_CR18","volume-title":"Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp R (1972) Reducibility among combinatorial problems. In: Miller R, Thatcher J (eds) Complexity of computer computations. Plenum Press, New York"},{"issue":"4","key":"971_CR19","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ipl.2006.09.006","volume":"101","author":"L Khachiyan","year":"2007","unstructured":"Khachiyan L, Boros E, Elbassioni K, Gurvich V (2007) A global parallel algorithm for the hypergraph transversal problem. Inf Process Lett 101(4):148\u2013155","journal-title":"Inf Process Lett"},{"key":"971_CR20","volume-title":"Proceedings of the 22nd international workshop on principles of diagnosis (DX-11), pp 100\u2013105","author":"J de Kleer","year":"2011","unstructured":"de Kleer J (2011) Hitting set algorithms for model-based diagnosis. In: Proceedings of the 22nd international workshop on principles of diagnosis (DX-11), pp 100\u2013105"},{"issue":"1","key":"971_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(87)90063-4","volume":"32","author":"J de Kleer","year":"1987","unstructured":"de Kleer J, Williams BC (1987) Diagnosing multiple faults. Artif Intell 32(1):97\u2013130","journal-title":"Artif Intell"},{"key":"971_CR22","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1109\/TCYB.2014.2347801","volume":"45","author":"RH Kwong","year":"2015","unstructured":"Kwong RH, Yonge-Mallo DL (2015) Fault diagnosis in discrete-event systems with incomplete models: learnability and diagnosability. IEEE Trans Cybern 45:1236\u20131249. doi: 10.1109\/TCYB.2014.2347801","journal-title":"IEEE Trans Cybern"},{"issue":"1","key":"971_CR23","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1023\/A:1020974704946","volume":"18","author":"G Lamperti","year":"2003","unstructured":"Lamperti G, Zanella M (2003) EDEN: an intelligent software environment for diagnosis of discrete-event systems. Appl Intell 18(1):55\u201377","journal-title":"Appl Intell"},{"issue":"5","key":"971_CR24","doi-asserted-by":"publisher","first-page":"2222","DOI":"10.1109\/TSMCB.2004.835008","volume":"34","author":"G Lamperti","year":"2004","unstructured":"Lamperti G, Zanella M (2004) A bridged diagnostic method for the monitoring of polymorphic discrete-event systems. IEEE Trans Syst Man Cybern Part B Cybern 34(5):2222\u20132244","journal-title":"IEEE Trans Syst Man Cybern Part B Cybern"},{"issue":"1","key":"971_CR25","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"},{"key":"971_CR26","volume-title":"Proceedings of the 13th international workshop on principles of diagnosis (DX-02), pp 77\u201380","author":"L Lin","year":"2002","unstructured":"Lin L, Jiang Y (2002) Computing minimal hitting sets with genetic algorithm. In: Proceedings of the 13th international workshop on principles of diagnosis (DX-02), pp 77\u201380"},{"issue":"4","key":"971_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0020-0190(02)00506-9","volume":"86","author":"L Lin","year":"2003","unstructured":"Lin L, Jiang Y (2003) The computation of hitting sets: review and new algorithms. Inf Process Lett 86 (4):177\u2013184","journal-title":"Inf Process Lett"},{"issue":"1","key":"971_CR28","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.ins.2011.08.023","volume":"185","author":"M Luo","year":"2012","unstructured":"Luo M, Li Y, Sun F, Liu H (2012) A new algorithm for testing diagnosability of fuzzy discrete event systems. Inf Sci 185(1):100\u2013113","journal-title":"Inf Sci"},{"key":"971_CR29","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/978-3-642-39799-8_39","volume":"8044","author":"J Marques-Silva","year":"2013","unstructured":"Marques-Silva J, Janota M, Belov A (2013) Minimal sets over monotone predicates in boolean formulae. Lect Notes Comput Sci 8044:592\u2013607","journal-title":"Lect Notes Comput Sci"},{"issue":"1","key":"971_CR30","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1109\/TSMCA.2010.2048750","volume":"41","author":"M Nyberg","year":"2011","unstructured":"Nyberg M (2011) A generalized minimal hitting-set algorithm to handle diagnosis with behavioral modes. IEEE Trans Syst Man Cybern Part A Syst Humans 41(1):137\u2013148","journal-title":"IEEE Trans Syst Man Cybern Part A Syst Humans"},{"key":"971_CR31","volume-title":"Proceedings of the 20th european conference on artificial intelligence (ECAI-12). IOS Press, pp 648\u2013653","author":"I Pill","year":"2012","unstructured":"Pill I, Quaritsch T (2012) Optimizations for the boolean approach to computing minimal hitting sets. In: Proceedings of the 20th european conference on artificial intelligence (ECAI-12). IOS Press, pp 648\u2013653"},{"key":"971_CR32","volume-title":"Proceedings of the 24th international joint conference on artificial intelligence (IJCAI-15), pp 1980\u20131987","author":"A Previti","year":"2015","unstructured":"Previti A, Ignatiev A, Morgado A, Marques-Silva J (2015) Prime compilation of non-clausal formulae. In: Proceedings of the 24th international joint conference on artificial intelligence (IJCAI-15), pp 1980\u20131987"},{"issue":"1","key":"971_CR33","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"},{"issue":"11","key":"971_CR34","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1002\/int.20497","volume":"26","author":"I Shah","year":"2011","unstructured":"Shah I (2011) A hybrid algorithm for finding minimal unsatisfiable subsets in over-constrained csps. Int J Intell Syst 26(11):1023\u20131048. doi: 10.1002\/int.20497","journal-title":"Int J Intell Syst"},{"key":"971_CR35","volume-title":"Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI-15). AAAI Press, pp 3221\u20133228","author":"K Shchekotykhin","year":"2015","unstructured":"Shchekotykhin K, Jannach D, Schmitz T (2015) Mergexplain: fast computation of multiple conflicts for diagnosis. In: Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI-15). AAAI Press, pp 3221\u20133228"},{"key":"971_CR36","volume-title":"Proceedings of the 26th AAAI conference on artificial intelligence (AAAI-12). AAAI Press, pp 828\u2013834","author":"R Stern","year":"2012","unstructured":"Stern R, Kalech M, Feldman A, Provan G (2012) Exploring the duality in conflict-directed model-based diagnosis. In: Proceedings of the 26th AAAI conference on artificial intelligence (AAAI-12). AAAI Press, pp 828\u2013834"},{"issue":"2","key":"971_CR37","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0888-613X(00)00051-7","volume":"25","author":"S Vinterbo","year":"2000","unstructured":"Vinterbo S, Ohrn A (2000) Minimal approximate hitting sets and rule templates. Int J Approx Reason 25 (2):123\u2013143","journal-title":"Int J Approx Reason"},{"issue":"3","key":"971_CR38","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10489-008-0143-x","volume":"36","author":"J Weber","year":"2012","unstructured":"Weber J, Wotawa F (2012) Diagnosis and repair of dependent failures in the control system of a mobile autonomous robot. Appl Intell 36(3):511\u2013528","journal-title":"Appl Intell"},{"key":"971_CR39","unstructured":"Wikipedia (2015) Set cover problem. https:\/\/en.wikipedia.org\/wiki\/set_cover_problem"},{"issue":"12","key":"971_CR40","doi-asserted-by":"publisher","first-page":"1562","DOI":"10.1016\/j.dam.2005.10.022","volume":"155","author":"BC Williams","year":"2007","unstructured":"Williams BC, Ragno RJ (2007) Conflict-directed a* and its role in model-based embedded systems. Discret Appl Math 155(12):1562\u20131595. doi: 10.1016\/j.dam.2005.10.022","journal-title":"Discret Appl Math"},{"issue":"1","key":"971_CR41","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0020-0190(00)00166-6","volume":"79","author":"F Wotawa","year":"2001","unstructured":"Wotawa F (2001) A variant of reiter\u2019s hitting-set algorithm. Inf Process Lett 79(1):45\u201351","journal-title":"Inf Process Lett"},{"key":"971_CR42","doi-asserted-by":"publisher","first-page":"7511","DOI":"10.1016\/j.eswa.2010.12.117","volume":"38","author":"L Zhang","year":"2011","unstructured":"Zhang L, Zeng H, Yang F, Ouyang D (2011) Dynamic theorem proving algorithm for consistency-based diagnosis. Expert Syst Appl 38:7511\u20137516","journal-title":"Expert Syst Appl"},{"issue":"2","key":"971_CR43","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1080\/10020070612331343209","volume":"16","author":"X Zhao","year":"2006","unstructured":"Zhao X, Ouyang D (2006) A method of combining SE-tree to compute all minimal hitting sets. Prog Nat Sci 16(2):169\u2013174","journal-title":"Prog Nat Sci"},{"key":"971_CR44","volume-title":"Proceedings of the 3rd international conference on intelligent computing (ICIC-07), lecture notes in computer science, vol. 4681. Springer, pp 157\u2013166","author":"X Zhao","year":"2007","unstructured":"Zhao X, Ouyang D (2007) Improved algorithms for deriving all minimal conflict sets in model-based diagnosis. In: Proceedings of the 3rd international conference on intelligent computing (ICIC-07), lecture notes in computer science, vol. 4681. Springer, pp 157\u2013166"},{"key":"971_CR45","volume-title":"Proceedings of the 18th European conference on artificial intelligence (ECAI-08). IOS Press, pp 189\u2013193","author":"X Zhao","year":"2008","unstructured":"Zhao X, Ouyang D (2008) Model-based diagnosis of discrete event systems with an incomplete system model. In: Proceedings of the 18th European conference on artificial intelligence (ECAI-08). IOS Press, pp 189\u2013193"},{"key":"971_CR46","volume-title":"Proceedings of the 24th international workshop on principles of diagnosis (DX-13), pp 33\u201338","author":"X Zhao","year":"2013","unstructured":"Zhao X, Ouyang D (2013) A distributed strategy for deriving minimal hitting-sets. In: Proceedings of the 24th international workshop on principles of diagnosis (DX-13), pp 33\u201338"},{"issue":"7","key":"971_CR47","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1109\/TSMC.2015.2400423","volume":"45","author":"X Zhao","year":"2015","unstructured":"Zhao X, Ouyang D (2015) Deriving all minimal hitting sets based on join relation. IEEE Trans Syst Man Cybern Syst 45(7):1063\u20131076","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"key":"971_CR48","volume-title":"Proceedings of the IEEE international conference on information and automation (ICIA-2016), pp 1132\u20131137","author":"X Zhao","year":"2016","unstructured":"Zhao X, Ouyang D (2016) Deriving all minimal hitting-sets by merging. In: Proceedings of the IEEE international conference on information and automation (ICIA-2016), pp 1132\u20131137"},{"issue":"4","key":"971_CR49","doi-asserted-by":"crossref","first-page":"285","DOI":"10.3233\/AIC-2012-0518","volume":"25","author":"X Zhao","year":"2012","unstructured":"Zhao X, Ouyang D, Zhang L, Wang X, Mo Y (2012) Reasoning on partially-ordered observations in online diagnosis of dess. AI Commun 25(4):285\u2013294","journal-title":"AI Commun"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10489-017-0971-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-017-0971-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-017-0971-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T05:37:33Z","timestamp":1659159453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10489-017-0971-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,30]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["971"],"URL":"https:\/\/doi.org\/10.1007\/s10489-017-0971-7","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"value":"0924-669X","type":"print"},{"value":"1573-7497","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,30]]},"assertion":[{"value":"30 June 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}