Core-Guided Minimal Correction Set and Core Enumeration
Abstract
A set of constraints is unsatisfiable if there is no solution that satisfies these constraints. To analyse unsatisfiable problems, the user needs to understand where inconsistencies come from and how they can be repaired. Minimal unsatisfiable cores and correction sets are important subsets of constraints that enable such analysis. In this work, we propose a new algorithm for extracting minimal unsatisfiable cores and correction sets simultaneously. Building on top of the relaxation and strengthening framework, we introduce novel techniques for extracting these sets. Our new solver significantly outperforms several state of the art algorithms on common benchmarks when it comes to extracting correction sets and compares favorably on core extraction.
Cite
Text
Narodytska et al. "Core-Guided Minimal Correction Set and Core Enumeration." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/188Markdown
[Narodytska et al. "Core-Guided Minimal Correction Set and Core Enumeration." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/narodytska2018ijcai-core/) doi:10.24963/IJCAI.2018/188BibTeX
@inproceedings{narodytska2018ijcai-core,
title = {{Core-Guided Minimal Correction Set and Core Enumeration}},
author = {Narodytska, Nina and Bjørner, Nikolaj S. and Marinescu, Maria-Cristina V. and Sagiv, Mooly},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1353-1361},
doi = {10.24963/IJCAI.2018/188},
url = {https://mlanthology.org/ijcai/2018/narodytska2018ijcai-core/}
}