Generalizing Consistency and other Constraint Properties to Quantified Constraints

Details Generalizing Consistency and other Constraint Properties to Quantified Constraints Generalizing Consistency and other Constraint Properties to Quantified Constraints

2007-05-24

arxiv.org/abs/0705.3561v1

Computer Science

Logic in Computer Science

Scientific paper

Quantified constraints and Quantified Boolean Formulae are typically much more difficult to reason with than classical constraints, because quantifier alternation makes the usual notion of solution inappropriate. As a consequence, basic properties of Constraint Satisfaction Problems (CSP), such as consistency or substitutability, are not completely understood in the quantified case. These properties are important because they are the basis of most of the reasoning methods used to solve classical (existentially quantified) constraints, and one would like to benefit from similar reasoning methods in the resolution of quantified constraints. In this paper, we show that most of the properties that are used by solvers for CSP can be generalized to quantified CSP. This requires a re-thinking of a number of basic concepts; in particular, we propose a notion of outcome that generalizes the classical notion of solution and on which all definitions are based. We propose a systematic study of the relations which hold between these properties, as well as complexity results regarding the decision of these properties. Finally, and since these problems are typically intractable, we generalize the approach used in CSP and propose weaker, easier to check notions based on locality, which allow to detect these properties incompletely but in polynomial time.

Affiliated with

Also associated with

No associations

Rating

Generalizing Consistency and other Constraint Properties to Quantified Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalizing Consistency and other Constraint Properties to Quantified Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalizing Consistency and other Constraint Properties to Quantified Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-606210