CONSTRAINT TIGHTNESS AND LOOSENESS VERSUS LOCAL AND GLOBAL CONSISTENCY

Constraint networks are a simple representation and reasoning framewor k with diverse applications. In this paper, we identify two new comple mentary properties on the restrictiveness of the constraints in a netw ork-constraint tightness and constraint looseness-and we show their us efulness for estimating the level of local consistency needed to ensur e global consistency, and for estimating the level of local consistenc y present in a network. In particular, we present a sufficient conditi on, based on constraint tightness and the level of local consistency, that guarantees that a solution can be found in a backtrack-free manne r. The condition can be useful in applications where a knowledge base will be queried over and over and the preprocessing costs can be amort ized over many queries. We also present a sufficient condition for loc al consistency, based on constraint looseness, that is straightforward and inexpensive to determine. The condition can be used to estimate t he level of local consistency of a network. This in turn can be used i n deciding whether it would be useful to preprocess the network before a backtracking search, and in deciding which local consistency condit ions, if any, still need to be enforced if we want to ensure that a so lution can be found in a backtrack-free manner. Two definitions of loc al consistency are employed in characterizing the conditions: the trad itional variable-based notion and a recently introduced definition of local consistency called relational consistency.