Julien Vion,

Université d’Artois


The problem of extracting Minimal Unsatisfiable Cores (MUCs) from constraint networks is a computationally hard problem which has a practical interest in many application domains such as configuration, planning, diagnosis, etc. Indeed, identifying one or several disjoint MUCs can help circumscribe different sources of inconsistency in order to repair a system. We propose an original approach that involves performing successive runs of a complete backtracking search, using constraint weighting, in order to surround an inconsistent part of a network, before identifying all transition constraints belonging to a MUC using a dichotomic process.


Date: 2006-Apr-11     Time: 14:30:00     Room: 217

For more information: