large classes of languages whose constraint satisfaction problem could be placed in non-deterministic logarithmic space [@majority-nl]. While the languages that we study are already known to be polynomial-time tractable [@CCC; @twosemilattices], from the standpoint of understanding the complexity and algorithmic properties of constraint languages, we believe our tractability results to be particularly attractive for a couple of reasons. First, relative to a fixed language, singleton arc consistency runs in quadratic time [@bd-theoretical], constituting a highly non-trivial running time improvement over the cubic time bound that was previously known for the studied languages. Also, in showing that these languages are amenable to solution by singleton arc consistency, we demonstrate their polynomial-time tractability in an alternative fashion via an algorithm that is different from the previously used ones; the techniques that we employ expose a different type of structure in the studied constraint languages.

Preliminaries
=============

Our definitions and notation are fairly standard. For an integer $k \geq 1$, we use the notation $[k]$ to denote the set containing the first $k$ positive integers, that is, the set $\{ 1, \ldots, k \}$.

#### Structures.

A *tuple* over a set $B$ is an element of $B^k$ for a value $k \geq 1$ 