Quantified Constraint Satisfaction Problems: From Relaxations to Explanations

Alex Ferguson, Barry O’Sullivan

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. We further present an algorithmfor computing a generalisation of conflict-based explanations of inconsistency for the QCSP.

Subjects: 15.2 Constraint Satisfaction


Submitted: Oct 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.