Generalizing consistency and other constraint properties to quantified constraints

DOI10.1145/1507244.1507247MaRDI QIDQ2946575zbMATH OpenOpenAlexFDO

Authors Lucas Bordeaux, Marco Cadoli, Toni Mancini

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.3561

zbMATH Keywords

constraint satisfactionquantified constraintsquantified Boolean formulae

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

• Reusing CSP Propagators for QCSPs
• Consistency for Quantified Constraint Satisfaction Problems
• Principles and Practice of Constraint Programming – CP 2004
• The complexity of problems for quantified constraints
• Solving quantified constraint satisfaction problems

Cited in

(12)

• Reusing CSP Propagators for QCSPs
• scientific article; zbMATH DE number 5526522 (Why is no real title available?)
• Quantified Constraints and Containment Problems
• Consistency for Quantified Constraint Satisfaction Problems
• Quantified Constraints in Twenty Seventeen
• scientific article; zbMATH DE number 7270290 (Why is no real title available?)
• Expressing quantification in relational calculus by participation constraints
• Variable Dependencies of Quantified CSPs
• On generalized constraints and certificates
• scientific article; zbMATH DE number 6519660 (Why is no real title available?)
• Towards an arithmetic theory of consistency enforcement based on preservation of \(\delta\)-constraints
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Generalizing consistency and other constraint properties to quantified constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946575)