also work on characterizing the languages ${\mathbf{B}}$ for which the problem ${{\mathsf{CSP}}}({\mathbf{B}})$ is contained in lower complexity classes such as L (logarithmic space) and NL (non-deterministic logarithmic space) [@dalmau-pathwidth; @larose-tesson]. With such aims providing motivation, there have been efforts to characterize the languages amenable to solution by certain algorithmic techniques, notably, representing solution spaces by generating sets [@IMMVW] and consistency methods [@LaroseZadori; @abd-affine; @bkbw], which we now turn to discuss.

Checking for *consistency* is a primary reasoning technique for the practical solution of the CSP, and has been studied theoretically from many viewpoints [@LaroseZadori; @abd-affine; @akv; @abd; @aft; @bkbw; @atserias-weyer]. The most basic and simplest form of consistency is *arc consistency*, which algorithmically involves performing inferences concerning the set of feasible values for each variable. The question of how to efficiently implement an arc consistency check has been studied intensely, and highly optimized implementations that are linear in both time and space have been presented. In general, a consistency check typically involves running an efficient method that performs inference on bounded-size sets of variables, and which can sometimes detect that a CSP instance is inconsistent and has no solution. While these methods exhibit one-sided error in that they do not 