catch all non-soluble CSP instances (as one expects from the conjunction of their efficiency and the intractability of the CSP), it has been shown that, for certain constraint languages, they can serve as complete decision procedures, by which is meant, they detect an inconsistency if (and only if) an instance has no solution. As an example, *unit propagation*, a consistency method that can be viewed as arc consistency specialized to SAT formulas, is well-known to decide the Horn-SAT problem in this sense.

Contributions
-------------

In this paper, we study arc consistency and three natural extensions thereof from the perspective of constraint languages. The extensions of AC that we study are look-ahead arc consistency (LAAC) [@SLAAC]; peek arc consistency (PAC) [@peek], and singleton arc consistency (SAC) [@db-sac; @bd-theoretical]. Each of these algorithms is natural, conceptually simple, readily understandable, and easily implementable using arc consistency as a black box. Tractability results for constraint languages have been presented for AC by Feder and Vardi [@FederVardi] (for instance); and for LAAC and PAC in the previously cited work. In fact, for each of these three algorithms, characterizations of the class of tractable languages have been given, as we discuss in the paper.

We give 