of the algorithm, has the property that for any solution $h$, it must hold that $h(a) \in S_a$. The algorithm continually shrinks the sets $S_a$ in a natural fashion until they stabilize; at this point, if some set $S_a$ is the empty set, then no solution can exist, and the algorithm rejects the instance.

[**Arc Consistency**]{}\

------------------------------------------------------------------------

Feder and Vardi [@FederVardi] have studied arc consistency, under an equivalent formulation in terms of Datalog Programs, for constraint languages. The results in this section are due to this reference. The connection of the results in Feder and Vardi with arc consistency was made explicit in Dalmau and Pearson [@DalmauPearson].

\[def:acc\] An instance $({\mathbf{A}}, {\mathbf{B}})$ has the *arc consistency condition (ACC)* if there exists a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$.

\[prop:acc\] The arc consistency algorithm does not reject an instance $({\mathbf{A}}, {\mathbf{B}})$ if and only if the instance has the ACC.

\[def:ac-solves\] Let ${\mathbf{B}}$ be a structure. We say that arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: $({\mathbf{A}}, {\mathbf{B}})$ has the ACC implies that there is a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$.

Note that the converse of the condition given in this definition always holds: if $h$ is a homomorphism 