Generalizing consistency and other constraint properties to quantified constraints

DOI10.1145/1507244.1507247zbMATH Open1351.68252arXiv0705.3561OpenAlexW2022485444MaRDI QIDQ2946575FDOQ2946575

Authors: Lucas Bordeaux, Marco Cadoli, Toni Mancini 

Publication date: 17 September 2015

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

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.

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

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

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)

Cited In (12)

• Reusing CSP Propagators for QCSPs
• Title not available (Why is that?)
• Quantified Constraints and Containment Problems
• Consistency for Quantified Constraint Satisfaction Problems
• Quantified Constraints in Twenty Seventeen
• Title not available (Why is that?)
• Expressing quantification in relational calculus by participation constraints
• Variable Dependencies of Quantified CSPs
• On generalized constraints and certificates
• Title not available (Why is that?)
• 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)