{ i, a } can be made arc consistent  The initial problem is therefore singleton arc consistent Figure c shows that there exists a constraint network on which SAC holds and strong PC
does not  Therefore  strong PC is strictly stronger than SAC
□
Theorem 9 Singleton restricted path consistency is strictly stronger than singleton arc conststency.

Proof Singleton restricted path consistency is stronger than singleton arc consistency since RPC is stronger than AC  Figure  d shows that there exists a constraint network on which SAC holds and SRPC does not  Therefore  SRPC is strictly strongerthan SAC
The stronger relation does not induce a total ordering Some local consistencies are incomparable

## Theorem 10

1. If IX I >3, path inverse consistency and k-restricted path consistency are incomparable.

2. Neighborhood inverse consistency and singleton arc consistency are incomparable.

3. Neighborhood inverse consistency and strong path consistency are incomparable.

4. Neighborhood inverse consistency and singleton restricted path consistency are incomparable.

## Proof

h and Figure j cf Figure

d and Figure  e cf Figure cf Figure  d and Figure  e cf  Figure  e and Figure f
summarizes the relations between the local consistencies There is an arrow Fig ure from LC to LC l iff LC is strictly stronger than LC l  A crossed line between two local consistencies means that they are not comparable w r t  the  stronger  relation When LC is not stronger than LC 1  LC 1 is strictly stronger than LC  or LC and LC 1 are not comparable a CN in which LC holds and LC t does not can be found in Figure Obviously the stronger relation is transitive  In Figure  
we omit the transitivity arcs