PlumX Metrics
Embed PlumX Metrics

Generalizing consistency and other constraint properties to quantified constraints

ACM Transactions on Computational Logic, ISSN: 1529-3785, Vol: 10, Issue: 3, Page: 1-25
2009
  • 7
    Citations
  • 0
    Usage
  • 10
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Metrics Details

  • Citations
    7
    • Citation Indexes
      7
  • Captures
    10

Article Description

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 (CSPs), 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 it is desirable to benefit from similar reasoning methods in the resolution of quantified constraints. In this article, we show that most of the properties that are used by solvers for CSP can be generalized to quantified CSP. This requires a rethinking 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. © 2009 ACM.

Bibliographic Details

Lucas Bordeaux; Marco Cadoli; Toni Mancini

Association for Computing Machinery (ACM)

Mathematics; Computer Science

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know