Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability

Lucas bordeaux, Marco Cadoli, and Toni Mancini

Abstract

Literature on Constraint Satisfaction exhibits the definition of several “structural” properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability. Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search.

In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields' literature, and shed light on the semantical relationships among them. This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems.

In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable's domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, including
inconsistency, substitutability and others.

Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning.

Details

Publication typeArticle
Published inJ. of Artificial Intelligence Research
URLhttp://www.bing.com/search?q=doi%3A10.1613%2Fjair.2538
Pages607-629
Volume32
> Publications > A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability