Quantified constraint satisfaction problems: from relaxations to explanations
Alex Ferguson, Barry O’Sullivan · 2007
The Quantified Constraint Satisfaction Problem (QCSP) is a generalisation of the classical CSP in which some of variables can be universally quantified. In this paper, we extend two well-known concepts in classical constraint satisfaction to the quantified case: problem relaxation and explanation of inconsistency. We show that the generality of the QCSP allows for a number of different forms of relaxation not available in classical CSP. Wefurther present an algorithm for computing a generalisation of conflict-based explanations of inconsistency for the QCSP. 1