Finding All Minimal Unsatisfiable Subsets

Autor:	Peter J. Stuckey, Maria Garcia de la Banda, Jeremy Wazny
Předmět:	Set (abstract data type) Constraint (information theory) Mathematical optimization Computer science Order (group theory) Type error Algorithm Independence (probability theory)
Zdroj:	Scopus-Elsevier PPDP
Popis:	An unsatisfiable set of constraints is minimal if all its (strict) subsets aresatisfiable.A number of forms of error diagnosis, including circuit error diagnosis and type error diagnosis, require finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. In this paper we give algorithms for efficiently determining all minimal unsatisfiable subsets for any kind of constraints. We show how taking into account notions of independence of constraints and using incremental constraint solvers can significantly improve the calculation of these subsets.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37888b347f2e923ab95993066a55c83e http://www.scopus.com/inward/record.url?eid=2-s2.0-1242287835&partnerID=MN8TOARS Zobrazit plný text záznamu