From Russell-Norvig:
A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)-consistent, . . . all the way down to 1-consistent.
How can a CSP be k-consistent without being (k - 1)-consistent? I can't think of any counter example for this case. Any help would be appreciated.
Define P as a CSP where X, Y are the variables, domain of both is {1,2,3,4} and conditions in normal form are:
P is 2-consistent (arc consistent) because for any X value it is possible to find a Y value that fulfills the arc-condition X=Y.
However, P is not 1-consistent (node-consistent) because exist a X value (X=4) that can not fulfill the node condition x<4.
For these reasons, this problem is 2-consistent but not strongly 2-consistent.
Obviously, it is straightforward to convert this example in a strongly 2-consistent problem, just reducing the domain to {1,2,3}.
