Network satisfaction problems solved by <i>k</i> -consistency

In this paper, we show that the problem of deciding for a given finite relation algebra [Formula: see text] whether the network satisfaction problem for [Formula: see text] can be solved by the k-consistency procedure, for some [Formula: see text], is undecidable. For the important class of finite relation algebras [Formula: see text] with a normal representation, however, the decidability of this problem remains open. We show that if [Formula: see text] is symmetric and has a flexible atom, then the question whether [Formula: see text] can be solved by k-consistency, for some [Formula: see text], is decidable (even in polynomial time in the number of atoms of [Formula: see text]). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures.