期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：32
页码：607-629
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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
