TY - JOUR AU - Previti, Alessandro AU - Mencía, Carlos AU - Järvisalo, Matti AU - Marques-Silva, Joao PY - 2018/04/26 Y2 - 2024/03/28 TI - Premise Set Caching for Enumerating Minimal Correction Subsets JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 32 IS - 1 SE - Main Track: Search and Constraint Satisfaction DO - 10.1609/aaai.v32i1.12213 UR - https://ojs.aaai.org/index.php/AAAI/article/view/12213 SP - AB - <p> Methods for explaining the sources of inconsistency of overconstrained systems find an ever-increasing number of applications, ranging from diagnosis and configuration to ontology debugging and axiom pinpointing in description logics. Efficient enumeration of minimal correction subsets (MCSes), defined as sets of constraints whose removal from the system restores feasibility, is a central task in such domains. In this work, we propose a novel approach to speeding up MCS enumeration over conjunctive normal form propositional formulas by caching of so-called premise sets (PSes) seen during the enumeration process. Contrasting to earlier work, we move from caching unsatisfiable cores to caching PSes and propose a more effective way of implementing the cache. The proposed techniques noticeably improves on the performance of state-of-the-art MCS enumeration algorithms in practice. </p> ER -